OmkarPathak · Sep 19, 2017
diff --git a/...st_geometry/test_extrapolated_intersection/az_test_one_moving_many_stationary_touching.py b/...st_geometry/test_extrapolated_intersection/az_test_one_moving_many_stationary_touching.py
@@ -0,0 +1,44 @@
+from utils import create_newfig, create_moving_polygon, create_still_polygon, run_or_export
+
+func_code = 'az'
+func_name = 'test_one_moving_many_stationary_touching'
+
+def setup_fig01():
+    fig, ax, renderer = create_newfig('{}01'.format(func_code), xlim=(-1, 12), ylim=(-1, 12))
+    create_moving_polygon(fig, ax, renderer, ((3, 3, 'botleft'), (4, 3), (4, 4), (3, 4)), (3, 4), 'none')
+    create_still_polygon(fig, ax, renderer, ((6, 3, 'botleft'), (7, 3), (7, 4), (6, 4)), 'none')
+    create_still_polygon(fig, ax, renderer, ((3, 6, 'botleft'), (3, 7), (4, 7), (4, 6)), 'none')
+    create_still_polygon(fig, ax, renderer, ((4, 10), (6, 11), (6, 8), (2, 7)))
+
+    return fig, ax, '{}01_{}'.format(func_code, func_name)
+
+def setup_fig02():
+    fig, ax, renderer = create_newfig('{}02'.format(func_code), xlim=(-3, 9), ylim=(-10, 5))
+    create_moving_polygon(fig, ax, renderer, ((-1, -9.5), (-1, -5.5), (3, -5.5), (4, -7.5)), (4, 6))
+    create_still_polygon(fig, ax, renderer, ((6, -6), (8, -7), (7, -9)))
+    create_still_polygon(fig, ax, renderer, ((0, 2), (2, 3), (1, 1)))
+    create_still_polygon(fig, ax, renderer, ((-2, -2, 'botleft'), (-2, -1), (-1, -1), (-1, -2)), 'none')
+    create_still_polygon(fig, ax, renderer, ((8, -4, 'botleft'), (8, -3), (7, -3), (7, -4)), 'none')
+
+    return fig, ax, '{}02_{}'.format(func_code, func_name)
+
+def setup_fig03():
+    fig, ax, renderer = create_newfig('{}03'.format(func_code), xlim=(-1, 21), ylim=(-1, 15))
+    create_moving_polygon(fig, ax, renderer, ((18.5, 3), (17.5, 3), (17.5, 5), (19.5, 5)), (-12.5, 2))
+    create_still_polygon(fig, ax, renderer, ((18, 13), (20, 14), (18.5, 11)))
+    create_still_polygon(fig, ax, renderer, ((5, 5), (6, 2), (3, 3), (2, 4)))
+
+    return fig, ax, '{}03_{}'.format(func_code, func_name)
+
+def setup_fig04():
+    fig, ax, renderer = create_newfig('{}04'.format(func_code), xlim=(-9, 7), ylim=(-4, 6))
+    create_moving_polygon(fig, ax, renderer, ((-6, 2), (-6, 1), (-8, 0), (-8, 2)), (5, 1))
+    create_still_polygon(fig, ax, renderer, ((-7, 3, 'botleft'), (-7, 4), (-6, 4), (-6, 3)), 'none')
+    create_still_polygon(fig, ax, renderer, ((-6, 3, 'botleft'), (-6, 4), (-5, 4), (-5, 3)), 'none')
+    create_still_polygon(fig, ax, renderer, ((-5, 3, 'botleft'), (-5, 4), (-4, 4), (-4, 3)), 'none')
+    create_still_polygon(fig, ax, renderer, ((-4, 3, 'botleft'), (-4, 4), (-3, 4), (-3, 3)), 'none')
+
+
+    return fig, ax, '{}04_{}'.format(func_code, func_name)
+
+run_or_export(setup_fig01, setup_fig02, setup_fig03, setup_fig04)
diff --git a/...extrapolated_intersection/out/az01_test_one_moving_many_stationary_touching.png b/...extrapolated_intersection/out/az01_test_one_moving_many_stationary_touching.png
diff --git a/...extrapolated_intersection/out/az02_test_one_moving_many_stationary_touching.png b/...extrapolated_intersection/out/az02_test_one_moving_many_stationary_touching.png
diff --git a/...extrapolated_intersection/out/az03_test_one_moving_many_stationary_touching.png b/...extrapolated_intersection/out/az03_test_one_moving_many_stationary_touching.png
diff --git a/...extrapolated_intersection/out/az04_test_one_moving_many_stationary_touching.png b/...extrapolated_intersection/out/az04_test_one_moving_many_stationary_touching.png
diff --git a/pygorithm/geometry/extrapolated_intersection.py b/pygorithm/geometry/extrapolated_intersection.py
@@ -17,6 +17,85 @@
 
 """
 
+from pygorithm.geometry import (vector2, line2, polygon2, axisall)
+import math
+
+def __calc_one_moving_one_stat_vertical_velocity(point, velocity, line, offset):
+  line_as_axisall = axisall.AxisAlignedLine(None, line.min_x + offset.x, line.max_x + offset.x)
+  outer, inner = axisall.AxisAlignedLine.contains_point(line_as_axisall, point.x)
+  if not outer and not inner:
+    return False, None
+
+  if line.vertical:
+    if velocity.y > 0:
+      if point.y < line.min_y + offset.y:
+        dist = line.min_y + offset.y - point.y
+        return True, dist
+      else:
+        return False, None
+    else:
+      if point.y > line.max_y + offset.y:
+        dist = point.y - line.max_y - offset.y
+        return True, dist
+      else:
+        return False, None
+
+  line_yintr = line.calculate_y_intercept(offset)
+  liney_at_pointx = line.slope * point.x + line_yintr
+
+  point_to_line = liney_at_pointx - point.y
+  if not math.isclose(math.copysign(1, point_to_line), math.copysign(1, velocity.y)):
+    return False, None
+
+  return True, abs(point.y - liney_at_pointx)
+
+def __calc_one_moving_one_stat_vertical_line(point, velocity, line, offset):
+  # nonvertical velocity, point not on line
+
+  if math.isclose(point.x, line.start.x, abs_tol = 1e-07):
+    # it's impossible that the point intersects a vertical line that it 
+    # is at the start of except at the point, but that's checked previously
+    return False, None
+
+  if velocity.x > 0 and (line.start.x + offset.x) < point.x:
+    return False, None
+  if velocity.x < 0 and (line.start.x + offset.x) > point.x:
+    return False, None
+
+  point_slope = velocity.y / velocity.x
+  point_yintr = point.y - point_slope * point.x
+
+  point_y_at_line_x = point_slope * (line.start.x + offset.x) + point_yintr
+
+  line_as_axisall = axisall.AxisAlignedLine(None, line.min_y + offset.y, line.max_y + offset.y)
+  outer, inner = axisall.AxisAlignedLine.contains_point(line_as_axisall, point_y_at_line_x)
+  if not outer and not inner:
+    return False, None
+
+  dist = (vector2.Vector2(line.start.x + offset.x, point_y_at_line_x) - point).magnitude()
+  return True, dist
+
+def __calc_one_moving_one_stat_parallel(point, velocity, line, offset, point_slope):
+  # vel not vertical, line not vertical, point not on line, line is parallel to velocity
+
+  if not math.isclose(line.slope, point_slope, abs_tol=1e-07):
+    return False, None
+
+  line_as_axisall = axisall.AxisAlignedLine(line.axis, (line.start + offset).dot(line.axis), (line.end + offset).dot(line.axis))
+  point_on_axis = point.dot(line.axis)
+  vel_on_axis_sign = math.copysign(1, velocity.dot(line.axis))
+
+  if point_on_axis < line_as_axisall.min:
+    if vel_on_axis_sign < 0:
+      return False, None
+    else:
+      return True, line_as_axisall.min - point_on_axis
+  else:
+    if vel_on_axis_sign > 0:
+      return False, None
+    else:
+      return True, point_on_axis - line_as_axisall.max 
+
 def calculate_one_moving_point_and_one_stationary_line(point, velocity, line, offset):
     """
     Determine if the point moving at velocity will intersect the line.
