# 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

collision between irregular shape and circle

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++) {
}
// 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
}

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.

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