Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 7 of 7

Thread: Finding all the points that lie inside a polygon

  1. #1
    Junior Member Regular Contributor
    Join Date
    Jun 2010
    Posts
    162

    Finding all the points that lie inside a polygon

    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.

  2. #2
    Senior Member OpenGL Guru Dark Photon's Avatar
    Join Date
    Oct 2004
    Location
    Druidia
    Posts
    3,183
    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.

  3. #3
    Junior Member Regular Contributor
    Join Date
    Jun 2010
    Posts
    162
    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.

  4. #4
    Senior Member OpenGL Guru Dark Photon's Avatar
    Join Date
    Oct 2004
    Location
    Druidia
    Posts
    3,183
    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.

  5. #5
    Junior Member Regular Contributor
    Join Date
    Apr 2012
    Location
    Los Angeles
    Posts
    173
    Quote Originally Posted by jenny_wui View Post
    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.

  6. #6
    Junior Member Regular Contributor
    Join Date
    Jun 2010
    Posts
    162
    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.

  7. #7
    Junior Member Regular Contributor
    Join Date
    Apr 2012
    Location
    Los Angeles
    Posts
    173
    Quote Originally Posted by jenny_wui View Post
    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.
    Last edited by Carmine; 07-18-2013 at 04:49 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •