LEDA Guide: Curve Reconstruction

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:

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 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.read_mouse();
  W.screenshot("crust");

  return 0;
}

Manual Entries

Manual Page of Geometry Algorithms