# Finding the outside of arbitrary shape

This is a discussion on Finding the outside of arbitrary shape within the Game Programming forums, part of the General Programming Boards category; Originally Posted by BobMcGee123 Well the OP did define this to be for 'closed' shapes, which to me says convex ...

1. Originally Posted by BobMcGee123
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.

2. Originally Posted by Bubba
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.

3. 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.

Page 2 of 2 First 12