sort Mesh

Hey,

do I have a chance to sort the MeshFaces (see first Picture)? Best solution would be like the second picture

Replies to This Discussion

Permalink Reply by David Rutten on March 23, 2011 at 4:40am

Well a single mesh must have a single array of mesh faces, so you certainly won't be able to have two (or more) faces with the same index. However, a list of polylines (like the outlines of each meshface) could be sorted and split into multiple lists.

It seems your original mesh faces are already sorted though. Is this something that can be relied upon? In other words, do you need to just shuffle the order or do you really need to sort any collection of meshfaces?

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Dedackelzucht on March 23, 2011 at 4:50am

Hey David,

I have already produced the outlines as polylines. mhhh... That would be enough for me to sort them.

I could use the coordinates to sort them, or how would you do that? I have got a sort file I am using in this case, mabe that works.

Best Regards

Dackel

Attachments:

101104_List sort.ghx, 380 KB

Permalink Reply by David Rutten on March 23, 2011 at 5:38am

I attached a solution for re-ordering an ordered set.

David Rutten

david@mcneel.com

Poprad, Slovakia

Attachments:

re-order-mesh-faces.ghx, 182 KB

Permalink Reply by David Rutten on March 23, 2011 at 5:45am

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

from + (along * 1000)

let me know, I'll try to explain.

David Rutten

david@mcneel.com

Poprad, Slovakia

Attachments:

2d-sort.ghx, 123 KB

Permalink Reply by Dedackelzucht on March 23, 2011 at 6:33am

I love it!

the re-order-mesh I understand. Specially the % in the pathmapper is nice to know. Its already insert into my libery :-)

And of course I do not understand the f(x,y) , as you knew. But I have a guess:

The function needs as an input t and D. t can be quiet small and in addition with D you get conflicts (wrong sort) comparing the rows, if you only sum them.

Thank you very much for your files. As I said: I like them

Best regards

Johannes

Permalink Reply by Danny Boyes on March 23, 2011 at 7:57am

Hi Johannes,

Also note the "\" a.k.a. Integer Divide a.k.a Backslash Divide will actually do the job without the need for the Flip Matrix.

The way I see it \ gives you 5 items on 20 Branches and % gives you 5 Branches with 20 items. \ = I (items) % = B (branches)

Permalink Reply by Dedackelzucht on March 23, 2011 at 8:06am

Hey Danny,

:-) I have already recognized that one. (I think that was you some mounth ago, who helped me with the \ ? I am defently a path mapper fan)

But thanks for the post.

Best Regards

DeDackel

Permalink Reply by L]G on March 23, 2011 at 8:32am

Hi, by "\" you guys mean tree mapper target?. do you guys know anywhere you can get tutorials or learn about trees and data. i get really confused when it comes to trees, strings, domains,list etc ;),

thanks you

Permalink Reply by Danny Boyes on March 23, 2011 at 8:47am

Ages ago there was a post by Sameer Kumar that outlined all the things you could do with pathmapper. http://www.i-m-a-d-e.org/fabrication/wp-content/uploads/2010/08/pat...

But I find the most useful the three most useful applications are

1) to flatten branches up a level without flattening the entire tree.

This usually goes in the form {A;B;C}(i) --> {A;B} where every individual item on branch C is collected together on B as a group but all the A's remain separated still.

2) Divide the tree by Items

The backslash "\N" (where N is an integer) is integer divide which will put the first N items on one branch and then the next N on the second and so on.

3) Divide the tree by Branches

The modulo divide "%N" puts every Nth item on Nth Branch i.e. first item and N+1, 2N+1 etc on first Branch and the second and N+2, 2N+2 on the second etc.

Permalink Reply by David Rutten on March 23, 2011 at 8:46am

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 dA and 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

Permalink Reply by RWNB on March 23, 2011 at 8:56am

very interesting material.
please more of it.

Permalink Reply by L]G on March 23, 2011 at 1:19pm

thanks alot David,this is great, im a tad less confused than i was before. :), but i have not yet found a way of getting the list of point sorted out. i just dont get why when u select all the point as ur data, the order that it is automaticly chosen is so random.

on the grasshopper primer seems as when a curve is devided, the point follow a logical order, starting at one of the ends and ending at the other end.but when i select the points it goes crazy and picks the first to be at random in te centre. i guess it has to do with the order in which the poins where made, or in this case the lines and intersections.

here are the files in case you guys wanna have a look. im trying diferent ways of getting around it.

cheers

Attachments: