I Getting Points Inside Of A Polygon

  • Thread starter twoski
  • Start date
181
2
Let's say we have a somewhat complex polygon shape.

fNmZ4fZ.png


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

10,231
3,788
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.
 
181
2
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.
 
10,231
3,788
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.
 
32,372
8,350
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.
 
10,231
3,788
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

Science Advisor
2,467
1,312
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

Science Advisor
Homework Helper
Insights Author
Gold Member
5,367
652

Want to reply to this thread?

"Getting Points Inside Of A Polygon" You must log in or register to reply here.

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

Top Threads

Top