PointsNBoxes

1. Introduction

Reconstructing a curve from a discrete set of sample points is a classical problem, often called the connect-the-dots problem. It, together with its twin problem of surface reconstruction, has long been of interest. Both problems arise in various real situations.

Recently, there has been particular activity in the computational geometry community relating to curve and surface reconstruction. Most of the approaches, and accompanying software, are based on constructing Delaunay triangulations of the sample points and choosing edges.

The PointsNBoxes program is the result of a new approach to curve reconstruction developed by Sumanta Guha and implemented by Paula Josiah, Anoop Mittal and Son Dinh Tran, when the group was together at the University of Wisconsin-Milwaukee. The underlying theory is based on bounding the curvature and determining monotone pieces of the curve. Theoretical guarantees are established. The implemented algorithm, based heuristically on the theory, proceeds by iteratively partitioning the sample points using an octree data structure. The octree is used to subdivide the sample points into containing boxes so that the piece of the curve in each box is monotone with respect to one of the axes. The strengths of the approach lie in that it

• is simple to implement.
• is efficient - it is not Delaunay-based but compares favorably with such algorithms.
• in practice, handles well curves with multiple components and sharp corners (that often cause difficulties with other methods).
• extends to surface reconstruction.

Figures below show the program's output on some sample input. On the left are pictures of raw input (point sets). On the right are reconstructed curves.

They are thumbnails, click to enlarge.

2. Source Files

Here is the source code for PointsNBoxes in C++:
 PnB.zip

3. Requirements

1. Microsoft Windows 98 or higher with VC++ and OpenGL to view the output.
2. Unix/Linux and GNU C++ with the support of OpenGL (or Mesa) to view the output.

4. Installation

1. Download PnB.zip.
2. Unzip the file to a local directory.
   Windows: use "Winzip".
   Unix: use "unzip".
3. Compile.
   Windows: compile in command line mode, or use the project files provided in the VC directory.
   Unix: just type "make" to make the program.
4. Run.
   Enter the name of the output in the previous step. When prompted for filename, enter the path to the input you want the program to run on. We have put data for some sample curves in the directory Data - you may want to try these first.

The accompanying README.txt (which is also included in PnB.zip) describes requirements and installation procedure in full detail.

If you have trouble in running the program do not hesitate to contact us. We would also appreciate any feedback regarding performance, bugs, etc. Please send mail to Sumanta Guha (guha@ait.ac.th) or Son Dinh Tran (sontran@cs.umd.edu).

5. Papers

A short paper combining our results for 2- and 3-space - there are actually significant differences in developing the theory for planar and 3-d curves - "Non-Delaunay-based Curve Reconstruction" appeared at the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002), Vancouver, Canada, 2002. A more detailed journal version "Reconstructing Curves without Delaunay Computation" (PS, PDF) will appear soon in Algorithmica.

6. Other Software

1. Althaus et al: http://www.mpi-sb.mpg.de/~althaus/LEP:Curve-Reconstruction/curve.html
2. Amenta et al: http://www.cs.utexas.edu/users/amenta
3. Dey et al: http://www.cis.ohio-state.edu/~tamaldey/curverecon.htm