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:

enter image description here

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.

  • $\begingroup$ 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? $\endgroup$ – nicoguaro Aug 17 '16 at 14:01
  • $\begingroup$ 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? $\endgroup$ – spektr Aug 17 '16 at 17:18
  • $\begingroup$ @nicoguaro that's actually a great idea. Haven't thought about that. I'm going to experiment with that. $\endgroup$ – Superkuuk Aug 18 '16 at 7:40
  • $\begingroup$ @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. $\endgroup$ – Superkuuk Aug 18 '16 at 7:42

Your Answer

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

Browse other questions tagged or ask your own question.