Hey, Duder! Wanna know bout Point in Polygon Checks?

Point in Polygon you say!?

A point in polygon check is exactly what it sounds like. It's a check to determine whether or not a point lies inside or outside of a given polygon on a 2D plane. These types of checks are fairly common in video games and especially so when dealing with rectangles and circles. A very easy example would be your mouse cursor over any type of interface. Your mouse pointer has a coordinate, and that coordinate is typically being checked against a bunch of polygons (though usually in interfaces they're just rectangles and circles. . . more on that later) to determine whether the cursor should change shape and what should happen when any buttons are depressed.

What up with Rectangles and Circles?

Checking a point against a rectangle or a circle is super easy peasy. For a circle, all you need is the center point of the circle and its radius. You check if the distance between the center point and the point you're checking is greater than the radius of the circle and if it is, not inside. Otherwise. Inside. Done. For a rectangle it's also pretty damn easy in that you just check if the point is within the left and right sides (x) and also within the top and bottom (y) of the rectangle and you're done.

Non-rectangular polygons?

Once you have to start checking against irregular shapes, things get a bit more complicated but not to worry because there's plenty of resources online. The type of check that would work best for your needs depends highly on your specific needs. A small list of the types of things that could determine which methods might work best for you include things such as:

1. Which is more important, speed or accuracy.

2. Whether you're working with floating point numbers or integers.

3. If all your polygons are concave.

4. Whether your polygons have holes in them.

5. The number of polygons you need to check against.

6. The number of points you need to check.

7. Whether or not you will be breaking your complex polygons down into triangles.

There are plenty more factors which should determine what methods you use in your game/program.

Popular methods include

Hmm. . . I was going to write up a bunch of methods, but really. . . it's mostly just math. In most cases involving non-convex, complicated polygons, you'll probably use some form of ray-casting to determine whether your point is inside or not. That's a method where the point in question has a line drawn through it and the number of borders in the polygon is counted to determine whether it is inside (odd) or outside (even) the polygon. There are some issues with this method with the largest being floating point precision issues.

Floating point what now?

This can get super technical and you can find endless reading material on it just by searching Google for "floating point precision".

The super watered down, I don't give a shit about math version is that programming uses different types of containers for numbers. The higher the accuracy of a number you want, the larger the container needs to be. A bit can be a 1 or a 0. A byte can be between 0 through 255. An int can hold -32,768 ~ 32,768 etc. For the calculations that are required when working with decimals and fractions (which we are for point in poly tests with non-rectangular shapes) you use floats and floats are squirrely bastards. They can hold up to 7 digits with a decimal point within somewhere which gives you a pretty damn good range but when you go over that (as you generally do when working with crazy fractions), the numbers can sorta shift around. So, when you do some math one time, you may get 1.234567 but you do the exact same problem later and you could end up with 1.234568 or 1.234566 or seemingly any damn random number filling that last spot that floats can't go beyond. So even though it's a small as all hell error, that tiny amount could mean the difference between a point being in a polygon and not. Soooo. . . if you need to be uber accurate, it could cause issues.

Why. . . Why all this?

I originally just wanted to post about some progress I made today with my game. I had spent around 2 and a half to 3 months working on the vision portion of my game engine to accurately simulate line of sight in a 2D isometric world and after trying a bunch of things, I found that the best way to do it would be to create polygons for in world objects/walls/floors/etc and then test points to see whether things are seen or not against those polygons. Now, the way I'm doing it is different from other 2D games with line of sight in that I didn't just want horizontal line of sight, but vertical as well because it's isometric with multiple vertical floors. Anyway, basically I went from this

to this

During a vision check, it would take almost half a second to finish because I was running over 3 million point in poly checks against 6,539 polygons. I set up the test to take place in manufactured situation that the player probably wouldn't encounter but they might and I'd rather the game not chug if they do. When I first plugged in the debug methods to check exactly how many times it was running the point in poly check, and more importantly, how many of them were hits rather than misses, I was pretty shocked. Less than 0.01% of the checks were returning as hits meaning that 99.99% of the checks were fails. . . I had already set up the method to cull out any polygons that they were nowhere near but I had to do more. What I ended up doing was increasing the fidelity of the array that was populated by the polygons which increased the number of polygons added to arrays from 11,116 to 92,322 but the trade off was close to 3 million point in poly checks. Also, the time it takes to run the method dropped by around 85%. So barring any memory issues, I think I'm on the right track =)

Oh, and the new hit count is around 21% which isn't bad at all in my opinion. I'm fairly decent at FPS games and my hit rate is rarely that high. I mean, because that's what I should be comparing it to right? -_-;;.

So yea, that's it

My quick status update of "Totally reduced the amount of time it takes to run a function today" into this mess. So I'll pretty much end this blog with a big ol "Fuck floating point precision errors!"