# Snap/Fit a chain of lines to points

I am looking for an algorithm to fit a chain of lines to a set of points/pixels. I am pretty sure that there is a suitable algorithm but I can't think of the correct search words to find it.

Here is an image to illustrate what I want:

The figure shows a chain consisting of 3 individual lines. The lines are always connected, but their connecting points can be moved. The goal is to fit the connecting points such that the resulting lines are in a sense optimal with respect to the points/pixels (here in black with blue border), for example minimzing some distance. It would be nice if one could adapt this optimality criterion, e.g., such that the lines might snap to the point cloud coming from below the point cloud.

In my current problem I could also give some side conditions for the connecting (yellow) points, such as: point 1 has to be somewhere between x and y on the horizontal axis. Also, I could give conditions on the angles between the lines.

It would be awesome if someone could point me in the right direction and tell me actually what I am looking for :)

• It's not clear enough to me what you want to achieve. Should all points lie on one side of the line? – adrianN Jun 15 '16 at 11:43
• @adrianN: I realize, my description is not 100% clear in that aspect. Actually I would be interested in two things: 1) a solution minizming some distance criterion, 2) a snapping from below the point cloud (which would mean that "all" points lie above the lines). I am not quite sure what the better solution would be for me. Do both things result in very different algorithms? – user1809923 Jun 15 '16 at 11:47
• If you want all points to be on one side of the line you could start with a triangulation of the point cloud, or a convex hull to find the "outer" points. – adrianN Jun 15 '16 at 13:05
• yes, and then I could probably continue with some form of 1). – user1809923 Jun 15 '16 at 13:20

1. Define an "loss function" $L$. The loss function takes as input the location of the connecting points, and it outputs a measure of how good/bad this set of connecting points is. Smaller is better. You mention "minimizing some distance"; this is where you put that, but you'll need to decide on a specific loss function you want to minimize. If there are four connecting points, the loss function will take the form $L((x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4))$ and will output a single real number. Choose a function that is continuous and differentiable.
2. Use gradient descent to find a location for the connecting points that minimizes the loss function. Pick some reasonable initialization value (e.g., where the user initially drew the lines; or use some heuristic to pick a crude guess at where to put the connecting points), and then use gradient descent to improve this initial choice and find a minimum for $L$.