While looking at Anders Hoff work I saw images where he made a square that is seemingly cut into smaller and smaller pieces.
I wanted to reproduce the effect using Processing and this is what I came up with.
First I created a couple of classes to simplify things.
“Point” that stores two floats and draws a small circle.
“Line” that stores two Points and draws a line in between.
public class Point {
public float x;
public float y;
public Point (float x, float y) {
this.x = x;
this.y = y;
}
public void draw(int s) {
ellipse(x, y, s, s);
}
}
public class Line {
public Point p1;
public Point p2;
public Line(float x1, float y1, float x2, float y2) {
p1 = new Point(x1, y1);
p2 = new Point(x2, y2);
}
public Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
public void draw() {
line(p1.x, p1.y, p2.x, p2.y);
}
}
Next was a “Polygon” class.
It stores the positions of each points, the lines between points and can draw the polygon.
To store the Points and Lines I used ArrayLists so I can add and remove elements easily.
This class has a method called “addPoint” that takes a Point and add it to the points list.
It then checks the number of points in the list and adds lines accordingly :
| one point | no line added. |
| two points | a single line is added between the two points p1 and p2. |
| three points | two new lines are added. From p2 to p3 and from p3 to p1. |
| more than three points | the last line is removed and two new lines are added. From the previous last point to the new last point and from the new last point to the first point. |
public class Polygon {
public ArrayList<Point> points;
public ArrayList<Line> lines;
public Polygon () {
points = new ArrayList<Point>();
lines = new ArrayList<Line>();
}
public void draw() {
for (int i = 0; i < lines.size(); ++i) {
lines.get(i).draw();
}
for (int i = 0; i < points.size(); ++i) {
points.get(i).draw(5);
}
}
public void addPoint(Point point) {
points.add( point );
if (points.size()==2) {
lines.add( new Line( points.get(0), points.get(1) ) );
}
else
if (points.size()==3) {
lines.add( new Line(points.get(1), points.get(2)) );
lines.add( new Line(points.get(2), points.get(0)) );
}
else
if (points.size()>3) {
lines.remove(lines.size()-1);
lines.add( new Line(points.get(points.size()-2), points.get(points.size()-1)) );
lines.add( new Line(points.get(points.size()-1), points.get(0)) );
}
}
}
With this I can create and draw simple polygons such as this nice square.
// create polygon Polygon polygon = new Polygon(); polygon.addPoint(200,200); polygon.addPoint(200,600); polygon.addPoint(600,600); polygon.addPoint(600,200); // draw polygon polygon.draw();
Now that I have a square, I need to have a line that cuts it in two.
I start by getting a point inside of the square.
Because I know my square goes from 200 to 600 in the x and y coordinates, I simply get two random numbers between 300 and 500.
These will be the the coordinates of the point.
I also need an angle for the line passing through that point. For that I get another random number, this time between between 0 and 180.
From that point and angle I want to create a line at that angle passing through that point.
A bit of trigonometry later I have the coordinates of two new points that will define the start and end of the cutting line.
The sine and cosine are multiplied by 1000 to make sure that the new points are far away from the polygon.
// get random point
Point p = new Point((int)random(300,500), (int)random(300,500));
int angle = (int)random(0,180);
// create intersecting line
Point p1 = new Point(p.x + 1000*sin(angle), p.y + 1000*cos(angle));
Point p2 = new Point(p.x - 1000*sin(angle), p.y - 1000*cos(angle));
Line line = new Line(p1, p2);Afterwards I need to find where the cutting line intersect with the polygon.
I added a method in the Line class to find the intersection between the current line and another one.
It returns the intersection point if any or null if there was no intersection.
// this is some voodoo magic from Andre LaMothe
public Point intersect(Line line) {
Point s1 = new Point( p2.x - p1.x, p2.y - p1.y );
Point s2 = new Point( line.p2.x - line.p1.x, line.p2.y - line.p1.y);
float s = (-s1.y * (p1.x - line.p1.x) + s1.x * (p1.y - line.p1.y)) / (-s2.x * s1.y + s1.x * s2.y);
float t = ( s2.x * (p1.y - line.p1.y) - s2.y * (p1.x - line.p1.x)) / (-s2.x * s1.y + s1.x * s2.y);
if ( s >= 0 && s <= 1 && t >= 0 && t <= 1 ) {
// collision
float intX = p1.x + (t * s1.x);
float intY = p1.y + (t * s1.y);
return new Point(intX, intY);
}
// no collision
return null;
}
I am not going to explain this method here but it works very well.
Now I can iterate over each line in the polygon and check if they intersect with the cutting line.
The next step is to cut the polygon in two.
The old polygon will be discarded and two new ones will be creates in its place.
To keep tracks of the polygons I have an ArrayList of Polygon to which I will add the new ones.
ArrayList<Polygon> polygons = new ArrayList<Polygon>();
First I create two empty polygons and have one of them be the one I’m currently adding points to.
For each lines in the original polygon I add the starting point to the current new polygon.
I then check if the cutting line intersects the current line. If it does, I add the intersection point to the current new polygon and set the other new polygon as the current one. The intersection point is added to this new current polygon
When all the lines in the original polygon have been processed, the two polygons should have all their points.
I then move the two new polygons around by a random amount so they appear disjointed.
public void cutPolygon( Polygon polygon, Line line ) {
Polygon poly1 = new Polygon();
Polygon poly2 = new Polygon();
Polygon polyCreated = poly1; // the polygon we are currently adding poins to
// for each line in the parent polygon
for (int i = 0; i < polygon.lines.size(); ++i) {
// the first point of the line goes to the currently created poly
polyCreated.addPoint( polygon.lines.get(i).p1 );
// check if the current line is intersected
Point pInt = polygon.lines.get(i).intersect(line);
if (pInt != null) {
// lines intersect !
// add the intersection point to the current poly
polyCreated.addPoint( pInt );
// switch poly
if (polyCreated == poly1) {
polyCreated = poly2;
} else {
polyCreated = poly1;
}
// add the intersection point to the current poly (the other one)
// using a new point so the intersection point is not used by the two polygons
polyCreated.addPoint( new Point(pInt.x, pInt.y) );
// the last point of the line will be the first of the next line
}
}
// move new polygons
poly1.move(random(-1,1)*20, random(-1,1)*20);
poly2.move(random(-1,1)*20, random(-1,1)*20);
// add the two created polygons to the list
polygons.add(poly1);
polygons.add(poly2);
}
Using this cutPolygon() method ,I can easily cut any polygons in two.
But I still need a valid point inside the polygon to initiate the cut.
I added a method in the Polygon class to get a point in the middle of the polygon.
public Point middle;
private void findMiddle() {
if (points.size()<3) {
middle = null;
return;
}
float sumX = 0;
float sumY = 0;
for (Point p : points) {
sumX += p.x;
sumY += p.y;
}
middle = new Point(sumX/points.size(), sumY/points.size());
}
Each times a point is added to the polygon I call this method to update the middle point of the polygon.
As long as the polygon has three or more points, this middle point will be set and be inside the polygon.
public void addPoint(Point point) {
// previous code...
findMiddle();
}
Because I start with a convex polygon and only cut it in a straight line, all resulting polygons will also be convex.
Doing this let me average the X and Y value of each points and be sure that the resulting point will be inside the polygon.
I still choose a random point for the first polygon cut. That way the cut doesn’t go through the middle of the polygon. I think it looks nicer.
You can see the cut polygons and their middle points in the following image.
To simplify things I added a method to get a random line passing through a point.
The code is almost the same as what I did previously.
Line getRandomLine(Point p) {
int angle = (int)random(0,180);
Point p1 = new Point(p.x + 1000*sin(angle), p.y + 1000*cos(angle));
Point p2 = new Point(p.x - 1000*sin(angle), p.y - 1000*cos(angle));
return new Line(p1, p2);
}
With this method and cutPolygon(…) I can create a loop, pick a polygon from the list and cut it. (don’t forget to remove the cut polygon from the list)
for (int i = 0; i < 20; ++i) {
int index = (int)random(0, polygons.size());
cutPolygon( polygons.get(index), getRandomLine(polygons.get(index).middle) );
polygons.remove(index);
}
Depending on which polygon is chosen the result will vary.
Picking the first polygon in the list will result in an evenly cut polygon as the smaller pieces are added at the end of the list.
Picking a polygon at random in the list tends to create smaller and smaller pieces because as the list grows the large ones have a smaller ans smaller chance of being chosen
Here is an example of picking the first polygon in the list.
An example of random polygon selection. (and middle points sot shown)
And another one with the first polygon selected but this time the pieces are moves a bit more when cut. (also the polygons points are not shown, just the lines)
Some other results with varying polygon selection and displacement.
Note:
A lot of improved can be made to the code but the speed is not really an issue so I think it’s not that bad for an experiment..
A nice thing to do could be to fill the polygons and draw them ordered by size, the small ones on top of the big ones.
Animating the creation and/or displacement also gives good results.