Simplifying a polygon

• US 8,508,533 B2
• Filed: 09/28/2011
• Issued: 08/13/2013
• Est. Priority Date: 09/28/2011
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Cervelli, Daniel P., Carrino, John A.
• Primary Examiner(s): Wu, Xiao M.
• Assistant Examiner(s): BUTTRAM, ALAN T
• Application Number:
  US13/247,986
• Publication Number:
  US 20130076732A1
• Time in Patent Office: 685 Days
• Field of Search: 345441-443, 345/472, 345/472.1
• US Class Current: 345/441
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H03M 7/3064 Segmenting

Abstract

Processes, machines, and computer-readable media are provided for expanding and simplifying a polygon or reducing and simplifying a polygon. Polygon expanding or reducing logic receives information that represents a polygon having a set of vertices. The polygon expanding or reducing logic determines another polygon having another set of vertices, such that the other polygon encompasses or is encompassed by the polygon, by determining, for each vertex of the set of vertices, a new set of vertices that are derived from the vertex and are at least a particular distance outside or inside the polygon. The vertex reducing logic determines whether an intermediate vertex is within the particular distance of a proposed segment between two other vertices of the other set of vertices, even though the intermediate vertex is not on the proposed segment, and, if so, removing the intermediate vertex from the other set of vertices.

Claims

1. A process comprising:

receiving, by one or more computing devices, first data representing a first polygon having a first set of vertices;

generating a resulting polygon at least in part by;

using polygon reducing logic of the one or more computing devices, causing determining a second polygon having a second set of vertices, such that the second polygon is encompassed by the first polygon, by determining, for each particular vertex in the first set of vertices, one or more new vertices that are determined from that particular vertex and are at least a particular distance inside the first polygon;

using vertex reducing logic of the one or more computing devices, causing determining, for an intermediate vertex of the second set of vertices, whether the intermediate vertex is within the particular distance of a proposed segment between two other vertices of the second set of vertices, wherein the intermediate vertex is not on the proposed segment;

using the vertex reducing logic, causing removing the intermediate vertex from the second set of vertices in response to determining that the intermediate vertex is within the particular distance of the proposed segment;

on one or more non-transitory computer-readable storage media, storing the resulting polygon in association with the first polygon, wherein the resulting polygon has fewer vertices than the first polygon.

2. The process of claim 1, wherein the one or more new vertices are a fixed distance away from the particular vertex, wherein the fixed distance is greater than the particular distance.

3. The process of claim 1, wherein the one or more new vertices include all those vertices, from a fixed number of possible vertices at fixed angles away from the particular vertex, that are inside the first polygon by at least the particular distance.

4. The process of claim 1, further comprising:

using the vertex reducing logic, causing determining, for a plurality of intermediate vertices of the second set of vertices, whether the intermediate vertices are within the particular distance of segments between other vertices of the second set of vertices;

using the vertex reducing logic, causing removing a subset of the plurality of intermediate vertices in response to determining that intermediate vertices from the subset of the plurality of intermediate vertices are within the particular distance of segments between other vertices of the second set of vertices.

5. The process of claim 1, wherein the proposed segment is a first proposed segment, further comprising recursively performing:

determining a third polygon having a third set of vertices, wherein the third set of vertices is encompassed by a prior second polygon having a prior second set of vertices, determining whether an intermediate vertex of the third set of vertices is within the particular distance of a second proposed segment between two other vertices of the third set of vertices, and removing the intermediate vertex from the third set of vertices in response to determining that the intermediate vertex is within the particular distance of the second proposed segment between the two other vertices of the third set of vertices.

6. The process of claim 5, comprising repeating the steps of determining the third polygon, determining whether the intermediate vertex is within the particular distance, and removing the intermediate vertex until the resulting polygon has fewer than a specified number of vertices.

7. The process of claim 6, further comprising:

receiving the specified number as user input;

causing display of the first polygon before receiving the specified number;

causing display of the resulting polygon in response to receiving the specified number as user input.

8. The process of claim 5, comprising repeating the steps of determining the third polygon, determining whether the intermediate vertex is within the particular distance, and removing the intermediate vertex to form the resulting polygon, further comprising:

causing receiving a command to be evaluated against the first polygon;

in response to receiving the command, causing evaluation of the command against the resulting polygon.

9. The process of claim 8, wherein the command is a search for data items outside of the first polygon, wherein causing evaluation of the command against the resulting polygon generates a resulting set of data items, the process further comprising causing determining that one or more data items in the resulting set of data items are inside of the first polygon and, in response, removing the one or more data items from the resulting set of data items.

10. The process of claim 1, wherein the polygon reducing logic comprises logic for performing a Minkowski subtraction shrinking process on the particular vertex and a radially symmetric polygon;

wherein the vertex reducing logic comprises logic for performing a Ramer-Douglas-Peucker vertex reducing process on the intermediate vertex and the two other vertices.

11. The process of claim 1, wherein the first polygon is on a three-dimensional surface, and wherein the particular distance is a distance along the three-dimensional surface.

12. The process of claim 1, wherein the first polygon is on a plane, and wherein the segment is a line segment.

