Re-Order Some Points.

Hi All,

I'm pretty sure this is a Script component solution question as opposed to the native GH components.

I have a series of points which I receive from a Third Party application. There is a bug in the process that returns some unwanted solutions.

The input for this software is a whole bunch of surfaces and the outcome should be a polyline representation of these surfaces in a given plane.

From what I can gather the routine finds the closest surface to the origin of the plane and starts at that edge.

It then works around the surface until the next edge is reached.

It finds the next closest surface and starts at the closest edge. (there may be a gap)

It then repeats this until all surfaces have been included in the polyline.

the error I get is that when there is a large enough gap it sometimes gets the polyline wrong (correct with the algorithm though) as the closest point does not lie on the ground plane (most cases it does)

What I need to do is to post process these points and re-order them so that when the gap occurs (always when Z=0) it doesn't find the next point that is closest but rather the next point the is closest on the ground plane.

See image or definition attached for illustrations

To clarify I need to take a list of ordered points that is very nearly correct (red curves in image above) and then re-order them based (blue curve above)

Any help with this is most appreciated.

Danny

Attachments:

PointOrderingProblem.gh, 62 KB

Replies to This Discussion

Permalink Reply by David Rutten on September 19, 2013 at 9:07am

Sorry, I'm still a bit confused. Let me try and explain what I think you need:

You have a bunch of points that come in from some other application.
It's a single list, representing a polyline that travels over the planar section of a bunch of surfaces.
Every group of points that 'belong' to a single surface end with a point with z=0.0
Every group of points that 'belong' to a single surface should start with z=0.0, but it doesn't always do this.
You want to parse this list of points and re-order the points inside each subgroup so that it always ends and starts at z=0.0

Or do you have the curves available and are simply looking to generate this single list of points correctly?

David Rutten

david@mcneel.com

Tirol, Austria

Permalink Reply by Danny Boyes on September 19, 2013 at 12:36pm

Hi david,

In the top illustration there are black and green curves representing where each surface starts and ends. I.e. One colour is one surface. There are eight surfaces in all. Three on the left and five on the right.

The problem stems from the fact that when the point order jumps from the left collection to the right collection it spans the gap to the closest edge of the closest surface. What i need is to reorder the points as if it had spanned the gap to the closest surface's closest edge to the ground usually z=0. And then to continue with the order by getting the next surface from the closest edge. Typically there is only ever one gap and the next set typically starts from the ground

In the definition there are three point components with the orders of the examples. The last one is the only correct outcome.

I provide an iges of the surfaces to the program but only get the points back in a list but i have the opportunity to manipulate the list before i use it.

Thanks

Permalink Reply by Yoann Mescam (Systemiq) on September 19, 2013 at 3:04pm

Wouldn't that work ?

Permalink Reply by Yoann Mescam (Systemiq) on September 19, 2013 at 3:55pm

Or perhaps this better

Attachments:

PointOrderingProblem_Systemiq2.gh, 49 KB

Permalink Reply by Danny Boyes on September 20, 2013 at 2:54am

Thanks systemiq,

I looked at these sorts of solutions and unfortunately they don't work for scenarios where the point spacing is less consistent. If I have large areas of flat surfaces then the points returned have a large span which is not the same as the gap at ground level between the two entities.

for example:

Permalink Reply by David Rutten on September 20, 2013 at 5:05am

This is turning out to be quite difficult (as you've no doubt already figured out). When you change the order of points on the second shape so that the transition from the first shape goes along z=0.0, how do you keep the order of points after that intact. This is problematic for possible solution #2 in your original image as there is a little loop and it's not obvious to me how to correctly ignore one of the connecting segments but not the other.

It's easy enough to copy the points into another collection until you hit z=0.0, then find the nearest remaining point which also has z=0.0. But how then do you continue? I'm assuming finding the nearest point in 3D space until you hit z=0.0 again is not good enough?

I think I have an inkling on how to solve it, but it's little more than a feeling. Any thoughts welcome in the meantime.

David Rutten

david@mcneel.com

Tirol, Austria

Permalink Reply by Danny Boyes on September 20, 2013 at 5:22am

Glad I'm not the only one :)

I'm assuming finding the nearest point in 3D space until you hit z=0.0 again is not good enough?

I can see where this can go wrong but if the surfaces supplied where all touching (to within a tolerance) I don't think there would be an issue. It's a shame that the program doesn't return the duplicate points representing edges then it would be easier to distinguish the order.

For now the next closest point would suffice provided that the start of the next set was on Z=0

BTW z=0.0 must be a tolerance due to some peoples inaccuracies in modelling :)

Permalink Reply by David Rutten on September 20, 2013 at 8:07am

The attached hasn't been thoroughly tested.

The basic logic is thus:

The first point in the unsorted list also becomes the first point in the sorted list.
In every iteration the nearest point in the unsorted list to the last point in the sorted list is found. If the last point signifies a shape-end-point, then the search is limited to the plane, otherwise the search happens in 3D

David Rutten

david@mcneel.com

Tirol, Austria

Attachments:

vbhell.gh, 6 KB

Permalink Reply by David Rutten on September 20, 2013 at 8:10am

Actually, take this one, it also outputs the sorted indices. Note that duplicate points will remain in the output, you can collapse short polyline segments if you want.

David Rutten

david@mcneel.com

Tirol, Austria

Attachments:

SmartSorting.gh, 9 KB

Permalink Reply by David Rutten on September 20, 2013 at 8:17am

Ah, possible improvement, you could also limit the search for nearest points until the nearest zero-point. That way you won't accidentally jump to the next shape, even if it is closer.

David Rutten

david@mcneel.com

Tirol, Austria

Permalink Reply by Danny Boyes on September 20, 2013 at 11:21am

Excellent!

Thank you very much for you help.

RSS