Visual creation of a triangle-filled circle

Programming Questions

arthur.es..

Visual creation of a triangle-filled circle

in Programming Questions • 2 months ago

Hello,

I have some troubles coding a sketch (using processing 2 with the Pshape library). Basically, what I want to do is a code that generate a visual pattern, something that looks a lot like the logo for the creative applications logo: I want the shape of an ellipse to be filled with triangles, each of them with a different color, maybe even with radiants (one color per vertex).

The method I choose for this is to calculate the area of the ellipse, then try to calculate the area of every triangle I create, add them all until it sums up to the area of the ellipse.

So, here's my code:

int num = 200; //just used to set up the arrays
PShape s[] = new PShape[num]; //the triangle
float x[] = new float[num];
float y[] = new float[num]; //its coordinates
float v_x[][] = new float[num][num];
float v_y[][] = new float[num][num]; //the coordinates of every vertex that has been created this far
float ray; //the radius of the circle
float aire_cercle; //the area of the circle
float aire_tri_totale; //the addition of each and every triangle's area
float aire_tri; //the being-created triangle's area
int t;
int n_vertex;
int i;
void setup() {
size(800, 600, P2D);
frameRate(8); //I like things to go slow at first, so I can understand what's happening
fill(80, 124, 132, 90);
stroke(255);
ray = 0.5*(height/1.2);
background(0);
//basic setup, nothing interesting here, I just set the radius of my circle
}
void draw() {
translate(width/2, height/2); // I want things to start from the center of the screen
aire_cercle = (ray*ray)*PI; //That's the area of my ellipse
println(aire_cercle);
//I want triangles to be created as long as their area do not match the ellipse's area
while (aire_tri_totale < aire_cercle) {
s[t] = createShape(); //we create a new shape
beginShape();
for (i = 0; i < 3; i++) { //i is the number of the vertex being created
if (t == 0) { //if this is the first shape, she can start wherever she wants
x[i] = random(-ray, ray);
y[i] = random(-ray, ray);
}
else { //else, it will have to merge two of its three vertices to the previous shape
if (i == 0) {
x[i] = v_x[t-1][ceil(random(0, 1))]; //let's choose a vertex
y[i] = v_y[t-1][ceil(random(0, 1))];
}
else if (i ==1) {
x[i] = v_x[t-1][ceil(random(1, 2))]; //and another one
y[i] = v_y[t-1][ceil(random(1, 2))];
}
else {
//and finally, the third one is random within a certain range
//(so that there ain't one big shape taking all of the place)
x[i] = random(x[i-1]-ray/8, x[i-1]+ray/8);
y[i] = random(y[i-1]-ray/8, y[i-1]+ray/8);
}
}
v_x[t][i] = x[i];
v_y[t][i] = y[i];
//every vertice's coordinates gets to be stocked
vertex(x[i], y[i]); //and is created
}
endShape(CLOSE);
for (i = 2; i > 0; i--) {
aire_tri += abs(((x[i]*y[i-1]) - (x[i-1]*y[i]))/2);
/*
I found this formula on a forum to calculate the area of a polygon. I can't really understand what
it's doing though, moreover seeing if something wrong...
As I recall, it is suppose to "go back" to each vertex, multiplying one of its coordinates with
the other of the previous one, divising it all by 2...
Nah, I can't even understand what I'm saying...
*/
}
aire_tri_totale += aire_tri;
t++;
println(aire_tri_totale);
}
noLoop();
}

And as you can see... It's not working...

I have absolutely no idea what's going wrong, since the problem, I guess, lies in the part where the area is being calculated and that I can barely look without crying blood. Have I mentioned that I am a total failure when it comes to maths?

It even seems like the triangles a getting bigger every time one is created, which is totally unwanted, of course...

That's why I'm turning it to you, asking for help. As I am in a bit of a hurry, I would love to have someone giving me an hand on this.

Sorry if my english is a bit approximative, frenchman here, speaking.

Au revoir et merci d'avance!

Edit: I almost forgot, another issue, I would like vertices not to be created within a pre-existing triangle. Something like a hit-test system should do the trick, however I find myself incapable of creating, or at least, incorporate a thing like that

Replies(6)

asimes

Re: Visual creation of a triangle-filled circle

2 months ago

I would say the first step is to make the bounding polygon (looks like they are using a 15 sided one) and learn how point in polygon testing works. Here is a polygon maker:

int radius = 200;
int numSides = 15;
float[] boundingX = new float[numSides];
float[] boundingY = new float[numSides];
void setup() {
size(600, 600);
float theta = 0;
float thetaInc = TWO_PI/numSides;
for (int i = 0; i < numSides; i++) {
boundingX[i] = width/2+cos(theta)*radius;
boundingY[i] = height/2+sin(theta)*radius;
theta += thetaInc;
}
}
void draw() {
background(255);
beginShape();
for (int i = 0; i < numSides; i++) vertex(boundingX[i], boundingY[i]);
endShape(CLOSE);
}

The idea then is to use boundingX and boundingY as a list of sorted points (going clockwise). Because they are sorted, they also describe all of the edges of the polygon. For example:

line(boundingX[0], boundingY[0], boundingX[1], boundingY[1]);

If you make a random point and want to test if it is within the edges of the polygon then you have to pretend the point is a line. The line goes from where the point actually is to somewhere arbitrarily far. If this line intersects one of the polygon's edges the point is inside the polygon, otherwise it is outside. Here is an example:

int radius = 200;
int numSides = 15;
float[] boundingX = new float[numSides];
float[] boundingY = new float[numSides];
float randomX, randomY;
void setup() {
size(600, 600);
float theta = 0;
float thetaInc = TWO_PI/numSides;
for (int i = 0; i < numSides; i++) {
boundingX[i] = width/2+cos(theta)*radius;
boundingY[i] = height/2+sin(theta)*radius;
theta += thetaInc;
}
randomX = random(width);
randomY = random(height);
}
void draw() {
background(255);
beginShape();
for (int i = 0; i < numSides; i++) vertex(boundingX[i], boundingY[i]);
endShape(CLOSE);
// This is the random point
ellipse(randomX, randomY, 3, 3);
// This is thinking of the point as a line to another point arbitrarily far away
line(randomX, randomY, width, randomY);
}

Edit: I did not include the line to line intersection code, that can be found by searching the forum or online: http://wiki.processing.org/w/Line-Line_intersection

arthur.es..

Re: Visual creation of a triangle-filled circle

2 months ago

Thank you for your reply asimes.

I've made some little progress. No it... Kind of... Still doesn't work.

But I've managed to get how does the line-segment intersection function works, and so I've tried to use it in order to create a collision test function that would do the trick.

I'm having issues though, as I think the first half of it works (finding out if the point is within the bounding polygon) but not the second half (finding out if it is within another triangle already made).

Anyway, here's my code:

