| 摘要 |
Embodiments of the invention obtain dual points by examining the intersection between each line and a perpendicular projection from the line to a point of origin. The dual points are sorted in accordance with a modified quadtree or octtree. The drawing is recursively broken up into equal subdivisions until the maximum allowed number of points for a subdivision has been reached or until the size of the subdivision is less than a tolerance value. Once the number of points in a subdivision is less than the maximum allowed number of points, the points are individually compared to each other. If the subdivision is less than a tolerance value, the subdivision is small enough such that all of the lines within the subdivision are coincident. If the number of points is greater than the maximum allowed number of points and the subdivision is larger than the tolerance, the area is recursively subdivided. If two or more dual points are in a subdivision, to determine if the lines represented are coincident, a tolerance value is compared to the distance between the two dual points. If the distance is less than (or equal to) the tolerance value, the lines are coincident. If the distance is greater than the tolerance value, the lines are not coincident. The tolerance value may be obtained by multiplying an angular tolerance by the distance from the origin to the center of the subdivision. If the lines are parallel, a parallel distance tolerance may be utilized in the comparison.
|
