2 Replies Latest reply: Mar 13, 2010 8:54 PM by 843853 RSS

    Fast algorithm to detect 2 polygon have the same edge

    843853
      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.
      BasicStroke bs = new BasicStroke(0.001f);
      Area c = new Area(bs.createStrokedShape(a));
      c.intersect(new Area(bs.createStrokedShape(b)));
      return !c.isEmpty();
      is there any fast algorithm to solve my problem ?

      thanks

      tenly
        • 1. Re: Fast algorithm to detect 2 polygon have the same edge
          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.");
          }
          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.
          int nexta, nextb;
          for(int i = 0; i < b.npoints; i+=2){
          // check if the i-th 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 = j-1;
          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 = i-1;
          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
            tenly wrote:
            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.
            You want to check whether two polygons overlap?

            If you have an accurate but slow algorithm then you can combine it with a fast pre-test. Then often the average time can be improved because the pre-test 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.