How tell if a point is within a polygon for texture

Question

This seems to be a rather asked question - (hear me out first! :)

I've created a polygon with perlin noise, and it looks like this:

I need to generate a texture from this array of points. (I'm using Monogame/XNA, but I assume this question is somewhat agnostic).

Anyway, researching this problem tells me that many people use raycasting to determine how many times a line crosses over the polygon shape (If once, it's inside. twice or zero times, it's outside). This makes sense, but I wonder if there is a better way, given that I have all of the points. Doing a small raycast for every pixel I want to fill in seems excessive - is this the only/best way?

If I have a small 500px square image I need to fill in, I'll need to do a raycast for 250,000 individual pixels, which seems like an awful lot.

Answer 1

If you want to do this for every pixel, you can use a sweeping line:

Start from the topmost coordinate and examine a horizontal ray from left to right. Calculate all intersections with the polygon and sort them by their x-coordinate. Then iterate all pixels on the line and remember if you are in or out. Whenever you encounter an intersection, switch to the other side. If some pixel is in, set the texture. If not, ignore it. Do this from top to bottom for every possible horizontal line.

The intersection calculation could be enhanced in several ways. E.g. by using an acceleration data structure like a grid, quadtree, etc. or by examining the intersecting or touching edges of the polygon before. Then, when you sweep the line, you will already know, which edges will cause an intersection.