Implement Geometry Clipping

[Shkyrockett]

A Polygon clipping system is needed. It will most likely be used by the Editor more than anything else, but is needed.

Requirements:

• [ ] Needs to be performant.
• [ ] Simple polygon, to simple polygon clipping.
• [ ] Simple polygon, to multiple contour clipping.
• [ ] Multiple contour, to multiple contour clipping.
• [ ] Polyline to Polygon.
• [ ] Geometry path to polygon.
• [ ] Any shape to polygon.
• [ ] Must be able to handle self intersecting.
• [ ] Must be able to handle clockwise, as well as counter-clockwise windings.
• [ ] Must be able to handle edge coincident points.
• [ ] Should use common structures as much as possible.

[Shkyrockett]

While researching, I have found that there are several interesting algorithms.

• Sutherland Hodgman The Algorithm seems to be rather simple to implement, but doesn't seem to work with Polygons of multiple contours.
  • Weiler Atherton Seems to be a fairly early algorithm.
• Vatti which is used in the Clipper library.
• Greiner Hormann Is an algorithm that is supposed to be faster than Vatti, but cannot handle degeneracies.
• Martínez There are two versions, both seem to be in the public domain, and can handle polygons with multiple contours.

[Shkyrockett]

Have implementations of Sutherland Hodgman, Greiner Hormann, and Martinez. Martinez is looking promising. If I could separate the clipping algorithm from Clipper, it would be interesting to see how Vatti works, and whether it meets the qualifications.

[Shkyrockett]

The current implementation of the Martinez polygon clipping algorithm here does not work quite right when an inside shape node intersects an outer shape line. The following picture is supposed to be an intersection clipping. The red should be the intersection, the blue green is what it should look like. The current implementation of the Martinez polygon clipping algorithm uses the older version of the algorithm. This could possibly have been fixed in the later update that has been released.