# 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:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![clausneergaard](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/clausneergaard/32/7501_2.png) [@clausneergaard](https://discourse.processing.org/u/clausneergaard)\
**Post date:** [December 14, 2019, 12:49pm UTC](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395/1 "2019-12-14T12:49:08Z")

</div>

Hi all -

Does anyone know how to work with a way to connect the outermost randomly placed dots to make a shape?

E.g., if you make 25 random points on screen and there are 10 dots on the perimeter and 15 on the inside, I would like to connect the 10 outermost dots with a single line, defining the outline of the “shape”?

Any help is appreciated.  
Thanks.

---

<div class="post-metadata">

**Author:** ![kll](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/kll/32/964_2.png) [@kll](https://discourse.processing.org/u/kll)\
**Post date:** [December 14, 2019, 12:56pm UTC](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395/2 "2019-12-14T12:56:57Z")

</div>

[https://en.wikibooks.org/wiki/Algorithm\_Implementation/Geometry/Convex\_hull/Monotone\_chain](https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain)  
here i play with it:  
[Andrew's monotone chain algorithm](https://discourse.processing.org/t/andrews-monotone-chain-algorithm/5485/3) ,

better  
[Path around a perimeter](https://discourse.processing.org/t/path-around-a-perimeter/15059/4) ,

---

<div class="post-metadata">

**Author:** ![clausneergaard](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/clausneergaard/32/7501_2.png) [@clausneergaard](https://discourse.processing.org/u/clausneergaard)\
**Post date:** [December 14, 2019, 1:03pm UTC](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395/3 "2019-12-14T13:03:03Z")

</div>

Hey -

Thank you for your quick reply. It’s fascinating how many things people are researching these days … I am now wondering if there’s a tool built for Processing that automates many of these processes? Do you know about that?

I know, for instance, that for Grasshopper (add-on) for Rhino 3D, there’s theses plugins that does the trick for you …

Thanks.

---

<div class="post-metadata">

**Author:** ![kll](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/kll/32/964_2.png) [@kll](https://discourse.processing.org/u/kll)\
**Post date:** [December 14, 2019, 1:06pm UTC](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395/4 "2019-12-14T13:06:38Z")

</div>

you mean a library, for this i did not know, so i just copy the code into a processing test  
yes, might be,  
but if it uses a other name for that functionality, how you find it?

i think testing and describing all internal and external libraries  
add the java ones you just can load as a .jar  
might fill a book.

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [December 16, 2019, 7:38am UTC](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395/5 "2019-12-16T07:38:45Z")

</div>

> [@clausneergaard](#):
>
> connect the outermost randomly placed dots to make a shape?

The term of art for that is “convex hull” – and there are several tools that do it: the Mesh library, and openCV (I believe), and you can also just implement the algorithm directly.

[http://leebyron.com/mesh/](http://leebyron.com/mesh/)

> A Convex Hull is the encompassing shape around a group of points. As if you were to wrap a piece of string around all of the points. This is handy when doing collision tests on complex shapes, or finding the most extreme points within a dataset.

![hull](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/b/b25b773c29ab3e8ec03d641ca550630f8ccd58e6.png)

and

> **[GitHub - atduskgreg/Processing-Convex-Hull: An example of finding the convex...](https://github.com/atduskgreg/Processing-Convex-Hull)**
>
> An example of finding the convex hull containing a set of points. Algorithm from Computational Geometry by de Berg, et al - GitHub - atduskgreg/Processing-Convex-Hull: An example of finding the con...

For a recent related discussion see:

> [@Anyone knows how to use getConvexHull();?](https://discourse.processing.org/t/anyone-knows-how-to-use-getconvexhull/8268/2):
>
> Hi! If you look at the source code it seems like the method returns a new contour but you are not using it (not even storing it in a variable).

---

<div class="post-metadata">

**Author:** ![Lexyth](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/lexyth/32/7403_2.png) [@Lexyth](https://discourse.processing.org/u/Lexyth)\
**Post date:** [December 16, 2019, 9:36am UTC](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395/6 "2019-12-16T09:36:27Z")

</div>

Though Andrew’s Monotonous Chain was interesting, so i tried to implement a version using angles yesterday, but got stuck on the chains backtracking. Got lucky today and now it works like a charm 😅

So it should be relatively easy to implement it, if you follow the original (also because there‘s Java Code for it in the Wikipedia Page).

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [December 16, 2019, 5:46pm UTC](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395/7 "2019-12-16T17:46:07Z")

</div>

There is also a Java example of Monotone Chain here:

[https://en.wikibooks.org/wiki/Algorithm\_Implementation/Geometry/Convex\_hull/Monotone\_chain#Java](https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#Java)

which has an animation demonstrating the search method

[![](https://upload.wikimedia.org/wikipedia/commons/9/9a/Animation_depicting_the_Monotone_algorithm.gif) ](https://upload.wikimedia.org/wikipedia/commons/9/9a/Animation_depicting_the_Monotone_algorithm.gif)

…and a video demo of atduskgreg’s hull implementation which also shows the search method:

https://player.vimeo.com/video/43366054

---

<div class="post-metadata">

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

</div>

There‘s also a complete Java Code for it there 😉

---

<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)_

---

<div class="post-metadata">

**Author:** ![clausneergaard](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/clausneergaard/32/7501_2.png) [@clausneergaard](https://discourse.processing.org/u/clausneergaard)\
**Post date:** [December 28, 2019, 3:45pm UTC](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395/10 "2019-12-28T15:45:50Z")

</div>

Hello all -

Thanks for all your very interesting replies - I will definitely try out your suggestions. There’s a lot of good info, to get me going, thank you!

Best, Claus