# Find alternative path closest to original

I have a set of points in a 2D space. I want to connect the outer points so I get the convex hull. The problem here is that there is a limit to the distance between two points. Let me clarify that with a picture:

The green lines are lines that are good. The distance between the two points of the convex hull doesn't exceed the maximum distance (the outer circle of a point). But the red lines aren't correct. They exceed the maximum distance.

What I need is a line, through multiple points, correctly drawn (e.g. all green lines), as an alternative for the red lines, while keeping the path a kind of convex hull.

I've been looking in concave hulls, and that might do the trick, but I haven't been able to find a good, preferably in Javascript, algorithm.

• Can you split the red lines into segments up to the point the have the right length and then find the closest point to the new (artificial) boundary points? – nicoguaro Aug 17 '16 at 14:01
• What do you mean by keeping it "kind of" like a convex hull? Just looking at the graphic, solving your problem having constraints on connection length would result in the boundary not being a convex hull anymore. Can you be more precise, perhaps? – spektr Aug 17 '16 at 17:18
• @nicoguaro that's actually a great idea. Haven't thought about that. I'm going to experiment with that. – Superkuuk Aug 18 '16 at 7:40
• @choward It's indeed not a convex hull anymore. I think it's called a concave hull then. There need to be little 'gaps' in the convex hull in order to get a valid hull. – Superkuuk Aug 18 '16 at 7:42