Three-dimensional point-in-polygon operation to facilitate displaying three-dimensional structures

• US 9,607,414 B2
• Filed: 04/30/2015
• Issued: 03/28/2017
• Est. Priority Date: 01/27/2015
• Status: Active Grant

• Current Assignee: Splunk Inc. (Cisco Systems, Inc.)
• Original Assignee: Splunk Inc. (Cisco Systems, Inc.)
• Inventors: Hendrey, Geoffrey R.
• Primary Examiner(s): Mushambo, Martin
• Application Number:
  US14/700,685
• Publication Number:
  US 20160217153A1
• Time in Patent Office: 698 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: A63F 13/537 using indicators, e.g. showing the condition of a game character on screen
• CPC Class Codes: A63F 13/577 using determination of contact between game characters or objects, e.g. to avoid collision between virtual racing cars
• CPC Class Codes: B64D 43/00 Arrangements or adaptations of instruments arrangements of cameras B64D47/08; aeronautical measuring instruments per se G01C
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06T 2210/21 Collision detection, intersection

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

1. A computer-implemented method for generating a visual representation of a set of polyhedra in a three-dimensional space, comprising:

receiving a query to be processed, wherein the query is associated with the set of polyhedra;

using a late-binding schema generated from the query to retrieve a set of one or more data points from a set of events containing previously gathered data;

projecting polygons that define faces of each polyhedron in the set of polyhedra onto projected polygons in a reference plane;

for each data point in the set of one or more data points to be processed to determine what polyhedra the data point falls into,

projecting the data point onto a projected data point in the reference plane,

performing a two-dimensional point-in-polygon (PIP) operation in the reference plane to determine which projected polygons the projected data point falls into, and

for each projected polygon that the projected data point falls into, performing a three-dimensional crossing number (CN) operation to

identify zero or more polyhedra that the data point falls into;

generating a visual representation of the set of polyhedra, wherein the visual representation of each polyhedron is affected by data points that fall into the polyhedron; and

presenting the visual representation to a user.

2. The computer-implemented method of claim 1,

wherein each polygon, which defines a face of a polyhedron in the set of polyhedra, comprises line segments that define a border of the polygon, and wherein each line segment is defined by three-dimensional coordinates for endpoints of the line segment;

and

wherein performing the two-dimensional point-in-polygon (PIP) operation for each projected data point in the reference plane comprises;

projecting rays in the reference plane from endpoints of projected line segments that comprise the projected polygons onto a reference line in the reference plane, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line;

for each interval between pairs of consecutive intersection points on the reference line, keeping track of open line segments that project onto the interval;

identifying a relevant interval on the reference line that the projected data point projects onto; and

performing a two-dimensional crossing number (CN) operation by counting intersections between a projected ray from the projected data point and open line segments associated with the relevant interval to identify zero or more projected polygons that the projected data point falls into in the reference plane.

3. The computer-implemented method of claim 1, wherein performing the three-dimensional CN operation includes 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 the zero or more polyhedra that the data point falls into.

4. The computer-implemented method of claim 1, wherein the reference plane is a plane that includes an X- and a Y-coordinate axis.

5. The computer-implemented method of claim 1, wherein the reference line is an X-coordinate axis.

6. The computer-implemented method of claim 1, wherein the reference line is a Y-coordinate axis.

7. The computer-implemented method of claim 1, wherein projecting the data point onto the projected data point in the reference plane includes setting a Z-coordinate for the data point to zero.

8. The computer-implemented method of claim 1, wherein projecting polygons in the set of polyhedra onto projected polygons in the reference plane includes setting Z-coordinates for line segments that comprise the set of polyhedra to zero.

9. The computer-implemented method of claim 1, wherein generating the visual representation for the set of polyhedra includes one of:

generating a visual representation for a computer game that includes the set of polyhedra; and

generating a visualization for a medical-imaging system that includes the set of polyhedra.

