Concave Polygon Intersection - Algorithm

Question

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):

---

1. For each vertex in PolygonA:
   1.1 If vertex is inside PolygonB then Add this vertex to groupA.
   
   
2. For each vertex in PolygonB:
   2.1 If vertex is inside PolygonA then Add this vertex to groupB.
   
   
3. 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.
   
   
4. 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)

Answer 1

First, order the $Blue \cup Yellow$ points according to a clockwise visit of A, and similarly, order the $Red \cup Yellow$ points according to a clockwise visit of B.

Now start at a blue point (if there is one) and follow A clockwise until you are at a yellow point. Then follow B clockwise until you are at a yellow point again; then follow A clockwise, and so on, switching from following one polygon to the other every time you encounter a yellow point. Continue until you are back at the starting point. See Weiler-Atherton clipping algorithm and the references there.

If there are no blue points, start instead from a red point and follow B initially. If there are only yellow points (with no blue nor red), start from any yellow point and follow the polygon that makes you stay inside the other polygon.

Note that in general the intersection of non-convex polygons may consist of multiple disconnected regions. The procedure above will only give you one of these regions.

Answer 2

OK, so the solution wasn't simple but here it goes:
Given 3 arrays and original shapes:
- GroupA - all the points of polygonA inside polygonB
- GroupB - all the points of polygonB inside polygonA
- GroupI - all the intersection points of both polygons
- The original Polygons: PolygonA and PolygonB

Step 1:
Create Array: A+ by: merge PolygonA with GroupI:
1.1 Loop over the edges of PolygonA (each 2 neighbor points creating an edge - also the first and the last).
1.2 For each edge create a line equation: "y = mx + b" (given 2 points)
1.3 Collect all the point of GroupI that are placed on the line created at "1.2"
1.4 Sort the collected points by distance from the edge start point.
1.5 Add the sorted collection to PolygonA after the edge start point.
2. Return the new PolygonA as a new array: A+

Step 2:
Repeat step1 but create B+ form PolygonB with groupI.

Step 3:
Create Array A* by removing points from A+ that not exist of GroupA

Step 4:
Create Array B* by removing points from B+ that not exist of GroupB

Step 5:
Merge Array A* with B*
5.1 - Create a new array Result
5.2 - Loop over A* and B* with 2 indexes: iA and iB, for each point:
5.3 - If point is None intersection point - add it to the Result array and increment the active index (iA or iB)
5.4 - If point is intersection point - add it the the result array and switch to the 2nd array (if you where iterating over A* switch to B* and vise versa).
5.4.1 - Set the index to the position of the intersection point in the 2nd array (meaning if you are at pointX in A* and this is intersection point, start running on B* from the location of pointX at B*)

Here is an example: