Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (117)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Point in 2d polygon.  (Read 8736 times)
0 Members and 1 Guest are viewing this topic.
Offline 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.
Online 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);
    }

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline 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.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online 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?

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline Roquen
« 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)
Offline 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.






Offline Roquen
« 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.
Offline tarlek

Junior Member


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 Davisson

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

Online Riven
« League of Dukes »

JGO Overlord


Medals: 800
Projects: 4
Exp: 16 years


Hand over your head.


« 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 Davisson

public 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
Offline tarlek

Junior Member


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 Smiley
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline 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  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Grunnt (18 views)
2014-09-23 14:38:19

radar3301 (14 views)
2014-09-21 23:33:17

BurntPizza (31 views)
2014-09-21 02:42:18

BurntPizza (22 views)
2014-09-21 01:30:30

moogie (20 views)
2014-09-21 00:26:15

UprightPath (29 views)
2014-09-20 20:14:06

BurntPizza (33 views)
2014-09-19 03:14:18

Dwinin (48 views)
2014-09-12 09:08:26

Norakomi (75 views)
2014-09-10 13:57:51

TehJavaDev (105 views)
2014-09-10 06:39:09
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!