Radial sort of points on a plane

Recommended Posts

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 by guache

Share on other sites

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)

Share on other sites

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 by guache
Share on other sites

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.

Share on other sites

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

Share on other sites

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

Edited by konstantin magnus
Share on other sites

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

Share on other sites

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.

oh, never knew that, thanks.

Share on other sites

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:

Edited by konstantin magnus
Share on other sites

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 by guache

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×