Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Curve Reconstruction

## Curve Reconstruction

The function discussed here is a direct application of Voronoi diagrams.

### What is a Curve Reconstruction?

We want to reconstruct a curve from a set of sample points . Let `F` be a smooth curve in the plane and let `S` be a finite set of sample points from `F`. A polygonal reconstruction of `F` is a graph that connects every pair of samples adjacent along `F`, and no others.

The algorithm CRUST described below takes a list S of points and returns a graph `G`. The graph `G` is guaranteed to be a polygonal reconstruction of `F` if `F` is sufficiently densely sampled by `S`.

Result of CRUST for a set of (non-random) points. The picture is a screenshot from the program below.

### The Algorithm

The algorithm proceeds in three steps:
1. Construct the Voronoi diagram `VD` of the points in `S`.
2. Construct a set `L=SUV`, where `V` consists of all proper vertices of `VD`.
3. Construct the Delaunay triangulation `DT` of `L` and make `G` the graph of all edges in `DT` that connect points in `L`.

### The Implementation

```void 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 Reconstruction

The following program uses CRUST to reconstruct the curve corrsponding to the points in `L` and uses a window to display the result.

```#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.screenshot("crust");

return 0;
}	   ```

Delaunay Triangulations

Data Types for 2-D Geometry

Linear Lists

Writing Kernel Independent Code

Windows and Panels

Extremal Circles

Minimum Annuli

Geometry Algorithms

Geometry

GeoWin

### Manual Entries

Manual Page of Geometry Algorithms