A platform for research: civil engineering, architecture and urbanism
A platform for research: civil engineering, architecture and urbanism
Comparison of region approximation techniques based on Delaunay triangulations and Voronoi diagrams
AbstractRegion approximation techniques based on constructions from sample data points, i.e. points whose position is known and which are known to be inside or outside the region of interest, can be advantageous in a variety of applications. This paper compares two different constructions and presents results from a Monte Carlo model that shows that the construction based on mid points of edges in a Delaunay triangulation produces the lowest errors. These errors are some 10% less than those produced by the Voronoi diagram construction which appears to be more widely used at present. A consideration of the basic geometries of the different constructions leads to an expression for approximating the expected error in the case of a random point distribution. The expression takes the formwhere S is the average point spacing, lo is the length of region boundary being approximated (the optimum length for the construction), and lc the length of the constructed line approximating the boundary. The constant kd accounts for the non-uniform spacing of the points in the distribution and has a value of about 1.1 for a random distribution. Predictions from this expression agree well with the results from the Monte Carlo model.The case of finite as well as infinite radius of curvature is considered and some possible improvements on the constructions modelled are suggested.
Comparison of region approximation techniques based on Delaunay triangulations and Voronoi diagrams
AbstractRegion approximation techniques based on constructions from sample data points, i.e. points whose position is known and which are known to be inside or outside the region of interest, can be advantageous in a variety of applications. This paper compares two different constructions and presents results from a Monte Carlo model that shows that the construction based on mid points of edges in a Delaunay triangulation produces the lowest errors. These errors are some 10% less than those produced by the Voronoi diagram construction which appears to be more widely used at present. A consideration of the basic geometries of the different constructions leads to an expression for approximating the expected error in the case of a random point distribution. The expression takes the formwhere S is the average point spacing, lo is the length of region boundary being approximated (the optimum length for the construction), and lc the length of the constructed line approximating the boundary. The constant kd accounts for the non-uniform spacing of the points in the distribution and has a value of about 1.1 for a random distribution. Predictions from this expression agree well with the results from the Monte Carlo model.The case of finite as well as infinite radius of curvature is considered and some possible improvements on the constructions modelled are suggested.
Comparison of region approximation techniques based on Delaunay triangulations and Voronoi diagrams
Barclay, Michael (author) / Galton, Antony (author)
Computers, Environments and Urban Systems ; 32 ; 261-267
2008-01-01
7 pages
Article (Journal)
Electronic Resource
English
Region , Approximation , Error , Delaunay , Voronoi
Comparison of region approximation techniques based on Delaunay triangulations and Voronoi diagrams
| British Library Conference Proceedings | 2008
Comparison of region approximation techniques based on Delaunay triangulations and Voronoi diagrams
| Online Contents | 2008
Comparison of region approximation techniques based on Delaunay triangulations and Voronoi diagrams
| Online Contents | 2008
Incremental Planar Delaunay Tessellation and Voronoi Diagrams Constructions in Rectilinear Metric
| British Library Conference Proceedings | 1995
Research Papers - Delaunay Triangulations and Stereographic Projections
| Online Contents | 1999