2
\$\begingroup\$

I am drawing a continuous line using Pixmap. I want to check for a collision / intersection of my line with the already drawn line.

\$\endgroup\$
1
\$\begingroup\$

In general you can check if any Intersection exist between your two lines 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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.