Print Page - How can we cut the polygon according to the line?

Programming => Graphics and Multimedia => Graphics => Topic started by: loaded on August 02, 2021, 11:59:40 am

Title: How can we cut the polygon according to the line?
Post by: loaded on August 02, 2021, 11:59:40 am

Hi All,
I want to split the polygon given in the example code from the line.

procedure TForm1.Button1Click(Sender: TObject);
 var
   points:array of TPoint; // polygon to cut
   line:array[0..1] of TPoint;  //  will cut right
begin
     setlength(points,4);
     points[0]:=Point(100,100);
     points[1]:=Point(200,100);
     points[2]:=Point(200,200);
     points[3]:=Point(100,200);
     canvas.Polygon(points);
     line[0]:=Point(50,150);
     line[1]:=Point(250,199);
     canvas.Line(line[0],line[1]);
end;  

I've done some research on the subject before, but I haven't come across a remarkable, simple-to-use solution. I had the idea that the absolute solution is in triangulation. But I have come to the end of the road, now I have to somehow overcome this situation.Before diving into geometry formulas, I wanted to consult you one last time. What is the logic of dividing polygons according to the line? Is there an easy way to do this?
I would really appreciate if you can help. Respects.

Title: Re: How can we cut the polygon according to the line?
Post by: Edson on August 02, 2021, 05:44:18 pm

Do you refer to split a specific polygon like in your code or a general case?

A general case would be more difficult. You must define some rules, like the maximum numbers of point of the polygon and if it's granted the line intersect the polygon and if intersection will only generates 2 polygons.

Title: Re: How can we cut the polygon according to the line?
Post by: winni on August 02, 2021, 07:25:35 pm

Hi!

Let's do Edsons solution step by step:

Does Line0_Line1 intersect with

P0_P1: no
P1_P2: yes --> Inter1
P2_P3: no
P3_P0: yes --> Inter2

Polygon1 := [P0, P1, Inter1, Inter2];
Polygon2 := [P2, P3, Inter2, Inter1];

A global solution is more complicated.
You have to keep track which polygon lines intersect with Line0_Line1.

Winni

Title: Re: How can we cut the polygon according to the line?
Post by: Handoko on August 02, 2021, 07:27:26 pm

Maybe it is not what OP wants, but this look interesting:
http://angusj.com/delphi/clipper.php

Title: Re: How can we cut the polygon according to the line?
Post by: winni on August 02, 2021, 07:33:35 pm

Hi!

Here is a cookbook about about clipping.
Not what you are searching for but you want a two time clipping:

http://www.inf.usi.ch/hormann/papers/Greiner.1998.ECO.pdf (http://www.inf.usi.ch/hormann/papers/Greiner.1998.ECO.pdf)

Perhaps it helps!

Winni

Title: Re: How can we cut the polygon according to the line?
Post by: loaded on August 02, 2021, 08:05:05 pm

First of all, thank you very much for your answers Edson and winni and Handoko

Quote from: Edson on August 02, 2021, 05:44:18 pm

Do you refer to split a specific polygon like in your code or a general case?

My aim is to divide the cadastral parcels shown in the attached picture according to the desired area or line.

Handoko, I looked at the solution in the link. It was too complicated for me. And I couldn't do what I wanted.

I thought it might be an easy method. But ;
Looks like I have to go the way Winni and Edson described.
But this path seems as challenging to me as climbing Mount Everest. :o

Title: Re: How can we cut the polygon according to the line?
Post by: winni on August 02, 2021, 08:57:33 pm

Hi!

Do you need a map or do you need exact coordinates?

In case of a map you simply could work with a mask.

Winni

And hurry up with the Mount Everest:
It is growing half a centimeter every year!

Title: Re: How can we cut the polygon according to the line?
Post by: loaded on August 02, 2021, 09:20:22 pm

Quote from: winni on August 02, 2021, 08:57:33 pm

Do you need a map or do you need exact coordinates?

Yes, I need coordinates to calculate Area and Perimeter.

Quote from: winni on August 02, 2021, 08:57:33 pm

And hurry up with the Mount Everest:
It is growing half a centimeter every year!

It would be great if you didn't give this news today. ;D

Title: Re: How can we cut the polygon according to the line?
Post by: winni on August 02, 2021, 10:24:11 pm

Hi!

Handoko is right.
Angus Johnsons library does what you need.

There was a discussion about it in this forum some time ago:

https://forum.lazarus.freepascal.org/index.php/topic,39910.msg274890.html#msg274890
(https://forum.lazarus.freepascal.org/index.php/topic,39910.msg274890.html#msg274890)
Winni

Title: Re: How can we cut the polygon according to the line?
Post by: loaded on August 03, 2021, 07:11:35 am

Thank you very much for your answers winni.
You're right, it might be helpful for me to take a u-turn at the last exit before the tunnel and examine Handoko's link.

By the way, I found such a resource reminds me of my high school years. probably the formulas here will work for me. Let's put it here, maybe it will be useful to someone one day.
http://paulbourke.net/geometry/pointlineplane/ (http://paulbourke.net/geometry/pointlineplane/)

Title: Re: How can we cut the polygon according to the line?
Post by: winni on August 06, 2021, 07:10:16 pm

@ loaded

Perhaps you dived deep into the source of Angus Johnson.

But I found another Geo page working with Pascal.

http://www.partow.net/projects/fastgeo/index.html (http://www.partow.net/projects/fastgeo/index.html)

Delphi and fpc compatibel.
A bunch of functions including polygon intersection.

Winni

Title: Re: How can we cut the polygon according to the line?
Post by: loaded on August 06, 2021, 09:30:37 pm

You found a great treasure. :o winni, I can't thank you enough.
There's probably more here than I was looking for.
May God increase your knowledge.

Title: Re: How can we cut the polygon according to the line?
Post by: VTwin on August 07, 2021, 12:16:29 am

Thanks for the links Handoko and Winni.

Poking around a bit I realized that FastGEO was incorporated into JEDI Math, which I am familiar with, although have not used extensively:

https://sourceforge.net/projects/jedimath/

The original version of FastGEO (Winni's link) is "Common Public License", while FastGEO in JEDI Math (JmGeometry.pas) is "Mozilla Public License". Both are FastGEO 5.0.1.

I think MPL is compatible with LGPL, while CPL is not, but don't quote me on that.

Lazarus

Programming => Graphics and Multimedia => Graphics => Topic started by: loaded on August 02, 2021, 11:59:40 am