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