# Collision detection between 2 irregular shapes

I need to implement a collision system for a vertical-shotter and the bullets can have any type of shape; i've implemented the shape class with an array of choords and an array of lines which have the references of start and end points; in case the line is bezier it have an array of anchor points.

so:

Line { Choord Start,End; Choord [] Anchors = null; ... }
Choord { float X, Y; ... }
Shape { Choord [] Vertexs; Line [] Lines; ... }


i have to handle a collision like this:

anyone have a general idea for check collision with this type of shapes? and this model can work?

i've tryed with SAT collisions but it works only for convex polygons.

• When an object is concave you will need to perform triangulation, and then you can test for collision detection. Other than that you are really complicating things. – concept3d Oct 19 '14 at 13:05
• I can subdivide the shape into triangles , and " triangles with a curved edge" ? i need to Implement mixed shapes because the hitboxes are created by users. – Andrea Demontis Oct 19 '14 at 13:10
• You don't need to represent real curves in your collision detection (even the draw curves are approximations). Rough approximation using multiple triangles is good enough. And the user won't notice. Remember that this is called engineering, you don't need a 100% exact representation (even if you want, you can't because of various precision and memory limitations). – concept3d Oct 19 '14 at 13:24

In general you can check if any Intersection exist between your two polygon (even non-convex) as below.

Problem: Given n line segments; Report all(as k in algorithms) Intersections.

You can implement any of these two algorithm in your desire language and use them. they take your line segments as input and return if any intersection ( Collision in your case) exists.

Note: Time/Space complexity of these algorithms for collision detection break with k=1. because as you see first intersection, you can stop algorithm and report collision.

Solution 1: Sweep Algorithm (Bentley, Ottmann '79)

Time Complexity: O(n*lg(n)+k)

Space Complexity: O(n+k)

Pseudo Code:

ReportIntersections()
{

Initialize event queue EQ = all segment endpoints;
Sort EQ by increasing x and y;
Initialize sweep line SL to be empty;
Initialize output intersection list IL to be empty;

While (EQ is nonempty) {
Let E = the next event from EQ;
If (E is a left endpoint) {
Let segE = E's segment;
Let segA = the segment Above segE in SL;
Let segB = the segment Below segE in SL;
If (I = Intersect( segE with segA) exists)
Insert I into EQ;
If (I = Intersect( segE with segB) exists)
Insert I into EQ;
}
Else If (E is a right endpoint) {
Let segE = E's segment;
Let segA = the segment Above segE in SL;
Let segB = the segment Below segE in SL;
Delete segE from SL;
If (I = Intersect( segA with segB) exists)
If (I is not in EQ already)
Insert I into EQ;
}
Else {  // E is an intersection event
Add E’s intersect point to the output list IL;
Let segE1 above segE2 be E's intersecting segments in SL;
Swap their positions so that segE2 is now above segE1;
Let segA = the segment above segE2 in SL;
Let segB = the segment below segE1 in SL;
If (I = Intersect(segE2 with segA) exists)
If (I is not in EQ already)
Insert I into EQ;
If (I = Intersect(segE1 with segB) exists)
If (I is not in EQ already)
Insert I into EQ;
}
remove E from EQ;
}
return IL;
}


Solution 2: Divide & Conquer Algorithm (Balaban '95)

Complexity: O(n*lg(n)+k)

Space Complexity: O(n)