PDA

View Full Version : Finding all the points that lie inside a polygon



jenny_wui
07-16-2013, 10:11 AM
Hello, I have separated some portion of a rectangular image which is now a polygon. I would like to consider only the pixels that lie inside the polygon. Could anyone suggest how that can be implemented? Thanks.

Dark Photon
07-16-2013, 04:14 PM
Where would you like to consider that? On the CPU? Or on the GPU (e.g. in a shader)?

If the latter, tessellate the polygon, rasterize the component triangles, and process the covered pixels in those triangles.

If the former, do something similar, but you need to implement a triangle rasterizer to generate pixel spans.

jenny_wui
07-17-2013, 03:24 PM
Thanks for the reply, but if I have a lot of boundary points, then I shall have too many triangles. In image processing, there is a function bwconvexhull, which can separate the region, but I don't know it's underlying algorithm, whether it is similar to triangulation or not.

Dark Photon
07-17-2013, 05:23 PM
Why too many triangles? If convex hull gives you your polygon, triangulation is easy (since it's convex) -- pick 2 adjacent verts and then iteratively select one of the remaining verts for a 3rd. The GPU is fast, so don't worry about it.

On the flip side, if you have your region in pixel form rather than vector form (implied by your mention of bwconvexhull), then you could transfer it to the stencil buffer or alpha channel to "mask off" pixel ops so they only take affect within your region.

Carmine
07-18-2013, 11:12 AM
I have separated some portion of a rectangular image which is now a polygon. I would like to consider only the pixels that lie inside the polygon. Could anyone suggest how that can be implemented? It's an interesting problem. Can give more specifics on the 'polygon' you are working with. Is it defined by vertices with known x, y coordinates? Do you know the ordering of these vertices? Or - is it just a blob of contiguous pixels? If it is a blob, seems to me it would be more difficult. How would you even know which pixels are polygon vertices, polygon edges, or internal? A convex hull routine would only identify some of the vertices. What do you mean by 'consider' the inside pixels. A picture of the polygon you are starting with would be helpful.

jenny_wui
07-18-2013, 02:19 PM
Thanks for the reply. I think I need to clarify a bit. Suppose my convex hull consists of 30 boundary points. i know the x,y coordinates of all boundary points of convex hull. I am trying to extract all the pixels (may be of different intensity value) inside the convex hull. Now the triangles may be too thin, pixels may be duplicated when I shall try to process triangles containing the pixels inside it. and I may need to process 28 triangles.

Carmine
07-18-2013, 05:32 PM
Thanks for the reply. I think I need to clarify a bit. Suppose my convex hull consists of 30 boundary points. i know the x,y coordinates of all boundary points of convex hull. I am trying to extract all the pixels (may be of different intensity value) inside the convex hull. Now the triangles may be too thin, pixels may be duplicated when I shall try to process triangles containing the pixels inside it. and I may need to process 28 triangles.I didn't know the polys you're working with are convex. That makes things simpler. Are you SURE this is the case? Now, all you have to do is loop thru all the pixels in the image (converting to x,y), and test to see if it's in the hull. That's really not too complicated. I'm sure you can find several ways to do that on the web.