# I 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?

#### Attachments

• 9.9 KB Views: 165

#### jedishrfu

Mentor
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

Mentor
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

Mentor
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

Mentor
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

Homework Helper
Gold Member

"Getting Points Inside Of A Polygon"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving