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.

Answer

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)