# Triangulation libraries issue (unwanted edge)

**URL:** <https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964>\
**Category:** Libraries\
**Created:** [December 4, 2020, 8:42pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964 "2020-12-04T20:42:42Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![nktlst](https://avatars.discourse-cdn.com/v4/letter/n/9dc877/32.png) [@nktlst](https://discourse.processing.org/u/nktlst)\
**Post date:** [December 4, 2020, 8:42pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/1 "2020-12-04T20:42:43Z")

</div>

Hi! Im playing around with triangulation libraries and got an issue where algorhythm adds one “unwanted” edge… Check image… i tried both libraries “trianglulate” and “mesh”… mesh did pretty good but with one unwanted edge and triangulate library looks dirty… but my shape is very simple and i stucked because want triangulate more complex shapes from svg files… Is this “unwanted” edge is specific of algorhytm? or i can fix it? Here is the code, sorry for messy codestyle, many test things inside…

image with renders and what i need from original shape.

 ![processing_triangulation](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/f/f02b58e2edb3cfc3303f8636e365f1b0e850bd40.png)

```auto
import org.processing.wiki.triangulate.*;
import megamu.mesh.*;

int pcount = 20;
PShape s;
PShape tria;
int childglobal; // num of point from svg
PShape source;
float[][] spoints = new float[8][2];
PVector p;
ArrayList triangles = new ArrayList();
ArrayList points = new ArrayList();

void setup() {
  size(1000, 800);
  s = loadShape("shape.svg");
  eat(s);
    triangles = Triangulate.triangulate(points);
  
}
void draw() {
  background(255);
  frameRate(3);
    for (int i = 0; i < points.size(); i++) {
    PVector p = (PVector)points.get(i);
    ellipse(p.x, p.y, 2.5, 2.5);
  }
  
  beginShape(TRIANGLES);
  for (int i = 0; i < triangles.size(); i++) {
    Triangle t = (Triangle)triangles.get(i);
    vertex(t.p1.x + 200, t.p1.y+ 300);
    vertex(t.p2.x + 200, t.p2.y+ 300);
    vertex(t.p3.x + 200, t.p3.y+ 300);
  }
  endShape(CLOSE);
  
  // PShape ini
  s = createShape();
  float[][] hpoints = new float[pcount][2];
  for (int row = 0; row < pcount; row++) {
    //for (int col = 0; col < 1; col++) {
      PVector pv = new PVector(random(100,500),random(100,500));
      hpoints[row][0] = pv.x;
      hpoints[row][1] = pv.y;
      //printArray(hpoints[row][col]);
    //}
  }
  
  println(childglobal);
    pushMatrix();
    translate(-100, -100);
    Delaunay myDelaunay = new Delaunay( spoints );
    float[][] myEdges = myDelaunay.getEdges();
    for(int i=0; i<myEdges.length; i++)
    {

      float startX = myEdges[i][0];
      float startY = myEdges[i][1];
      float endX = myEdges[i][2];
      float endY = myEdges[i][3];
      line( startX, startY, endX, endY );
    }
    popMatrix();

    shape(tria,0,0);
     
}

void eat(PShape source) {
  stroke(255, 0, 0);
  strokeWeight(2);
  tria = createShape();
  tria.beginShape();
  tria.fill(0, 255, 0, 50);
  for ( int c = 0; c < source.getChildCount(); ++c ) {
    println("c = " + source.getChildCount());
    PShape child = source.getChild(c);
    childglobal = child.getVertexCount();
    for ( int i = 0; i < child.getVertexCount(); ++i ) {
      println( "Distorting vertex: " + i + " of " + child.getVertexCount() );
       p = child.getVertex(i);
       println(p.x, p.y);
      //p.x += random( -100, 100 );
      //p.y += random( -100, 100 );
      //child.setVertex( i, p );
       // add points from svg to 2d array for create Delaunay
      println("childglobal = " + childglobal);
      println("i = " + i);
      spoints[i][0] = p.x + 600;
      spoints[i][1] = p.y + 100;
      points.add(p);
      tria.vertex(p.x, p.y);
      println("spoints count = " + child.getVertexCount());
      println(p.x, p.y);
      
    }
  }
  tria.endShape(CLOSE); 

}
```

---

<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 4, 2020, 11:29pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/2 "2020-12-04T23:29:03Z")

</div>

Hi @nktlst !

It would not have been a problem if you had asked your question in the previous thread but now that you have opened a new topic we’ll keep it here (no worries).

The diagram on the top right of your picture is correct because a triangulation forms triangles only based on input points. In other words, it is not “aware” of your polygon and only takes into account its vertices.

The [HE\_Mesh](https://github.com/wblut/HE_Mesh) library had a `triangulateConstrained2D()` and `triangulateConforming2D()` functions that would have come in handy in your case but unfortunately both methods seem to be broken at the moment.

One simple thing you could do is compute the center point for each triangle and check if it lies inside your polygon. If not, just remove the triangle.

```auto
//Function to determine whether a point is inside a shape/polygon or not
boolean contains(PShape shp, float x, float y){
    int N = shp.getVertexCount();
    boolean isInside = false;
    for (int i = 0; i < N; i++){
        PVector v1 = shp.getVertex((i+1)%N);
        PVector v2 = shp.getVertex(i);
        if ((v2.y > y) != (v1.y > y)){
            if (x < (v1.x - v2.x) * (y - v2.y) / (v1.y - v2.y) + v2.x){
                isInside = !isInside;
             }
         }
    }
    return isInside;
}

```

---

<div class="post-metadata">

**Author:** ![nktlst](https://avatars.discourse-cdn.com/v4/letter/n/9dc877/32.png) [@nktlst](https://discourse.processing.org/u/nktlst)\
**Post date:** [December 5, 2020, 10:14pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/3 "2020-12-05T22:14:17Z")

</div>

@solub thnx for reply!  
im trying to understand logic of your code example… sorry for that.

1. shp - is my shape i want to scan for unwanted triangle?
2. `PVector v1 = shp.getVertex((i+1)%N);` - what this line do? it scanning every (?) next point of my shp and then with P1 coords compares it with x/y ? i know what % do, but this is still hard to me to understand.
3. can you explain this formulas  
3.1 `((v2.y > y) != (v1.y > y))`  
3.2 `x < (v1.x - v2.x) * (y - v2.y) / (v1.y - v2.y) + v2.x`
4. ‘Mesh’ library draw lines… so im not sure how i can “delete” unwanted triangle in the next step…

thnx for your time and help! i dont want just copy/paste code, need some info 😉

---

<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 5, 2020, 11:52pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/4 "2020-12-05T23:52:55Z")

</div>

Sure, no problem !

1/ Yes, `shp` is your polygon. In this case the function assumes it is a `PShape` object. So you would need to convert your polygon to a `PShape` using [`createShape`](https://processing.org/reference/createShape_.html) as a first step. If you prefer instead to pass a list of vertices directly (the vertices of your polygon) you would need to change the function accordingly. Feel free to tell me what you like best.

2/ Yes, exactly. `v1` and `v2` are the end points of each edge being scanned. `(i+1)%N` makes sure to wrap around the array of vertices once the loop has come full circle.

 ![Screenshot 2020-12-06 004207](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/2/29febde2fbe000bc37a73ac961ce4dd468b0540a.png)

For example, in the picture above when `i` equals 6, `i+1` would be equal to 7. However there is no index 7 as the polygon only has 7 vertices (from 0 to 6). `(i+1)%N` makes sure to grab the first vertex instead (index `0`) so the edge `6-0` can be selected.

3/ You can find a detailed explanation [here](https://stackoverflow.com/questions/8721406/how-to-determine-if-a-point-is-inside-a-2d-convex-polygon/8721483) (2nd answer from top).

4/ I would suggest to try with HE\_Mesh library instead.

```auto
WB_Triangulation2D triangulation = WB_Triangulate.triangulate2D(yourVertices);
triangles = triangulation.getTriangles();

```

**edit** : A quick example in Python mode for reference.

> **Triangulate Polygon**
>
> ```auto
> add_library('hemesh')
> 
> verts = [PVector(131, 255),PVector(235, 267),PVector(328, 184),
> PVector(221, 146),PVector(198, 192),PVector(149, 90),
> PVector(77, 197)]
> 
> def setup():
> size(400, 400, P2D)
> background(255)
>     
> #Create a PShape from the list of vertices
> poly = createPShape(verts)
>     
> #Convert PVectors to WB_Points (Hemesh vector format)
> wb_points = [WB_Point(v.x, v.y) for v in verts]
>     
> #Triangulate points + get triangles
> triangulation = WB_Triangulate.triangulate2D(wb_points)
> triangles = triangulation.getTriangles() #!! Be careful, triangles is a 1D list of indices. We still need to group them by 3.
> 
> #Group triangles indices by 3
> it = iter(triangles)
> for tridex in zip(it, it, it):
> tripts = map(lambda i: verts[i], tridex) #Get 3 corresponding points
> cx, cy, _ = map(lambda f: sum(f)/3, zip(*tripts)) #compute centroid
> 
> #If centroid in inside polygon -> draw triangle
> if contains(poly, cx, cy):
> p1, p2, p3 = tripts
> triangle(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y)
>     
> #Draw polygon
> shape(poly)
>     
> noLoop()
> 
> def createPShape(verts):
>     
> '''Create a PShape from a list of vertices'''
>     
> poly = createShape()
> poly.beginShape()
> poly.stroke(20)
> poly.noFill()
> poly.strokeWeight(3)
> for v in verts:
> poly.vertex(v.x, v.y)
> poly.endShape(CLOSE)
>     
> return poly
>     
>     
> def contains(poly, x, y):
>     
> '''Returns a boolean.
> Determine whether a point lies inside a shape/polygon or not.'''
>     
> N = poly.getVertexCount()
> isInside = 0
>     
> for i in xrange(N):
> v1 = poly.getVertex((i+1)%N)
> v2 = poly.getVertex(i)
>         
> if (v2.y > y) != (v1.y > y):
> if x < (v1.x - v2.x) * (y - v2.y) / (v1.y - v2.y) + v2.x:
> isInside = not isInside
>                 
> return isInside
> 
> ```

![Screenshot 2020-12-06 012935](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/3/38d7d1f1d376a44ccae9bd280f06649eead7ff37.png)

---

<div class="post-metadata">

**Author:** ![nktlst](https://avatars.discourse-cdn.com/v4/letter/n/9dc877/32.png) [@nktlst](https://discourse.processing.org/u/nktlst)\
**Post date:** [December 6, 2020, 2:03pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/5 "2020-12-06T14:03:36Z")

</div>

1. Not sure which method i need, will play with current one.
2. thnx, its clear for me now!
3. and 4. — okay! need more time to analyse all this info)  
will back with new questions 😁

---

<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 6, 2020, 3:57pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/6 "2020-12-06T15:57:58Z")

</div>

Feel free to describe with more details what you are trying to achieve. It seems your question is related to your previous post about non-overlapping triangles but it’s hard to guess what your end goal is.

Depending on your objectives what is considered as the most suitable approach can drastically change (different routine, different library, …)

So if you have a description of what you have in mind specifically, maybe we can better identify your needs and provide you with more relevant suggestions.

---

<div class="post-metadata">

**Author:** ![nktlst](https://avatars.discourse-cdn.com/v4/letter/n/9dc877/32.png) [@nktlst](https://discourse.processing.org/u/nktlst)\
**Post date:** [December 6, 2020, 4:44pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/7 "2020-12-06T16:44:04Z")

</div>

Current task not really related to my previous topic, but progress in current task can help me better understand triangulation libraries, so i can back to previous one with overlapping…

This is my 2 ideas i want to achieve:

1. This topic:  
1.1 I want import any SVG to Processing and manipulate it: im already done with import SVG and creating copy from it with PShape…  
1.2 Then i want add triangulation effect to my PShape (from SVG)… and here i faced this problem with “unwanted” triangle…  
1.3 Then i want to learn how generate N-points (with random x,y) inside that custom shape to make random triangulation effect…
2. Previous topic: [Generate random not overlapping triangles](https://discourse.processing.org/t/generate-random-not-overlapping-triangles/25875)  
2.1 I want to learn generate patterns with random objects, so i decided to start from triangles because its not just squares inside which i can put any other objects, want create something more complex so i decided to start from triangles, and faced overlapping issue.  
2.2. What i really wanted here is: Setup how many random triangles i want to fill my sketch or shape, they not overlapping, they random sized and random placed.
3. Also have to decide which Triangulation library i can focus, because i faced 3 of them already… and they all old… and you said HE\_MESH is broken, but it more powerful… and i didnt find any documentations about HE\_MESH…

---

<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 6, 2020, 7:16pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/8 "2020-12-06T19:16:56Z")

</div>

> [@nktlst](#):
>
> Then i want to learn how generate N-points (with random x,y) inside that custom shape to make random triangulation effect…

For that you would have to:

- 
  1. Load your shape (either a `PShape` or a list of vertices)

- 
  1. Display points all over your canvas with Poisson Disk Sampling and select those that are inside your shape with the `contains` function

- 
  1. Triangulate the remaining points (both the shape vertices and selected points) and cull the triangles whose centroid is outside the shape. (still using the `contains` function)

- 
  1. Style your shape as you wish (colors, stroke-width, etc)

 ![Screenshot 2020-12-06 194711](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/2/25a82c6bf22bcb850d8a67e461b3ef158ff07c42.png)

> [@nktlst](#):
>
> Setup how many random triangles i want to fill my sketch or shape, they not overlapping, they random sized and random placed.

I believe all the answers are in the other thread already but feel free to ask questions again if you face some issue.

> [@nktlst](#):
>
> Also have to decide which Triangulation library i can focus, because i faced 3 of them already… and they all old… and you said HE\_MESH is broken, but it more powerful… and i didnt find any documentations about HE\_MESH…

I would strongly suggest to focus on Hemesh. This is probably the most extensive, stable and efficient Processing library dedicated to computational geometry (only the 2 methods I mentioned are broken but all the rest works like a charm).

It is indeed difficult to navigate between / get accustomed to all the functionalities as there is no documentation available but the library comes with a significant collection of introductory examples and the source code is always accessible on Github.

---

<div class="post-metadata">

**Author:** ![nktlst](https://avatars.discourse-cdn.com/v4/letter/n/9dc877/32.png) [@nktlst](https://discourse.processing.org/u/nktlst)\
**Post date:** [December 7, 2020, 1:08pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/9 "2020-12-07T13:08:08Z")

</div>

@solub thank you for all this information and decomposition to steps i need to research — its very helpful! hope ill post some result here soon 😅

---

<div class="post-metadata">

**Author:** ![nktlst](https://avatars.discourse-cdn.com/v4/letter/n/9dc877/32.png) [@nktlst](https://discourse.processing.org/u/nktlst)\
**Post date:** [December 8, 2020, 10:51pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/10 "2020-12-08T22:51:04Z")

</div>

Got some result. But not sure how to end last step.  
My pic.

 ![processing_triangles to remove](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/1/1c2e5c91e4bbbe0237523dadc97b25d3cebd16b3.png)

**My Theory (Is it right?)**

1. i have to get points from HE\_MESH “triangles” array…
2. for each 3 points (as triangle) calculate centroid

```auto
// finding triangle centroid formula
center.x = (p1.x + p2.x + p3.x)/3;
center.y = (p1.y + p2.y + p3.y)/3;

```

1. check if centroid inside my shape
2. if inside then remove this 3 points from “triangles” array.

I printed for test “triangles” array (first free numbers) and its returned something like “First triangle: [0, 1, 5]”. Seems like its not float/int coords of what i need… not sure what this 3 numbers are… and what i have to do next with that result… is special indices of HE\_MESH WB\_Points?

My HE\_MESH code

```auto
WB_Triangulation2D 
  triangulation=WB_Triangulate.triangulate2D(points);
  triangles=triangulation.getTriangles();// 1D array of indices of triangles, 3 indices per triangle
  edges=triangulation.getEdges();// 1D array of indices of triangulation edges, 2 indices per edge
  render.drawTriangle2D(triangles, points);

```

---

<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 8, 2020, 11:20pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/11 "2020-12-08T23:20:18Z")

</div>

1. Yes
2. Yes
3. Yes
4. No, you keep it as it is.

> [@nktlst](#):
>
> not sure what this 3 numbers are… is special indices of HE\_MESH WB\_Points?

Yes ! These are indeed indices of your `points` array list. You have to take them 3 by 3 and get the corresponding points to form triangles.

```auto
indices = [0, 1, 2, 1, 2, 3, 3, 2, 4, ...]
grouped_indices = [(0, 1, 2), (1, 2, 3), (3, 2, 4), ...]
triangles_coordinates = [(points[0], points[1], points[2]), (points[1], points[2], points[3]), (points[3], points[2], points[4]), ...]

```

Then, as you correctly guessed, you compute the center of each of these triangles. And if that center point lies inside your polygon, you draw the triangle with Processing [triangle](https://processing.org/reference/triangle_.html) function.

That is roughly what I wrote in the Python script I posted earlier (see above):

```auto
#Group triangles indices by 3
it = iter(triangles)
for tridex in zip(it, it, it):
    tripts = map(lambda i: verts[i], tridex) #Get 3 corresponding points
    cx, cy, _ = map(lambda f: sum(f)/3, zip(*tripts)) #compute centroid

    #If centroid in inside polygon -> draw triangle
    if contains(poly, cx, cy):
        p1, p2, p3 = tripts
        triangle(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y)

```

You could use Hemesh default renderer instead but then you would have first to remove from `triangles` the indices of the triangles whose center is **not** inside the polygon (the opposite of your point `4.`).

Does that make sense ?

---

<div class="post-metadata">

**Author:** ![nktlst](https://avatars.discourse-cdn.com/v4/letter/n/9dc877/32.png) [@nktlst](https://discourse.processing.org/u/nktlst)\
**Post date:** [December 9, 2020, 9:47pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/12 "2020-12-09T21:47:15Z")

</div>

1. I like that i can use Processing triangle function at last step!
2. not really understand why array includes nums like “0,1,5” — each of this this indices also contains coords inside?
3. i understand hopefully logic of your code, but need more time to research “iter” “map” “lambda” etc also its harder for me because i learning Java mode, not Python…

---

<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 10, 2020, 12:11am UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/13 "2020-12-10T00:11:33Z")

</div>

1. The array `triangles` has indeed a misleading name. It doesn’t really contains triangles but a series of **indices**. Those indices are similar to _addresses_, they are **pointing** to specific coordinates in the `points` array. Example:

 ![Screenshot 2020-12-10 004611](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/6/6a9f16eb72ab8d13e46dd1c81e8bd449ec61c6d4.png)

1. As you can see, the indices (`triangles`) are stored in a 1 dimensional array. This is confusing because one would expect them to be grouped by 3, like this:

- `(0, 1, 5), (1, 2, 0), (2, 1, 3), (1, 3, 4), (5, 4, 1)`

```auto
final PVector[] points = {
  new PVector(0, 200), 
  new PVector(180, 178), 
  new PVector(160, 300), 
  new PVector(240, 255),
  new PVector(210, 100), 
  new PVector(150, 0)
};

int[] triangles = {0, 1, 5, 1, 2, 0, 2, 1, 3, 1, 3, 4, 5, 4, 1};

for (int i = 0; i < triangles.length; i=i+3){
  PVector p1 = points[triangles[i]];
  PVector p2 = points[triangles[i+1]];
  PVector p3 = points[triangles[i+2]];
  
  float cx = (p1.x + p2.x + p3.x)/3;
  float cy = (p1.y + p2.y + p3.y)/3;
    
  //if (contains(poly, cx, cy)) {
  // triangle(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
  //}
  
}

```

---

<div class="post-metadata">

**Author:** ![nktlst](https://avatars.discourse-cdn.com/v4/letter/n/9dc877/32.png) [@nktlst](https://discourse.processing.org/u/nktlst)\
**Post date:** [December 11, 2020, 10:10pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/14 "2020-12-11T22:10:09Z")

</div>

One more question.  
Is here a way convert PVector to WB\_Point and vise versa?  
All HE\_MESH examples have no PVectors inside, seems like have to do job without PVectors.

For test if i try pass coords from one WB\_Point to another i got error “The field WB\_MutableCoordinate2D.x is not visible” and this problem occur when i try pass coords to my function which detecting points inside.

```auto
for (int t = 0; t < triangles.length; t++) {
    WB_Point p1;
    WB_Point p2;
    p1 = new WB_Point (points.get(triangles[t]));
    p2 = new WB_Point (p1.x, p1.y);
    //boolean inside = contains_tria(my_s, p1.x, p1.y);
    //printArray("p1 = " + p1);
    //println("Yes");
    //p1.y = triangles[t+1];
    // printArray("triangles" + " " + triangles[t]);
  }

```

---

<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 11, 2020, 11:14pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/15 "2020-12-11T23:14:43Z")

</div>

Can you post the entire script ?

The `contains` function (in its original state) doesn’t take a _point_ as input but _floats_: namely the `x` and `y` coordinates of a center point. With HEmesh just type `.xf()` or `.yf()` to access these values.

```auto
for (int i = 0; i < triangles.length; i=i+3){
  WB_Point p1 = points[triangles[i]];
  WB_Point p2 = points[triangles[i+1]];
  WB_Point p3 = points[triangles[i+2]];
  
  float cx = (p1.xf() + p2.xf() + p3.xf())/3;
  float cy = (p1.yf() + p2.yf() + p3.yf())/3;

```

---

<div class="post-metadata">

**Author:** ![nktlst](https://avatars.discourse-cdn.com/v4/letter/n/9dc877/32.png) [@nktlst](https://discourse.processing.org/u/nktlst)\
**Post date:** [December 11, 2020, 11:26pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/16 "2020-12-11T23:26:34Z")

</div>

Yeah. here it is. sorry for trash inside.

```auto
import wblut.core.*;
import wblut.geom.*;
import wblut.hemesh.*;
import wblut.math.*;
import wblut.nurbs.*;
import wblut.processing.*;
import java.util.List;

// for PDS >>>
int a = 0;
int RADIUS = 20; // PDS distance
ArrayList<PVector> plist; // PDS List of points

// For SVG / Shape
PShape s; // My SVG
PShape my_s; // Shape from SVG
int s_vcount; // for triangulation test

// for triangulation
WB_GeometryFactory gf=new WB_GeometryFactory();
WB_Render2D render;
//List<WB_Coord> points;
WB_Point point;
WB_Polygon polygon;
//WB_Point[] points;
ArrayList<WB_Point> points = new ArrayList<WB_Point>();
int[] triangles;
int[] edges;

void setup() {
  size(1000, 800, P2D);
  background(255);
  plist = poissonDiskSampling(RADIUS, 30);
  s = loadShape("shape.svg");
  eat(s); // eat SVG 
  render=new WB_Render2D(this);

}

void draw() {
   // Start of Poisson Disk Sampling >>>
  while (a < plist.size()) {
    stroke(0);
    noFill();
    ellipse(plist.get(a).x, plist.get(a).y, 1, 1);
    a++;
  }
   // <<< End of Poisson Disk Sampling
  
  // My shape
  pushMatrix();
  translate(width/2, height/2);
  shape(my_s,0,0,200,200);
  popMatrix();
  
  // check PSD point for inside
  for (int i = 0; i < plist.size(); i++) {
   PVector p = plist.get(i);
   boolean inside = contains(my_s, p.x, p.y);
   if (inside) {
     stroke(255,0,0);
     strokeWeight(4);
     point(p.x, p.y);
     point = new WB_Point (p.x,p.y);
     points.add(point);
     // points[i] = ??; // add inside point to triangulation array
   }
  }
  
 // check HE_MESH triangulation points point for inside
  //for (int t = 0; t < triangles.length; t++) {
  // WB_Point p1;
  // p1 = new WB_Point (points.get(triangles[t]));
  // //boolean inside = contains_tria(my_s, p1.x, p1.y);
  // //printArray("p1 = " + p1);
  // //println("Yes");
  // //p1.y = triangles[t+1];
  // // printArray("triangles" + " " + triangles[t]);
  //}
  
    // Triangulation
  //points= new ArrayList<WB_Coord>();
  //points=new WB_Point[s_vcount];
  //for (int i=0; i < s_vcount; i++) {
  // points[i] = source.nextPoint();
  //}
  
  // HE_MESH create polygon
  polygon=gf.createSimplePolygon(points);
  fill(0,0,255);
  render.drawPolygon2D(polygon);  

  
  WB_Triangulation2D 
  triangulation=WB_Triangulate.triangulate2D(points);
  triangles=triangulation.getTriangles();// 1D array of indices of triangles, 3 indices per triangle
  // println("First triangle: ["+triangles[0]+", "+triangles[1]+", "+triangles[2]+"]");
  edges=triangulation.getEdges();// 1D array of indices of triangulation edges, 2 indices per edge
   //println("First edge: ["+edges[0]+", "+edges[1]+"]");

  render.drawTriangle2D(triangles, points);
  //printArray(points);
}

void eat(PShape source) {
  stroke(255, 0, 0);
  strokeWeight(1);
  my_s = createShape();
  my_s.beginShape();
  my_s.noFill();
  for ( int c = 0; c < source.getChildCount(); ++c ) {
    PShape child = source.getChild(c);
    s_vcount = child.getVertexCount();
    for ( int i = 0; i < child.getVertexCount(); ++i ) {
      println( "Distorting vertex: " + i + " of " + child.getVertexCount() );
      PVector p = child.getVertex(i);
      my_s.vertex(p.x, p.y);
      point = new WB_Point (p.x,p.y);
      print(point);
      points.add(point);
    }
  }
  my_s.endShape(CLOSE); 
}

// Poisson Disk Sampling >>>
// https://sighack.com/post/poisson-disk-sampling-bridsons-algorithm
boolean isValidPoint(PVector[][] grid, float cellsize,
                     int gwidth, int gheight,
                     PVector p, float radius) {
  /* Make sure the point is on the screen */
  if (p.x < 0 || p.x >= width || p.y < 0 || p.y >= height)
    return false;

  /* Check neighboring eight cells */
  int xindex = floor(p.x / cellsize);
  int yindex = floor(p.y / cellsize);
  int i0 = max(xindex - 1, 0);
  int i1 = min(xindex + 1, gwidth - 1);
  int j0 = max(yindex - 1, 0);
  int j1 = min(yindex + 1, gheight - 1);

  for (int i = i0; i <= i1; i++)
    for (int j = j0; j <= j1; j++)
      if (grid[i][j] != null)
        if (dist(grid[i][j].x, grid[i][j].y, p.x, p.y) < radius)
          return false;

  /* If we get here, return true */
  return true;
}

void insertPoint(PVector[][] grid, float cellsize, PVector point) {
  int xindex = floor(point.x / cellsize);
  int yindex = floor(point.y / cellsize);
  grid[xindex][yindex] = point;
}

ArrayList<PVector> poissonDiskSampling(float radius, int k) {
  int N = 2;
  /* The final set of points to return */
  ArrayList<PVector> points = new ArrayList<PVector>();
  /* The currently "active" set of points */
  ArrayList<PVector> active = new ArrayList<PVector>();
  /* Initial point p0 */
  PVector p0 = new PVector(random(width), random(height));
  PVector[][] grid;
  float cellsize = floor(radius/sqrt(N));

  /* Figure out no. of cells in the grid for our canvas */
  int ncells_width = ceil(width/cellsize) + 1;
  int ncells_height = ceil(width/cellsize) + 1;

  /* Allocate the grid an initialize all elements to null */
  grid = new PVector[ncells_width][ncells_height];
  for (int i = 0; i < ncells_width; i++)
    for (int j = 0; j < ncells_height; j++)
      grid[i][j] = null;

  insertPoint(grid, cellsize, p0);
  points.add(p0);
  active.add(p0);

  while (active.size() > 0) {
    int random_index = int(random(active.size()));
    PVector p = active.get(random_index);
    
    boolean found = false;
    for (int tries = 0; tries < k; tries++) {
      float theta = random(360);
      float new_radius = random(radius, 2*radius);
      float pnewx = p.x + new_radius * cos(radians(theta));
      float pnewy = p.y + new_radius * sin(radians(theta));
      PVector pnew = new PVector(pnewx, pnewy);
      
      if (!isValidPoint(grid, cellsize,
                        ncells_width, ncells_height,
                        pnew, radius))
        continue;
      
      points.add(pnew);
      insertPoint(grid, cellsize, pnew);
      active.add(pnew);
      found = true;
      break;
    }
    
    /* If no point was found after k tries, remove p */
    if (!found)
      active.remove(random_index);
  }

  return points;
}
// <<< Poisson Disk Sampling

//Function to determine whether a point is inside a shape/polygon or not
boolean contains(PShape shp, float x, float y){
    int N = shp.getVertexCount();
    boolean isInside = false;
    for (int i = 0; i < N; i++){
        PVector v1 = shp.getVertex((i+1)%N);
        PVector v2 = shp.getVertex(i);
        if ((v2.y > y) != (v1.y > y)){
            if (x < (v1.x - v2.x) * (y - v2.y) / (v1.y - v2.y) + v2.x){
                isInside = !isInside;
             }
         }
    }
    return isInside;
}

//Function to determine whether a centroid of triangle is inside a shape/polygon or not
boolean contains_tria(PShape shp, float x, float y) {
    
  // WB_Point p1;
  // PVector p2;
  // PVector p3;
  // PVector center;
    
  // // finding triangle centroid formula
  // //center.x = (p1.x + p2.x + p3.x)/3;
  // //center.y = (p1.y + p2.y + p3.y)/3;
  //for (int tria = 0; tria < 3; tria++) {
    
  // for (int t = 0; t < triangles.length; t++) {
  // p1 = new WB_Point (points.get(triangles[t]));
  // printArray("p1 = " + p1);
  // println("Yes");
  // //p1.y = triangles[t+1];
  // // printArray("triangles" + " " + triangles[t]);
  // }
  //}
    
    int N = shp.getVertexCount();
    boolean isInside = false;

    
    for (int i = 0; i < N; i++){
        PVector v1 = shp.getVertex((i+1)%N);
        PVector v2 = shp.getVertex(i);
        if ((v2.y > y) != (v1.y > y)){
            if (x < (v1.x - v2.x) * (y - v2.y) / (v1.y - v2.y) + v2.x){
                isInside = !isInside;
             }
         }
    }
    return isInside;
}

```

---

<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 11, 2020, 11:27pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/17 "2020-12-11T23:27:50Z")

</div>

… and the `svg` file so I can test.

---

<div class="post-metadata">

**Author:** ![nktlst](https://avatars.discourse-cdn.com/v4/letter/n/9dc877/32.png) [@nktlst](https://discourse.processing.org/u/nktlst)\
**Post date:** [December 11, 2020, 11:32pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/18 "2020-12-11T23:32:47Z")

</div>

SVG

> **[shape.svg](https://drive.google.com/file/d/1C-8I-c0tMQIqAEvppA6UJzz87q-AcFBj/view?usp=sharing)**
>
> Google Drive file.

---

<div class="post-metadata">

**Author:** ![GoToLoop](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/gotoloop/32/86_2.png) [@GoToLoop](https://discourse.processing.org/u/GoToLoop)\
**Post date:** [December 11, 2020, 11:54pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/19 "2020-12-11T23:54:15Z")

</div>

## “shape.svg”:

```auto
<svg width="477" height="339" viewBox="0 0 477 339" fill="none" xmlns="http://www.w3.org/2000/svg">
<path d="M0 134.721L102.04 25.3823L300.505 0L477 161.08L310.026 231.857L230.688 143.019L135.728 339L0 134.721Z" fill="black"/>
</svg>

```

---

<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 12, 2020, 2:49pm UTC](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964/20 "2020-12-12T14:49:38Z")

</div>

I have added a `dividePLine()` function to your sketch in order to place `n` equidistant points along the edges of a shape. They kind of act as “attachment points” for the inner triangles and prevent them from overflowing on the edges of the shape.

The denser the Poisson Disk Sampling, the more points you will need along the edges.

 ![Screenshot 2020-12-12 152132](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/5/5a3ef91e838f0a7f6547b4a7d06d2563a080137e.png)

Alternatively, you could look for collisions between the edges of the triangles and the edges of the shape and draw a line to the intersection point when a collision is detected. You’ll find in the script an `intersect()` function for you to test out.

Please note that my experience with Java is close to zero and that the following is probably one of the finest Java pasta (👌) you will find around here.

```auto
import wblut.core.*;
import wblut.geom.*;
import wblut.hemesh.*;
import wblut.math.*;
import wblut.nurbs.*;
import wblut.processing.*;

int[] triangles;

PShape poly; 

ArrayList<WB_Point> verts = new ArrayList<WB_Point>();
ArrayList<WB_Point> PDSPoints;
ArrayList<WB_Point> contourPoints;

void setup(){
  size(1020, 760, P2D);
  background(255);
  smooth(8);
  noFill();
  
  //Store shape vertices in dedicated arrayList
  verts.add(new WB_Point(36.0, 307.0));
  verts.add(new WB_Point(311.0, 724.0)); 
  verts.add(new WB_Point(504.0, 327.0)); 
  verts.add(new WB_Point(664.0, 507.0)); 
  verts.add(new WB_Point(1005.0, 363.0));
  verts.add(new WB_Point(644.0, 35.0)); 
  verts.add(new WB_Point(243.0, 85.0));
  
  //Create a PShape from the list of vertices
  poly = createPShape(verts);
  
  //Distribute points across canvas (PDS)
  PDSPoints = poissonDiskSampling(20, 30);
  
  //Divide shape edges into N equidistant points
  contourPoints = dividePLine(verts, 200, true); 
  
  //Merge 3 arrayLists (vertices + PDSPoints + contourPoints)
  final ArrayList<WB_Point> points = new ArrayList<WB_Point>();
  for (int i = 0; i < verts.size(); i++) points.add(verts.get(i));
  for (int i = 0; i < PDSPoints.size(); i++) points.add(PDSPoints.get(i));
  for (int i = 0; i < contourPoints.size(); i++) points.add(contourPoints.get(i)); 

  //Triangulate points + get triangle indices
  WB_Triangulation2D triangulation = WB_Triangulate.triangulate2D(points);
  triangles = triangulation.getTriangles();
  
  //Group triangles indices by 3
  for (int i = 0; i < triangles.length; i=i+3){
    WB_Point p1 = points.get(triangles[i]);
    WB_Point p2 = points.get(triangles[i+1]);
    WB_Point p3 = points.get(triangles[i+2]);
  
    //Compute centroid coordinates
    float cx = (p1.xf() + p2.xf() + p3.xf())/3;
    float cy = (p1.yf() + p2.yf() + p3.yf())/3;
    
    //If centroid within polygon
    if (contains(poly, cx, cy)) {
      
      //(not mandatory) Look for intersections between triangle edges and polygon edges
      boolean isValid = true;
      
      //for (int j = 0; j < verts.length; j++){
      // WB_Point v1 = verts[j];
      // WB_Point v2 = verts[(j+1)%verts.length];
        
      // if (intersect(v1.xf(), v1.yf(), v2.xf(), v2.yf(), p1.xf(), p1.yf(), p2.xf(), p2.yf()) || 
      // intersect(v1.xf(), v1.yf(), v2.xf(), v2.yf(), p1.xf(), p1.yf(), p3.xf(), p3.yf()) || 
      // intersect(v1.xf(), v1.yf(), v2.xf(), v2.yf(), p2.xf(), p2.yf(), p3.xf(), p3.yf())) {
      // isValid = false;
      // break;
      // }
      //}
      
      //If no intersection -> draw triangle
      if (isValid) {
        triangle(p1.xf(), p1.yf(), p2.xf(), p2.yf(), p3.xf(), p3.yf());
      }
    }
  }
  

  //Draw shape
  shape(poly);
  
  //Draw contour points
  pushStyle();
  fill(255, 30, 60);
  for (WB_Point p: contourPoints) {
    ellipse(p.xf(), p.yf(), 8, 8);
  }
  popStyle();

  
  noLoop();

}

PShape createPShape(ArrayList<WB_Point> verts){
    
    poly = createShape();
    poly.beginShape();
    poly.stroke(20);
    poly.noFill();
    poly.strokeWeight(3);
    for (WB_Point v: verts){
        poly.vertex(v.xf(), v.yf());
    }
    poly.endShape(CLOSE);
    
    return poly;
}
    

boolean contains(PShape shp, float x, float y){
  
    int N = shp.getVertexCount();
    boolean isInside = false;
    for (int i = 0; i < N; i++){
        PVector v1 = shp.getVertex((i+1)%N);
        PVector v2 = shp.getVertex(i);
        if ((v2.y > y) != (v1.y > y)){
            if (x < (v1.x - v2.x) * (y - v2.y) / (v1.y - v2.y) + v2.x){
                isInside = !isInside;
             }
         }
    }
    
    return isInside;
}

boolean intersect(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
  
  // calculate the distance to intersection point
  float uA = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  float uB = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  
  // if uA and uB are between 0-1, lines are colliding
  if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {
    
    // optionally, draw a circle where the lines meet
    
    //float intersectionX = x1 + (uA * (x2-x1));
    //float intersectionY = y1 + (uA * (y2-y1));

    return true;
  }
  
  return false;
}

ArrayList<WB_Point> dividePLine(ArrayList<WB_Point> verts, int N, boolean closed){
    
    /// Returns a list of WB_Points.
    /// Divide a polyline into N equidistant points.///
    
    if (closed) {
        verts.add(verts.get(0));
        N = N+1;
    }

    ArrayList<WB_Point[]> edges = new ArrayList<WB_Point[]>();
    for (int i = 0; i < verts.size(); i++){
      WB_Point v1 = verts.get(i);
      WB_Point v2 = verts.get((i+1)%verts.size());
      edges.add(new WB_Point[] {v1, v2});
    }

    ArrayList<Float> tvals = getParameters(verts);
    
    ArrayList<WB_Point> points = new ArrayList<WB_Point>();
    points.add(verts.get(0));
    
 
    
    for (int n = 1; n < N-1; n++){
      
      float t = 1/float(N-1) * n;
      int idx = 0;
     
      for (int i = 0; i < tvals.size(); i++){
        
        float val = tvals.get(i);
        
        if (val < t) continue;
        
        idx = i-1;
        
        break;
      }
    
      WB_Point p1 = edges.get(idx)[0];
      WB_Point p2 = edges.get(idx)[1];
      float t1 = tvals.get(idx);
      float t2 = tvals.get((idx+1)%tvals.size());
      float itp = norm(t, t1, t2);
      
      points.add(p2.sub(p1).mul(itp).add(p1));
    }
        
    if (!closed){
      points.add(verts.get(verts.size()-1));
    }
        
    return points;
  
}

ArrayList<Float> getParameters(ArrayList<WB_Point> verts){
    
    /// Returns a list of floats.
    /// Compute the t-values of the provided coordinates.///
    
    ArrayList<Float> tvals = new ArrayList<Float>();
    tvals.add(0.0);
    
    for (int i = 1; i < verts.size(); i++){
      tvals.add(tvals.get(i-1) + (float)verts.get(i).getDistance(verts.get(i-1)));
    }
    
    for (int i = 0; i < tvals.size(); i++){
        tvals.set(i, tvals.get(i) / tvals.get(tvals.size()-1));
    }
        
    return tvals;
    
}

boolean isValidPoint(WB_Point[][] grid, float cellsize,
                     int gwidth, int gheight,
                     WB_Point p, float radius) {
                       
  /* Make sure the point is on the screen */
  if (p.xf() < 0 || p.xf() >= width || p.yf() < 0 || p.yf() >= height)
    return false;

  /* Check neighboring eight cells */
  int xindex = floor(p.xf() / cellsize);
  int yindex = floor(p.yf() / cellsize);
  int i0 = max(xindex - 1, 0);
  int i1 = min(xindex + 1, gwidth - 1);
  int j0 = max(yindex - 1, 0);
  int j1 = min(yindex + 1, gheight - 1);

  for (int i = i0; i <= i1; i++)
    for (int j = j0; j <= j1; j++)
      if (grid[i][j] != null)
        if (dist(grid[i][j].xf(), grid[i][j].yf(), p.xf(), p.yf()) < radius)
          return false;

  /* If we get here, return true */
  return true;
}

void insertPoint(WB_Point[][] grid, float cellsize, WB_Point point) {
  int xindex = floor(point.xf() / cellsize);
  int yindex = floor(point.yf() / cellsize);
  grid[xindex][yindex] = point;
}

ArrayList<WB_Point> poissonDiskSampling(float radius, int k) {
  int N = 2;
  /* The final set of points to return */
  ArrayList<WB_Point> points = new ArrayList<WB_Point>();
  /* The currently "active" set of points */
  ArrayList<WB_Point> active = new ArrayList<WB_Point>();
  /* Initial point p0 */
  WB_Point p0 = new WB_Point(random(width), random(height));
  WB_Point[][] grid;
  float cellsize = floor(radius/sqrt(N));

  /* Figure out no. of cells in the grid for our canvas */
  int ncells_width = ceil(width/cellsize) + 1;
  int ncells_height = ceil(width/cellsize) + 1;

  /* Allocate the grid an initialize all elements to null */
  grid = new WB_Point[ncells_width][ncells_height];
  for (int i = 0; i < ncells_width; i++)
    for (int j = 0; j < ncells_height; j++)
      grid[i][j] = null;

  insertPoint(grid, cellsize, p0);
  points.add(p0);
  active.add(p0);

  while (active.size() > 0) {
    int random_index = int(random(active.size()));
    WB_Point p = active.get(random_index);
    
    boolean found = false;
    for (int tries = 0; tries < k; tries++) {
      float theta = random(360);
      float new_radius = random(radius, 2*radius);
      float pnewx = p.xf() + new_radius * cos(radians(theta));
      float pnewy = p.yf() + new_radius * sin(radians(theta));
      WB_Point pnew = new WB_Point(pnewx, pnewy);
      
      if (!isValidPoint(grid, cellsize,
                        ncells_width, ncells_height,
                        pnew, radius))
        continue;
      
      points.add(pnew);
      insertPoint(grid, cellsize, pnew);
      active.add(pnew);
      found = true;
      break;
    }
    
    /* If no point was found after k tries, remove p */
    if (!found)
      active.remove(random_index);
  }

  return points;
}

```

[Next page](https://discourse.processing.org/t/triangulation-libraries-issue-unwanted-edge/25964.md?page=2)