HN Explorer

Ask HN: Is there any CS concept for joining individual lines into shapes

4 points by ramtatatam ↗ HN
Hello fellow HN users!

I recently stumbled across the problem where I am given a list of lines and need to join them into shapes. Some lines may overlap with other lines, some lines might be very close (unwanted artifacts), some lines might produce shapes that are not closed and I would need to join beginning and end myself.

Is there any literature which would touch on some more general problem? My intuition tells me I probably should look into graphs theory but maybe there is more intuitive approach? Lines are coming from contour detection algorithm and they may be very very close each to other but not touch each other- human eye would see the shape easily, but from programmatic point of view I feel I'll have to figure out some thresholds that if lines are close enough I consider them part of shape.

3 comments

[ 23.7 ms ] story [ 344 ms ] thread
mindcrime
I'm not sure I'm following exactly what you're working with and what the intention behind it is, so this may be entirely off-base. But the first thing that pops to mind is the idea of finding convex hulls[1]. If you have line segments, then you have endpoints by definition, and if you have a group of points you can find a convex hull. So if you're trying to classify groups of line segments as shapes, some sort of iterative process of trying to match those sets as the convex hull of a shape might work... dunno, not an expert on this, and I may well be misunderstanding what your goal is.

In any case, I would suspect that an answer would be found somewhere in the bowels of graph theory / combinatorics, or maybe topology.

[1]: https://en.wikipedia.org/wiki/Convex_hull

ramtatatam
Thanks for the hint!

I deal with contour produced by OpenCV and it's the picture that I'm passing through that are resulting in weird set of lines. Imagine taking a photo of old map and trying to figure out where oceans and continents are. For very good quality photo tuned contour algorithm will find shapes of continents. With degrading quality of photo (also with bad light conditions) there will be more and more artifacts picked up by the algorithm. I take the resulting contour apart and treat it as separate lines in hope that this will help me remove those artifacts and only leave contours of continents.

mindcrime
OK, gotcha. Sounds like an interesting problem.

Another area that might be worth exploring is fractal geometry. Many real world shapes (coastlines, for example) have a fractal aspect. And given that there are means for calculating the fractal complexity of a section of such a thing, you might be able to do some iterative thing where you perform such a calculation over a part of your image, then start taking edges out, and see how much that affects the calculated value. It may be that lines that were never really part of the actual real world shape have a different impact when removed, compared to lines that were part of the actual shape. Or if that not exactly, the whole world of fractals and the associated math might have something that would be useful to you.

https://users.math.yale.edu/public_html/People/frame/Fractal...

A clustering algorithm might also be useful. It may be that you can cluster the endpoint locations in such a way that the "artifact" lines will clearly fall outside the cluster, which might make it possible to spot and remove them.