## Curve ReconstructionThe function discussed here is a direct application of Voronoi diagrams.
## The AlgorithmThe algorithm proceeds in three steps:- Construct the Voronoi diagram
`VD` of the points in`S` . - Construct a set
`L=SUV` , where`V` consists of all proper vertices of`VD` . - Construct the Delaunay triangulation
`DT` of`L` and make`G` the graph of all edges in`DT` that connect points in`L` .
## The Implementationvoid CRUST(const list<POINT> S,GRAPH<POINT,int> G) { list<POINT> L=S; map<POINT,bool> voronoi_vertex(false); GRAPH<CIRCLE,POINT> VD; VORONOI(L,VD); node v; forall_nodes(v,VD) { //add Voronoi vertices and mark them if (VD.outdeg(v)<2) continue; POINT p=VD[v].center(); voronoi_vertex[p]=true; L.append(p); } DELAUNAY_TRIANG(L,G); forall_nodes(v,G) if (voronoi_vertex[G[v]]) G.del_node(v); } ## Example Program for Curve ReconstructionThe following program uses CRUST to reconstruct the curve corrsponding
to the points in #include <LEDA/core/list.h> #include <LEDA/geo/point.h> #include <LEDA/graphics/window.h> #include <LEDA/geo/geo_alg.h> using namespace leda; int main() { list<point> L; L.append(point(0,-30)); L.append(point(0,15)); L.append(point(10,-20)); L.append(point(5,20)); L.append(point(20,-10)); L.append(point(15,30)); L.append(point(25,30)); L.append(point(30,0)); L.append(point(30,20)); L.append(point(-10,-20)); L.append(point(-5,20)); L.append(point(-20,-10)); L.append(point(-15,30)); L.append(point(-25,30)); L.append(point(-30,0)); L.append(point(-30,20)); GRAPH<point,int> G; CRUST(L,G); window W; W.init(-50,50,-50); W.open(); W.display(); W.set_node_width(2); W.set_line_width(2); point p; forall(p,L) W.draw_filled_node(p.to_point()); edge e; forall_edges(e,G) { point p=G[G.source(e)]; point q=G[G.target(e)]; W.draw_segment(p,q,red); } W.read_mouse(); W.screenshot("crust"); return 0; } |
## See also:
## Manual Entries |

Please send any suggestions, comments or questions to leda@algorithmic-solutions.com

© Copyright 2001-2003, Algorithmic Solutions Software GmbH