Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

Author Topic: How can we cut the polygon according to the line?  (Read 6348 times)

• Sr. Member
• Posts: 265
How can we cut the polygon according to the line?
« on: August 02, 2021, 11:59:40 am »
Hi All,
I want to split the polygon given in the example code from the line.
Code: Pascal  [Select][+][-]
1. procedure TForm1.Button1Click(Sender: TObject);
2.  var
3.    points:array of TPoint; // polygon to cut
4.    line:array[0..1] of TPoint;  //  will cut right
5. begin
6.      setlength(points,4);
7.      points[0]:=Point(100,100);
8.      points[1]:=Point(200,100);
9.      points[2]:=Point(200,200);
10.      points[3]:=Point(100,200);
11.      canvas.Polygon(points);
12.      line[0]:=Point(50,150);
13.      line[1]:=Point(250,199);
14.      canvas.Line(line[0],line[1]);
15. 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.
Installing the spelling, google translate is used

Edson

• Hero Member
• Posts: 1208
Re: How can we cut the polygon according to the line?
« Reply #1 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.
Lazarus 2.0.10 - FPC 3.2.0 - x86_64-win64 on Windows 8

winni

• Hero Member
• Posts: 2664
Re: How can we cut the polygon according to the line?
« Reply #2 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

Handoko

• Hero Member
• Posts: 4327
• My goal: build my own game engine using Lazarus
Re: How can we cut the polygon according to the line?
« Reply #3 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

winni

• Hero Member
• Posts: 2664
Re: How can we cut the polygon according to the line?
« Reply #4 on: August 02, 2021, 07:33:35 pm »
Hi!

Not what you are searching for but you want a two time clipping:

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

Perhaps it helps!

Winni

• Sr. Member
• Posts: 265
Re: How can we cut the polygon according to the line?
« Reply #5 on: August 02, 2021, 08:05:05 pm »
First of all, thank you very much for your answers Edson and winni and Handoko

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.
Installing the spelling, google translate is used

winni

• Hero Member
• Posts: 2664
Re: How can we cut the polygon according to the line?
« Reply #6 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!

• Sr. Member
• Posts: 265
Re: How can we cut the polygon according to the line?
« Reply #7 on: August 02, 2021, 09:20:22 pm »
Do you need a map or do you need exact coordinates?
Yes, I need coordinates to calculate Area and Perimeter.

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.
Installing the spelling, google translate is used

winni

• Hero Member
• Posts: 2664
Re: How can we cut the polygon according to the line?
« Reply #8 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

Winni

• Sr. Member
• Posts: 265
Re: How can we cut the polygon according to the line?
« Reply #9 on: August 03, 2021, 07:11:35 am »
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/
« Last Edit: August 03, 2021, 07:38:05 am by loaded »
Installing the spelling, google translate is used

winni

• Hero Member
• Posts: 2664
Re: How can we cut the polygon according to the line?
« Reply #10 on: August 06, 2021, 07:10:16 pm »

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

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

Winni

• Sr. Member
• Posts: 265
Re: How can we cut the polygon according to the line?
« Reply #11 on: August 06, 2021, 09:30:37 pm »
You found a great treasure.  winni, I can't thank you enough.
There's probably more here than I was looking for.
Installing the spelling, google translate is used

VTwin

• Hero Member
• Posts: 1050
• Former Turbo Pascal 3 user
Re: How can we cut the polygon according to the line?
« Reply #12 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.
« Last Edit: August 07, 2021, 12:47:49 am by VTwin »
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.0
macOS 10.13.6: Lazarus 2.0.12 (64 bit Cocoa)
Ubuntu 18.04.3: Lazarus 2.0.12 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.0.12 (64 bit on VBox)