Irregular shapes collision detection

Processing Coding Questions
5

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