Polygon created by subtracted polygons

Question

Above is a polygon (gray area) where I subtracted 4 polygons (red, green, purple, and blue areas). Is there a way to get the vertices of the created sub-polygon (small gray polygon)?

The polygons can be of any shape. Also, the side subtracted polygon can lie on the side of the main polygon (that's why I did not call it hole).

Answer 1

Algorithm:

My proposal is in this particular case that you make an UNION operation of those bright colored polygons. After operation the solution consists of two polygons: The outer which has an orientation CW and a hole polygon which has an orientation of CCW. You need this hole polygon and to know which one of those two is a hole, you can calculate the area of both. The polygon with negative area is a hole polygon.

---

Implementation:

Clipper library provides you the needed UNION operation and the area calculation operation (as well as many other operations also).

Clipper is available in eg. C++, C#, Delphi and Javascript.

C++, C#, Delphi: https://sourceforge.net/projects/polyclipping/

Javascript: https://sourceforge.net/projects/jsclipper/
Demo: http://jsclipper.sourceforge.net/6.2.1.0/main_demo.html

The image below is a screenshot of Clipper Javascript Demo. The operation is INTERSECT.

Answer 2

You want to look into clipping algorithms like Vatti. Or may be you want some port or binding of gpc.