Irregular shapes collision detection

Processing Coding Questions
7

Here is a simple example to get started that doesn’t rely on .java – just Processing.

It draws two irregular polygons, then checks that they overlap (they do).

PVector[] shape1;
PVector[] shape2;

void setup() {
  shape1 = new PVector[]{
    new PVector(-20, -20), 
    new PVector(20, 10), 
    new PVector(15, -10), 
    new PVector(5, -10)
  };
  shape2 = new PVector[]{
    new PVector(40, -40), 
    new PVector(30, 0), 
    new PVector(40, 40), 
    new PVector(0, -20), 
    new PVector(-40, -40)
  };
}

void draw() {
  background(192);
  translate(width/2,height/2);
  drawShape(shape1);
  drawShape(shape2);
  if(polyPoly(shape1, shape2)){
    println("hit");
  }
  noLoop();
}

void drawShape(PVector[] shape) {
  for (int i=0; i<shape.length; i++) {
    line(shape[i].x, shape[i].y, shape[(i+1)%shape.length].x, shape[(i+1)%shape.length].y);
  }
}


boolean lineLine(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
  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 >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {
    return true;
  }
  return false;
}

boolean polyLine(PVector[] vertices, float x1, float y1, float x2, float y2) {
  int next = 0;
  for (int current=0; current<vertices.length; current++) {
    next = current+1;
    if (next == vertices.length) next = 0;
    float x3 = vertices[current].x;
    float y3 = vertices[current].y;
    float x4 = vertices[next].x;
    float y4 = vertices[next].y;
    boolean hit = lineLine(x1, y1, x2, y2, x3, y3, x4, y4);
    if (hit) {
      return true;
    }
  }
  return false;
}

boolean polyPoly(PVector[] p1, PVector[] p2) {
  int next = 0;
  for (int current=0; current<p1.length; current++) {
    next = current+1;
    if (next == p1.length) next = 0;
    PVector vc = p1[current];
    PVector vn = p1[next];
    boolean collision = polyLine(p2, vc.x, vc.y, vn.x, vn.y);
    if (collision) return true;
  }
  return false;
}
3 Likes