Shortest Interpolated Curve

this seems to be a very simple problem but still we can´t solve it, maybe one of you could help us:
we have 4,5,6 point in one plane and want to interpolate them.
but it always generates strange curves. (see .jpg: red curve is wrong, black one correct)
of course this has to do with the order in which the points are picked.
but there is no way for us to define the order, as there are multiple curves to be generated, that have different orders of there own.
the easiest option would be to create all possible interpolated curves and delete all but the shortest one.
but how to do that?
your help would be really welcome!
thanks,
thomas

Attachments:

KurzesteKurve.jpg, 231 KB

Replies to This Discussion

Permalink Reply by Benjamin Golder on October 31, 2009 at 8:07am

You should upload your definition or a picture of your definition if you want help. There is probably a much better solution than finding the shortest curve, but it is important to know how the points are currently ordered and how they need to be ordered. I think it would be best to find a way to order the points.

the easiest way to find the shortest curve is to get the lengths of the curves, then use the "sort list" component. you would put the curve lengths into the "K" input and the curves themselves into the "A" input. Then attach the "A" output to the "L" of a "list item" component, and set the integer of the "i" to 0. This will isolate the shortest curve in any list.

Permalink Reply by Damien Alomar on October 31, 2009 at 12:39pm

Well, it might be "easiest", but creating all the possible curves is certainly not the best because as you add more points their becomes exponentially more solutions. Any solution that scales exponentially is generally not the best thing for real time or dynamic interactions. What would be much better in this case would be trying to find some sort of logic for sorting the points that will make a good curve. With the assumption that the points are at least in a relative "polyline order" (ie. they aren't just random), than a good way of sorting them is by whichever's the closest to the previous point in the list.

I was actually writing some code for just this exact thing last weekend, so I've attached the definition that sorts the points. There's a few extra things in there for what I needed, but it should certainly work for you.

Attachments:

sortPtList_closest.ghx, 121 KB

Permalink Reply by Jacek Jaskólski on October 31, 2009 at 1:00pm

Hey Damien,
Are you using Dijkstra's algorithm or is it something else?

One other thing makes me curious:
Will the curve created from the shortest polyline's vertices always be the shortest possible curve? It seems it could be a bit more complex problem...

Permalink Reply by Damien Alomar on October 31, 2009 at 1:42pm

No...just copying the rhinoscript method SortPointList...iterating through the point set to find the closest point to the one previous. Nothing special really.

No, its not always going to be the shortest possible line, but if the points are visually in a discernible order, than it will arrive at what I would call a "satisfactory" solution (ie one of the shorter possibilities if not the shortest). Its only when the points get more randomized that the solution becomes less effective.

Permalink Reply by Jacek Jaskólski on November 1, 2009 at 5:38am

Thanks for the explanation.

Permalink Reply by thomas pearce on November 1, 2009 at 11:08am

yes thank you verry much! you all are of great help!
this was the solution we had finally thought of as well. we were writing kind of the same script as the one you sent us, and it works quite well, as does yours.
indeed for us our curves aren´t that complicated so it always comes up with the correct curve - were planning a pavillon out of wooden lats with a rectengular profile for a university project to be built next spring...
thanks again!
thomas pearce
(berlin)

RSS