### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

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

• Full Member
• Posts: 186
##### Is There a Ready Routine for Intersection Calculation in Polygons?
« on: January 03, 2021, 07:02:31 pm »
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?
Installing the spelling, google translate is used

#### wp

• Hero Member
• Posts: 8318
##### 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.
Mainly Lazarus trunk / fpc 3.2.0 / all 32-bit on Win-10, but many more...

#### circular

• Hero Member
• Posts: 3694
##### 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
Conscience is the debugger of the mind

#### Seenkao

• Full Member
• Posts: 141
##### 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.

• Full Member
• Posts: 186
##### 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.
Installing the spelling, google translate is used

#### marcov

• Global Moderator
• Hero Member
• Posts: 9235
• 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: 271
##### 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