Search code examples
processinglineintersectionshapespoints

Separate shapes as lines split the canvas + Select points to draw shapes from arrays

I want to detect separate shapes as random-generated lines split the canvas. I saved line intersection points in separate arrays for x and y positions (same order), but don't know how to connect points that complete multiple pieces of shapes .

  1. Is there any way to detect nearby points to close a minimal possible shape whether it be a triangle, rectangle, or polygon (e.g., by using beginShape and endShape)?
  2. If 1) is too complicated, is there any method to select 3 or more random points from an array?

Here's a sample image that has 4 lines splitting the canvas with their intersection points marked in red. I also saved the top and bottom points (marked in black) of each random-generated line, plus the four corners of the canvas in the same arrays for x and y positions separately (px, py).

sample image that has lines dividing the canvas with their intersection points marked Multiple lines split the canvas.

shapes split by multiple lines How to get shapes split by lines in Processing?

I was able to get all the intersection points, but having a problem with connecting them into separate shapes. Here's the Processing code that I am working on:

//Run in Processing.
//Press r to refresh.
//Top and bottom points are added to px and py when refreshed (filled in black).
//Intersection points are added to px and py when detected (filled in red).
int l = 4; //set number of lines
float[] r1 = new float[l];
float[] r2 = new float[l];
float[] px = {}; //array to save x positions of all possible points
float[] py = {}; //array to save y positions of all possible points
boolean added = false;
void setup(){
  size(800, 800);
  background(255);
  
  refresh();
}
void draw(){ 
  background(255);
  stroke(0, 150, 255, 150);
  strokeWeight(1);
  for(int i=0; i < r1.length; i++){
    for(int j=0; j < r1.length; j++){
      if(i>j){
      boolean hit = lineLine(r1[i], 0, r2[i], height, r1[j], 0, r2[j], height);
      if (hit) stroke(255, 150, 0, 150);
      else stroke(0, 150, 255, 150);
      }
    line(r1[i], 0, r2[i], height);
    }
  }
  added = true;
  print(px.length);
}
//source: http://jeffreythompson.org/collision-detection/line-line.php
boolean lineLine(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));
    fill(255,0,0);
    noStroke();
    ellipse(intersectionX,intersectionY, 20,20);
    if(added==false){
      px = append(px, intersectionX);
      py = append(py, intersectionY);
    }
    return true;
  }
  return false;
}
void refresh(){
  added = false;
  px = new float[0];
  py = new float[0];
  r1 = new float[l];
  r2 = new float[l];
  
  px = append(px, 0);
  py = append(py, 0);
  px = append(px, 0);
  py = append(py, height);
  px = append(px, width);
  py = append(py, 0);
  px = append(px, width);
  py = append(py, height);
  
  for(int i=0; i< r1.length; i++){
    r1[i] = random(800);
  }
  for(int i=0; i< r2.length; i++){
    r2[i] = random(800);
  }
  for(int i=0; i < r1.length; i++){
      stroke(0);
      line(r1[i], 0, r2[i], height);
      px = append(px, r1[i]);
      py = append(py, 0);
      px = append(px, r2[i]);
      py = append(py, height);
  }
}
void keyReleased() {
  if (key == 'r') refresh();
}
Solution

  • If you want to draw a shape made of the intersection points only you're on the right track with beginShape()/endShape().

    Currently it looks like you're placing all the points in px, py: the intersection points and also the points defining the lines used to compute the intersections in the first place.

    You might want to separate the two, for example a couply of arrays for points defining lines only and another pair of x,y arrays for the intersection points only. You'd only need to iterated through the intersected coordinates to place vertex(x, y) calls inbetween beginShape()/endShape(). Here's a modified version of you code to illustrate the idea:

    //Run in Processing.
//Press r to refresh.
//Top and bottom points are added to px and py when refreshed (filled in black).
//Intersection points are added to px and py when detected (filled in red).
int l = 4; //set number of lines
float[] r1 = new float[l];
float[] r2 = new float[l];
float[] px = {}; //array to save x positions of all possible points
float[] py = {}; //array to save y positions of all possible points
float[] ipx = {}; // array to save x for intersections only
float[] ipy = {}; // array to save y for intersections only
boolean added = false;

