Skip to content

Instantly share code, notes, and snippets.

@mvanga
Created February 14, 2018 16:08
Show Gist options
  • Save mvanga/ce3884395859e0c67f963db282988ac2 to your computer and use it in GitHub Desktop.
Save mvanga/ce3884395859e0c67f963db282988ac2 to your computer and use it in GitHub Desktop.
import processing.pdf.*;
int MARGIN = 0;
class Circle {
float x;
float y;
float r;
Circle(float x, float y, float r) {
this.x = x;
this.y = y;
this.r = r;
}
boolean collides(Circle c) {
float dist = sq(c.x - x) + sq(c.y - y);
if (dist <= sq(r + c.r + MARGIN))
return true;
return false;
}
}
ArrayList<Circle> circles;
float r;
float minr = 16;
int iteration = 0;
int failed = 0;
ArrayList<Circle> collision_objects;
void find_stroke() {
float x, y;
boolean collides;
while (r >= minr) {
x = random(width);
y = random(height);
Circle nc = new Circle(x, y, r);
Circle nc2 = new Circle(x, y, r + MARGIN/2);
collides = false;
collision_objects.clear();
quad.retrieve(collision_objects, nc2);
for (int k = 0; k < collision_objects.size(); k++) {
// Run collision detection algorithm between objects
if (collision_objects.get(k).collides(nc2)) {
collides = true;
break;
}
}
if (collides) {
failed++;
if (failed % 100000 == 0)
println(failed + " tries completed");
if (failed > 1024 * 1024 / (r*r*r)) {
println(failed + " tries completed");
println("new radius: " + r/1.1);
failed = 0;
r = r/1.2;
return;
}
continue;
}
colorMode(HSB, 360, 255, 255);
fill(random(280, 300), 255, 255);
//ellipse(x, y, 2*r, 2*r);
ellipse(x, y, 2*r, 2*r);
circles.add(nc);
quad.insert(nc2);
break;
}
}
class Rectangle {
double x, y, w, h;
Rectangle(double x, double y, double w, double h) {
this.x = x;
this.y = y;
this.w = w;
this.h = h;
}
double getX() {
return x;
}
double getY() {
return y;
}
double getWidth() {
return w;
}
double getHeight() {
return h;
}
}
class Quadtree {
int MAX_OBJECTS = 10;
int MAX_LEVELS = 20;
int level; /* The level of this QuadTree node */
int quad;
ArrayList<Circle> objects; /* Objects at this level */
Rectangle bounds; /* The bounds of this QuadTree node */
Quadtree[] nodes; /* Nodes for each child quadrant */
boolean is_split;
/* Constructor */
Quadtree(int pLevel, int pQuad, Rectangle pBounds) {
level = pLevel;
quad = pQuad;
objects = new ArrayList<Circle>();
bounds = pBounds;
nodes = new Quadtree[4];
is_split = false;
}
void clear() {
objects.clear();
for (int i = 0; i < nodes.length; i++) {
if (nodes[i] != null) {
nodes[i].clear();
nodes[i] = null;
nodes[i].is_split = false;
}
}
}
void split() {
double x = bounds.getX();
double y = bounds.getY();
double subWidth = bounds.getWidth() / 2;
double subHeight = bounds.getHeight() / 2;
println("Splitting new level: " + (level + 1));
/* Top-right */
nodes[0] = new Quadtree(level+1, 0, new Rectangle(x + subWidth, y, subWidth, subHeight));
/* Top-left */
nodes[1] = new Quadtree(level+1, 1, new Rectangle(x, y, subWidth, subHeight));
/* Bottom-left */
nodes[2] = new Quadtree(level+1, 2, new Rectangle(x, y + subHeight, subWidth, subHeight));
/* Bottom-right */
nodes[3] = new Quadtree(level+1, 3, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight));
is_split = true;
}
boolean intersects(Circle circle, Rectangle rect)
{
float circleDistance_x = abs((float)(circle.x - (rect.x + rect.getWidth()/2)));
float circleDistance_y = abs((float)(circle.y - (rect.y + rect.getHeight()/2)));
if (circleDistance_x > (rect.getWidth()/2 + circle.r)) { return false; }
if (circleDistance_y > (rect.getHeight()/2 + circle.r)) { return false; }
if (circleDistance_x <= (rect.getWidth()/2)) { return true; }
if (circleDistance_y <= (rect.getHeight()/2)) { return true; }
float cornerDistance_sq = sq((float)(circleDistance_x - rect.getWidth()/2)) + sq((float)(circleDistance_y - rect.getHeight()/2));
return (cornerDistance_sq <= sq(circle.r));
}
int get_indices(Circle c) {
int index = 0;
double xmin = bounds.getX();
double ymin = bounds.getY();
double xmax = xmin + bounds.getWidth();
double ymax = ymin + bounds.getHeight();
double xmid = xmin + (bounds.getWidth() / 2);
double ymid = ymin + (bounds.getHeight() / 2);
double nwidth = bounds.getWidth();
double nheight = bounds.getHeight();
double cxmin = c.x - c.r;
double cxmax = c.x + c.r;
double cymin = c.y - c.r;
double cymax = c.y + c.r;
boolean top = (cymin <= ymid && cymax >= ymin);
boolean bottom = (cymax >= ymid && cymin < ymax);
boolean left = (cxmin <= xmid && cxmax >= xmin);
boolean right = (cxmax >= xmid && cxmin < xmax);
top = intersects(c, new Rectangle(xmin, ymin, nwidth, nheight/2));
bottom = intersects(c, new Rectangle(xmin, ymid, nwidth, nheight/2));
left = intersects(c, new Rectangle(xmin, ymin, nwidth/2, nheight));
right = intersects(c, new Rectangle(xmid, ymin, nwidth/2, nheight));
//println(top + "," + bottom + "," + left + "," + right);
//println("xmin=" + xmin + ",xmax=" + xmax + ",ymin=" + ymin + ",ymax=" + ymax);
//println("cxmin=" + cxmin + ",cxmax=" + cxmax + ",cymin=" + cymin + ",cymax=" + cymax);
//println("xmid=" + xmid + ",ymid=" + ymid);
if (left) {
if (top) { index |= 1 << 1; }
if (bottom) { index |= 1 << 2; }
}
if (right) {
if (top) { index |= 1 << 0; }
if (bottom) { index |= 1 << 3; }
}
return index;
}
void insert(Circle c) {
if (is_split) {
int index = get_indices(c);
if (index != 0) {
for (int k = 0; k < 4; k++) {
if ((index & (1 << k)) != 0)
nodes[k].insert(c);
}
}
return;
} else {
objects.add(c);
//println("Inserting into quadrant " + (quad + 1) + " at level " + level);
if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
//println("Split and rehashed " + objects.size() + " objects at quadrant " + quad + " @ level " + level);
split();
while (objects.size() > 0) {
Circle x = objects.remove(0);
int index = get_indices(x);
if (index != 0) {
for (int k = 0; k < 4; k++) {
if ((index & (1 << k)) != 0)
nodes[k].insert(x);
}
} else {
println("Whoops unable to find place for object at quadrant " + quad + " @ level " + level);
stroke(0);
noFill();
//ellipse(x.x, x.y, 2*x.r, 2*x.r);
//line((float)bounds.getX(), (float)bounds.getY() + (float)bounds.getHeight()/2, (float)bounds.getX() + (float)bounds.getWidth(), (float)bounds.getY() + (float)bounds.getHeight()/2);
//line((float)bounds.getX() + (float)bounds.getWidth()/2, (float)bounds.getY(), (float)bounds.getX() + (float)bounds.getWidth()/2, (float)bounds.getY() + (float)bounds.getHeight());
//rect((float)bounds.getX(), (float)bounds.getY(), (float)bounds.getWidth(), (float)bounds.getHeight());
}
}
objects.clear();
}
}
}
ArrayList<Circle> retrieve(ArrayList<Circle> ret, Circle c) {
if (is_split) {
int index = get_indices(c);
for (int i = 0; i < 4; i++) {
if ((index & (1 << i)) != 0)
nodes[i].retrieve(ret, c);
}
} else {
ret.addAll(objects);
}
return ret;
}
}
PImage img;
Quadtree quad;
void setup() {
size(500, 500); //, PDF, "scape" + n + ".pdf");
background(255);
noStroke();
circles = new ArrayList<Circle>();
quad = new Quadtree(0, 0, new Rectangle(0, 0, width, height));
quad.clear();
r = 128;
minr = 1;
failed = 0;
iteration = 0;
collision_objects = new ArrayList<Circle>();
}
void draw() {
noStroke();
if (r >= minr)
find_stroke();
else {
//filter(BLUR, 1);
noLoop();
}
//stroke(0);
//line(0, height/2, width, height/2);
//line(width/2, 0, width/2, height);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment