Thread: Finding the outside of arbitrary shape

  1. #16
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by BobMcGee123 View Post
    Well the OP did define this to be for 'closed' shapes, which to me says convex polygons.
    No, from his description I think it is clear that he meant arbitrary shapes.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  2. #17
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by Bubba View Post
    I'm a bit confused why you bring this up and then add code that definitely breaks it for concave shapes.
    Yeah sorry, the code I posed was certainly not intended to work with non-convex shapes either. But am fairly certain that was intended by the OP. It is equivalent to your code.

    One way to handle arbitrary shapes is by triangularization (Delaunay) into convex shapes, or as you point out, by casting rays.
    Last edited by Sang-drax; 08-21-2008 at 04:32 AM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  3. #18

    Join Date
    May 2005
    Posts
    1,042
    No, from his description I think it is clear that he meant arbitrary shapes.
    Yeah, especially re-reading and he says 'horizontal and vertical lines only' (which means that they often won't be convex, as the definition is that the inner angle between adjacent lines is less than 180).

    as sang drax said you either need to use Bubba's method of simple ray casting from the outside of the object (to determine if the point is inside the geometry), or you need to subdivide each shape into convex regions. The former would probably be easier.

    I wasn't familiar with Delauney triangulation, I did some reading up on it and while it'd work, I really think the op'd be better off using a raycasting technique or something similar (esp. considering the assumption of only horizontal and vertical lines).

    Another method, considering the fact that you're using OpenGL, is to do an offline render using the gl occlusion query extension. Render the geometry in question, then (with occlusion query turned on) render a primitive (a square, circle or just a point) that represents the cursor position somewhere further down the z-axis. The occlusion query will tell you how many pixels of the depth-test passed (if none passed, then the cursor is inside the geometry). This may seem complicated, but it'd actually spare you of basically all of the math details. It isn't relatively computationally efficient, but it'd work and it's an interesting solution. However I don't know what you'd do if the end user's card doesn't support the occlusion query.

    Anyway just an idea, the ray casting idea is still ultimately probably the best option.
    Last edited by BobMcGee123; 08-21-2008 at 03:08 PM.
    I'm not immature, I'm refined in the opposite direction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Filling a shape
    By SlayerBlade in forum C Programming
    Replies: 5
    Last Post: 10-07-2005, 08:26 PM
  2. Newbie- having trouble with functions
    By bnmwad in forum C Programming
    Replies: 7
    Last Post: 02-22-2005, 04:41 PM
  3. Area of irregular shape
    By Brian in forum Game Programming
    Replies: 4
    Last Post: 06-23-2004, 10:54 AM
  4. CDC shape Helps
    By cfrost in forum C++ Programming
    Replies: 3
    Last Post: 05-13-2004, 05:49 AM
  5. MFC :: Finding Child Window of a CWnd* Object?
    By SyntaxBubble in forum Windows Programming
    Replies: 2
    Last Post: 09-06-2003, 09:06 AM