Method and device for simplifying a complex path
View Patent ↗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.
2. The method according to claim 1 , wherein the monotonic vectors include straight-line vectors and/or monotonic curve vectors.
3. The method according to claim 2 , further comprising:
determining, by the cumputer, intersection points of each vector with other vectors in the vector linked-list, wherein the determining includes:
obtaining positional information of endpoints of the vectors in the vector linked-list;
sorting all the endpoints according to their positional information and obtaining a list of vectors' endpoints which are arranged in order; and
determining intersecting vectors for each vector according to the list of vectors' endpoints, and evaluating intersection points between each vector and its intersecting vectors.
4. The method according to claim 3 , wherein
the positional information of the endpoints includes coordinate values of the endpoints in the first and second orthogonal coordinate directions and the endpoints' relative position in a vector; and
the sorting all the endpoints according to their positional information includes:
sorting all the endpoints according to their coordinate values in one of the first and second coordinate directions; and
if there are endpoints with the same coordinate value in the one coordinate direction, sorting the endpoints with the same coordinate value according to their relative position in the vector.
5. The method according to claim 4 , wherein the sorting all the endpoints according to their positional information further includes:
if there are endpoints with the same coordinate value and same relative position in vectors, sorting the endpoints with the same coordinate value and same relative position according to the sequence of appearance of vectors to which the endpoints belong.
6. The method according to claim 5 , wherein the first coordinate direction is the X-axis coordinate direction.
7. The method according to claim 6 , wherein the vector segments located on the boundary of the region defined by the complex path are extracted from vector segments connected with a right side of each endpoint.
8. The method according to claim 5 , further comprising:
determining, by the cumputer, whether a vector segment is located on the boundary of the region or not, wherein the determining includes:
determining between two regions divided by the vector segment whether one of the two regions is an inner portion inside the region defined by the complex path and the other of the two regions is an outer portion outside the region defined by the complex path; if yes, the vector segment is determined to be located on the boundary of the region defined by the complex path.
9. The method according to claim 1 , further comprising:
determining, by the cumputer, intersection points of each vector with other vectors in the vector linked-list, wherein the determining includes:
obtaining positional information of endpoints of the vectors in the vector linked-list;
sorting all the endpoints according to their positional information and obtaining a list of vectors' endpoints which are arranged in order; and
determining intersecting vectors for each vector according to the list of vectors' endpoints, and evaluating intersection points between each vector and its intersecting vectors.
10. The method according to claim 3 , wherein
the positional information of the endpoints includes coordinate values of the endpoints in the first and second coordinate directions and the endpoints' relative position in a vector; and
the sorting all the endpoints according to their positional information includes:
sorting all the endpoints according to their coordinate values in one of the first and second coordinate directions; and
if there are endpoints with the same coordinate value in the one coordinate direction, sorting the endpoints with the same coordinate value according to their relative position in the vector.
11. The method according to claim 10 , wherein the sorting all the endpoints according to their positional information further includes:
if there are endpoints with the same coordinate value and same relative position in vectors, sorting the endpoints with the same coordinate value and same relative position according to the sequence of appearance of vectors to which the endpoints belong.
12. The method according to claim 1 , wherein the first coordinate direction is the X-axis coordinate direction.
13. The method according to claim 12 , wherein the vector segments located on the boundary of the region defined by the complex path are extracted from vector segments connected with a right side of each endpoint.
14. The method according to claim 1 , further comprising:
determining, by the cumputer, whether a vector segment is located on the boundary of the region or not, wherein the determining includes:
determining between two regions divided by the vector segment whether one of the two regions is an inner portion inside the region defined by the complex path and the other of the two regions is an outer portion outside the region defined by the complex path; and if yes, the vector segment is determined to be located on the boundary of the region defined by the complex path.
15. A device for simplifying a complex path, comprising:
parsing unit, configured to parse a complex path into a vector linked-list of linked monotonic vectors;
dividing unit, configured to divide 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
a processing unit, configured to extract vector segments located on a boundary of a region defined by the complex path from all the vector segments, and connect the extracted vector segments according to their locations to obtain a simple path,
wherein the processing unit is configured to exact the vector segments by:
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.