Three-dimensional point-in-polygon operation to facilitate visualizing 3D locations enclosed by 3D geometric regions
First Claim
1. A computer-implemented method for visualizing location of a 3D location relative to a 3D geometric region, comprising:
- translating each face of the 3D geometric region onto a reference plane to generate corresponding 2D geometric regions;
performing, for a first of the 2D geometric regions, a 2D point-in-polygon (PIP) operation using an index of open line segments to determine that the first 2D geometric region encloses a translation of the 3D location onto the reference plane;
determining that the 3D location is enclosed by the 3D geometric region; and
causing a presentation of a visual representation based on the determination that the 3D location is enclosed by the 3D geometric region.
1 Assignment
0 Petitions
Accused Products
Abstract
A system, a method and instructions embodied on a non-transitory computer-readable storage medium that solve a 3D point-in-polygon (PIP) problem is presented. This system projects polygons that comprise a set of polyhedra onto projected polygons in a reference plane. Next, the system projects a data point onto the reference plane, and performs a 2D PIP operation in the reference plane to determine which projected polygons the projected data point falls into. For each projected polygon the projected data point falls into, the system performs a 3D crossing number operation by counting intersections between a ray projected from the corresponding data point in a direction orthogonal to the reference plane and polyhedral faces corresponding to projected polygons, to identify polyhedra the data point falls into. The system then generates a visual representation of the set of polyhedra, wherein each polyhedron is affected by data points that fall into it.
-
Citations
30 Claims
-
1. A computer-implemented method for visualizing location of a 3D location relative to a 3D geometric region, comprising:
-
translating each face of the 3D geometric region onto a reference plane to generate corresponding 2D geometric regions; performing, for a first of the 2D geometric regions, a 2D point-in-polygon (PIP) operation using an index of open line segments to determine that the first 2D geometric region encloses a translation of the 3D location onto the reference plane; determining that the 3D location is enclosed by the 3D geometric region; and causing a presentation of a visual representation based on the determination that the 3D location is enclosed by the 3D geometric region. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for visualizing location of a 3D location relative to a 3D geometric region, the method comprising:
-
translating each face of the 3D geometric region onto a reference plane to generate corresponding 2D geometric regions; performing, for a first of the 2D geometric regions, a 2D point-in-polygon (PIP) operation using an index of open line segments to determine that the first 2D geometric region encloses a translation of the 3D location onto the reference plane; determining that the 3D location is enclosed by the 3D geometric region; and causing a presentation of a visual representation based on the determination that the 3D location is enclosed by the 3D geometric region. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. A system for visualizing location of a 3D location relative to a 3D geometric region, comprising:
-
at least one processor and at least one associated memory; and a display mechanism that executes on the at least one processor and is configured to; translate each face of the 3D geometric region onto a reference plane to generate corresponding 2D geometric regions; perform, for a first of the 2D geometric regions, a 2D point-in-polygon (PIP) operation using an index of open line segments to determine that the first 2D geometric region encloses a translation of the 3D location onto the reference plane; determine that the 3D location is enclosed by the 3D geometric region; and cause a presentation of a visual representation based on the determination that the 3D location is enclosed by the 3D geometric region. - View Dependent Claims (26, 27, 28, 29, 30)
-
Specification