Algorithm to determine the points delimiting the boundaries of a shape -- using javascript

Question

I'm working on a html map maker, and i'd like to offer our users the ability to create shapes quickly by clicking in a zone instead of having them define the shape manually.

First let's have a look at what we're doing for the moment. The user would like to map the area A. What he has to do is click multiple times on each point to define the boundaries of the shape.

I'd like to know is if there is an algorithm that would allow the user to click in the A area and could determine what points to dispose in order to create an near-optimal shape following the shape boundaries - based on the image contrast.

My first idea to handle this was to determine the furthest points up, left, down, right from the clicked point. Set these four points as our starting points. Then for each segment, subdivide it with a new point and move the new point along the vector normal until i hit a contrasted edge.

Of course, there are some limitations to this approach, but here is what i can assume

• the shape can be convex, concave, etc...
• the contrast should be black against white but to handle possible evolutions the contrast treshold should be configurable.
• in the example i've been thinking about above, there would obviously be a limit to the subdivision depth in order not to kill the users machine

If any of you know about such an alogrithm, that would be really great.

Answer 1

Have a look at Region Growing algorithms. This is basically the same as the flood-fill algorithm described above by tokland in the basic case.

Answer 2

This seems like a hard problem (btw, I don't know about a specific algorithm for this). My 2 cents:

1. Use a flood-fill algorithm, but instead of getting the whole surface, get only the perimeter.

2. Take a starting point of the perimeter and go in one way; when you detect that the accumulated quadratic error between the virtual segment (current point - initial point) and the real perimeter goes over a threshold, put a point there and start again till you get to the starting point.

The first step seems pretty easy, the second is harder.

Answer 3

You may use an Edge Detection Algorithm (EDA).

In Javascript you may use Pixastic, or roll your own.

After being processed by the EDA, your image gets to:

After that, simply throw any line in any direction from your interior point to the first white pixel, and follow the contour.