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)