Polygon simplification

Patent metadata

Field	Value
Publication number	US-9721364-B2
Application number	US-201414325236-A
Country	US
Kind code	B2
Filing date	Jul 7, 2014
Priority date	Jul 7, 2014
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

Abstract

Polygons can be simplified from an original, higher resolution to a simplified, lower resolution such that the simplified versions of the polygons do not introduce errors and also do not render boundaries shared with other polygons invalid.

First claim

What is claimed is:

1. A computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:
identifying a first of a plurality of original polygons represented in a spatial database at a first level of resolution that is to be projected within a computer-rendered image at a second level of resolution that is coarser than the first level of resolution, the second level of resolution comprising a simplified resolution pixel size;
decomposing the first original polygon internally into a sequence of a plurality of paths, each of the plurality of paths connecting two points;
generating, based at least on the decomposing of the first original polygon, a corresponding first simplified polygon, the generating comprising:
omitting, from the first original polygon, a first point, when the first point and a second point connected to the first point by one of the plurality of paths in the first original polygon occupy a same pixel of the simplified resolution pixel size;
increasing a local resolution of at least one path in the first simplified polygon comprising the second point, when the omitting of the first point results in an error;
validating the first simplified polygon, the validating comprising verifying that any boundaries of the first simplified polygon that are shared with one or more adjacent polygons are rendered at a same scale in both the first simplified polygon and the one or more adjacent polygons; and
storing, in the spatial database, the first simplified polygon, the storing of the first simplified polygon comprising storing, at the spatial database, a subset of the plurality of paths comprising the first original polygon.

2. The computer program product of claim 1 , wherein the verifying comprises:
determining that the at least path in the first simplified polygon corresponds to a shared boundary with the one or more adjacent polygons, the shared boundary having a lower resolution than the increased local resolution of the at least one path; and
increasing the lower resolution of the shared boundary to match the increased local resolution of the at least on path.

3. The computer program product of claim 2 , wherein the verifying is based at least on an inverse mapping of between the plurality of paths in the first simplified polygons and paths in the one or more adjacent polygons.

4. The computer program product of claim 1 , wherein the error comprises an error in a circumference of the first simplified polygon relative to the first original polygon.

5. The computer program product of claim 1 , wherein the error comprises an error in an area of the first simplified polygon relative to the first original polygon.

6. The computer program product of claim 1 , wherein the error comprises at least one path in the first simplified polygon being zero and/or self-intersecting.

7. A system comprising:
computer hardware configured to perform operations comprising:
identifying a first of a plurality of original polygons represented in a spatial database at a first level of resolution that is to be projected within a computer-rendered image at a second level of resolution that is coarser than the first level of resolution, the second level of resolution comprising a simplified resolution pixel size;
decomposing the first original polygon internally into a sequence of a plurality of paths, each of the plurality of paths connecting two points;
generating, based at least on the decomposing of the first original polygon, a corresponding first simplified polygon, the generating comprising:
omitting, from the first original polygon, a first point, when the first point and a second point connected to the first point by one of the plurality of paths in the first original polygon occupy a same pixel of the simplified resolution pixel size;
increasing a local resolution of at least one path in the first simplified polygon comprising the second point, when the omitting of the first point results in an error; and
validating the first simplified polygon, the validating comprising verifying that any boundaries of the first simplified polygon that are shared with one or more adjacent polygons are rendered at a same scale in both the first simplified polygon and the one or more adjacent polygons; and

storing, in the spatial database, the first simplified polygon, the storing of the first simplified polygon comprising storing, at the spatial database, a subset of the plurality of paths comprising the first original polygon.

8. The system of claim 7 , wherein the verifying comprises:
determining that the at least path in the first simplified polygon corresponds to a shared boundary with the one or more adjacent polygons, the shared boundary having a lower resolution than the increased local resolution of the at least one path; and
increasing the lower resolution of the shared boundary to match the increased local resolution of the at least on path.

9. The system of claim 8 , wherein the verifying is based at least on an inverse mapping of between the plurality of paths in the first simplified polygons and paths in the one or more adjacent-polygons.

10. The system of claim 7 , wherein the error comprises an error in a circumference of the first simplified polygon relative to the first original polygon.

11. The system of claim 7 , wherein the error comprises an error in an area of the first simplified polygon relative to the first original polygon.

12. The system of claim 7 , wherein the error-comprises the at least one path in the first simplified polygon being zero and/or self-intersecting.

13. The system of claim 7 , wherein the computer hardware comprises:
a programmable processor; and
a machine-readable medium comprising instructions that, when executed by the programmable processor, cause the programmable processor to perform at least some of the operations.

14. A computer-implemented method, comprising:
identifying a first of a plurality of original polygons represented in a spatial database at a first level of resolution that is to be projected within a computer-rendered image at a second level of resolution that is coarser than the first level of resolution, the second level of resolution comprising a simplified resolution pixel size;
decomposing the first original polygon internally into a sequence of a plurality of paths, each of the plurality of paths connecting two points;
generating, based at least on the decomposing of the first original polygon, a corresponding first simplified polygon, the generating comprising:
omitting, from the first original polygon, a first point, when the first point and a second point connected to the first point by one of the plurality of paths in the first original polygon occupy a same pixel of the simplified resolution pixel size;
increasing a local resolution of at least one path in the first simplified polygon comprising the second point, when the omitting of the first point results in an error; and
validating the first simplified polygon, the validating comprising verifying that any boundaries of the first simplified polygon that are shared with one or more adjacent polygons are rendered at a same scale in both the first simplified polygon and the one or more adjacent polygons; and

storing, in the spatial database, the first simplified polygon, the storing of the first simplified polygon comprising storing, at the spatial database, a subset of the plurality of paths comprising the first original polygon.

Assignees

• Kazmaier Gerrit Simon
• Gildhoff Hinnerk
• Volker Lars
• Grouisborn Tim
• Sap Se

Inventors

• Kazmaier Gerrit Simon
• Gildhoff Hinnerk
• Volker Lars
• Grouisborn Tim

Classifications

• G06T11/23 Primary

  using straight lines or curves · CPC title

• G06T11/203 Primary

  Physics · mapped topic

• G06F17/30

  Physics · mapped topic

• G06F16/51

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/00

  Information retrieval; Database structures therefor; File system structures therefor · CPC title