Getting Points Inside Of A Polygon

  • I
  • Thread starter twoski
  • Start date
  • #1
181
2

Main Question or Discussion Point

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

Answers and Replies

  • #2
11,826
5,448
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.
 
  • #3
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.
 
  • #4
11,826
5,448
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.
 
  • #5
34,391
10,479
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.
 
  • Like
Likes jedishrfu
  • #6
11,826
5,448
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.
 
  • #7
Tom.G
Science Advisor
3,248
1,995
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.
 

Related Threads on Getting Points Inside Of A Polygon

  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
5
Views
992
  • Last Post
Replies
21
Views
12K
  • Last Post
Replies
4
Views
6K
  • Last Post
Replies
3
Views
9K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
5
Views
3K
Top