Irregular shapes collision detection

Hello… sorry for my very bad english! I am looking for a method to determine if there are collision between 2 irregular shapes . In the idea of the circle packing but with random shapes ! Thank you for directing my research!

1 Like
1 Like

Thanks ! It s very helpful but it s does’nt give solution for irregular shapes… like for example shapes that look like pieces of a puzzle. Thanks again

i think, this might help you in research.

collision between irregular shape and circle
outputhd__real
i dont know how exactly it works

/**
 * Non-orthogonal Collision with Multiple Ground Segments 
 * by Ira Greenberg. 
 * 
 * Based on Keith Peter's Solution in
 * Foundation Actionscript Animation: Making Things Move!
 */

Orb orb;
ArrayList<Orb> orbs = new ArrayList<Orb>();

PVector gravity = new PVector(0, 0.05);
// The ground is an array of "Ground" objects
int segments = 40;
Ground[] ground = new Ground[segments];

void setup() {
  //size(640, 360);
  fullScreen();
  // An orb object that will fall and bounce around
  //orb = new Orb(50, 50, 3);

  for (int i = 0; i < 50; i++) {
    orbs.add(new Orb(random(width), random(300), random(5, 10)));
  }
  // Calculate ground peak heights 
  float[] peakHeights = new float[segments+1];
  for (int i=0; i<peakHeights.length; i++) {
    peakHeights[i] = random(height-200, height-150);
  }

  /* Float value required for segment width (segs)
   calculations so the ground spans the entire 
   display window, regardless of segment number. */
  float segs = segments;
  for (int i=0; i<segments; i++) {
    ground[i]  = new Ground(width/segs*i, peakHeights[i], width/segs*(i+1), peakHeights[i+1]);
  }
}


void draw() {
  // Background
  noStroke();
  fill(0);
  rect(0, 0, width, height);

  // Move and display the orb
  for (Orb orb : orbs) {
    orb.move();
    orb.display();
    // Check walls
    orb.checkWallCollision();

    // Check against all the ground segments
    for (int i=0; i<segments; i++) {
      orb.checkGroundCollision(ground[i]);
    }
  }

  // Draw ground
  fill(127);
  beginShape();
  for (int i=0; i<segments; i++) {
    vertex(ground[i].x1, ground[i].y1);
    vertex(ground[i].x2, ground[i].y2);
  }
  vertex(ground[segments-1].x2, height);
  vertex(ground[0].x1, height);
  endShape(CLOSE);
}

class Ground {
  float x1, y1, x2, y2;  
  float x, y, len, rot;

  // Constructor
  Ground(float x1, float y1, float x2, float y2) {
    this.x1 = x1;
    this.y1 = y1;
    this.x2 = x2;
    this.y2 = y2;
    x = (x1+x2)/2;
    y = (y1+y2)/2;
    len = dist(x1, y1, x2, y2);
    rot = atan2((y2-y1), (x2-x1));
  }
}

class Orb {
  // Orb has positio and velocity
  PVector position;
  PVector velocity;
  float r;
  // A damping of 80% slows it down when it hits the ground
  float damping = 0.8;

  Orb(float x, float y, float r_) {
    position = new PVector(x, y);
    velocity = new PVector(.5, 0);
    r = r_;
  }

  void move() {
    // Move orb
    velocity.add(gravity);
    position.add(velocity);
  }

  void display() {
    // Draw orb
    noStroke();
    fill(200);
    ellipse(position.x, position.y, r*2, r*2);
  }
  
  // Check boundaries of window
  void checkWallCollision() {
    if (position.x > width-r) {
      position.x = width-r;
      velocity.x *= -damping;
    } 
    else if (position.x < r) {
      position.x = r;
      velocity.x *= -damping;
    }
  }

  void checkGroundCollision(Ground groundSegment) {

    // Get difference between orb and ground
    float deltaX = position.x - groundSegment.x;
    float deltaY = position.y - groundSegment.y;

    // Precalculate trig values
    float cosine = cos(groundSegment.rot);
    float sine = sin(groundSegment.rot);

    /* Rotate ground and velocity to allow 
     orthogonal collision calculations */
    float groundXTemp = cosine * deltaX + sine * deltaY;
    float groundYTemp = cosine * deltaY - sine * deltaX;
    float velocityXTemp = cosine * velocity.x + sine * velocity.y;
    float velocityYTemp = cosine * velocity.y - sine * velocity.x;

    /* Ground collision - check for surface 
     collision and also that orb is within 
     left/rights bounds of ground segment */
    if (groundYTemp > -r &&
      position.x > groundSegment.x1 &&
      position.x < groundSegment.x2 ) {
      // keep orb from going into ground
      groundYTemp = -r;
      // bounce and slow down orb
      velocityYTemp *= -1.0;
      velocityYTemp *= damping;
    }

    // Reset ground, velocity and orb
    deltaX = cosine * groundXTemp - sine * groundYTemp;
    deltaY = cosine * groundYTemp + sine * groundXTemp;
    velocity.x = cosine * velocityXTemp - sine * velocityYTemp;
    velocity.y = cosine * velocityYTemp + sine * velocityXTemp;
    position.x = groundSegment.x + deltaX;
    position.y = groundSegment.y + deltaY;
  }
}

