Name
Title | ||
|---|---|---|
Polyline approach for approximating Hausdorff distance between planar free-form curves |
Abstract | ||
|---|---|---|
This paper presents a practical polyline approach for approximating the Hausdorff distance between planar free-form curves. After the input curves are approximated with polylines using the recursively splitting method, the precise Hausdorff distance between polylines is computed as the approximation of the Hausdorff distance between free-form curves, and the error of the approximation is controllable. The computation of the Hausdorff distance between polylines is based on an incremental algorithm that computes the directed Hausdorff distance from a line segment to a polyline. Furthermore, not every segment on polylines contributes to the final Hausdorff distance. Based on the bound properties of the Hausdorff distance and the continuity of polylines, two pruning strategies are applied in order to prune useless segments. The R-Tree structure is employed as well to accelerate the pruning process. We experimented on Bezier curves, B-Spline curves and NURBS curves respectively with our algorithm, and there are 95% segments pruned on approximating polylines in average. Two comparisons are also presented: One is with an algorithm computing the directed Hausdorff distance on polylines by building Voronoi diagram of segments. The other comparison is with equation solving and pruning methods for computing the Hausdorff distance between free-form curves. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.cad.2011.02.008 | Computer-Aided Design |
Keywords | Field | DocType |
pruning method,hausdorff distance,free-form curves,final hausdorff distance,pruning strategy,free-form curve,approximating hausdorff distance,incremental algorithm,precise hausdorff distance,polyline approach,polylines,planar free-form curve,approximating polylines,pruning process,pruning,voronoi diagram,tree structure,bezier curve | Hausdorff dimension,Line segment,Combinatorics,Equation solving,Planar,Bézier curve,Hausdorff distance,Voronoi diagram,Mathematics,Computation | Journal |
Volume | Issue | ISSN |
43 | 6 | Computer-Aided Design |
Citations | PageRank | References |
13 | 0.61 | 24 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yan-Bing Bai | 1 | 13 | 2.64 |
| Jun-hai Yong | 2 | 620 | 61.47 |
| Chang-Yuan Liu | 3 | 13 | 0.61 |
| Xiao-Ming Liu | 4 | 31 | 1.62 |
| Yu Meng | 5 | 13 | 0.61 |