8

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.

Jacob
  • 34,255
  • 14
  • 110
  • 165
Kate
  • 109
  • 1
  • 5
  • The function is 'polybool'. And i can calculate the area with 'polyarea' (which is available for me). – Kate Oct 27 '11 at 12:21
  • I think you shouldn't ask for users to violate copyrights. Edited. – Dr. belisarius Oct 27 '11 at 12:51
  • 1
    @Kate: Are your polygons guaranteed to be convex? – Jacob Oct 27 '11 at 13:11
  • @Verde, amused as I was by your comment, I think your objection is misplaced. I think it's unlikely that the *algorithm* is belongs to MathWorks rather than the implementation, and the question is asking for an algorithm. Whether the (independent) re-implementation violates copyright or patent law, I suspect, depends on your jurisdiction. – Superbest Aug 31 '12 at 23:48

4 Answers4

3

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.

enter image description here

Jacob
  • 34,255
  • 14
  • 110
  • 165
1

I would do like this:

  1. Let S be the set of vertices from both polygons.
  2. For each edge e1 in polygon 1
    1. For each edge e2 in polygon 2
      1. If e1 intersects with e2
        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 ;-)

aioobe
  • 413,195
  • 112
  • 811
  • 826
  • thank you for your answer, but how can i find intersection points? is it necessary to use equation of a line? – Kate Oct 27 '11 at 12:41
  • Added two links to my answer. – aioobe Oct 27 '11 at 12:44
  • thank you. i know math, but unfortunately i'm not a very good programmer, so having codes there is very nice. – Kate Oct 27 '11 at 12:49
  • This FEX package computes the intersection points between polygons: http://www.mathworks.com/matlabcentral/fileexchange/8908-curve-intersect-2. – Jacob Oct 27 '11 at 13:09
-1

The idea is to break every intersect edge into four parts and form a new polygon with these. When you want the union, take the two outer edges. If you want intersection, take the two inner edges.

Brad Koch
  • 19,267
  • 19
  • 110
  • 137
waTer
  • 21
  • 7
-1

I found intersection points of my polygons and added vertices that are inside/outside polygons for intersection/union task (check if any of vertices of polygon 1 lies inside a polygon 2 and vice versa using 'inpolygon'). Then all points were transformed into polar coordinates with center in the mean coordinates of the matrix and sorted by angle, so that now they form consecutive closed contour. Knowing this it is easy to find intersection/union area using 'polyarea'.

Kate
  • 109
  • 1
  • 5