pt-line.py

class Point(object):
  def __init__(self, x, y):
    self.x = float(x)
    self.y = float(y)

def square(x):
  return x * x

def distance_squared(v, w):
  return square(v.x - w.x) + square(v.y - w.y)

def distance_point_segment_squared(p, v, w):
  # Segment length squared, |w-v|^2
  d2 = distance_squared(v, w) 
  if d2 == 0: 
    # v == w, return distance to v
    return distance_squared(p, v)
  # Consider the line extending the segment, parameterized as v + t (w - v).
  # We find projection of point p onto the line.
  # It falls where t = [(p-v) . (w-v)] / |w-v|^2
  t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / d2;
  if t < 0:
    # Beyond v end of the segment
    return distance_squared(p, v)
  elif t > 1.0:
    # Beyond w end of the segment
    return distance_squared(p, w)
  else:
    # Projection falls on the segment.
    proj = Point(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y))
    # print proj.x, proj.y
    return distance_squared(p, proj)
    
# set up a random line and a point 
    
from shapely.geometry import LineString
import random

last_vtx = (0.0,0.0)
line_array = [last_vtx]
for _ in range(10):
    nxt = (last_vtx[0] + random.random()*10, last_vtx[1] + random.random()*10)
    line_array.append(nxt)
    last_vtx = nxt
line = LineString(line_array)
bounds = line.bounds
point = Point(*bounds[1:3])

# a pairwise generator

def pairs(l):
    c = l.coords
    return zip(c,c[1:])
    
def check(line, dist):
    d2 = dist*dist
    for pair in pairs(line):
        dl = distance_point_segment_squared(point, Point(*pair[0]), Point(*pair[1]))
        if dl < d2:
            return True
    return False

# for the line I generated 48 is close to the midpoint
%timeit check(line, 24)
%timeit check(line, 48)
%timeit check(line, 1000)


57.9 µs ± 737 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
48.9 µs ± 989 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
37.1 µs ± 820 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)


# try it with shapely
from shapely.geometry import Point as Pt
pt = Pt(*bounds[1:3])

def check2(line, dist):
    return pt.distance(line) < dist
    
%timeit check2(line, 24)
%timeit check2(line, 48)
%timeit check2(line, 1000)

6.05 µs ± 173 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
5.92 µs ± 95.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
6 µs ± 144 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)