Select all points in polygon challenge

hello OF

I have a brainteaser/challenge for anyone who is interested.

I’ve long been working on a sketch where I create a complex polygon, and then need to make an index of all integer points that fall within it (so basically, a vectorglm::vec2) which I later use for lots of different functions.

Initially I just used the point in polygon check, for an ofPolyline, iterating through the bounding rectangle of the polygon shape, and adding points to the vector if they returned inside.

But, this was pretty slow - because of the polygon complexity, and the fact that there were circa 500,000 points.

Then I moved to a different approach; drawing the polygon in pink to an ofFbo; using .readToPixels to copy the Fbo into a pixels object, and then iterating through the pixels using .getColor and adding points to the vector if they returned pink.

The second approach is much faster, albeit with a bottleneck around the readToPixels

Can anyone suggest a method that beats this? I am mainly intrigued to know if there is one.
S

1 Like

I think pixels will be a lot faster than geometry but some thoughts

a) for geometry, can you use a bounding box of the polygon or even a coarse grid – for example, if you divide the space into rectangles to identify regions you don’t need to check at all vs regions you need to check. (ie, this rectangle is 100% in the polygon, or 100% not, so don’t check any of these points)
b) could extend (a) with some spatial subdivision algorithms. I’ve had great luck in the past with things like bounding view hierarchy (for a different problem)

for pixels

c) use fast fbo read back (https://github.com/satoruhiga/ofxFastFboReader) to speed up the read to pixels call
d) you could not do read back but instead pack the data (~500000 = about 700x700) into an image, then do the pixel check on the gpu and read the data back…

also I’d be curious if there isn’t a library for doing this where someone has worked on this problem, for example


seems like maybe in the geospatial world there would be alot of research in this.

Hi,

Isn’t your question the same than “which algorithm to draw a polygon” (CPU side) ?
Such an algorithm have to find the points to draw. So all you may have to do should be to replace the
paintPixel(x,y,color) part of this algorithm by some
pixels_vector.push_back( Point(x,y) ) where Point is any class that handle integer points.

A basic algorithm might be enough, because you don’t seem to have to care about border pixels and antialiasing, you just want the pixels that are fully opaques.

I know an approach is to triangulate the polyline then draw each triangle. I remember about scanline strategies to fill a triangle. I would look for such algorithm(s) using the terms polylines triangulation or tesselation

and triangles rasterization

OF already has tesselation functions
https://openframeworks.cc//documentation/graphics/ofPath/#!show_getTessellation
https://openframeworks.cc/documentation/graphics/ofTessellator/
and I don’t know for rasterization but I guess not, because OpenGL do it.

Another thought: can’t you do all the work GPU side with shaders ?