void setup(){
  size(800, 800);
  background(255);
  
  refresh();
}
void draw(){ 
  background(255);
  stroke(0, 150, 255, 150);
  strokeWeight(1);
  for(int i=0; i < r1.length; i++){
    for(int j=0; j < r1.length; j++){
      if(i>j){
      boolean hit = lineLine(r1[i], 0, r2[i], height, r1[j], 0, r2[j], height);
      if (hit) stroke(255, 150, 0, 150);
      else stroke(0, 150, 255, 150);
      }
    line(r1[i], 0, r2[i], height);
    }
  }
  added = true;
  
  // draw intersections
  beginShape();
  for(int i = 0 ; i < ipx.length; i++){
    vertex(ipx[i], ipy[i]);
  }
  endShape();
  
  //print(px.length);
  //println(px.length, py.length);
}
//source: http://jeffreythompson.org/collision-detection/line-line.php
boolean lineLine(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));
    fill(255,0,0);
    noStroke();
    ellipse(intersectionX,intersectionY, 20,20);
    if(added==false){
      px = append(px, intersectionX);
      py = append(py, intersectionY);
      
      // store intersections
      ipx = append(ipx, intersectionX);
      ipy = append(ipy, intersectionY);
      
    }
    return true;
  }
  return false;
}
void refresh(){
  added = false;
  px = new float[0];
  py = new float[0];
  ipx = new float[0];
  ipy = new float[0];
  r1 = new float[l];
  r2 = new float[l];
  
  px = append(px, 0);
  py = append(py, 0);
  px = append(px, 0);
  py = append(py, height);
  px = append(px, width);
  py = append(py, 0);
  px = append(px, width);
  py = append(py, height);
  
  for(int i=0; i< r1.length; i++){
    r1[i] = random(800);
  }
  for(int i=0; i< r2.length; i++){
    r2[i] = random(800);
  }
  for(int i=0; i < r1.length; i++){
      stroke(0);
      line(r1[i], 0, r2[i], height);
      px = append(px, r1[i]);
      py = append(py, 0);
      px = append(px, r2[i]);
      py = append(py, height);
  }
  
}
void keyReleased() {
  if (key == 'r') refresh();
}

    Bare in mind this simlpy draws the points in the order in which the intersections were computed. On a good day you'll get something like this:

    triangle defined by intersection of lines

    It doesn't exclude the possiblity of polygons with the wrong vertex order (winding):

    ribbon defined by intersection of lines: instead of a quad, the wrong winding order generates the ribbon

    and you might be get convave polygons too.

    If you only need the outer 'shell' of these intersection points you might need something like a convex hull algorithm

    One option to at least visually split shapes might to use beginShape(TRIANGLES); with endShape(CLOSE); which should iterate through points and draw a triangle for every coordinate triplate, however given random points and number of interesections you might end up with a missing triangle or two (e.g. 6 points = 2 triangles, 7 points = 2 triangles and 1 point with no missing pairs)

    The only other note I have is around syntax: arrays are ok to get started with but you might want to look into ArrayList and PVector. This would allow you to use a single dynamic array of PVector instances which have x, y properties.

    Update

    Overall the code can be simplified. If we take out the line intersection related code we can get away with something like:

    int l = 4; //set number of random lines
float[] r1 = new float[l];  // random x top
float[] r2 = new float[l];  // random x bottom

void setup() {
  size(800, 800);
  strokeWeight(3);
  stroke(0, 150, 255, 150);
  
  refresh();
}

void draw() { 
  background(255);
  
  // random lines
  for (int i=0; i < r1.length; i++) {
    line(r1[i], 0, r2[i], height);
  }
  
  // borders
  line(0, 0, width, 0);
  line(width, 0, width - 1, height - 1);
  line(0, height - 1, width - 1, height - 1);
  line(0, 0, 0, height - 1);
}

void refresh() {
  r1 = new float[l];
  r2 = new float[l];

  for (int i=0; i< r1.length; i++) {
    r1[i] = random(800);
    r2[i] = random(800);
  }
}

void keyReleased() {
  if (key == 'r') refresh();
}

    If we were to use a basic Line class and make use of PVector and ArrayList we could rewrite the above as:

    int numRandomLines = 4;
ArrayList<PVector> points = new ArrayList<PVector>();


void setup() {
  size(800, 800);
  stroke(0, 150, 255, 150);
  strokeWeight(3);
  refresh();
}

void refresh(){
  // remove previous points
  points.clear();
  //add borders
  points.add(new PVector(0, 0)); points.add(new PVector(width, 0));
  points.add(new PVector(width, 0));points.add(new PVector(width - 1, height - 1));
  points.add(new PVector(0, height - 1));points.add(new PVector(width - 1, height - 1));
  points.add(new PVector(0, 0)); points.add(new PVector(0, height - 1));
  // add random lines
  for (int i=0; i< numRandomLines; i++) {
    points.add(new PVector(random(800), 0));  points.add(new PVector(random(800), height));
  }
}

void draw(){
  background(255);
  
  beginShape(LINES);
  for(PVector point : points) vertex(point.x, point.y);
  endShape();
}

void keyReleased() {
  if (key == 'r') refresh();
}

    and grouping a pair of points (PVector) into a Line class:

    int numRandomLines = 4;
ArrayList<Line> lines = new ArrayList<Line>();

void setup() {
  size(800, 800);
  stroke(0, 150, 255, 150);
  strokeWeight(3);
  refresh();
}

