Method and device for simplifying a complex path

摘要

The invention relates to a technical field of graphic image processing, especially to a technology for simplifying a complex path. The invention provides a method and a device for simplifying a complex path, to accomplish simplification of any complex path into a simple path of a region described by the complex path. The method for simplifying a complex path comprises: parsing the complex path into a vector linked-list consisted of linked monotonic vectors; dividing each vector in the vector linked-list into vector segments according to intersection points of the vector with other vectors in the vector linked-list; and extracting from all vector segments the vector segments located on a boundary of a region defined by the complex path, and connecting the extracted vector segments according to their location to obtain a simple path. According the method of the present application, a complex path can be simplified to a simplest path defining a region by utilizing node scanning process, such that operations on a vector level for a complex path can be realized.

主权项

1. A computer-implemented method for simplifying a complex path, the complex path comprises a plurality of vectors with self-intersection therebetween, the method comprising:
parsing, by a cumputer, the complex path into a vector linked-list of linked monotonic vectors; dividing, by the cumputer, each vector in the vector linked-list into vector segments according to intersection points of the vector with other vectors in the vector linked-list; and extracting, by the cumputer and from all vector segments, the vector segments located on a boundary of a region defined by the complex path, and connecting the extracted vector segments according to their locations to obtain a simple path, wherein the extracting includes: sequentially numbering all endpoints in order of their coordinate values in a first coordinate direction, and if there are endpoints with the same coordinate value in the first coordinate direction, numbering the endpoints with the same coordinate value in order of their coordinate values in a second coordinate direction orthogonal to the first coordinate direction; and sequentially extracting by number the vector segments located on the boundary of the region defined by the complex path from vector segments connected with each endpoint.