I'm trying to develop an Algorithm for Polygon Intersection. Where each polygon is an array of Points, where each Point has X and Y properties.
Algorithm limitations:
- Algorithm input: 2 Polygons.
- Algorithm output: Intersection Polygon.
- Polygons may be convex or concave (angle between 2 neighbor edges my be more than 180).
- Polygons will not have any holes and will not be self intersection polygons.
I managed to develop this algorithm this far (given 2 polygons A and B):
- For each vertex in PolygonA:
1.1 If vertex is inside PolygonB then Add this vertex to groupA. - For each vertex in PolygonB:
2.1 If vertex is inside PolygonA then Add this vertex to groupB. - For each edge {edgeA} in PolygonA:
3.1 For each edge {edgeB} in PolygonB:
3.1.1 If edgeA and edgeB are intersect (in the edgeA and edgeB segment area) then add there intersection point to groupI. - marge(groupA, groupB, groupI); // I don't know how to implement this
In debug I see that the Intersection area is built from vertexes combined groupA, groupB and groupI. But I don't know how should I merged them together - how to order/sort them???
I have try to sort the clockwise around the center point of the new intersection polygon - but this will only work for convex polygons not for concave.
In this example:
- The Blue Points are vertexes of PolygonA inside PolygonB (groupA)
- The Red Points are vertexes of PolygonB inside PolygonA (groupB)
- The Yellow Points are intersect vertexes of PolygonA with PolygonB (groupI)