float ray;
int num = 200;
int num_sides = 15;
float[][] boundingX = new float[num_sides][2];
float[][] boundingY = new float[num_sides][2];
float[][][] s_x = new float[num][num_sides][3];
float[][][] s_y = new float[num][num_sides][3];
float randomX, randomY, theta, thetaInc;
PVector line_test;
int i;
int t;
String coll_test;
int lines_crossed;
int cycle = 0;
void setup() {
size(800, 600, P2D);
ray = (height/2)*0.9;
theta = 0;
thetaInc = TWO_PI/num_sides;
background(0);
stroke(255);
noFill();
frameRate(2);
coll_test = "NOT_OK";
//creating the bounding polygon
beginShape();
for (t = 0; t < num_sides; t++) {
for (int i = 0; i <= 1; i++) {
if (i == 0 && t > 0) {
boundingX[t][i] = boundingX[t-1][i+1];
boundingY[t][i] = boundingY[t-1][i+1];
}
else {
boundingX[t][i] = (width/2+cos(theta)*ray);
boundingY[t][i] = (height/2+sin(theta)*ray);
theta += thetaInc;
}
}
}
endShape(CLOSE);
}
void draw() {
for (t = 0; t < num_sides; t++) {
beginShape();
if (cycle == 0) { //The first cycle will be the same as the bounding polygon
for (i = 0; i < 2; i ++) {
s_x[cycle][t][i] = boundingX[t][i];
s_y[cycle][t][i] = boundingY[t][i];
}
}
//Then we get to the real point
for (i = 0; i <= 2; i ++) {
//The very first point of every triangle wiil be the last of the previous one
if (i == 0 && cycle != 0) {
s_x[cycle][t][i] = s_x[cycle-1][t][2];
s_y[cycle][t][i] = s_y[cycle-1][t][2];
}
if (i == 1 && cycle != 0) {
s_x[cycle][t][i] = s_x[cycle-1][t][1];
s_y[cycle][t][i] = s_y[cycle-1][t][1];
}
if (i == 2) {
//I wanted to go in it with a while loop, but it makes my program runs on forever, something must be wrong with my collision test function...
//while(coll_test != "OK"){
s_x[cycle][t][i] = random(min(s_x[cycle][t][i-2], s_x[cycle][t][i-1])-50, max(s_x[cycle][t][i-2], s_x[cycle][t][i-1])+50);
s_y[cycle][t][i] = random(min(s_y[cycle][t][i-2], s_y[cycle][t][i-1])-50, max(s_y[cycle][t][i-2], s_y[cycle][t][i-1])+50);
coll_test = test_collision(s_x[cycle][t][i], s_y[cycle][t][i]);
println(coll_test);
//}
}
vertex(s_x[cycle][t][i], s_y[cycle][t][i]);
}
endShape(CLOSE);
}
cycle ++;
}
//Line-segment intersection
PVector segIntersection(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4)
{
float bx = x2 - x1;
float by = y2 - y1;
float dx = x4 - x3;
float dy = y4 - y3;
float b_dot_d_perp = bx * dy - by * dx;
if (b_dot_d_perp == 0) {
return null;
}
float cx = x3 - x1;
float cy = y3 - y1;
float t = (cx * dy - cy * dx) / b_dot_d_perp;
if (t < 0 || t > 1) {
return null;
}
float u = (cx * by - cy * bx) / b_dot_d_perp;
if (u < 0 || u > 1) {
return null;
}
return new PVector(x1+t*bx, y1+t*by);
}
//This function just helps my code being a bit more understandable by
//calling one after the other the collision test functions
String test_collision(float s_x, float s_y) {
String test_bounding;
String test_poly;
test_bounding = testBounding(s_x, s_y); //let's see if it's inside the bounding poly
if (test_bounding == "INSIDE_BOUNDING") { //if it is
test_poly = testPoly(s_x, s_y); //let's see if it is in another triangle
if (test_poly == "OK") { //and if not
return"OK"; //you're good to go!
}
else {
return "NOT_OK";
}
}
else {
return "NOT_OK";
}
}
//Used to test if the point is within the bouding polygon
String testBounding(float s_x, float s_y) {
for (int u = 0; u < num_sides; u++) {
for (int i = 1; i <= 1; i++) { //each side of the bounding is decomposed as side0.vertex0, side0.vertex1, side1.vertex0 (the same as the one before), etc...
line_test = segIntersection(s_x, s_y, width, s_y, boundingX[u][i-1], boundingY[u][i-1], boundingX[u][i], boundingY[u][i]);
//So we try an intersection test with every side of the bounding gon. If it crosses 2 sides, then it's outside.
//If it only cross on, then it's inside
if (line_test == null) { //each time it crosses a side, the function returns null
lines_crossed ++;
}
}
}
if (lines_crossed % 2 == 0) {
return "INSIDE_BOUNDING";
}
else {
return "OUTSIDE_BOUNDING";
}
}
//Used to test if the point is within another triangle
String testPoly(float x, float y) {
PVector poly_test;
//We will basically do the same thing as in the first test. Only this time we have to run it for every side of every triangle made. Yummy.
//The triangles goes that way cycle0.side0.vertex0, cycle0.side0.vertex1, cycle0.side0.vertex2, cycle0.side1.vertex0, etc...
//The cycle value takes one when every side has a polygon on it, so every 15 if num_sides is 15
//Which gives us three for loops right?
for (int d = 0; d <= cycle; d++) { //The cycle loop
for (int u = 0; u < num_sides; u++) { //The side loop
for (int j = 1; j <= 2; j++) { //The vertex loop. Starts to one so I can send the previous vertex's coordinates
poly_test = segIntersection(x, y, width, y, s_x[d][u][j-1], s_y[d][u][j-1], s_x[d][u][j], s_y[d][u][j]);
//and every times it gave us back null
if (poly_test == null) {
lines_crossed ++;
}
}
//Once we've tested all the lines of the polygon
if (lines_crossed % 2 != 0) {
return "NOT_OK";
}
}
}
//But if we've finished testing every line of every polygon of every cycle and it was inside noone
return "OK";
}

