sorting algorithm for xy plotter

As I managed to get my pen plotter (a nice Roland DXY-1150A) working with gh via chiplotle (a also nice library that enables you to talk to the plotter via usb to serial port interface) all I need to be happy is the right sorting algorithm for the curves..

Will post some of the workflow and results later on here on the forum.

The task is to create a scripting component that sorts a given list of curves and lines and also flips them in a way that an xy plotter (or cutter or whatever) will go through them with the shortest walk.

And this time we will also have a price. I will ship a unique generative watercolor plot to the winner.

To determine the winner I will measure the plotting time on my plotter.

----------------------------------------------------------------------------------------

Here are some assumptions I made but of course any other solution is welcome:

In my opinion it should be something like David Mans "Sequentially Sort Points by Distance Component" for curves.

pseudo code would be:

input: list of curves and lines

make a list of all endpoints and start points of the given curves
start with a given point
find the closest point regardless of whether its a start point or an endpoint.
delete that point from the list
take the other point of that curve

and so on until you reach the end of the list.

the curves get sorted sequentially according to pattern above.

output would be the sorted indices of the curves and a true/false pattern whether

the first picked point was a start point or an endpoint.

to be able to flip the curves afterwards...

Replies to This Discussion

Permalink Reply by Jake Newsum on October 1, 2014 at 3:42pm

Hi Christian,

Here is a python script that works in the same way as your pseudo code/sketch. I would say that this produces a short walk, but not the shortest. This is a first pass at how to start sorting out the problem, and there is a lot of room for improvement.

Let me know if you have any questions.

Kind Regards,

Attachments:

141001_SortCurveExample.gh, 4 KB

Permalink Reply by Christian Schmidts on October 2, 2014 at 2:19pm

Hello Jake,

looks really good! Just tested it and it does pretty much of what i intended.

could you please leave me out the line segments between the original curves in the output?

Thanks a lot! I really appreciate it!

Permalink Reply by Jake Newsum on October 3, 2014 at 7:57pm

Here is a version that will output the sorted/flipped curves and the traverse paths as separate outputs. Let me know if you have any other suggestions or comments.

Kind Regards,

Attachments:

141003_Python_02.gh, 5 KB

Permalink Reply by Christian Schmidts on October 4, 2014 at 3:41pm

Great - works like a charm! There is one last (hopefully small) thing I just realized. I would need also the an output with the sorted indices in order to sort a list of attribute colors simultaneous.. Thank you again!

Permalink Reply by Jake Newsum on October 6, 2014 at 12:12pm

Are you wanting the index of the original curves that were input to show where they came from?

If you want the index of the sorted curves, the curves that are output from the FlippedPath are sorted in the order that they should be printed, so their index order would be 0,1,2,3,...

I will try to add in the indices output later today that represent how the original list became the output. It will take a bit because I set the script up so that it works on a list that deletes the curves as they are used, so the index of each of the curves I call out will not match the input after the first loop.

I am glad that the script is working out for you. I have been using simple scripts like this to drive machines for a while and they are quite useful.

Kind Regards,

Permalink Reply by Jake Newsum on October 6, 2014 at 12:49pm

Here is the updated component. I am not sure if this is what you wanted, but it now outputs the indices that reference the original order. The definition shows how to sort the Flipped Path back to the original organization.

Kind Regards,

Attachments:

141006_Python_03.gh, 9 KB

Permalink Reply by Christian Schmidts on October 7, 2014 at 7:09am

Just made a test plot and everything is working perfect now!

Yes indeed a proper sorting is useful especially if you print a lot.

The thing with the indices was exactly what you did.

And I saw that it is working even on multiple branches - that's really cool!

Thank you a lot for all your effort!!

If you want and send me a mailing address via private message I will be happy to send you one of my generative water color plots.

Best, Chris

Permalink Reply by Jake Newsum on October 7, 2014 at 3:18pm

Thanks Chris, I am glad that it is working for you.

I was thinking about the shortest path issue, because the component that I gave you makes a 'short path', but it doesn't continue to evaluate to see if it is actually the shortest possible path.

If run time for the best solution is only measured by how long the drawing takes, then you would want to use this update. This new version will take a lot longer to process and may take a really long time if you have a lot of input curves, but it will output the shortest overall path relative to your start point.

Give it a try with a few curves and see what you think. I will send you a pm with my address in a bit. I am looking forward to seeing some of the results!

Kind Regards,

Jake

Attachments:

141006_Python_04.gh, 5 KB

Permalink Reply by Christian Schmidts on October 9, 2014 at 6:53am

I see - just tested it. As the previous version is also quite close to the "best" result and I have lots of curves I think i will rather stick to this.

But nice to know. When I have some time I would like to get trough the code - I'm sure i can learn a lot from it.

Thank for your address. I will send the plot next week - so you are warned if you notice a strange package from Germany:)

Best,

Chris

Permalink Reply by Jake Newsum on October 15, 2014 at 1:06pm

Thank you Chris!

I know, the newer code is extremely slow, but it could save a lot of time if you were printing the same file over and over.. The previous version will work fine for one offs.

I tried to write the code so that it is fairly easy to read. I am sure that someone could make a much faster/efficient way of doing thins, but I am a designer not a real programmer. If you have any questions, let me know.

Looking forward to the print!

Kind Regards,

Jake

Permalink Reply by Ethan on January 23, 2015 at 8:58am

Jake, great work on this short walk solution. I tried the second version and get this error: 1. Solution exception:'NoneType' object is unsubscriptable.... any ideas what I am doing wrong? Thanks! e

Attachments: