Patent ID: 8717365
Filing Date: 2014-05-06
Classification: G06T

Abstract:
1. A method, comprising: receiving data that describes a polyline having a first endpoint, a second endpoint, and a plurality of intermediate vertices, each of the intermediate vertices lying between the first endpoint and the second endpoint; drawing an estimation line segment between the first endpoint and the second endpoint; identifying, as a pivot vertex, an intermediate vertex from the plurality of intermediate vertices that is a greatest distance from the estimation line segment; calculating a flatness ratio by dividing a distance of the pivot vertex from the estimation line segment by a length of the estimation line segment; comparing, in a computer, the flatness ratio to a predetermined threshold value; and if the flatness ratio does not exceed the predetermined threshold value, discarding the intermediate vertices, thereby modifying the polyline: comparing the distance of the pivot vertex from the estimation line segment to a predetermined distance value; and if the distance of the pivot vertex from the estimation line segment does not exceed the predetermined distance value and if the flatness ratio does not exceed the predetermined threshold value, discarding the intermediate vertices; if the distance of the pivot vertex from the estimation line segment exceeds the predetermined distance value or if the flatness ratio exceeds the predetermined threshold value, splitting the polyline into a second polyline and a third polyline, the second polyline having as endpoints the first endpoint and the pivot vertex, and the third polyline having as endpoints the pivot vertex and the second endpoint; determining if the second polyline has vertices in addition to the first endpoint and the pivot vertex; if the second polyline has vertices in addition to the first endpoint and the pivot vertex, drawing a second estimation line between the first endpoint and the pivot vertex; identifying, as a second pivot vertex, an intermediate vertex from the plurality of intermediate vertices that is a greatest distance from the second estimation line segment; calculating a second flatness ratio by dividing a distance of the second pivot vertex from the second estimation line segment by a length of the second estimation line segment; comparing, in a computer, the second flatness ratio to the predetermined threshold value; and if the second flatness ratio does not exceed the predetermined threshold value, discarding the second pivot vertex and intermediate vertices, if any, between the first endpoint and the pivot vertex; if the third polyline has vertices in addition to the pivot vertex and the second endpoint, drawing a third estimation line between the pivot vertex and the second endpoint; identifying, as a third pivot vertex, an intermediate vertex from the plurality of intermediate vertices that is a greatest distance from the third estimation line segment; calculating a third flatness ratio by dividing a distance of the third pivot vertex from the third estimation line segment by a length of the third estimation line segment; comparing, in a computer, the third flatness ratio to the predetermined threshold value; and if the third flatness ratio does not exceed the predetermined threshold value, discarding the third pivot vertex and intermediate vertices, if any, between the pivot vertex and the second endpoint.