Recent

Author Topic: Is There a Ready Routine for Intersection Calculation in Polygons?  (Read 1919 times)

loaded

  • Hero Member
  • *****
  • Posts: 824
Hi Everyone.

Code: Pascal  [Select][+][-]
  1.  
  2. procedure TForm1.FormPaint(Sender: TObject);
  3. var
  4.   poly:array[0..3] of TPoint;
  5.   cline:array[0..1] of TPoint;
  6. begin
  7.   poly[0]:=Point(100,100);
  8.   poly[1]:=Point(ClientWidth-100,100);
  9.   poly[2]:=Point(ClientWidth-100,ClientHeight-100);
  10.   poly[3]:=Point(100,ClientHeight-100);
  11.   canvas.brush.color:=clred;
  12.   canvas.brush.Style:=bsCross;
  13.   canvas.Polygon(poly);
  14.   cline[0]:=Point(round(ClientWidth/2)+10,10);
  15.   cline[1]:=Point(round(ClientWidth/2)-10,ClientHeight-10);
  16.   canvas.pen.Width:=3;
  17.   canvas.Polyline(cline);
  18. end;  
  19.  

With the code above
There is an example polygon that I have drawn (it consists of 4 points in the drawing, but it can actually consist of 3-50 points). And I want to cut this polygon according to a certain line. So actually I want to get their intersections as fields. In the future, I will work to calculate the combination or differences of intertwined areas.
Before dealing with geometry formulas, I wanted to consult you.
What is the best method for this job?
Check out  loaded on Strava
https://www.strava.com/athletes/109391137

wp

  • Hero Member
  • *****
  • Posts: 11858
Re: Is There a Ready Routine for Intersection Calculation in Polygons?
« Reply #1 on: January 03, 2021, 10:33:32 pm »
This is pretty complicated stuff for the general case... There is a Delphi library "Clipper" by Angus Johnson from which you maybe get an idea what to do. It is for Graphics32, but I think the algorithm should be general enough so that you can extend it to your purpose: https://sourceforge.net/projects/polyclipping/.

I am attaching the demo project as well as Angus' clipper unit, converted to Lazarus. Please note that the demo required Graphics32 to be installed -- you can get it via Online-Package-Manager as pl_Graphics32.

P.S.
Maybe similar stuff is in BGRABitmap, I don't know.

circular

  • Hero Member
  • *****
  • Posts: 4196
    • Personal webpage
Re: Is There a Ready Routine for Intersection Calculation in Polygons?
« Reply #2 on: January 03, 2021, 10:35:31 pm »
Not yet in BGRABitmap. But that would be cool  8)
Conscience is the debugger of the mind

Seenkao

  • Hero Member
  • *****
  • Posts: 546
    • New ZenGL.
Re: Is There a Ready Routine for Intersection Calculation in Polygons?
« Reply #3 on: January 03, 2021, 11:40:48 pm »
Разбейте полигон на треугольники.

Eng: Divide the polygon into triangles.
Rus: Стремлюсь к созданию минимальных и достаточно быстрых приложений.

Eng: I strive to create applications that are minimal and reasonably fast.
Working on ZenGL

loaded

  • Hero Member
  • *****
  • Posts: 824
Re: Is There a Ready Routine for Intersection Calculation in Polygons?
« Reply #4 on: January 04, 2021, 12:24:02 pm »
wp, circular, seenkao, thank you individually.
wp, I'm trying to run the demo you posted. I hope it works.
circular, I hope you add these features to a BGRAbitmap, and we pray for you.
seenkao, my path will definitely cross with the triangulation process one day. This is an issue that I am aware of but always avoid.
If I can't find an easier way, I'll gradually learn to triangulate.
Check out  loaded on Strava
https://www.strava.com/athletes/109391137

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Is There a Ready Routine for Intersection Calculation in Polygons?
« Reply #5 on: January 04, 2021, 12:29:15 pm »
Angus library has a bit weird license.

BeanzMaster

  • Sr. Member
  • ****
  • Posts: 268
Re: Is There a Ready Routine for Intersection Calculation in Polygons?
« Reply #6 on: January 22, 2021, 08:05:16 am »
Hi load look at the function TBZ2DPolygonTool.IntersectWithLine(aLine : TBZ2DLineTool; out IntersectPoints : TBZArrayOfFloatPoints) : Boolean; (line 423) here https://github.com/jdelauney/BZScene/blob/master/Source/Utils/BZGeoTools.pas perhaps it can help you a bit.

Cheers

 

TinyPortal © 2005-2018