10. The computer-implemented method of claim 1,

wherein the method operates in an aircraft navigation system;

wherein each data point represents an aircraft;

wherein each polyhedron represents an air corridor or a portion of an air corridor; and

wherein the method additionally determines when each aircraft enters or leaves an air corridor.

11. The computer-implemented method of claim 1,

wherein the method operates in a video game;

wherein each data point represents a vehicle that can be manned or unmanned;

wherein each polyhedron represents a physical object in the video game; and

wherein the method additionally determines when each vehicle collides with or is in danger of colliding with a physical object.

12. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for generating a visual representation of a set of polyhedra in a three-dimensional space, the storage medium including:

instructions for receiving a query to be processed, wherein the query is associated with the set of polyhedra;

instructions for using a late-binding schema generated from the query to retrieve a set of one or more data points from a set of events containing previously gathered data;

instructions for projecting polygons that define faces of each polyhedron in the set of polyhedra onto projected polygons in a reference plane;

for each data point in the set of one or more data points to be processed to determine what polyhedra the data point falls into,

instructions for projecting the data point onto a projected data point in the reference plane,

performing a two-dimensional point-in-polygon (PIP) operation in the reference plane to determine which projected polygons the projected data point falls into, and

for each projected polygon that the projected data point falls into, instructions for performing a three-dimensional crossing number (CN) operation to identify zero or more polyhedra that the data point falls into;

instructions for generating a visual representation of the set of polyhedra, wherein the visual representation of each polyhedron is affected by data points that fall into the polyhedron; and

instructions for presenting the visual representation to a user.

13. The non-transitory computer-readable storage medium of claim 12,

wherein each polygon, which defines a face of a polyhedron in the set of polyhedra, comprises line segments that define a border of the polygon, and wherein each line segment is defined by three-dimensional coordinates for endpoints of the line segment;

and

wherein the instructions for performing the two-dimensional point-in-polygon (PIP) operation for the projected data point in the reference plane comprise;

instructions for projecting rays in the reference plane from endpoints of projected line segments that comprise the projected polygons onto a reference line in the reference plane, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line;

for each interval between pairs of consecutive intersection points on the reference line, instructions for keeping track of open line segments that project onto the interval;

instructions for identifying a relevant interval on the reference line that the projected data point projects onto; and

instructions for performing a two-dimensional crossing number (CN) operation by counting intersections between a projected ray from the projected data point and open line segments associated with the relevant interval to identify zero or more projected polygons that the projected data point falls into in the reference plane.

14. The non-transitory computer-readable storage medium of claim 12, wherein the instructions for performing the three-dimensional CN operation includes instructions for 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 the zero or more polyhedra that the data point falls into.

15. The non-transitory computer-readable storage medium of claim 12, wherein the reference plane is a plane that includes an X- and a Y-coordinate axis.

16. The non-transitory computer-readable storage medium of claim 12, wherein the reference line is an X-coordinate axis.

17. The non-transitory computer-readable storage medium of claim 12, wherein the reference line is a Y-coordinate axis.

18. The non-transitory computer-readable storage medium of claim 12, wherein the instructions for projecting the data point onto the projected data point in the reference plane include instructions for setting a Z-coordinate for the data point to zero.

19. The non-transitory computer-readable storage medium of claim 12, wherein the instructions for projecting polygons in the set of polyhedra onto projected polygons in the reference plane include instructions for setting Z-coordinates for line segments that comprise the set of polyhedra to zero.

20. The non-transitory computer-readable storage medium of claim 12, wherein the instructions for generating the visual representation for the set of polyhedra include one of:

instructions for generating a visual representation for a computer game that includes the set of polyhedra; and

instructions for generating a visualization for a medical-imaging system that includes the set of polyhedra.

21. The non-transitory computer-readable storage medium of claim 12,

wherein the instructions operate in an aircraft navigation system;

