Patent ID: 8248409

Claim:
A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer cause the computer to perform a method, the method comprising: identifying a query point to analyze, where the query point is identifiable in a three dimensional space; identifying a solid polyhedron to analyze, the solid polyhedron being identifiable in the three dimensional space, the solid polyhedron comprising a set of boundary polygons represented as a set of planar faces in the three dimensional space, where a member of the set of planar faces has at least one edge in common with at least one other member of the set of planar faces; producing a vertex avoiding ray from the query point to a point outside the minimum bounding volume of the solid polyhedron by: identifying a reference line that includes the query point and that is parallel to one axis in the three dimensional frame of reference associated with the solid polyhedron; producing a set of lines L 1 through L N , N being an integer equal to the number of vertices of the solid polyhedron, where a line L x connects the query point to a vertex V x of the solid polyhedron; computing a set of angles A 1 through A N , where an angle A x describes an angle between a line L x and the reference line; identifying an angle A NOT that is not in the set of angles A 1 through A N ; and establishing the vertex avoiding ray as a ray that begins at the query point and travels in the direction described by A NOT ; initializing a count of crossing intersections to an initial value; manipulating the count of crossing intersections based, at least in part, on the vertex avoiding ray and a set of intersections; and providing a signal that indicates whether the query point is inside the solid polyhedron based, at least in part, on the count of crossing intersections.