How to find coordinates of non intersecting areas between two intersecting polygons?

Question

I have two polygons that have some intersection. Then there are some areas which belong to either Polygon1 or Polygon2.

How can I find the coordinates of those areas? Is there any algorithm to do that?

Please suggest !!

The image shows that the points belonging to shaded area is what I want to have here.

Answer 1

This is a standard, though quite non-trivial, computational geometry problem.

It is not too difficult to write your own algorithm to organize a loose list of points and edges into a polyhedral complex, by detecting line segment intersections, sorting edges around each vertex, walking around the faces, etc etc. But the path of least effort will surely involve leveraging as many existing libraries as possible. For example, here's how I would do it:

• pass the input lines and points into Shewchuk's "triangle" library (https://www.cs.cmu.edu/~quake/triangle.html) to get a triangulation of the union of the two polygons, subordinate to the original edges.
• classify each triangle of the output as lying inside the first polygon, the second, or both. Do this by e.g. testing containment of the centroid of each triangle.
• For the triangles belonging only to the first input polygon, split them into connected components, then compute boundary edge cycles for each connected component.
• Repeat for the second input polygon.