0
$\begingroup$

I need to solve the following type of problem. I have a list of many connected lines forming a closed contour. These lines come as the output of a MarchingSquare algorithm. Consequently they are lines that have their start and end points on the sides of a grid. Furthermore, the lines never intersect except at the extreme points. But these lines are in random order and I would like to rearrange them in such a way that each line is in the list exactly before and after the two adjacent lines that start and end at the start and end point of the line in question. I tried a first "brutal" algorithm that works as follows, but obviously it's very slow: I start from any of the lines in question that I add to the new list. I pass through each of the other lines and evaluate the distance between the start and end point of this last line and my starting line. If I find that the distance is smaller than the tolerance I gave myself (for example 1e-10) I remove the line from the list I add the line to the new list. Then I iterate the procedure until I have emptied the initial list.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

  1. Don't work with distances but with the indexes of the grid edges (assign distinct numbers to all sides, vertical or horizontal). In marching squares, every point is repeated on two neighboring cells, on their shared edge, and there is no more than one point per edge.

  2. Generate all line segments and store their endpoints in a single hash map with the edge index for the key, but keep mutual links.

  3. Starting from an endpoint, follow the link to the buddy, and from the buddy find the matching endpoint on the same edge.

  4. Continue until you are back to the initial point, or hit a border of the domain (in this case restart the search from the initial point, to the other side).

The total search time will be roughly proportional to the number of segments.

Be careful to handle the special cases with endpoints close to a grid node. A Quick and dirty solution is to apply a small displacement to endpoints near a node.

E.g.: segments $9-8',8'-3,3-4,5-4,11'-5,13-11',\cdots$ (all upward), curve following $9-8'-3-4-5-11'-13-\cdots$,

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.