# Connecting outermost dots with a single line?

**URL:** <https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395>\
**Category:** Libraries\
**Created:** [December 14, 2019, 12:49pm UTC](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395 "2019-12-14T12:49:08Z")\
**Posts on this page:** 1\
**Showing post:** 9

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [December 18, 2019, 8:55am UTC](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395/9 "2019-12-18T08:55:11Z")

</div>

Hi @clausneergaard,

Adding to the previous suggestions and replying to your question:

- the **Mesh** library (already mentioned) has a `Hull()` class ([example](http://leebyron.com/mesh/#newhull)) – 2D only
- the **Hemesh** library has a `HEC_ConvexHull()` class ([example](https://github.com/wblut/HE_Mesh/blob/d4133a7257857c5e97852da076b1be3948cb87d5/src/hemesh_creators/wblut/hemesh/HEC_ConvexHull.java)) – 3D only
- the **ComputationalGeometry** library has `QuickHull3D()` class ([example](http://thecloudlab.org/processing/reference/quickhull3d/QuickHull3D.html)) – 3D only
- the **bRigid** libray has `BConvexHull()` class ([example](https://github.com/djrkohler/bRigid/blob/8982f43d7c087427bf63659e29895a7b971dc52c/distribution/bRigid-2/download/bRigid/examples/ConvexHull/ConvexHull.pde)) – 3D only
- the **giCentre Utils** library has a `ConvexHull()` class (example below) – 2D only

```auto
####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):

```auto
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](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/6/674f9d33ff60781f69526b24ed77cb0274e80ea9.png)  
_Convex Hull with the giCentreUtils library (left) and Concave Hull with the Hemesh library (right)_

---

_[View the full topic](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395)._