@@ -41,7 +120,40 @@ def calculate_one_moving_point_and_one_stationary_line(point, velocity, line, of
     :returns: if the point will intersect the line, distance until intersection
     :rtype: bool, :class:`numbers.Number` or None
     """
-    return False, -1
+    if offset is None:
+      offset = vector2.Vector2(0, 0)
+
+    if line2.Line2.contains_point(line, point, offset):
+      return True, 0
+
+    if math.isclose(velocity.x, 0, abs_tol=1e-07):
+      return __calc_one_moving_one_stat_vertical_velocity(point, velocity, line, offset)
+    if line.vertical:
+      return __calc_one_moving_one_stat_vertical_line(point, velocity, line, offset)
+
+    point_slope = velocity.y / velocity.x
+    if math.isclose(line.slope, point_slope, abs_tol=1e-07):
+      return __calc_one_moving_one_stat_parallel(point, velocity, line, offset, point_slope)
+
+    point_yintr = point.y - point_slope * point.x
+    line_yintr = line.calculate_y_intercept(offset)
+
+    # m1x + b1 = m2x + b2
+    # x = b2 - b1 / m1 - m2
+    intr_x = (line_yintr - point_yintr) / (point_slope - line.slope)
+    intr_y = point_slope * intr_x + point_yintr 
+    intr_vec = vector2.Vector2(intr_x, intr_y)
+    if not line2.Line2.contains_point(line, intr_vec, offset):
+      return False, None
+
+    point_to_intr = intr_vec - point
+    vel_normal = velocity.normalize()
+    ptintr_dot_veln = point_to_intr.dot(vel_normal)
+
+    if ptintr_dot_veln < 0:
+      return False, None 
+
+    return True, ptintr_dot_veln
 
 def calculate_one_moving_line_and_one_stationary_line(line1, offset1, velocity1, _line2, offset2):
     """

diff --git a/tests/test_geometry.py b/tests/test_geometry.py
@@ -1584,9 +1584,9 @@ def test_point_line_intr_later(self):
         self.assertAlmostEqual(3, dist, msg=repr(offset))
 
         # ad04
-        intr, dist, offset = fn(self.pt(6, 4), self.pt(-3, -1).normalize(), self.ln(self.pt(1, 1), self.pt(5, 3)))
+        intr, dist, offset = fn(self.pt(6, 4), self.pt(-3, -2).normalize(), self.ln(self.pt(1, 1), self.pt(5, 3)))
         self.assertTrue(intr, msg=repr(offset))
-        self.assertAlmostEqual(self.pt(-3, -1).magnitude(), dist, msg=repr(offset))
+        self.assertAlmostEqual(self.pt(-3, -2).magnitude(), dist, msg=repr(offset))
 
 
     # calculate_one_moving_line_and_one_stationary_line
@@ -2133,7 +2133,41 @@ def test_one_moving_many_stationary_no_intr(self):
         self.assertFalse(intr, msg=msg)
 
     def test_one_moving_many_stationary_touching(self):
-        pass
+        fn = self._calc_one_moving_many_stat_fuzzer
+
+        # az01
+        intr, msg = fn(((3, 3), (4, 3), (4, 4), (3, 4)), (3, 4), [
+          ((6, 3), (7, 3), (7, 4), (6, 4)),
+          ((3, 6), (3, 7), (4, 7), (4, 6)),
+          ((4, 10), (6, 11), (6, 8), (2, 7))
+        ])
+        self.assertFalse(intr, msg=msg)
+
+        # az02
+        intr, msg = fn(((-1, -9.5), (-1, -5.5), (3, -5.5), (4, -7.5)), (4, 6), [
+          ((6, -6), (8, -7), (7, -9)),
+          ((0, 2), (2, 3), (1, 1)),
+          ((-2, -2), (-2, -1), (-1, -1), (-1, -2)),
+          ((8, -4), (8, -3), (7, -3), (7, -4))
+        ])
+        self.assertFalse(intr, msg=msg)
+
+        # az03
+        intr, msg = fn(((18.5, 3), (17.5, 3), (17.5, 5), (19.5, 5)), (-12.5, 2), [
+          ((18, 13), (20, 14), (18.5, 11)),
+          ((5, 5), (6, 2), (3, 3), (2, 4))
+        ])
+        self.assertFalse(intr, msg=msg)
+
+        # az04
+        intr, msg = fn(((-6, 2), (-6, 1), (-8, 0), (-8, 2)), (-4, 6), [
+          ((-7, 3), (-7, 4), (-6, 4), (-6, 3)),
+          ((-6, 3), (-6, 4), (-5, 4), (-5, 3)),
+          ((-5, 3), (-5, 4), (-4, 4), (-4, 3)),
+          ((-4, 3), (-4, 4), (-3, 4), (-3, 3))
+        ])
+        self.assertFalse(intr, msg=msg)
+
     def test_one_moving_many_stationary_intr_at_start(self):
         pass
     def test_one_moving_many_stationary_intr_later(self):