wherein each data point represents an aircraft;

wherein each polyhedron represents an air corridor or a portion of an air corridor; and

wherein the method additionally determines when each aircraft enters or leaves an air corridor.

22. The non-transitory computer-readable storage medium of claim 12,

wherein the instructions operate in a video game;

wherein each data point represents a vehicle that can be manned or unmanned;

wherein each polyhedron represents a physical object in the video game; and

wherein the method additionally determines when each vehicle collides with or is in danger of colliding with a physical object.

23. A system that generates a visual representation of a set of polyhedra in a three-dimensional space, comprising:

at least one processor and at least one associated memory; and

a display mechanism that executes on the at least one processor, wherein during operation, the display mechanism;

receives a query to be processed, wherein the query is associated with the set of polyhedra;

uses a late-binding schema generated from the query to retrieve a set of one or more data points from a set of events containing previously gathered data;

projects polygons that define faces of each polyhedron in the set of polyhedra onto projected polygons in a reference plane;

for each data point in the set of one or more data points to be processed to determine what polyhedra the data point falls into,

projects the data point onto a projected data point in the reference plane,

performs a two-dimensional point-in-polygon (PIP) operation in the reference plane to determine which projected polygons the projected data point falls into, and

for each projected polygon that the projected data point falls into,

performs a three-dimensional crossing number (CN) operation to identify zero or more polyhedra that the data point falls into;

generates a visual representation of the set of polyhedra, wherein the visual representation of each polyhedron is affected by data points that fall into the polyhedron; and

presents the visual representation to a user.

24. The system of claim 23,

wherein each polygon, which defines a face of a polyhedron in the set of polyhedra, comprises line segments that define a border of the polygon, and wherein each line segment is defined by three-dimensional coordinates for endpoints of the line segment;

and

wherein while performing the two-dimensional point-in-polygon (PIP) problem for the projected data point in the reference plane, the system;

projects rays in the reference plane from endpoints of projected line segments that comprise the projected polygons onto a reference line in the reference plane, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line;

for each interval between pairs of consecutive intersection points on the reference line, keeps track of open line segments that project onto the interval;

identifies a relevant interval on the reference line that the projected data point projects onto; and

performs a two-dimensional crossing number (CN) operation by counting intersections between a projected ray from the projected data point and open line segments associated with the relevant interval to Identify zero or more projected polygons that the projected data point falls into in the reference plane.

25. The system of claim 23, wherein while performing the three-dimensional CN operation, the system counts 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 the zero or more polyhedra that the data point falls into.

26. The system of claim 23, wherein the reference plane is a plane that includes an X- and a Y-coordinate axis.

27. The system of claim 23, wherein the reference line is an X-coordinate axis.

28. The system of claim 23, wherein the reference line is a Y-coordinate axis.

29. The system of claim 23, wherein while projecting the data point onto the projected data point in the reference plane, the display mechanism sets a Z-coordinate for the data point to zero.

30. The system of claim 23, wherein while projecting polygons in the set of polyhedra onto projected polygons in the reference plane, the display mechanism sets Z-coordinates for line segments that comprise the set of polyhedral to zero.

31. The system of claim 23, wherein while generating the visual representation for the set of polyhedra, the display mechanism does one of the following:

generates a visual representation for a computer game that includes the set of polyhedra; and

generates a visualization for a medical-imaging system that includes the set of polyhedra.

32. The system of claim 23,

wherein the system is part of an aircraft navigation system;

wherein each data point represents an aircraft;

wherein each polyhedron represents an air corridor or a portion of an air corridor; and

wherein the system additionally determines when each aircraft enters or leaves an air corridor.

33. The system of claim 23,

wherein the system is part of a video game;

wherein each data point represents a vehicle that can be manned or unmanned;

wherein each polyhedron represents a physical object in the video game; and

wherein the system additionally determines when each vehicle collides with or is in danger of colliding with a physical object.