Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Calculating percentage overlap of polygons (C++)

Posted on 2005-04-28
23
Medium Priority
?
2,230 Views
Last Modified: 2012-05-05
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.
0
Comment
Question by:JustinBlandford
  • 9
  • 7
  • 3
  • +2
23 Comments
 
LVL 4

Expert Comment

by:smpoojary
ID: 13885056
See the book "Graphics in C". But I have forgotten Author of that book. There are so many methods to scan polygon. One is scan-by-line. If you get the C code then you can covert it to C++ language. Means you have to scan line by line of two polygons by pixel wise. Then you have to detect the pixels. Goto index of any "Graphics in C" book and check "polygon drawing" and mthod "scan-by-line".
-Mahesh
0
 
LVL 14

Expert Comment

by:wayside
ID: 13885079
To calculate the percentage overlap, you need to be able to either figure out:

- 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/book/AlgDesignManual/BOOK/BOOK4/NODE191.HTM

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

Hope this help.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 13885409
Area of polygon theory:
http://www.attewode.com/Calculus/AreaMeasurement/area.htm

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].y - polygon[i+1].x*polygon[i].y);
         else
              area += (polygon[i].x*polygon[0].y - polygon[0].x*polygon[i].y);
     }
     if (area<0.0)    /* area could be negative */
         area *= -0.5;
     else
         area *= 0.5;

     return area;
}
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 13885472
Polygon intersection algorithms in C language:
http://www.cs.man.ac.uk/aig/staff/alan/software/
0
 

Author Comment

by:JustinBlandford
ID: 13885518
Didn't particlarly want to buy a book and I've already looked at the link suggested by wayside.  There is a link there to a page which should access the source code but unfortunately it doesn't work.  

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.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 13885624
overlapping percentage:
C / (A+B+C) * 100

Where:
A = 1st polygon area
B = 2nd polygon area
C = overlapped area
0
 

Author Comment

by:JustinBlandford
ID: 13885831
What if the polygons are in different locations?  I've got a set of x,y coordinates for each polygon.  If I calculate the areas I get two numbers which do not have any relationship spatially.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 13885872
if 2 polygons have not overlapped area, then C=0, then percentage = 0 / (any+any+0) * 100 = 0
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 13885885
Also,  2 polygons can have more than 1 overlapping area, in that case, C is the sum of all these areas
0
 
LVL 14

Expert Comment

by:wayside
ID: 13885977
> C / (A+B+C) * 100

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.
0
 

Author Comment

by:JustinBlandford
ID: 13886016
How do I calculate C?  This is the crux of the problem.  I need to work out how to calculate the overlapping area of two polygons and then calculate the percentage.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 13886019
Oh, sorry, wayside is correct.
0
 
LVL 55

Accepted Solution

by:
Jaime Olivares earned 500 total points
ID: 13886117
You calculate C by reading this article, it is not as simple as my area algorithm:
http://www.cs.man.ac.uk/aig/staff/alan/software/

0
 

Author Comment

by:JustinBlandford
ID: 13886196
Looks really good although unfortunately, it is only available for use non-commercially which doesn't help me.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 13886415
The theory doesn't have copyright, you can re-code your own algorithm by yourself.
0
 

Author Comment

by:JustinBlandford
ID: 13887540
Have had a look at the source code.  Looks mighty complicated.  I'm a little bit cagey about the copyright stuff on the source code.  Not sure where I'd start attempting to re-code!  Appreciate all your help though.  Any other ideas or web links?  
0
 
LVL 14

Expert Comment

by:wayside
ID: 13887650
Why not send the guy an email and ask him for a commercial license? It may be very reasonably priced.
0
 

Author Comment

by:JustinBlandford
ID: 13887682
Will do that.  I'll see what he comes back with.  Was hoping that there may have been an alternative to paying tho.  Not being a scrooge but not sure if my company will fork money out!  I'll e-mail him to check cost.  
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 13887741
interesting references here:
http://www.utpadan.com/iop.htm
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 13887809
Are the polygons simple non-crossing convex, non-crossing concave, or crossing concave?  If they allow crossing, what winding rule are you using?
0
 

Author Comment

by:JustinBlandford
ID: 13888763
The polygons can be any shape (convex or concave) and crossing.  Could be holes or multiple polygons involved.  Not sure what you mean by winding rule?
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 13890350
The winding rule convention you choose determines how self-crossing polygons are to be handled.  There is an odd-even rule, the nonzero rule, and other ones you can use.  Basically, if a ray emanating from a point crosses N edges to make it to the outside world, is that point inside or outside the polygon?  The odd-even rule says yes if N is odd, no if N is even.  Other rules can be more complex, like adding one to a count when you cross an edge going towards the right of the ray, and subtracting one when you cross an edge going towards the left.  

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.
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 13896058
What method do you go through when you just want to calculate the area of one of your polygons?
0

Featured Post

Get expert help—faster!

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
Suggested Courses

577 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question