So, any ideas how to get this working?

Edit: Also, I just noticed that there is another problem. Every triangle seems to have a point attached to the bounding polygon, even if we're supposed to be far from the first iteration of the main loop. That's bad :(

asimes

Re: Visual creation of a triangle-filled circle

2 months ago

I don't want to sound too harsh, but your code has too many global variables, the indices of the arrays are hard to follow, and it does not do what you want so I did not try to modify it. I think it needed to separate the logic into functions because what you are trying to do is complicated.

It also is possible to model what you want with a Polygon class. The same class can be used for the bounding polygon as well as the triangles (they don't have to be triangles in the code below, any polygon will work).

I did not try to implement any code that creates the triangles in a clever way. I just showed how to create an arbitrary number of random ones. The pointInPolygon() function below can be used as a test for the bounding polygon or any of the triangles (or any other kind of polygon if you need them).

To test this out, click the mouse. Every time you do that the sketch is redrawn showing the bounding polygon, any triangles made in setup() (they are currently commented out), the random point created, and its intersection behavior.

Let me know if you have any questions:

ArrayList<Polygon> polys = new ArrayList<Polygon>();
void setup() {
size(600, 600);
noFill();
stroke(255);
// Bounding polygon
polys.add(new Polygon(15, height/2*0.9));
// Examples of a triangles for later
/* for (int i = 0; i < 3; i++) {
PVector[] example = new PVector[3];
example[0] = new PVector(random(width), random(height));
example[1] = new PVector(random(width), random(height));
example[2] = new PVector(random(width), random(height));
polys.add(new Polygon(example));
} */
drawPolygons();
}
void draw() {
// Empty for now, I'd recommed using mousePressed() for testing
}
// This is for testing adding a new point
void mousePressed() {
// Redraw so you can see what is going on
drawPolygons();
PVector newPoint = new PVector(random(width), random(height)); // Make a random point
ellipse(newPoint.x, newPoint.y, 5, 5); // See the random point
// 0 is the index of the bounding polygon, all other polygons will have a higher index
println("Is inside bounding polygon = "+pointInPolygon(newPoint, 0));
// If any triangles exists, test them separately like this (not a problem if none exist)
for (int i = 1; i < polys.size(); i++) println("Is inside triangle "+i+" = "+pointInPolygon(newPoint, i));
}
// This is intended to manage your bounding polygon and the triangles
class Polygon {
PVector[] vertices;
// This constructor is intended for the bounding polygon
Polygon(int inNum, float radius) {
vertices = new PVector[inNum];
float theta = -HALF_PI; // I changed this from 0 so that the polygon points up
float thetaInc = TWO_PI/inNum;
for (int i = 0; i < inNum; i++) {
vertices[i] = new PVector(width/2+cos(theta)*radius, height/2+sin(theta)*radius);
theta += thetaInc;
}
}
// This constructor is for polygons with specific vertices (probably triangles)
Polygon(PVector[] inVertices) {
vertices = inVertices;
}
}
void drawPolygons() {
background(0);
// For each polygon...
for (int i = 0; i < polys.size(); i++) {
Polygon iPoly = polys.get(i);
// ...draw a shape based on its vertices
beginShape();
for (int j = 0; j < iPoly.vertices.length; j++) {
PVector jVertex = iPoly.vertices[j];
vertex(jVertex.x, jVertex.y);
}
endShape(CLOSE);
}
}
PVector segIntersection(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
float bx = x2-x1;
float by = y2-y1;
float dx = x4-x3;
float dy = y4-y3;
float b_dot_d_perp = bx*dy-by*dx;
if (b_dot_d_perp == 0) return null;
float cx = x3-x1;
float cy = y3-y1;
float t = (cx*dy-cy*dx)/b_dot_d_perp;
if (t < 0 || t > 1) return null;
float u = (cx*by-cy*bx)/b_dot_d_perp;
if (u < 0 || u > 1) return null;
return new PVector(x1+t*bx, y1+t*by);
}
boolean pointInPolygon(PVector inP, int inIndex) {
int numIntersections = 0;
line(inP.x, inP.y, width, inP.y); // See the point as a line for the bounding test
// Test lines of the bounding polygon for intersection
Polygon inPoly = polys.get(inIndex);
for (int i = 0; i < inPoly.vertices.length-1; i++) {
PVector intersection = segIntersection(
inP.x, inP.y, width, inP.y, /* In point to arbitrary point */
inPoly.vertices[i].x, inPoly.vertices[i].y, /* Vertex i of polygon */
inPoly.vertices[i+1].x, inPoly.vertices[i+1].y); /* Vertex i+1 of polygon */
if (intersection != null) {
numIntersections++;
ellipse(intersection.x, intersection.y, 5, 5); // See the intersection
}
}
// There is still one case left to test for
PVector intersection = segIntersection(
inP.x, inP.y, width, inP.y, /* In point to arbitrary point */
inPoly.vertices[inPoly.vertices.length-1].x, inPoly.vertices[inPoly.vertices.length-1].y,
inPoly.vertices[0].x, inPoly.vertices[0].y);
if (intersection != null) {
numIntersections++;
ellipse(intersection.x, intersection.y, 5, 5); // See the intersection
}
return (numIntersections%2 == 1); // If the number of intersections is odd, return true
}

asimes

Re: Visual creation of a triangle-filled circle

2 months ago

I should have pointed out earlier that in general you don't want to only test if there was an intersection for bounding tests. It is possible that this happens:

- The polygon is in the center of the screen

- The random point is to the left of the polygon (not inside)

- The arbitrary point is set to be to the right of the polygon (not inside)

- The line from the random point to the arbitrary point intersects the polygon twice!

What you actually want to test when placing a random point is if the number of intersections is even or odd. If it is odd then the point is in the polygon.

arthur.es..

Re: Visual creation of a triangle-filled circle

2 months ago

Well... Thank you for this, you obviously spent a lot of time trying to help me, so, here I am, very grateful.

Though... Herm... Problem is... I don't understand the beginning of a bit of what you did there...

I mean I've read the comments, ok, I think I got what you're doing, the fact that you have to count the number of intersections was something I found out by myself, and I can see that your way of doing things is a lot more precise and short (concise? does it even mean something in english?)

But I'm just kinda lost here. I mean, where am I supposed to give the program instructions about creating the vertices of the triangle? I guess in the constructor you made for it, but how? Am I supposed to put some return like in a function?

Once again I wouldn't like to sound unthankful, as your help is very welcome. Sorry if I ask for a lot

asimes

Re: Visual creation of a triangle-filled circle

2 months ago

Well, that depends on how you want to add triangles. There is not only one way to do it. I could not figure out what you wanted to do in the last code you posted so I didn't implement it.

If you pay close attention to the logo (from your first post) it seems very unlikely that the points were randomly placed. It looks more like they placed the points on a trianglular grid and then randomly offset the points. If you were to do something similar then you could make triangles following two rules:

- Every vertex of the bounding polygon should form a triangle by connecting to its neighbor (probably clockwise order) and the closest random point in the center.

- Every random point should be a connection of six triangles (assuming it is a triangular grid). Even though the grid is randomly offset, you can pretend it is not when making the triangles.

If you have any specific questions about my code I will try to explain. I think it will make things much easier for you to use functions that don't differentiate between the bounding polygon and the triangles so much. Otherwise you'll end up with two very similar copies of the same code for functions.

Here is an example of making a triangle that uses the bounding polygon:

ArrayList<Polygon> polys = new ArrayList<Polygon>();
void setup() {
size(600, 600);
noFill();
stroke(255);
polys.add(new Polygon(15, height/2*0.9));
}
void draw() {
drawPolygons();
}
void mousePressed() {
PVector newPoint = new PVector(random(width), random(height));
if (pointInPolygon(newPoint, 0)) {
println("Is inside the bounding polygon");
// The random point was valid, add a triangle
PVector[] example = new PVector[3];
example[0] = new PVector(polys.get(0).vertices[0].x, polys.get(0).vertices[0].y);
example[1] = new PVector(polys.get(0).vertices[1].x, polys.get(0).vertices[1].y);
example[2] = new PVector(newPoint.x, newPoint.y);
polys.add(new Polygon(example));
}
else println("Outside the bounding polygon");
}
class Polygon {
PVector[] vertices;
Polygon(int inNum, float radius) {
vertices = new PVector[inNum];
float theta = -HALF_PI;
float thetaInc = TWO_PI/inNum;
for (int i = 0; i < inNum; i++) {
vertices[i] = new PVector(width/2+cos(theta)*radius, height/2+sin(theta)*radius);
theta += thetaInc;
}
}
Polygon(PVector[] inVertices) {
vertices = inVertices;
}
}
void drawPolygons() {
background(0);
for (int i = 0; i < polys.size(); i++) {
Polygon iPoly = polys.get(i);
beginShape();
for (int j = 0; j < iPoly.vertices.length; j++) {
PVector jVertex = iPoly.vertices[j];
vertex(jVertex.x, jVertex.y);
}
endShape(CLOSE);
}
}
PVector segIntersection(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
float bx = x2-x1;
float by = y2-y1;
float dx = x4-x3;
float dy = y4-y3;
float b_dot_d_perp = bx*dy-by*dx;
if (b_dot_d_perp == 0) return null;
float cx = x3-x1;
float cy = y3-y1;
float t = (cx*dy-cy*dx)/b_dot_d_perp;
if (t < 0 || t > 1) return null;
float u = (cx*by-cy*bx)/b_dot_d_perp;
if (u < 0 || u > 1) return null;
return new PVector(x1+t*bx, y1+t*by);
}
boolean pointInPolygon(PVector inP, int inIndex) {
int numIntersections = 0;
// Test lines of the bounding polygon for intersection
Polygon inPoly = polys.get(inIndex);
for (int i = 0; i < inPoly.vertices.length-1; i++) {
PVector intersection = segIntersection(
inP.x, inP.y, width, inP.y, /* In point to arbitrary point */
inPoly.vertices[i].x, inPoly.vertices[i].y, /* Vertex i of polygon */
inPoly.vertices[i+1].x, inPoly.vertices[i+1].y); /* Vertex i+1 of polygon */
if (intersection != null) numIntersections++;
}
// There is still one case left to test for
PVector intersection = segIntersection(
inP.x, inP.y, width, inP.y, /* In point to arbitrary point */
inPoly.vertices[inPoly.vertices.length-1].x, inPoly.vertices[inPoly.vertices.length-1].y,
inPoly.vertices[0].x, inPoly.vertices[0].y);
if (intersection != null) numIntersections++;
return (numIntersections%2 == 1); // If the number of intersections is odd, return true
}