Recent

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

loaded

  • Hero Member
  • *****
  • Posts: 824
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.
Check out  loaded on Strava
https://www.strava.com/athletes/109391137

Edson

  • Hero Member
  • *****
  • Posts: 1296
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.2.6 - FPC 3.2.2 - x86_64-win64 on Windows 10

winni

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

Perhaps it helps!

Winni

loaded

  • Hero Member
  • *****
  • Posts: 824
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.  :o
Check out  loaded on Strava
https://www.strava.com/athletes/109391137

winni

  • Hero Member
  • *****
  • Posts: 3197
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!

loaded

  • Hero Member
  • *****
  • Posts: 824
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. ;D
Check out  loaded on Strava
https://www.strava.com/athletes/109391137

winni

  • Hero Member
  • *****
  • Posts: 3197
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


loaded

  • Hero Member
  • *****
  • Posts: 824
Re: How can we cut the polygon according to the line?
« Reply #9 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/
« Last Edit: August 03, 2021, 07:38:05 am by loaded »
Check out  loaded on Strava
https://www.strava.com/athletes/109391137

winni

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


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

Winni

loaded

  • Hero Member
  • *****
  • Posts: 824
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.  :o winni, I can't thank you enough.
There's probably more here than I was looking for.
May God increase your knowledge.
Check out  loaded on Strava
https://www.strava.com/athletes/109391137

VTwin

  • Hero Member
  • *****
  • Posts: 1215
  • 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.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

 

TinyPortal © 2005-2018