CODEWITHSUNDEEP
algorithmmathlinecollision-detection
Asperger
Asperger

Reputation: 3222

How to detect collision of a circle on a polyline (line with multiple angles)?

Lets assume we have a zig zag line or something with multiple angles. How exactly do you catch if a point is touching the line? For example, lets assume I have a scenario like this: enter image description here]

Upvotes: 1

Views: 145

Answers (1)

mengg
mengg

Reputation: 310

The following python code works for me to compute the shortest distance from a point to a sequence of line segments:

from math import sqrt

def point_distance_to_line_segment((x,y),(lx1, ly1),(lx2, ly2)):
    line_length = sqrt((lx1-lx2)**2+(ly1-ly2)**2)
    dot_product = (x-lx1)*(lx2-lx1)+(y-ly1)*(ly2-ly1)

    proj_line = dot_product/line_length

    if proj_line < 0:
        # close to (x1,y1)
        return sqrt((x-lx1)**2+(y-ly1)**2)
    elif proj_line > line_length:
        # close to (x2,y2)
        return sqrt((x-lx2)**2+(y-ly2)**2)
    else:
        # in the middle
        cross_product = abs((x-lx1)*(ly2-ly1)-(y-ly1)*(lx2-lx1))
        return cross_product/line_length


line_pts = [(-1, 0), (0, 1), (1, 0), (2,0)]
test_p = (-1, 0)

print min([point_distance_to_line_segment(test_p,lp1,lp2) 
           for (lp1,lp2) in zip(line_pts[0::2], line_pts[1::2])])

Not sure if there is a way to avoid iterating through all segments. Then you can simply compare this shortest distance to your circle radius.

Upvotes: 2

Related Questions