World's most popular travel blog for travel bloggers.

# [Solved]: What are algorithms for computing contours from given edges?

, ,
Problem Detail:

Let's say I have a set of edges which makes the contour, however there are too many of them and some are too long. I have to remove edges, and shorten them to make contour. I cannot add new edges!

I am looking at least for the name of the algorithm to further look how this problem is solved.

Here is the example (please don't mind the grid) -- input:

and output in pink (the pink is the real output, the rest is left for comparison -- it should be removed by algorithm I am looking for):

As you can see I have a lot of redundant edges, too long, internal ones. Note also that this is not the convex hull problem; my shape is not convex.

The question: what are known algorithms for solving this problem?

#### Answered By : Joseph O'Rourke

How about tracing the contour, something like this?

Find one point \$p_1\$ on the contour (e.g., the vertically highest point). Find all the edge incident to \$p_1\$. Sort them around \$p_1\$ and identify an extreme edge \$e_1\$ (defining "extreme" here is a bit tricky). Follow \$e_1\$ until you reach either its endpoint or another edge intersecting \$e_1\$. Call that point \$p_2\$. Repeat.