13. The process of claim 12, further comprising causing determining the first polygon from another polygon on a three-dimensional surface by determining a projection from the three-dimensional surface onto the plane.

14. The process of claim 1, wherein the first polygon is a face of a first polyhedron, and wherein the second polygon is a corresponding face of a second polyhedron.

15. The process of claim 1, wherein the first polygon has a third set of vertices in addition to the first set of vertices, and wherein determining the second polygon is performed without determining, for any vertex in the third set of vertices, a new set of vertices that are at least a particular distance inside the first polygon.

16. One or more non-transitory computer-readable storage media storing instructions which, when executed by one or more processors, cause the one or more processors to perform:

receiving, by one or more computing devices, first data representing a first polygon having a first set of vertices;

generating a resulting polygon at least in part by;

using polygon reducing logic of the one or more computing devices, causing determining a second polygon having a second set of vertices, such that the second polygon is encompassed by the first polygon, by determining, for each particular vertex in the first set of vertices, one or more new vertices that are determined from that particular vertex and are at least a particular distance inside the first polygon;

using vertex reducing logic of the one or more computing devices, causing determining, for an intermediate vertex of the second set of vertices, whether the intermediate vertex is within the particular distance of a proposed segment between two other vertices of the second set of vertices, wherein the intermediate vertex is not on the proposed segment;

using the vertex reducing logic, causing removing the intermediate vertex from the second set of vertices in response to determining that the intermediate vertex is within the particular distance of the proposed segment;

on one or more non-transitory computer-readable storage media, storing the resulting polygon in association with the first polygon, wherein the resulting polygon has fewer vertices than the first polygon.

17. The media of claim 16, wherein the one or more new vertices are a fixed distance away from the particular vertex, wherein the fixed distance is greater than the particular distance.

18. The media of claim 16, wherein the one or more new vertices include all those vertices, from a fixed number of possible vertices at fixed angles away from the particular vertex, that are inside the first polygon by at least the particular distance.

19. The media of claim 16, further comprising instructions which when executed cause:

using the vertex reducing logic, causing determining, for a plurality of intermediate vertices of the second set of vertices, whether the intermediate vertices are within the particular distance of segments between other vertices of the second set of vertices;

using the vertex reducing logic, causing removing a subset of the plurality of intermediate vertices in response to determining that intermediate vertices from the subset of the plurality of intermediate vertices are within the particular distance of segments between other vertices of the second set of vertices.

20. The media of claim 16, wherein the proposed segment is a first proposed segment, further comprising instructions which when executed cause recursively performing:

determining a third polygon having a third set of vertices, wherein the third set of vertices is encompassed by a prior second polygon having a prior second set of vertices, determining whether an intermediate vertex of the third set of vertices is within the particular distance of a second proposed segment between two other vertices of the third set of vertices, and removing the intermediate vertex from the third set of vertices in response to determining that the intermediate vertex is within the particular distance of the second proposed segment between the two other vertices of the third set of vertices.

21. The media of claim 20, further comprising instructions which when executed cause repeating the determining the third polygon, determining whether the intermediate vertex is within the particular distance, and removing the intermediate vertex until the resulting polygon has fewer than a specified number of vertices.

22. The media of claim 19, further comprising instructions which when executed cause:

receiving the specified number as user input;

causing display of the first polygon before receiving the specified number;

causing display of the resulting polygon in response to receiving the specified number as user input.

23. The media of claim 20, further comprising instructions which when executed cause repeating the determining the third polygon, determining whether the intermediate vertex is within the particular distance, and removing the intermediate vertex to form the resulting polygon;

further comprising instructions which when executed cause receiving a command to be evaluated against the first polygon;

in response to receiving the command, causing evaluation of the command against the resulting polygon.

24. The media of claim 20, wherein the command is a search for data items outside of the first polygon, wherein causing evaluation of the command against the resulting polygon generates a resulting set of data items, the media further comprising instructions which when executed cause determining that one or more data items in the resulting set of data items are inside of the first polygon and, in response, removing the one or more data items from the resulting set of data items.

25. The media of claim 20, wherein the polygon reducing logic comprises logic for performing a Minkowski subtraction shrinking process on the particular vertex and a radially symmetric polygon;

wherein the vertex reducing logic comprises logic for performing a Ramer-Douglas-Peucker vertex reducing process on the intermediate vertex and the two other vertices.

26. The media of claim 20, wherein the first polygon is on a three-dimensional surface, and wherein the particular distance is a distance along the three-dimensional surface.

27. The media of claim 20, wherein the first polygon is on a plane, and wherein the segment is a line segment.

28. The media of claim 27, further comprising instructions which when executed cause determining the first polygon from another polygon on a three-dimensional surface by determining a projection from the three-dimensional surface onto the plane.

29. The media of claim 20, wherein the first polygon is a face of a first polyhedron, and wherein the second polygon is a corresponding face of a second polyhedron.

30. The media of claim 20, wherein the first polygon has a third set of vertices in addition to the first set of vertices, and wherein determining the second polygon is performed without determining, for any vertex in the third set of vertices, a new set of vertices that are at least a particular distance inside the first polygon.