Getting Points Inside Of A Polygon

[twoski]

Let's say we have a somewhat complex polygon shape.

We know the list of 2d vectors that make up its border loop.

Now let's say i want to create a list of points within this polygon. Currently i am using ray traces to create a grid of points that fall within the polygon. I'm certain there is a better and faster way to achieve this without using raytraces though. Does anyone know of an algorithm to detect whether a point falls within a polygon which may be concave?

 

[jedishrfu]

When I did games ages ago, I would use background color to determine if a point was inside.

Another trick would be bounding box to eliminate some points. For others it gets trickier.

 

[twoski]

I have read about one approach where you draw a ray from a given point to the right then count how many times it collides with a polygon edge. If the number is odd, it's inside. If it's even, it's outside. The issue with this approach, i think, is that it wouldn't be any faster than my current raytracing since you still have to do a fair bit of collision checking with the line.

 

[jedishrfu]

Yes also what do you do about shapes within shapes or shapes overlapping shapes. That’s why I liked the color pixel approach. You could subtly adjust the color value to make each shape unique or maybe its intensity value.

People won’t notice subtle changes.

 

[mfb]

You don't need to modify the output for the user, you can store an internal array of pixels if that is helpful for the game. If you need many points it might save some computing time.

 

[jedishrfu]

Great idea @mfb

My gaming experience is from the days of the C64 where memory was more constrained and pixel checks were somewhat common in Basic programming.

Also the shape fill method was available to do the tough work of colorizing the area.

 

[Tom.G]

I have read about one approach where you draw a ray from a given point to the right then count how many times it collides with a polygon edge. If the number is odd, it's inside. If it's even, it's outside. The issue with this approach, i think, is that it wouldn't be any faster than my current raytracing since you still have to do a fair bit of collision checking with the line.

Does it help if you actually draw the polygon perimeter in scratch memory? You could then sample a byte - or even a quadword - at a time to see if the ray has a bit set in the sample.

If you have a GPU available in the system there may even be a Call to do the testing.

Something that may lead to a different approach to the problem is the Flood Fill algorithm. Once one point is found inside the polygon, all the others are findable.

 

[robphy]

Possibly useful:

https://www.geogebra.org/m/zMrxGqbF
Testing if a point is inside a triangle (3 methods)
Author:Michael Borcherds

which makes reference to http://blackpawn.com/texts/pointinpoly/

Additionally, there is
https://en.wikipedia.org/wiki/Point_in_polygon
and
http://geomalgorithms.com/a03-_inclusion.html