-Mahesh

Solved

Posted on 2005-04-28

Does anyone know if there is a formula or function I can use to calculate the percentage overlap of two polygons? I have found sample code to detect if polygons intersect but my searches have been fruitless for a solution to calculate overlap percentage. The project I am working on is written in C++ so ideally I would like a solution in the same language.

23 Comments

-Mahesh

- the area of each polygon

- a new polygon which is either the intersection or union of the two polygons

- the area of the new polygon

From there the percentage overlap is simple arithmetic.

A quick search on google turned up this link, which has a nice discussion about it: http://www2.toki.or.id/boo

This link looks like is contains links to source code for operating on polygons; perhaps it will be useful to you.

Hope this help.

http://www.attewode.com/Ca

So, area of polygon algorithm must be, something like:

typedef struct { /* assumming some point structure */

double x;

double y;

} TPoint;

double AreaOfPolygon(TPoint *polygon, int nodes)

{

double area = 0;

int i;

if (nodes<3) /* protection */

return 0.0;

for (i=0; i<nodes; i++) {

if (i<nodes-1)

area += (polygon[i].x*polygon[i+1]

else

area += (polygon[i].x*polygon[0].y

}

if (area<0.0) /* area could be negative */

area *= -0.5;

else

area *= 0.5;

return area;

}

If I calculate the areas of each polygon, how then can I get the intersection percentage?

Cheers for looking though. I'm amazed by the rapid response as I'm a newby to EE.

C / (A+B+C) * 100

Where:

A = 1st polygon area

B = 2nd polygon area

C = overlapped area

I think this should be

C / (A + B - C) * 100

Consider the case where A = B = C, that is, both polygons are the same and exactly on yop of each other. By the first equation, the percentage comes out to 33 1/3%; by my equation it comes out to 100%.

> If I calculate the areas I get two numbers which do not have any relationship spatially.

The area of the overlap is what links them spatially. If they don't overlap, the area of the intersection will be 0.

http://www.cs.man.ac.uk/ai

Anyway, when the polygons are complex like yours I think it would be best to first tesselate them into sets of nicely behaved convex clockwise non-self-crossing polygons. It is very easy to check intersections of tame polygons like these.

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**25** Experts available now in Live!