Triangulation libraries issue (unwanted edge)

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 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.

//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;
}
1 Like

@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 :wink:

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 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.

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 (2nd answer from top).

4/ I would suggest to try with HE_Mesh library instead.

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

edit: A quick example in Python mode for reference.

Triangulate Polygon
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

3 Likes
  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 :grin:

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.

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
    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…

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)

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

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.

3 Likes

@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 :sweat_smile:

1 Like

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

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
// 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

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);
1 Like
  1. Yes
  2. Yes
  3. Yes
  4. No, you keep it as it is.

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.

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 function.

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

#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 ?

  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…
  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:

  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)

    But it is not the case by default so you have to do it yourself.
    In Python I combined iter() with zip() for that purpose but I would suggest not wasting your time searching for their specific meaning and focusing instead on how to implement that grouping logic in Java. Unfortunately I don’t know what is the best way to do this in Java, maybe @GoToLoop could help ?

    All I can come up with is this very naive interpretation:

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);
  //}
  
}
1 Like

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.

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]);
  }

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.

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;

Yeah. here it is. sorry for trash inside.

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;
}

… and the svg file so I can test.

SVG

“shape.svg”:

<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>
1 Like

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.

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 (:ok_hand:) you will find around here.

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;
}
2 Likes

@solub beautiful result! thank you for your help.