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 5 of 5

Thread: Finding the convex hull of a set of points

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

    Finding the convex hull of a set of points

    Hello every body, I need to find the convex hull of a set of points. Could any one help me how that can be done. Lastly, I need to find the boundary of the convex hull. Thanks.

  2. #2
    Junior Member Regular Contributor
    Join Date
    Apr 2012
    Location
    Los Angeles
    Posts
    187
    The convex hull of a set of points (call it P) in a plane would be made up of line segments connecting some of the points in P. The convex hull of a set of points in 3-space (call it Q) would be made up of a set of triangles with vertices from Q. Do you have a 2D or 3D situation? Have you tried Googling 'Convex Hull'? I believe there's some free code you can get to do hulls. I think QHull is one of them.

    Note: I'm not defining 'Convex Hull' in the statements above. I'm just describing what the geometric boundaries of 2D or 3D hulls would be.

  3. #3
    Junior Member Regular Contributor
    Join Date
    Jun 2010
    Posts
    162
    I need to find convex hull in 2D. Actually I am looking for some relevant code in the net. Thanks.

  4. #4
    Junior Member Regular Contributor
    Join Date
    Apr 2012
    Location
    Los Angeles
    Posts
    187
    2D is fairly straightforward. Maybe after reading overviews of some of the algorithms you can write it yourself? For 2D I suggest the gift wrapping approach. For 3D, I like the incremental approach.

  5. #5
    Junior Member Regular Contributor
    Join Date
    Jun 2010
    Posts
    162
    Thanks, a nice implementation has been given to the following link:
    http://en.wikibooks.org/wiki/Algorit...Monotone_chain

Posting Permissions

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