Collision detection between 2 irregular shapes

Question

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.

Answer 1

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;
            Add segE to SL;
            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)