Connecting outermost dots with a single line?

Processing Libraries
9

Hi @clausneergaard,

Adding to the previous suggestions and replying to your question:

  • the Mesh library (already mentioned) has a Hull() class (example) – 2D only
  • the Hemesh library has a HEC_ConvexHull() class (example) – 3D only
  • the ComputationalGeometry library has QuickHull3D() class (example) – 3D only
  • the bRigid libray has BConvexHull() class (example) – 3D only
  • the giCentre Utils library has a ConvexHull() class (example below) – 2D only
####Check full documentation here --> http://gicentre.org/utils/reference/

add_library('gicentreUtils')

N = 70
A = 60
points = []

def setup():
    size(1000, 600, P2D)
    background(255)
    strokeWeight(5)
    randomSeed(6)
    smooth(8)
    
    #Display points
    for i in xrange(1, N + 1):
        theta = radians(270 / float(N)) * int(random(N))
        x = width/2 + cos(theta) * random(100, 200)
        y = height/2 + sin(theta) * random(100, 200)
        points.append(PVector(x, y))
        
    #Compute convex Hull
    hull = ConvexHull(points).getHull()
        
    #Draw convex hull edges
    strokeWeight(2)
    stroke(0)
    for i in xrange(len(hull)):
        v1 = hull[i]
        v2 = hull[(i+1)%len(hull)]
        line(v1.x, v1.y, v2.x, v2.y)
        
    #Draw points
    strokeWeight(5)
    stroke(66, 9, 195)
    for p in points:
        point(p.x, p.y)

That being said, if you are trying to make a shape out of a disparate / irregularly distributed 2d point cloud chances are that you are actually looking for a concave hull algorithm (not convex). In that case, I would suggest to use the alphaTriangulate2D() and getAlphaEdges() methods from the Hemesh library.

Example sketch (Python mode):

add_library('hemesh')

N = 70
A = 60
points = []

def setup():
    size(1000, 600, P2D)
    background(255)
    smooth(8)
    
    #Display points
    for i in xrange(1, N + 1):
        theta = radians(270 / float(N)) * int(random(N))
        x = width/2 + cos(theta) * random(100, 200)
        y = height/2 + sin(theta) * random(100, 200)
        points.append(WB_Point(x, y))
        
    #Compute alpha-triangulation
    triangulation = WB_Triangulate2D().alphaTriangulate2D(points)
    
    #Get alpha edges
    alphaEdges = triangulation.getAlphaEdges(A)
    tuplesA = zip(alphaEdges[::2], alphaEdges[1::2])
    
    
    #Draw Points
    stroke(66, 9, 195)
    strokeWeight(5)
    for p in points:
        point(p.x, p.y)
       
    #Draw Contours (alpha edges) 
    stroke(0)
    strokeWeight(2)
    for n, (i1, i2) in enumerate(tuplesA):
        p1 = points[i1]
        p2 = points[i2]
        line(p1.x, p1.y, p2.x, p2.y)

convaxconcave
convaxconcave1087×570 148 KB

Convex Hull with the giCentreUtils library (left) and Concave Hull with the Hemesh library (right)

5 Likes