in reply to OT: point inside polyhedron test

I'm hoping I've read the question right: you want to check if a given point is inside a shape; and that shape is specified as a list of vertices. The shape is bounded by (straight) lines that connect those vertices.

One approach is to consider drawing a line from your candidate point to infinity: then count the number of times it crosses the bounding lines of the shape. If the number of lines that it crosses is an odd number, then the point was inside the shape. (Infinity is any point outside the bounding box of the shape).

--Dave

Replies are listed 'Best First'.
Re: Re: OT: point inside polyhedron test
by Dr. Mu (Hermit) on Feb 19, 2003 at 05:06 UTC
    One caveat: If the line crosses a bounding segment at one of its endpoints (a vertex), it will also cross the adjacent bounding segment at the same vertex, counting as two crosses. You will have to include a check for this condition and adjust accordingly.

    One way to do this is to count +1 if it crosses between the two endpoints, +1/2 if it intersects one endpoint, +0 if it intersects both endpoints (i.e. is coincident with the entire segment).

[reply]
      An anternative is to be careful with your inequalities. If the list of verticies follows a path, then you can simply exclude the endpoint that was part of the previous segment. --Dave
[reply]
        Yes, that's true, except in the case where both endpoints are intersected. You still have to check for this and discard such a segment from the count:
        
 *----------*
 |          |
 |          | A=1
 |          |
 |     @====X-----X==========>
 |            B=0 |
 |                | C=0
 |                |
 *----------------*

        [download]
        Moving clockwise, the second endpoint on A counts, since it wasn't part of the previous segment. If we counted the second endpoint of B, however, we'd end up with an even number, because this point cannot also count in C. So we have to discard segment B entirely.
[reply]
[d/l]

In Section Seekers of Perl Wisdom