Radial sort of points on a plane

[guache]

I sometimes need to sort a bunch of points radially. The points lie on a single plane and form a string-like, closed, irregular shape, kind of like a map of a country. I created my own OTL which computes a signed angle between each point and the centroid of the figure, then sorts the points. It works fine, but I was wondering if there's a quick (i.e. just a few SOPs) way to to do this using standard Houdini SOPs.

Edited December 9, 2018 by guache

[konstantin magnus]

There are numerous threads about this I think, if you just google "houdini sort points radially", eg:

 

[guache]

Thanks. If there are many threads about this, maybe SideFX should add it to the Sort SOP.

[Noobini]

11 hours ago, guache said:

 The points lie on a single plane and form a string-like, closed, irregular shape,

given the conditions above, it's quite easy...just 2 nodes required (you can add an extra sort to reverse order if required)

 

vu_sortradial.hiplc

[guache]

Thanks, but Edge Transport won't work. When I said "string-like", I don't mean the points are connected, only that they form an outline of a shape (like a map of a country), as opposed to being a random splotch of points. In your hip, the edge connectivity already "solves" the problem. From what I see: there are 2 approaches: 1) signed angle around the centroid, 2) cylindrical uv coordinates. Another solution just came to mind, if the points are reasonably far from the centroid and evenly (more or less) spaced apart: a vex code, where you loop through all points and find a nearpoint for each, while excluding all already-found nearpoints. This would "trace" the outline by finding closest points CW or CCW. This approach could deal with cases like radial "overhangs" (i.e. protruding "peninsulas" that curve left or right etc), where an angle-based approach wouldn't work right.

Edited December 10, 2018 by guache

[Noobini]

29 minutes ago, guache said:

Thanks, but Edge Transport won't work. When I said "string-like", I don't mean the points are connected, only that they form an outline of a shape (like a map of a country), as opposed to being a random splotch of points. In your hip, the edge connectivity already "solves" the problem. From what I see: there are 2 approaches: 1) signed angle around the centroid, 2) cylindrical uv coordinates. Another solution just came to mind, if the points are reasonably far from the centroid and evenly (more or less) spaced apart: a vex code, where you loop through all points and find a nearpoint for each, while excluding all already-found nearpoints. This would "trace" the outline by finding closest points CW or CCW. This approach could deal with cases like radial "overhangs" (i.e. protruding "peninsulas" that curve left or right etc), where an angle-based approach wouldn't work right.

this is why I specificly quoted your conditions.....a CLOSED shape. If they're not connected how can it be closed ?

If they were random non connected points...you can still use triangulate 2D but there's no guarantee of it working for overhang/concave parts.

[konstantin magnus]

If the points string is evenly spaced and non-overlapping this combination works also on concave shapes: 

1. Connect adjacent points (from connect adjacent pieces-node) set to 3 search points and a sufficient radius
2. Join node (only connected)
3. Fuse

 

@Noobini In your example above I think it would be sufficient to set the sort node to "vertex order" and leave out edgetransport.

connect_string_points.hip

[konstantin magnus]

And if you are ever dealing with a less organized point cloud you could abstract it with a grid before fitting a curve through.

curve_through_pointcloud.hip

Edited December 10, 2018 by konstantin magnus

[Aizatulin]

Hi,

nice solutions! Especially the "curve from pointcloud" approach from Konstantin. With the given curve defining a shape for the jittered point you can also use the xyzdist() function again to get the u-value (attribute) for the the sort node. This will also work for roughly given shapes which are not 100% accurate. For the radial method a circle will do it. If you check my example (a modified version of Konstantin example), you can see even if you switch to the circle the result won't change that much, but there is difference.

curve_through_pointcloud_M.hipnc

[Noobini]

6 hours ago, konstantin magnus said:

If the points string is evenly spaced and non-overlapping this combination works also on concave shapes: 

1. Connect adjacent points (from connect adjacent pieces-node) set to 3 search points and a sufficient radius
2. Join node (only connected)
3. Fuse

 

@Noobini In your example above I think it would be sufficient to set the sort node to "vertex order" and leave out edgetransport.

connect_string_points.hip

oh, never knew that, thanks.

[konstantin magnus]

5 hours ago, Aizatulin said:

With the given curve defining a shape for the jittered point you can also use the xyzdist() function again to get the u-value (attribute) for the the sort node.

Good idea! I cleaned up our procedure a bit, so we basically have four stages:

1. Input point cloud
2. Rasterization
3. Curve extraction
4. Retransfer and connecting  

Inspired by this paper: http://www.iosrjournals.org/iosr-jmce/papers/RDME-Volume4/RDME-38.pdf

It´s unexpectedly useful: you can jitter curves now quite a bit and still avoid overlappings:

connect_pointcloud_to_curve.hipnc

Edited December 10, 2018 by konstantin magnus

[guache]

Thanks for all the ideas. I just came up with a visual analogy for this type of a problem: imagine you have a gnarly tree trunk and you scan it with a laser scanner around its perimeter at a height of, say, 3 feet off the ground: you get a string-like, convoluted point cloud that "envelops" or "encloses" the trunk's cross-section at that level. The goal is to reconstruct the cross-section from the points, as a single, closed polyline. This example has the "no-overlaps" condition built-in, as a tree can't really grow "into itself", like an arbitrary curve can.

Edited December 11, 2018 by guache