Shape outlining library

How to outline a shape? How to build a path?

It started as simple kids dot-to-dot puzzle with one single BUT: instead of child we got a program. Is the puzzle making you think a lot? - Program does not know sequence numbers of dots and needs to put those ones itself. How to make computer to build a directed contour (path) having finite set of points? - the solution is below.

Problem

You have finite set of points. All these points belong to the same shape. Some of points are internal, another ones are outlining points. The goal is to get connected those points that outline a shape, omitting internal points. It is also important to build path from points after selecting ones at edge and removing ones from the set "heart", so that we know which are connected, like in dot-to-dot puzzle.

Convex hull case was described many times and has several solutions [Incremental, Gift Wrap, Divide and Conquer, QuickHull]. The case when a person draws outline himself is also trivial, even with smoothing or straightening. We are interested in bent, irregular, irrational, curvy, whimsical, fantastic shapes which could be convex, but not necessary are.

Shape outlining, path building library

aidReady is special library that provides functions for outlines recognition of images. The library provides shape outlines as array of points, so vector graphic techniques could be applied for built path. You can see shape examples below:
Shape outlining examples using aidReady library You can see three selected contours on the image above: a) is initial image, b), c) and d) show shapes outlines returned by library by single mouse click. Color gradient (from yellow to red) shows that path was created, but not only set of points.

You can find solutions for tomography (brain tumor volume estimation) based on this library at tumor volume estimation.

The library is available for .Net Framework, Java and C++ (Visual C++, G++). It is free for non-commercial use. Commercial use of the library is possible, but must be discussed beforehand. You can contact author for further development.