How can I sort in two dimensions?

This file shows the basic idea of 2D sorting. If you don't understand why it requires an expression like:

from + (along * 1000)

Then read the following explanation from David Rutten which is part of this discussion

Ok, so here's the basic idea. We need to sort our rectangles according to two constraints (along and from). But sorting only works on a single list of numbers. This means we need to find a way to encode those two numbers into a single sortable list.

Imagine the following setup, three shapes (A, B & C) and a sorting guide:

If we only cared about sorting the shapes along the line, all we had to do was compose a list of all the ts (the parameters along the sorting guide closest to the shapes) and sort those. tA is smaller than tB and both are smaller than tC, so the order we'd get in this case would be A-B-C.

If we had two objects that had the same t value, but different distances from the sorting guide, there's no telling in what order they'll end up. It really is random due to the nature of the QuickSort implementation in .NET

If on the other hand we only cared about sorting the shapes based on distance from the guide, then we'd need to make a list of all the ds (the distances from the shape to the line) and sort those. dC is smaller than dAand both are smaller than dB, so the order in this case would be C-A-B.

But we want both. And we want the ts to be dominant over the ds. Meaning we want to sort all rectangles first along the guide, and then sort the ones in the same 'row' by distance from the guide.

We somehow need to combine t and d to give us a single numeric value that can be used to sort all the shapes in one go. Just adding them together won't work. After all, it's easy to imagine that tB + dB is about the same value as tC + dC.

Let's assign some actual values to the ts and ds and see how they behave:

If we were to simply add the t and d of each shape we'd get the following, sorting keys:

A = 5.0

B = 7.3

C = 5.0

D = 4.0

E = 8.8

F = 6.8

G = 7.2

H = 6.7

Which would result in the sequence {D, A?C, H, F, G, B, E}.

Since we want the ts to be dominant we need to amplify them so much that the biggest change in d cannot overrule the smallest change in t. I chose to multiply by a 1000, but you may need to experiment depending on specific case what sort of number works best. So let's include our amplification factor of 1000.0 for the ts and recompute the sorting keys:

A = 4001.0

B = 4802.5

C = 2502.5

D = 2501.5

E = 4804.0

F = 4802.0

G = 4003.2

H = 2504.2

now if we sort this, we get the proper sequence {D, C, H, A, G, F, B, E}

This is not the smartest of all 2D sorting algorithms btw. Since t is amplified so much it might wreck havoc with the sorting if there's a tiny amount of noise in the t values. For example if the rectangles aren't exactly in a grid, or maybe if the guide wasn't precisely parallel to the grid. However making a better sorter would require a fair amount of logic with probably a lot of if...then statements, so it's hard to do that in Grasshopper at present.

David Rutten

david@mcneel.com

Poprad, Slovakia

Replies to This Discussion

Permalink Reply by ayg011 on May 22, 2012 at 10:54am

Is the lack of pure, logical functionality in GH another limiting factor (see related post) in regards to its use for design realisation? I suppose the counter-question is, if logical operators were created as a set of components, would users possess the cognitive ability to successfully implement their use, or even care in the first place? I say this as using such methods will firstly require an acquired knowledge that adds additional complexity to a process, and secondly, they serve abstractly by nature which many individuals will fail to comprehend. This scenario would put in motion the possibility that such components would be consigned to the rubbish-heap due to user inability or complacency. Subsequently, the unique benefits logical operators / conditional statements offer as part of the design exploration process will be completely overlooked.

That is of course if it is possible to create such components in the first place. It could be said that the application of logical functions will always be problem-specific, meaning no pre-configured component will ever be adaptable enough to fully - or successfully - parse the infinite variation and structure of possible data input, and their pursuit as a workable addition to the GH repertoire is therefore futile, or simply impossible.

http://www.grasshopper3d.com/forum/topics/constrain-rotation?xg_sou...

Permalink Reply by Michael Pryor on May 22, 2012 at 11:37am

If you have inquiries about grasshopper please post it here in the correct forum. This is a FAQ forum to help others, not to sell products :) Thanks

Permalink Reply by Danny Boyes on May 22, 2012 at 12:10pm

Welcome back agy011
Not sure if you saw this link but it would seem to be relevant to your post. Even if you post is not relevant to this discussion http://ieatbugsforbreakfast.wordpress.com/2012/04/01/programming-co...

Permalink Reply by ayg011 on May 23, 2012 at 3:10am

I am construing the point you made at the end of your post, hence the relevance. I did read the blog post you linked to, the day it was published in fact, and while i agree with some of the arguments put forward, i do feel some of the more important issues which i raised were not properly addressed.

Permalink Reply by Danny Boyes on May 23, 2012 at 4:05am

I find with the way multi threaded discussions go things can get lost so I wasn't sure if you had seen it.

I don't think your post here is relevant to a common question asked by many about 2D sorting specifically. If you wish to add to the 2D sorting problem please do, but it should be restricted to helping or improving the methods for sorting in 2D in Grasshopper.

If you would like to start a Discussion in the Discussion Forum not the FAQs about this topic then your questions can be addressed there as the content here will be removed to keep it simple.

Permalink Reply by Mateusz Zwierzycki on May 23, 2012 at 11:03am

To develop this subject further, let me introduce polar coordinate system* sorting.

If this explanation is not clear, read it with attachment file opened.

*read about polar coordinate system here

As you may know, PCS (from now I will call polar coordinate system with PCS, and cartesian one with CCS) describes point position with 2 values (like x and y in CCS) which are r and theta(r,theta). r is for distance from PCS center, theta is angular dimension which is in 0 to 360 or 0 to 2*pi domain.

To hark back to David's guide line - here it is replaced with guide circle.

Why to sort points like this ? As usual, one image tells more...

Here is logic behind all this stuff :

Find an average point of all given points*
Search for furthest point from an average point*
Create a circle with center at average point and radius = distance from average point to furthest point*

*Steps 1-3 can be replaced with custom hand-made circle, I decided to automate it that way.
For each point find closest point on circle - this will be used for finding theta value
For each point find distance to average point - this is r value
To overcome problem with same theta (t) values (like same x values in CCS), instead of multiplying by 1000, we will use a new create set component. This component creates set of integers, each one representing one unique input value. So if points A, B, C, D, E are (r,theta) :

A (1, 30)
B (2, 30)
C (3, 30)
D (1, 45)
E (1, 60)

Then create set will output list of integers = 0,0,0,1,2 (same theta for A, B, C other theta for D and E). Now its getting really easy - remap r values to domain 0 to 0.5 (or any less then 1), and add integers from create set component to remapped r values.

7. So what we have now is list of floating point numbers : A=0, B=0.25, C=0.5, D=1, E=2

Profit of remapping is that r values will never affect integers representing theta values - and all the information is stored in one floating point number ! By sorting these values we will obtain proper order of points - to complete this, we need to sort points parallel with values.

What's really cool about polar sorting - there could be any amount of points, but polyline connecting all of them will never self-intersect. Probably there is some relation with 2d convex hull.

Attachments:

sort radial.gh, 14 KB

Permalink Reply by David Rutten on May 23, 2012 at 12:09pm

Grasshopper 0.9.0001 will have a Sort Along Curve component which allows easy sorting along non-linear axes. It's technically not 2D sorting, but it does make certain operations a lot easier.

Unsorted points: