Draw outline around points

Hi there!

I am trying to create a curve/polyline outline around a set of points (the blue line in the screenshot)

I have attempted to do this by using Delaunay edges which draws lines between each of the points but I can not seem to get an outline around all of it.

Thank you!


draw line around points.gh (227.0 KB)

This (general case) is a concave hull task (not convex). Given a planar pts List a concave hull is this:

But if you can optain the right mesh out of your collection (this could be quite tricky mind) then the naked edges (i.e. mesh face edges that are connected to a single face) are the segments of the polyline that you are after: use the join Curves component on them (or use the MShadow against a suitable plane).

Plus if your collection is exactly as shown (i.e portions of a rectangular grid) then you can get what you want by excluding faces (on a Delauney mesh) that have edges greater than the diagonal length OR using other ways without a mesh … but I’m not sure how to achieve this without code (but that is a personal opinion).

Anyway: see attached that is the fastest way to cut the mustard - via a del mesh - on that matter … but is pure C# code (the bad news).

Points_ConcaveHullViaDelMesh.gh (341.9 KB)

Note: you are responsible for entering the right L - the diagonal distance (if not > bananas on sight).

Note: this works on rectangular grids.

2 Likes

~49K points!


draw_line_around_points_2019Nov25a.gh (236.1 KB)

Boundary surface is faster than I expected but misses the tiny “holes” and flips the normal direction on two of the surfaces.

2 Likes

Thank you, I will have a look at both of them!

What if you explode the rectangles, make mid points and cull(all) duplicate points…?
Maybe faster… will try…

Edit:


draw_line_around_points_2019Nov25a_V2.gh (236.5 KB)
Surprisingly, CullPt is really slow. Made a pseudo “CullPt” funcion and removed duplicated segments… it is somewhat faster overall…

Still RUnion is working really fast, incredible!

Added the purple group to move nested curves (“regions”) to the same branch as their parent so that Boundary surface works correctly to show the holes.

Also converted all the polylines to NURBS curves to smooth the edges.


draw_line_around_points_2019Nov25b.gh (253.8 KB)

I integrated your optimization into this file, @maje90. It appears to yield identical results as RUnion and is certainly faster. Unfortunately, two of the four holes disappear when I use it!? I can’t see why but left it disabled for now. :frowning:

This works 10-15% faster (does the Del mesh inside C#) plus it can - as an option - advise you upon the L value to use.

On an I9 or some Ryzen 9 expect ~300 milliseconds for 50K points (a bit pathetic but anyway).

NOTE: As always it works only against a rectangular collection (for the general case you’ll need a proper Concave Hull C#). Does NOT make a check on planarity (for speed) and a check of a Plane fitted to points (for speed).

Points_ConcaveHullViaDelMesh_V1.gh (343.1 KB)

2 Likes