1

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]

Community
  • 1
  • 1
Asperger
  • 3,064
  • 8
  • 52
  • 100
  • Shouldn't it be possble to simply check every segment for a collision with the circle? http://stackoverflow.com/questions/1073336/circle-line-segment-collision-detection-algorithm – Marco13 Oct 08 '16 at 16:05
  • @Marco13 you mean by searching for the nearest segment? – Asperger Oct 08 '16 at 16:07
  • If you find the slope of the line and the slope of tangent line overlaps, you know they collide. – Grendizer Oct 08 '16 at 16:07
  • @Grendizer indeed but just from point A to B. That means I would have to loop through the lines segments and do the same check for each one? – Asperger Oct 08 '16 at 16:09
  • I gotta think on how to minimize the number of steps to find the solution.. – Grendizer Oct 08 '16 at 16:13
  • @Grendizer so then a function that does the typical check. I figure out the equation of a perpendicular line to the target line. Then I see where they intersect (intersection point). At last I check if target point and intersection point delta are near 0. If yes then there is a collision. Then I use this function in a loop. The loop gets all the lines that make up the polyline. – Asperger Oct 08 '16 at 16:18
  • That sounds good :) – Grendizer Oct 08 '16 at 16:41
  • Is the motion of the circle linear? – Grendizer Oct 08 '16 at 16:42
  • @Grendizer the circle is actually the mouse coordinates and the line is an svg path. So I think yes. – Asperger Oct 08 '16 at 16:44
  • If you just want to check **if** the circle touches one of the line segments (and not *where* it touches it), then you can just do `foreach (segment) if (circle.center.distanceTo(segment) < circle.radius) return true;`. – Marco13 Oct 08 '16 at 17:44

1 Answers1

2

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.

mengg
  • 310
  • 2
  • 9