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.

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.

• javascript
• algorithm
• image-processing
• canvas

• Are the connecting lines known for each node? If yes, can they be navigated until the next node, even if it is halfway down a side (like the second point, in your third image)? If so, you could just use the "keep left" or "keep right" style of routing to find the innermost connecting shape. – Peter-Paul van Gemerden Commented Oct 21, 2011 at 12:26
• In fact the goal is to determine the nodes to create the polyline. I'm editing the question title to make it clearer – samy Commented Oct 21, 2011 at 12:28
• I'm sorry, I was assuming the image to be vector-based. Is it, in fact, a bitmap? – Peter-Paul van Gemerden Commented Oct 21, 2011 at 12:41
• I imagine that this requires converting the image into canvas in order to read the color of the pixels. Maybe you can add 'canvas' tag to attract canvas gurus' attention to this question ;) – Lukman Commented Oct 21, 2011 at 12:50
• How is the map represented in the first place? Is anything stopping you from piling all the possible areas in the server and just sending the processed data to the client? – hugomg Commented Oct 21, 2011 at 14:29

3 Answers 3

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.

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.

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.