Algorithm for defining points bounding the boundaries of a form - using javascript

Question

I am working on an html map creator, and I would like to offer our users the ability to quickly create shapes by clicking in the zone, instead of manually defining the shape.

First, let's see what we are doing at the moment. The user would like to display area A. He needs to click several times at each point to define the boundaries of the form.

I would like to know if there is an algorithm that allows the user to click in area A and can determine which points to position in order to create an almost optimal shape, following the boundaries of the form - based on the image contrast.

My first idea to deal with this was to identify the furthest points up, left, down, right from the click point. Set these four points as a starting point. Then, for each segment, divide it into a new point and move the new point along the vector normal until I click on the opposite edge.

Of course, there are some limitations to this approach, but here's what I can assume

• the shape may be convex, concave, etc.
• the contrast should be black from white, but to control possible changes, you must configure the contrast.
• in the example I was thinking about above, it is obvious that there will be a limit on the depth of the unit so as not to kill the user machine.

If any of you know about this alogrite, it will be really great.

Answer 1

This seems like a difficult problem (by the way, I don't know about a specific algorithm for this). My 2 cents:

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

• Take the starting point of the perimeter and go in one way; when you find that the accumulated quadratic error between the virtual segment (the current point is the starting point) and the real perimeter passes through the threshold, place the point there and start again until you reach the starting point.

The first step seems quite simple, the second is more complicated.

Answer 2

Check out Regional Development Algorithms . This is basically the same as the flood filling algorithm described above tokland in the main case.

Answer 3

You can use the edge detection algorithm (EDA).

In Javascript, you can use Pixastic or flip your own.

After processing the EDA, your image receives:

After that, just drop any line in any direction from your inside point to the first white pixel and follow the path.