in reply to Re: OT: point inside polyhedron test
in thread OT: point inside polyhedron test

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

  • Comment on Re: Re: OT: point inside polyhedron test

Replies are listed 'Best First'.
Re: Re: Re: OT: point inside polyhedron test
by dpuu (Chaplain) on Feb 19, 2003 at 19:00 UTC
    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]
        You're right, and we mustn't forget anther nasty case: 
          

  @=======*=====>
         / \
        /   \
       /_____\
        Here, we want to count the end-point twice! Endpoints are nasty. If you intersect one, you need to be careful. --Dave
[reply]

In Section Seekers of Perl Wisdom