intersection and union of polygons

Question

I have polygons defined with their vertices's, and i need to calculate areas of their union and intersection. The most upsetting thing is that it is implemented in Mapping Toolbox, but i can't buy it. Does anyone knows how to make a fast algorithm to calculate it? Thank you for your time.

Answer 1

You just need to find the area of intersection ; the area of the union is trivially obtained from that. The PolygonIntersection package from FEX might be useful.

Answer 2

I would do like this:

1. Let S be the set of vertices from both polygons.
2. For each edge e₁ in polygon 1
   1. For each edge e₂ in polygon 2
      1. If e₁ intersects with e₂
         1. Add the intersection point to S
3. Remove all vertices in S that are inside polygon 1 or 2.

The resulting set of vertices should make up the union of the polygons.

For the intersection you simply remove all vertices in S that are outside of both polygon 1 and 2 (in the third step).

(You can look up point intersection and "inside-polygon"-checks elsewhere ;-)

• Intersection point of two lines
• Determining if a point lies on the interior of a polygon