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
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.
- 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;
}
- 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;
}
- 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