Java-Gaming.org Hi !
 Featured games (91) games approved by the League of Dukes Games in Showcase (757) Games in Android Showcase (229) games submitted by our members Games in WIP (844) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Point in 2d polygon.  (Read 17902 times) 0 Members and 1 Guest are viewing this topic.
pitbuller
 « Posted 2012-03-13 21:06:21 »

I once again get hooked to pointless micro performance optimizations but didn't use as much time for checking the algorithm.

I made quite fast algorithm that check point vs any polygon. But is there way to do this even faster.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76 `public class Bench {         /**    * Checks whether the given point is in the polygon(can be concave). x[] and    * y[] is assumed to be least size of verticesNum    *     * @param x    *            array of x coordinates    * @param y    *            array of y coordinates    * @param verticesNum    * @param px    *            point x coordinate    * @param py    *            point y coordinate    * @return Wheter the point is in the polygon    */   public static boolean isPointInPolygon(float x[], float y[],         int verticesNum, float px, float py) {      if (verticesNum < 3)         return false;      boolean oddNodes = false;      float x2 = x[verticesNum - 1];      float y2 = y[verticesNum - 1];      float x1, y1;      for (int i = 0; i < verticesNum; x2 = x1, y2 = y1, ++i) {         x1 = x[i];         y1 = y[i];         if (((y1 < py) && (y2 >= py))               || (y1 >= py) && (y2 < py)) {            if ((py - y1) / (y2 - y1)                  * (x2 - x1) < (px - x1))               oddNodes = !oddNodes;         }      }      return oddNodes;   }         /**    * @param args    */   public static void main(String[] args) {      // TODO Auto-generated method stub      int N = 667;      float x[] = new float[N];      float y[] = new float[N];      x[0] = N;      y[0] = 0;      x[1] = 0;      y[1] = 0;      for (int i = 2; i < N; i++) {         x[i] = N;         y[i] = (float) Math.random() * N;      }      boolean t = false;      // warmup      for (int j = 0; j < N; j++) {         t = isPointInPolygon(x, y, N, j, j);      }      long time = System.nanoTime();      for (int j = 0; j < N; j++) {         for (int i = 0; i < N; i++) {            t = isPointInPolygon(x, y, N, j, i);         }      }      System.out.println(t + " time used:"            + (System.nanoTime() - time)            / 1000000 + "ms");   }`

I allready tried trick that is introduced there  http://alienryderflex.com/polygon/ but those didn't help at all.

This is used for box2dLights to check if given point is inside of any light to query is something in shadows.
philfrei
 « Reply #1 - Posted 2012-03-13 22:24:49 »

If anyone is interested in comparing, here is the implementation from Java.awt.geom, Polygon
I wonder how much slower it is.
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66 `    /**     * {@inheritDoc}     * @since 1.2     */    public boolean contains(double x, double y) {        if (npoints <= 2 || !getBoundingBox().contains(x, y)) {       return false;   }   int hits = 0;   int lastx = xpoints[npoints - 1];   int lasty = ypoints[npoints - 1];   int curx, cury;   // Walk the edges of the polygon   for (int i = 0; i < npoints; lastx = curx, lasty = cury, i++) {       curx = xpoints[i];       cury = ypoints[i];       if (cury == lasty) {      continue;       }       int leftx;       if (curx < lastx) {      if (x >= lastx) {          continue;      }      leftx = curx;       } else {      if (x >= curx) {          continue;      }      leftx = lastx;       }       double test1, test2;       if (cury < lasty) {      if (y < cury || y >= lasty) {          continue;      }      if (x < leftx) {          hits++;          continue;      }      test1 = x - curx;      test2 = y - cury;       } else {      if (y < lasty || y >= cury) {          continue;      }      if (x < leftx) {          hits++;          continue;      }      test1 = x - lastx;      test2 = y - lasty;       }       if (test1 < (test2 / (lasty - cury) * (lastx - curx))) {      hits++;       }   }   return ((hits & 1) != 0);    }`

pitbuller
 « Reply #2 - Posted 2012-03-14 07:40:17 »

If anyone is interested in comparing, here is the implementation from Java.awt.geom, Polygon
I wonder how much slower it is.

Its actually reasonable fast. Only 2919ms vs 1942ms.
Main point why I didn't want to use that that setting the polygon once per frame per light is not good for performance.
But I bet if I just would copy paste that method there would't be really any significant performance differ.

Edit: actually the algorithm is quite clever with paramaters. Helped me another 10% when I mimiced the curX, lastX system.
philfrei
 « Reply #3 - Posted 2012-03-15 08:46:06 »

Neat! I think that is pretty great you were able to benchmark a comparison, and glad the code helped. I'm kind of under a cold at the moment, not thinking too clearly--hope to eventually look closer at that code, myself, see what I can learn from it.

Now, I do have a question, and there may be an obvious answer why this isn't done, but it isn't obvious to me. Suppose you made a 2D array of every pixel on the screen where instead of storing a color (4 bytes, right?) you stored an Object ID. How much additional cost is that?

I mean, with double buffering and all that, we are already dealing with some massive data arrays. Would this additional array of object ID's be a terrible cost?

The benefit would be that finding whether you are within a polygon would be a simple lookup. Are there other aspects besides shaders that could benefit from such an array?

Or is this a nutty idea?

Roquen

JGO Kernel

Medals: 517

 « Reply #4 - Posted 2012-03-15 08:51:05 »

