Strategy for removing points inside PointCloud

I suddenly ran out of ideas. Starting from a fairly evenly distributed bunch of (planar) points, is there anyone out there having good ideas about a strategy for removing some of the points “inside” the cloud. What I want is to keep a band of points along the outer boundaries of the pointcloud.

A working solution would have to be able to get its way around the boundary also if it makes a turn into a “keyhole” (or “tunnel”) into the cloud (constrained by a minimum gap size as to avoid narrow inward “spikes”).

I need to come up with a C# algorithm, so any ideas illustrating a working strategy would be gold.

Fig 1. Before (Left) and After (Right).

The example PointCloud internalized (Disregard the C# component)
CullInnerArea_pointcloud.gh (213.0 KB)

// Rolf

So the main issue here seems to be determining the boundary of the point cloud?

Otherwise, something along these lines might work:

For any pointcloud, I’d like to keep only a band of the “outermost” existing points around the cloud, like the blue marked ones:

I would have no other input data than the cloud itself, and a desired width of that “blue band” of points to keep, [Edit:] so I wouldn’t have any curve boundary etc to know where to cull. It must all be derived from the cloud itself.

At first glance I didn’t really grasp how the definition works which you posted, but I’ll have a closer look asap. Thank you for posting!

// Rolf

I managed to get a “concave mesh” (white group) and perimeter boundary around the point cloud. I left out the Graph Mapper from the other model that causes the gradient effect and cull all the points within ‘edge_L’ distance from the perimeter.


CullInnerArea_pointcloud_2020May15a.gh (228.8 KB)

1 Like

Wow Joseph, that’s cool, I can definitely learn from this approach!

Thank you very much. This really looks clever. Edit: And it’s also super fast.
I’ll study it in more detail.

// Rolf

I didn’t mean to leave two ‘edge_L’ sliders in the model (copy/paste) but if you adjust the first one in the white group and hide the Join boundary curve, you can include that single point all by itself.

P.S. It looks like 9.5 is the smallest value possible on that slider in the white group to get the most edge detail. Smaller than that and it goes wacky.

1 Like

No problem. I would expect that, since if that value is divided by three it would be close to edge-length of the triangles (if I understood it correctly) and if edge-len is too short it’s no wonder if the algoritm caves in on itself.

I really like what I see here. Wow. :slight_smile:

// Rolf

There was no need for Explode and MA since it’s the same as polyline length.


CullInnerArea_pointcloud_2020May15b.gh (119.1 KB)

2 Likes

Edit: Spelling & some clarifications

I’m working on a C# component doing the magic as in your Gh definition. See upload below.

I have a question about the Polyline component. For some reason, the Polyline component produces a different result than what I can achieve using C# code to create the same Polyline. The difference appears when the input option Closed is set to Invert, or “True” (Closed = true). I marked this setting with a red ring in Fig 1. The difference in output is marked in Fig 2 below.

  • My Q: So what is it that causes the “closed” option to give the different result? I just can’t figure it out (so I could mimic it in C# code), because the closed result is the desired result.

Fig 1. A C# version (white ring) along with the original strategy (Gh definition) by @Joseph_Oster:

Fig 2. Different “Naked Edge” result for “closed” Polyline compared to C# created ditto. I marked some examples. The yellow line is the desired result from the Gh Polyline component with “closed” = true:

I added to the Gh definition a Sort component to ensure that only the longest Naked Edge is used for the final point culling.

Notice also that after adding a wire to any C# Component output, the Gh definition must be recomputed for the component to become aware of the change (it then know’s it needs to internally
process the desired output data, which is my optimization trick to skip processing such data which isn’t asked for).

The GH Definition and the C# Component:
ConcaveHull_BorderWidth_Component_R1.1.gh (257.8 KB)

I want to thank @Joseph_Oster again for this cool definition. I wouldn’t have come up with something similar in x thousand years. :+1: :+1: :+1: :+1: :+1: (out of 5)

// Rolf

I haven’t looked at your code but without the ‘Closed (C)’ set to True, only two of the three points will be connected. When all three points (vertices of a mesh face) are connected, a triangle is formed and it’s the sum of all three edge lengths that determines “large” faces from small ones. The CullF component then culls (filters) only the small faces with ‘Pattern (P)’ inverted, ignoring the large faces and leaving the “concave mesh”.

Glad you like it.

P.S. I don’t understand why Sort is added? Unless you end up with multiple mesh boundaries? I’m unable to examine your code at the moment.

P.P.S. Oh wait, you are using a value of nine and getting two boundaries; I warned against using values less than 9.5 to avoid that problem.

I absolutely love it!

Ok, so my code doesn’t close the face edge loop so to speak. I made a test and found this (green is created with C# code, the red is with the Gh component:

Fig 1. C# = not closed… (and no option to do so either AFAIK).
image

Gotta close it manually then. Here’s the current (unfixed) code that created the green Polyline(s):

var face_circumference = new double[m_F.Count];
Parallel.For(0, m_F.Count, i => //for (int i = 0; i < m_F.Count; i++)
  {
        // m_F = mesh Faces. m_V = mesh Vertices
        var point_triplet = new Point3d[3] { m_V[m_F[i].A], m_V[m_F[i].B], m_V[m_F[i].C] };;
        var pline = new Polyline(point_triplet); // TODO: Close loop!
        face_circumference[i] = pline.Length;
  });

The red loop (pictured above) is a “hole” which I found, hence the Sort component.

And yes, for different densities one would have to adjust the edge length properly.

// Rolf

OK, I see what’s going on. If you disable 'Closed (C)' in my GH version, the boundary matches yours.

Correct. You might want to enable preview on MEdges (Mesh Edges) to see the mesh faces. And I understand why you used Sort. I just avoided that problem by keeping the slider value at 9.5 or above. Cheers.

1 Like

Yes. I fixed the C# code so it closes the loop. The code fix:

Fixed version:
ConcaveHull_BorderWidth_Component_R1.2.gh (254.5 KB)

Have a nice weekend,
// Rolf

Hi @Joseph_Oster @RIL very nice solution to what it seems a more complex issue! Kind of reminds me of Alpha Shape.

I remember doing something similar to what Joseph did here:

There, I remember I used FaceBoundaries to get the polylines of faces. I believe it is native. Maybe FaceCircles could also be used for simplification/optimization purposes.