# US 2018/0322697 A1 · Three-dimensional point-in-polygon operation to facilitate visualizing 3d locations enclosed by 3d geometric regions > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2018/0322697 A1 - Document ID: US20180322697A1 - Status: Published application - Kind: A1 - Application number: 16/037,434 - Filed: 2018-07-17 - Published: 2018-11-08 - Earliest claimed: 2015-01-27 - Assignees: Splunk Inc. - Applicants: Splunk Inc. - Inventors: Geoffrey R. Hendrey - Web page: https://patentgrep.com/patent/US20180322697A1 ## CPC - A63F 13/577: using determination of contact between game characters or objects, e.g. to avoid collision between virtual racing cars - A63F 13/537: using indicators, e.g. showing the condition of a game character on screen - B64D 43/00: Arrangements or adaptations of instruments - G01C 21/3867: {Geometry of map features, e.g. shape points, polygons or for simplified maps} - G01C 21/3874: {Structures specially adapted for data searching and retrieval} - G06T 11/20: Drawing from basic elements - G06T 15/06: Ray-tracing - G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation} - G06T 19/00: Manipulating three-dimensional [3D] models or images for computer graphics - G06T 2210/21: Collision detection, intersection - A63F: CARD, BOARD, OR ROULETTE GAMES; INDOOR GAMES USING SMALL MOVING PLAYING BODIES; VIDEO GAMES; GAMES NOT OTHERWISE PROVIDED FOR - B64D: EQUIPMENT FOR FITTING IN OR TO AIRCRAFT; FLIGHT SUITS; PARACHUTES; ARRANGEMENT OR MOUNTING OF POWER PLANTS OR PROPULSION TRANSMISSIONS IN AIRCRAFT - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## 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. ## Claims ### 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. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the 2D point-in-polygon (PIP) operation comprises, for one of the 2D geometric regions: projecting parallel rays from segment endpoints of the 2D geometric region onto a reference line to generate intersection points between the projected rays and the reference line; and storing in the index at least a subset of the projected rays and associated open line segments of the 2D geometric region; obtaining from the index one of the projected rays and an associated set of open line segments, the obtained projected ray corresponding to a ray projected from the translated 3D location onto the reference line; and counting the open line segments in the set. ### Claim 3 (depends on 2) The computer-implemented method of claim 2, wherein storing the subset of projected rays in the index includes maintaining a list of open line segments for every nth interval on the reference line; and wherein obtaining a projected ray and an associated set of open line segments includes obtaining a list of open line segments for a nearest nth interval on the reference line, and adjusting the list to account for intervening line segment openings and closings associated with intersection points located between the nearest nth interval and a relevant interval on the reference line corresponding to the ray projected from the 3D location onto the reference line, to produce a list of open line segments for the relevant interval. ### Claim 4 (depends on 2) The computer-implemented method of claim 2, wherein the reference line is an X-coordinate axis or a Y-coordinate axis. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein determining that the 3D location is enclosed by the 3D geometric region comprises, for each 2D geometric region determined to enclose the translated 3D location, counting intersections between a ray projected from the 3D location in a direction orthogonal to the reference plane and a corresponding face of the 3D geometric region. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein the reference plane includes an X- and a Y-coordinate axis. ### Claim 7 (depends on 1) The computer-implemented method of claim 1, wherein the translation of the 3D location onto the reference plane comprises setting a Z-coordinate for the 3D location to zero. ### Claim 8 (depends on 1) The computer-implemented method of claim 1, wherein translating each face of the 3D geometric region onto a reference plane comprises setting Z-coordinates for line segments of each face of the 3D geometric region. ### Claim 9 (depends on 1) The computer-implemented method of claim 1, wherein the 3D geometric region comprises a weather model, a cell phone coverage map, or a sound model. ### Claim 10 (depends on 1) The computer-implemented method of claim 1, additionally comprising obtaining the 3D location by: receiving a query to be processed, wherein the query is associated with the 3D geometric region; and using a late-binding schema generated from the query to retrieve the 3D location from a set of events containing previously gathered data. ### Claim 11 (depends on 1) The computer-implemented method of claim 1, wherein the method operates in an aircraft navigation system; wherein the 3D location represents a location of an aircraft; wherein the 3D geometric region represents an air corridor or a portion thereof; and wherein the method additionally comprises determining when the aircraft enters or leaves the air corridor or portion thereof. ### Claim 12 (depends on 1) The computer-implemented method of claim 1, wherein the method operates in a video game; wherein the 3D location represents a location of a vehicle; wherein the 3D geometric region represents a physical object in the video game; and wherein the method additionally comprises determining when the vehicle collides with or is in danger of colliding with the physical object. ### Claim 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. ### Claim 14 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the 2D point-in-polygon (PIP) operation comprises, for one of the 2D geometric regions: projecting parallel rays from segment endpoints of the 2D geometric region onto a reference line to generate intersection points between the projected rays and the reference line; and storing in the index at least a subset of the projected rays and associated open line segments of the 2D geometric region; obtaining from the index a projected ray and an associated set of open line segments, the obtained projected ray corresponding to a ray projected from the translated 3D location onto the reference line; and counting the open line segments in the set. ### Claim 15 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein storing the subset of projected rays in the index includes maintaining a list of open line segments for every nth interval on the reference line; and wherein obtaining a projected ray and an associated set of open line segments includes obtaining a list of open line segments for a nearest nth interval on the reference line, and adjusting the list to account for intervening line segment openings and closings associated with intersection points located between the nearest nth interval and a relevant interval on the reference line corresponding to the ray projected from the 3D location onto the reference line, to produce a list of open line segments for the relevant interval. ### Claim 16 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein the reference line is an X-coordinate axis or a Y-coordinate axis. ### Claim 17 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein determining that the 3D location is enclosed by the 3D geometric region comprises, for each 2D geometric region determined to enclose the translated 3D location, counting intersections between a ray projected from the 3D location in a direction orthogonal to the reference plane and a corresponding face of the 3D geometric region. ### Claim 18 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the reference plane includes an X- and a Y-coordinate axis. ### Claim 19 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the translation of the 3D location onto the reference plane comprises setting a Z-coordinate for the 3D location to zero. ### Claim 20 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein translating each face of the 3D geometric region onto a reference plane comprises setting Z-coordinates for line segments of each face of the 3D geometric region. ### Claim 21 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the 3D geometric region comprises a weather model, a cell phone coverage map, or a sound model. ### Claim 22 (depends on 13) The non-transitory computer-readable storage medium of claim 13, the method additionally comprising obtaining the 3D location by: receiving a query to be processed, wherein the query is associated with the 3D geometric region; and using a late-binding schema generated from the query to retrieve the 3D location from a set of events containing previously gathered data. ### Claim 23 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the method operates in an aircraft navigation system; wherein the 3D location represents a location of an aircraft; wherein the 3D geometric region represents an air corridor or a portion thereof; and wherein the method additionally comprises determining when the aircraft enters or leaves the air corridor or portion thereof. ### Claim 24 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the method operates in a video game; wherein the 3D location represents a location of a vehicle; wherein the 3D geometric region represents a physical object in the video game; and wherein the method additionally comprises determining when the vehicle collides with or is in danger of colliding with the physical object. ### Claim 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. ### Claim 26 (depends on 25) The system of claim 25, wherein the display mechanism is configured to perform the 2D point-in-polygon (PIP) operation by, for one of the 2D geometric regions: projecting parallel rays from segment endpoints of the 2D geometric region onto a reference line to generate intersection points between the projected rays and the reference line; and storing in the index at least a subset of the projected rays and associated open line segments of the 2D geometric region; obtaining from the index a projected ray and an associated set of open line segments, the obtained projected ray corresponding to a ray projected from the translated 3D location onto the reference line; and counting the open line segments in the set. ### Claim 27 (depends on 26) The system of claim 26, wherein storing the subset of projected rays in the index includes maintaining a list of open line segments for every nth interval on the reference line; and wherein obtaining a projected ray and an associated set of open line segments includes obtaining a list of open line segments for a nearest nth interval on the reference line, and adjusting the list to account for intervening line segment openings and closings associated with intersection points located between the nearest nth interval and a relevant interval on the reference line corresponding to the ray projected from the 3D location onto the reference line, to produce a list of open line segments for the relevant interval. ### Claim 28 (depends on 26) The system of claim 26, wherein the reference line is an X-coordinate axis or a Y-coordinate axis. ### Claim 29 (depends on 25) The system of claim 25, wherein determining that the 3D location is enclosed by the 3D geometric region comprises, for each 2D geometric region determined to enclose the translated 3D location, counting intersections between a ray projected from the 3D location in a direction orthogonal to the reference plane and a corresponding face of the 3D geometric region. ### Claim 30 (depends on 25) The system of claim 25, wherein the reference plane includes an X- and a Y-coordinate axis.