Sorting points

1. From mesh I take the property get connected faces to vertex.

2. Then I calculate centers points of mesh faces.

But the order of those faces are not ordered to create a proper polyline.

Is there any method or approach how to order those faces centers in order to create anti-clock wise polygon?

Replies to This Discussion

Permalink Reply by Hyungsoo Kim on June 6, 2017 at 1:19pm

Hi.

Check this if you want.

Attachments:

SortPoints.gh, 7 KB

Permalink Reply by John on June 6, 2017 at 1:47pm

Hi,

Thank you for reply.

Sorry I made a mistake in my original post.

The issue I have is connected with meshes.

I get mesh faces connected to topo vertices from mesh like this:

mesh.TopologyVertices.ConnectedFaces(0)

Then I calculate their centers.

but the problem is that those connected faces to vertex are not in order.

If I draw a polyline between face centers and is some cases I get something like this below.

Is there any property in mesh structure to order them?

Permalink Reply by Hyungsoo Kim on June 6, 2017 at 2:09pm

Have a try Weaverbird's "Dual Graph".

Attachments:

SortPoints_v2.gh, 7 KB

Permalink Reply by John on June 6, 2017 at 4:05pm

I know I want to do this in c#... to understand logic behind dual

Permalink Reply by peter fotiadis on June 7, 2017 at 12:22am

For any mesh a point to face connectivity tree is one of the 9 classic connectivity trees (3 classes: vertices, edges, faces thus 9 combinations). Thus for point p you have all the indices of the adjacent faces (say: neighbors List). For each face there's a face to face connectivity tree. Thus you can have neighbor Neighbors List(s). Intersecting the former with any latter you can have the indices "sorted".

It's exactly the same logic widely used in trusses (especially on "random" ones) for locating member (bolts, sleeves, cones) clash situations (via trigonometry).

Are you familiar with C# ?

Permalink Reply by John on June 7, 2017 at 3:04am

Would it be possible to get an example for this in C#?

When I get neighbour faces to vertices.

Should I then take first face and get their face-face adjacency.

Then Check if vertex-face list contains one of them, if yes move to the next one.

Or is there a different method?

Permalink Reply by peter fotiadis on June 7, 2017 at 5:12am

OK, I'll prepare a C# demo that (a) does the required connectivity trees (b) does the "sorting" on neighbor vertices as briefly described. This means that you get a "dedicated" vvTree (vertex to a given face vertex connectivity) VS the classic one ... where the indices yield "sorted" points.

1M Q: Are you (in general) familiar with connectivity trees? (otherwise you wouldn't be able to follow what's happening).

That said a rather naive approach on that is to sort the neighbors along a curve (plane fit intersects with sphere fit = curve [circle]) but that takes ages to finish since the orthodox way does business with integers (indices) thus is the fastest approach imaginable.

A slightly smarter way if to sort neighbors by angle (classic sorting stuff that one) using a plane fit ... but nothing beats integer ops.

Here's a typical usage of all that (finding angles on random trusses [kinda an "customized" line graph]: the angles marked red are yielding clash events with regard a given MERO members configuration):

Permalink Reply by John on June 7, 2017 at 5:26am

I am familiar with graphs and binary trees, maybe it is similar ? I would really like to understand the non-geometrical approach via connectivity trees.

Thank you very much:)

Permalink Reply by peter fotiadis on June 7, 2017 at 5:42am

If List A contains cats and List B contains dogs then a cat-dog connectivity tree (lists all dogs that like a given cat) is a type int tree where:

(1) a given branch primary dimension is the index of a cat in List A

(2) the List of indices in that branch contains indices of dogs in List B

Therefor if you organize a mixed party ... peaceful coexistence is assured. Obviously with a single pass you can answer critical questions like: find all cats that are the most popular among dogs ... etc etc.

Permalink Reply by peter fotiadis on June 7, 2017 at 8:44am

Well ... in the Name of Science I decided to add 3 ways to skin the cat on that matter;

(a) Stupid (sort along curve: takes a week and a half),

(b) Hmm: (sort by angle: takes a day and a half) and

The move thingy parameter shown ... well you'll see what it does when this freaky case is ready.

Shown the week and a half option (only for the brave, naked vertices test [for closing the polylines or not] not yet implemented).

more soon

Permalink Reply by John on June 7, 2017 at 8:47am

Nice, would it be possible to see grasshopper file for the last image? :)

Permalink Reply by peter fotiadis on June 7, 2017 at 9:08am

You mean the C#? Well ... sure as soon as is ready (In fact it is [modified code from my truss related code(s)] but these 2 stupid options mentioned yield some work more for absolutely no reason [why I decided to add them? you tell me]).

See the reason (when a vertex is naked the related points List (adjacent MeshFaces centers modified by the move option if it's != 0) must be shifted until it starts from a boundary MashFace otherwise you get this captured result).