void refresh(){
  // remove previous points
  lines.clear();
  //add borders
  lines.add(new Line(new PVector(0, 0), new PVector(width, 0)));
  lines.add(new Line(new PVector(width, 0), new PVector(width - 1, height - 1)));
  lines.add(new Line(new PVector(0, height - 1), new PVector(width - 1, height - 1)));
  lines.add(new Line(new PVector(0, 0), new PVector(0, height - 1)));
  // add random lines
  for (int i=0; i< numRandomLines; i++) {
    lines.add(new Line(new PVector(random(800), 0), new PVector(random(800), height)));
  }
}

void draw(){
  background(255);
  
  for(Line line : lines) line.draw();
}

void keyReleased() {
  if (key == 'r') refresh();
}

class Line{
  
  PVector start;
  PVector end;
  
  Line(PVector start, PVector end){
    this.start = start;
    this.end = end;
  }
  
  void draw(){
    line(start.x, start.y, end.x, end.y);
  }
}

    At this stage to get the individual shapes as your diagram describes, we could cheat and use a computer vision library like OpenCV. This is if course overkill (as we'd get() a PImage copy of the drawing, convert that to an OpenCV image) then simply use findContours() to get each shape/contour.

    Going back to the original approach, the line to line intersection function could be integrated into the Line class:

    int numRandomLines = 4;
ArrayList<Line> lines = new ArrayList<Line>();
ArrayList<PVector> intersections = new ArrayList<PVector>();

void setup() {
  size(800, 800);
  strokeWeight(3);
  refresh();
}

void refresh(){
  // remove previous points
  lines.clear();
  intersections.clear();
  //add borders
  lines.add(new Line(new PVector(0, 0), new PVector(width, 0)));
  lines.add(new Line(new PVector(width, 0), new PVector(width - 1, height - 1)));
  lines.add(new Line(new PVector(0, height - 1), new PVector(width - 1, height - 1)));
  lines.add(new Line(new PVector(0, 0), new PVector(0, height - 1)));
  // add random lines
  for (int i=0; i< numRandomLines; i++) {
    lines.add(new Line(new PVector(random(800), 0), new PVector(random(800), height)));
  }
  // compute intersections
  int numLines = lines.size();
  // when looping only check if lineA intersects lineB but not also if lineB intersects lineA (redundant)
  for (int i = 0; i < numLines - 1; i++){
    Line lineA = lines.get(i);
    for (int j = i + 1; j < numLines; j++){
      Line lineB = lines.get(j);
      // check intersection
      PVector intersection = lineA.intersect(lineB);
      // if there is one, append the intersection point to the list
      if(intersection != null){
        intersections.add(intersection);
      }
    }
  }
}

void draw(){
  background(255);
  stroke(0, 150, 255, 150);
  // draw lines
  for(Line line : lines) line.draw();
  stroke(255, 0, 0, 150);
  // draw intersections
  for(PVector intersection : intersections) ellipse(intersection.x, intersection.y, 9, 9);
}

void keyReleased() {
  if (key == 'r') refresh();
}

class Line{
  
  PVector start;
  PVector end;
  
  Line(PVector start, PVector end){
    this.start = start;
    this.end = end;
  }
  
  void draw(){
    line(start.x, start.y, end.x, end.y);
  }
  
  //source: http://jeffreythompson.org/collision-detection/line-line.php
  //boolean lineLine(float this.start.x, float this.start.y, float this.end.x, float this.end.y, 
                   //float other.start.x, float other.start.y, float other.end.x, float other.end.y) {
  PVector intersect(Line other) {
    // calculate the distance to intersection point
    float uA = ((other.end.x-other.start.x)*(this.start.y-other.start.y) - (other.end.y-other.start.y)*(this.start.x-other.start.x)) / ((other.end.y-other.start.y)*(this.end.x-this.start.x) - (other.end.x-other.start.x)*(this.end.y-this.start.y));
    float uB = ((this.end.x-this.start.x)*(this.start.y-other.start.y) - (this.end.y-this.start.y)*(this.start.x-other.start.x)) / ((other.end.y-other.start.y)*(this.end.x-this.start.x) - (other.end.x-other.start.x)*(this.end.y-this.start.y));
    // 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 = this.start.x + (uA * (this.end.x-this.start.x));
      float intersectionY = this.start.y + (uA * (this.end.y-this.start.y));
      
      return new PVector(intersectionX, intersectionY);
    }
    return null;
  }
}

    The next step would be a more complex algorithm to sort the points based on x, y position (e.g. top to bottom , left to right), iterate though points comparing the first to the rest by distance and angle and trying to work out if consecutive points with minimal distance and angle changes connect.

    Having a quick look online I can see such algorithms for example:

    CGAL c++ computational geometry library example of the sweep line algorithm displaying two orthogonal intersecting line cut by a third diagonal lower left to upper right line which connects it's tip to the horizontal: red and blue colour coded circles illustrate the intersection of these lines highlighting the interior points