This content has been marked as final.
Show 2 replies

1. Re: Fast algorithm to detect 2 polygon have the same edge
843853 Feb 5, 2010 2:52 PM (in response to 843853)Are you trying to see if the polygons have the same edge or if they have an intersecting area? I'll give you an answer to both of these.
If you are looking to see if they have an intersecting area, you can just loop through the points of b and check if they are in a (assuming they are Polygons).
for(int i = 0; i < b.npoints; i++){ if(a.contains(b.xpoints,b.ypoints[i]))
System.out.println("Yay! They intersect so we break out of the loop if we want to.");
}
int nexta, nextb;If you want to check if they have the same edge, that is a different matter. You will again want to loop through the points of b, but we really only need to loop through every other point.
for(int i = 0; i < b.npoints; i+=2){
// check if the ith point of b is also a member of a
for(int j = 0; j < a.npoints; j++){
if(b.xpoints[i] == a.xpoints[j] && b.ypoints[i] == a.ypoints[j]){
// Found a point that is both in a and b
// Now we check if the neighboring points are as well
nexta = (j+1) % a.npoints;
nextb = (i+1) % b.npoints;
if(b.xpoints[nextb] == a.xpoints[nexta] && b.ypoints[nextb] == a.ypoints[nexta])
System.out.println("Found a shared edge.");
nexta = j1;
if(nexta < 0) nexta += a.npoints;
if(b.xpoints[nextb] == a.xpoints[nexta] && b.ypoints[nextb] == a.ypoints[nexta])
System.out.println("Found a shared edge.");
nextb = i1;
if(nextb < 0) nextb += b.npoints;
if(b.xpoints[nextb] == a.xpoints[nexta] && b.ypoints[nextb] == a.ypoints[nexta])
System.out.println("Found a shared edge.");
nexta = (j+1) % a.npoints;
if(b.xpoints[nextb] == a.xpoints[nexta] && b.ypoints[nextb] == a.ypoints[nexta])
System.out.println("Found a shared edge.");
}
}
}I didn't time my codes, but with 100 points in each polygon they were much faster than what you were getting. Edited by: notmuchtotell on Feb 5, 2010 12:52 PM  small change in my code

2. Re: Fast algorithm to detect 2 polygon have the same edge
843853 Mar 13, 2010 8:54 PM (in response to 843853)tenly wrote:
You want to check whether two polygons overlap?
Hi all,
I have some problem in detecting 2 polygon (with more than 100 points) have the same edge or not.
I have tried using Class Area, but it take a lot of time, around 5534 ms.
If you have an accurate but slow algorithm then you can combine it with a fast pretest. Then often the average time can be improved because the pretest makes you have to run the slow algorithm less frequently.
In your case you could keep a covering rectangle for each polygon. It's very fast to check whether two rectangles overlap. And only if two covering rectangles overlap do you need to run the slow algorithm.