Point in 2d polygon.

Performance Tuning
#1

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.


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.

#2

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

    /**
     * {@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);
    }
#3

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.

#4

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?

#5

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)

#6

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.

http://dl.dropbox.com/u/10960490/fan.png

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.

#7

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.

#8

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


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

The personal attacks thread. (everything goes)
#9

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

The personal attacks thread. (everything goes)
#10

I removed the semicolons, so I guess its apparent now that I didn’t really test it :slight_smile:

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