simplest way, you can use box2d library for complex collision thing

7 Likes

I have a shapes library I wrote that does generic 2D collision detection. If I just pull the polygon-polygon code out, it looks like this – use line-line, then check each edge of a polygon against a line, then check each edge of a polygon against each edge of a polygon. Presto: polygon-polygon collision detection.

The format here is .java, by the way.

  1. First, start with the line-line algorithm
package com.jeremydouglass.toolboxing.collisions;

import java.lang.Math;
import processing.core.PApplet;
import processing.core.PConstants;
import processing.core.PVector;

  /**
   * Line / Line collision detection.
   *
   * @param   x1   line A origin x
   * @param   y1   line A origin y
   * @param   x2   line A endpoint x
   * @param   y2   line A endpoint y
   * @param   x3   line B origin x
   * @param   y3   line B origin y
   * @param   x4   line B endpoint x
   * @param   y4   line B endpoint y
   * @return  true on collision
   *
   * See http://www.jeffreythompson.org/collision-detection/line-line.php
   */
  public static 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);

      return true;
    }
    return false;
  }
  1. next, use that to detect if a line collides with a polygon – this is, if it crosses any line in the polygon.
  // http://www.jeffreythompson.org/collision-detection/poly-line.php
  // POLYGON/LINE
  public static boolean polyLine(PVector[] vertices, float x1, float y1, float x2, float y2) {

    // go through each of the vertices, plus the next
    // vertex in the list
    int next = 0;
    for (int current=0; current<vertices.length; current++) {

      // get next vertex in list
      // if we've hit the end, wrap around to 0
      next = current+1;
      if (next == vertices.length) next = 0;

      // get the PVectors at our current position
      // extract X/Y coordinates from each
      float x3 = vertices[current].x;
      float y3 = vertices[current].y;
      float x4 = vertices[next].x;
      float y4 = vertices[next].y;

      // do a Line/Line comparison
      // if true, return 'true' immediately and
      // stop testing (faster)
      boolean hit = lineLine(x1, y1, x2, y2, x3, y3, x4, y4);
      if (hit) {
        return true;
      }
    }
    // never got a hit
    return false;
  }
  1. Finally, use that to make a polygon-polygon collision detection – which loops through each line in polygon A and checks for a collision against each line of polygon B. This is edge-based collision – optionally, it can also detect full containment.
  // http://www.jeffreythompson.org/collision-detection/poly-poly.php
  // POLYGON/POLYGON
  public static boolean polyPoly(PVector[] p1, PVector[] p2) {

    // go through each of the vertices, plus the next
    // vertex in the list
    int next = 0;
    for (int current=0; current<p1.length; current++) {

      // get next vertex in list
      // if we've hit the end, wrap around to 0
      next = current+1;
      if (next == p1.length) next = 0;

      // get the PVectors at our current position
      // this makes our if statement a little cleaner
      PVector vc = p1[current];    // c for "current"
      PVector vn = p1[next];       // n for "next"

      // now we can use these two points (a line) to compare
      // to the other polygon's vertices using polyLine()
      boolean collision = polyLine(p2, vc.x, vc.y, vn.x, vn.y);
      if (collision) return true;

      //// optional: check if the 2nd polygon is INSIDE the first
      //collision = polyPoint(p1, p2[0].x, p2[0].y);
      //if (collision) return true;
    }
    return false;
  }
4 Likes

Thank you for all informations… I will look all the proposal solution (i am artist not coder)… Nice forum for the new learner…

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

Here is an example I came up with to solve this problem.
click on the grid to add points. This is based on an old sketch which orders points around a circle. Replace the instances of ogrid. which are the ordered points with grid., to get more complex shapes. The algorithm currently makes use of the atan2 which isnt necessarily efficient.

Ps i dont know how to create complex shapes with vertices yet so the fill effect is off, but the algorithm works.

this returns false if shape1 is inside shape2