Another thing is that (assuming you're going to test more than one point..which seems highly likely) is precompute the AABB for a fast rejection.  Assuming that there is a collection of concave polys some spatial partition is additionally option.  Very minor, you'll get less cache data motion if you pack the vertices into a single array...noticeable?  It depends.

(EDIT: spelling mistake and added cache note)
pitbuller
 « Reply #5 - Posted 2012-03-15 21:33:17 »

Another thing is that (assuming you're going to test more than one point..which seems highly likely) is precompute the AABB for a fast rejection.  Assuming that there is a collection of concave polys some spatial partition is additionally option.  Very minor, you'll get less cache data motion if you pack the vertices into a single array...noticeable?  It depends.

(EDIT: spelling mistake and added cache note)

In my use case I test dst2 against square radius for fast rejection. Points/coneLights are shape like triangle fan so bounding circle is really good way to do it fast.

Becouse those are fans there is O(1) cost to triangulate polygon but doing n point in triangle test was bit slower than my old algo.

There this one way that invole some trigonometry too. I would calculate angle and then solve in which sector point is. This would give another fast fail path for cone light. Then test would be just one point in triangle. Problem is that solving the actual angle is so slow that number of vertex should be much higher than current use case is(about 32-64)

philfrei: If I could just ask one pixel color from fbo texture without any slowdows this would be trivial. All lights are rendered to fbo that size is around quester of screen size.

Roquen

JGO Kernel

Medals: 517

 « Reply #6 - Posted 2012-03-16 08:31:07 »

Bounding circle is reasonable.  OK, since your concave shapes are the hull of a triangle fan then you should have a fair amount of extra information.  I'm assuming that the winding is consistent (either clockwise or counter-clockwise) and you also have a point insured to be inside (the center of the fan).  This is enough information to allow to to test against a sub-hull rather than the full thing.  Assuming that my brain is functioning prior to my first coffee.
tarlek

Junior Devvie

Medals: 2
Projects: 1

 « Reply #7 - Posted 2012-09-01 17:10:17 »

Another way, adapted from some C code I had, only needs 2 multiplies per polygon point:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40 `// incomplete class, example only// by Joe Davissonpublic class Polygon{  int px[];  int py[];  int pcount;  public boolean pointIn(int x, int y)  {    int i;    int inside = 0;    for(i = 0; i < pcount - 1; i++)    {      int px1 = px[i];      int px2 = px[i + 1];      int py1 = py[i];      int py2 = py[i + 1];      if(py1 <= y)      {        if((py2 > y) && (((px2 - px1) * (y - py1) - (x - px1) * (py2 - py1)) > 0)          inside++;      }      else      {        if((py2 <= y) && (((px2 - px1) * (y - py1) - (x - px1) * (py2 - py1)) < 0)          inside++;      }    }    if((inside & 1) > 0)      return true;    else      return false;  }}`

Edit: P.S. this assumes that the last vertex is a copy of the first vertex.

Riven

« JGO Overlord »

Medals: 1340
Projects: 4
Exp: 16 years

 « Reply #8 - Posted 2012-09-01 18:50:07 »

Another way, adapted from some C code I had, only needs 2 multiplies per polygon point:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40 `// incomplete class, example only// by Joe Davissonpublic class Polygon{  int px[];  int py[];  int pcount;  public boolean pointIn(int x, int y)  {    int i;    int inside = 0;    for(i = 0; i < pcount - 1; i++)    {      int px1 = px[i];      int px2 = px[i + 1];      int py1 = py[i];      int py2 = py[i + 1];      if(py1 <= y)      {        if((py2 > y) && (((px2 - px1) * (y - py1) - (x - px1) * (py2 - py1)) > 0);          inside++;      }      else      {        if((py2 <= y) && (((px2 - px1) * (y - py1) - (x - px1) * (py2 - py1)) < 0);          inside++;      }    }    if((inside & 1) > 0)      return true;    else      return false;  }}`

Are you 100% sure you want those semicolons there??

Hi, appreciate more people! Î£ â™¥ = Â¾
Learn how to award medals... and work your way up the social rankings!
tarlek

Junior Devvie

Medals: 2
Projects: 1

 « Reply #9 - Posted 2012-09-02 00:16:46 »

I removed the semicolons, so I guess its apparent now that I didn't really test it
pitbuller
 « Reply #10 - Posted 2012-09-02 18:08:07 »

 1  2  3  4  5  6  7  8  9  10  11 `bool isPointInPolygon(const Vector2f& point, const Vector2f* vertices, const unsigned vertexCount){   bool inside = false;   for (unsigned i = 0, j = vertexCount-1; i < vertexCount; j = i++)   {      if (((vertices[i].y > point.y) != (vertices[j].y > point.y)) &&         (point.x < (vertices[j].x - vertices[i].x) * (point.y - vertices[i].y) / (vertices[j].y - vertices[i].y) + vertices[i].x))         inside = !inside;   }   return inside;}`

This is fastest c++ version that I have tested. It's not very elegant but really fast.

Tarlek: You forget to check segment between first and last point. This is needed.
Pages: [1]
 ignore  |  Print

 EgonOlsen (74 views) 2018-06-10 19:43:48 EgonOlsen (55 views) 2018-06-10 19:43:44 EgonOlsen (74 views) 2018-06-10 19:43:20 DesertCoockie (254 views) 2018-05-13 18:23:11 nelsongames (154 views) 2018-04-24 18:15:36 nelsongames (154 views) 2018-04-24 18:14:32 ivj94 (895 views) 2018-03-24 14:47:39 ivj94 (156 views) 2018-03-24 14:46:31 ivj94 (808 views) 2018-03-24 14:43:53 Solater (172 views) 2018-03-17 05:04:08
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org