Is there any CS concept for joining individual lines into shapes

Question

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.

mindcrime · Accepted Answer

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