World's most popular travel blog for travel bloggers.

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

, , No Comments
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:

enter image description here

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):

enter image description here

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?

Asked By : greenoldman

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44865

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback