Concave hull is a very common problem.
I use the VB script from here:
https://www.grasshopper3d.com/forum/topics/connecting-points-in-sequence
It would be nice to have it in GH2.
1 Like
it is a very good idea, there are many methods
http://www.portailsig.org/content/sur-la-creation-des-enveloppes-concaves-concave-hull-et-les-divers-moyens-d-y-parvenir-forme
Alpha Shape
K-nearest
https://www.researchgate.net/publication/220868874_Concave_hull_A_k-nearest_neighbours_approach_for_the_computation_of_the_region_occupied_by_a_set_of_points
Alpha Concave Hull
https://www.google.fr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwiZxPOTyIfcAhXIShQKHRLpDrAQFgg4MAE&url=https%3A%2F%2Farxiv.org%2Fpdf%2F1309.7829&usg=AOvVaw3niXMWUfjpss7elOCUMHzc
Delaunay method
Suppress too big triangles
Here a script that shows differents implementations of Concave Hull
You need Alpha Shape, Clipper…
Concave Hull Methods.gh (50.0 KB)
15 Likes
David’s method delivers different results for very similar cases.
As for those profiles in the image: the middle one will always come out wrong even thought I slide the F input between different values. Sometimes I get a self-intersecting curve.
Thanks for putting these algorithms together laurent - extremely helpful reference.
Fantastic!
1 Like
Concave Hull, any updates ?
It would be great to have a rhino.geometry.polylinecurve.createconcavehull2d method in addition to the already existing createconvexhull2d. Thank you devs for all your hard work.
https://developer.rhino3d.com/api/rhinocommon/rhino.geometry.polylinecurve/createconvexhull2d
1 Like
concave_hull.gh (17.4 KB)Concave Hull (α-shape) component for Grasshopper (Python 3)
I’ve just wrapped up a Python 3 script for Grasshopper that builds concave hulls using Edelsbrunner’s α-shape criterion using openai. In case anyone wants the intuition before diving into the code:
- Project to 2-D – all points are flattened onto the XY-plane.
- Pairwise check – for every pair of points we imagine all circles of a chosen radius R that pass through that pair.
- α-edge test – if at least one of those circles is empty (it contains no other sample points), we keep the segment connecting the pair; otherwise we discard it.
- Polyline join – the surviving segments are curve-joined into one or more closed polylines → your concave hull(s).
- Single knob control – shrink R for a tighter fit that follows every nook and cranny; grow R and the result relaxes toward the classic convex hull.
Conceptually this is straight from Edelsbrunner et al.’s α-shape work (nice visual here: https://www.researchgate.net/figure/The-alpha-shape-criteria_fig2_341645060) and mirrors the approach described in CGAL’s docs (CGAL 6.0.1 - 2D Alpha Shapes: User Manual). Similar performance to the alphashape component from Milkbox.
1 Like
Hello all!
I wrote with ChatGPT a Python script using scipy Delaunay with a max_radius for accuracy.
scipyDelaunay 250703BC.gh (94.6 KB)
import Rhino
import scriptcontext as sc
import rhinoscriptsyntax as rs
import numpy as np
from scipy.spatial import Delaunay
# Inputs:
# pts: list of points (Point3d or Guids)
# max_radius: float
# plane: Rhino.Geometry.Plane
def alpha_shape(points, max_radius, plane):
if len(points) < 4:
return []
# Project to plane & get UV
uv_coords = []
for pt in points:
pt_on_plane = plane.ClosestPoint(pt)
success, u, v = plane.ClosestParameter(pt_on_plane)
if success:
uv_coords.append([u, v])
coords = np.array(uv_coords)
tri = Delaunay(coords)
edge_count = {}
for ia, ib, ic in tri.simplices:
pa = coords[ia]
pb = coords[ib]
pc = coords[ic]
a = np.linalg.norm(pb - pc)
b = np.linalg.norm(pa - pc)
c = np.linalg.norm(pa - pb)
s = (a + b + c) / 2.0
area = max(s * (s - a) * (s - b) * (s - c), 1e-10)
area = np.sqrt(area)
circum_r = (a * b * c) / (4.0 * area)
if circum_r < max_radius:
edges = [(ia, ib), (ib, ic), (ic, ia)]
for edge in edges:
e = tuple(sorted(edge))
if e in edge_count:
edge_count[e] += 1
else:
edge_count[e] = 1
# Keep edges used only once
boundary_edges = [e for e, count in edge_count.items() if count == 1]
# Build adjacency dictionary
adj = {}
for e in boundary_edges:
adj.setdefault(e[0], []).append(e[1])
adj.setdefault(e[1], []).append(e[0])
# Find all loops
visited = set()
polylines = []
for start in adj.keys():
if start in visited:
continue
loop = [start]
visited.add(start)
current = start
prev = None
while True:
neighbors = adj[current]
next_pt = None
for n in neighbors:
if n != prev and n not in visited:
next_pt = n
break
if next_pt is None:
if len(loop) > 2 and loop[0] in adj[current]:
loop.append(loop[0]) # Close loop
break
loop.append(next_pt)
visited.add(next_pt)
prev, current = current, next_pt
if len(loop) >= 4:
# Convert to 3D points
poly_pts = []
for idx in loop:
uv = coords[idx]
pt3d = plane.PointAt(uv[0], uv[1])
poly_pts.append(pt3d)
polyline = Rhino.Geometry.Polyline(poly_pts)
if polyline.IsValid and polyline.IsClosed:
polylines.append(polyline.ToNurbsCurve())
return polylines
# --- Coerce points ---
pts_fixed = []
for p in pts:
if isinstance(p, Rhino.Geometry.Point3d):
pts_fixed.append(p)
else:
pt = rs.coerce3dpoint(p)
if pt:
pts_fixed.append(pt)
# --- Run function ---
curves = alpha_shape(pts_fixed, max_radius, plane)
a = curves
I need some help:
The script works great for a single list of points and a single plane, but I cannot make it work when I have several lists of points and several planes.
Can anyone improve it?
Thanks!