Concave Polygon Intersection - Algorithm 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)
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.