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?

  • $\begingroup$ It might be my lack of knowledge, but can you mention what a contour of a set of edges is or at least give a reference to its definition in the question? $\endgroup$ – orezvani Jul 30 '15 at 9:23
  • $\begingroup$ @emab, (errm, somebody deleted my comment for you) -- is this what you had in mind? See the updated question. Or you asking what the term "countour of set of edges" is? There is no such term -- there is "set of edges", well, set of edges, collection, and then you compute contour/outline out of it as pictured in the question. So the countour/outline is the result of processing set of edges. $\endgroup$ – greenoldman Jul 30 '15 at 10:09
  • $\begingroup$ That's what I guessed. But without exactly defining the problem, it will be unlikely to get good answers. $\endgroup$ – orezvani Jul 30 '15 at 10:14
  • 2
    $\begingroup$ Idea: compute the convex hull. Delete all edges that are not closest to some edge of the hull. $\endgroup$ – Raphael Jul 30 '15 at 10:44
  • $\begingroup$ @Raphael, I am also thinking about starting from convex hull -- keeping existing edges, and replacing the "added" edges by shortest path between points using existing (internal ones) edges. $\endgroup$ – greenoldman Jul 30 '15 at 12:48

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.

  • $\begingroup$ I think this could be it -- "extreme" could be measured by the angle between $p_1$ and given vertex. Thank you! $\endgroup$ – greenoldman Jul 30 '15 at 12:50
  • $\begingroup$ @greenoldman: The edges incident to $p_i$ form a cone, but the cone could span more than $\pi$ (at concavities), which is why it is perhaps not straightforward to identify the extremes, the boundaries of the cone. $\endgroup$ – Joseph O'Rourke Jul 30 '15 at 13:00
  • $\begingroup$ @greenoldman: Start with the previous edge $e_{i-1}$. Walk around the edges incident to $p_i$ clockwise until you come back to $e_{i-1}$. Then $e_i$ the the next-to-last edge before returning to $e_{i-1}$. $\endgroup$ – Joseph O'Rourke Jul 30 '15 at 13:10

This problem is not surprisingly called Concave Hull
You might be also interested in alpha shapes CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS by Adriano Moreira and Maribel Yasmina Santos

  • $\begingroup$ Thank you, once you know the name it is always easier to find a solution :-) $\endgroup$ – greenoldman Sep 6 '15 at 7:05

I'm not sure this problem is so well specified. For example, what happens when parts of edges "poke out" from the contour? You've said you can't remove edges so the only way the contour is well defined is if the contour has no "burrs".

Regardless, the algorithm you probably want to look at is called the Vatti clipping algrithm. Vatti's algorithm does arbitrary boolean operations (union, intersection, difference, xor) on two dimensional polygons. My apologies, I'm having trouble finding the run time through a cursory glance but I believe it's linear (or maybe $O( V\ ln(V))$) in the number of total polygon vertices, $V$. It uses a sweep line approach so besides whatever structures are used to store, sort, search, etc., the fundamental operation is scanning through the vertices which probably isn't much worse than linear.

By interpreting your problem as trying to find a (potentially convex) contour of many thin rectangles in the plane, you can use Vatti's clipping algorithm to get the contour. Here is one such way:

  • Do a large union of all the rectangles in the plane
  • Discard all 'holes' and consider only the outer contours
  • Do another union on all the outer contours

The reason for the multiple applications of Vatti's algorithm is that you can have polygon 'islands' that are completely enclosed (and not part of) an outer polygon contour. Discarding the holes will ensure the middle will get 'filled in' and the resulting polygon will be the union of all the contours. If there's a simple way to determine what the 'outer contour' is, then that would obviously be better but I don't know of any way to accomplish that without re-inventing Vatti's algorithm.

One can also imagine using some type of polygon offsetting to either fill out breaks in the contour or make the contour smoother.

Implementing Vatti's algorithm (and any fundamental geometry algorithm) is technical and often very subtle. Though I would never dissuade anyone from personal discovery or deprive anyone the joy of implementing algorithms but if you're more concerned with the end goal of finding the contour and aren't as concerned with personal development, I highly recommend Angus Johnson's Clipper library. The Clipper library has C++ bindings (among others) and there's even a JavaScript port of it. Clipper uses integers for it's representation, so there's less of a concern of round off error. This often means premultiplying your input to a desired resolution, applying Clipper operations on it, then dividing at the end. Clipper is offered under a free license (Boost). I've used Clipper for my own projects and have been quite happy with it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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