OmkarPathak · OmkarPathak · Sep 8, 2017 · Sep 4, 2017 · Sep 5, 2017 · Sep 6, 2017
diff --git a/docs/Geometry.rst b/docs/Geometry.rst
@@ -55,6 +55,7 @@ Features
 * Algorithms available:
     - Separating Axis Theorem (polygon2)
     - Broad-phase (rect2)
+    - Extrapolated intersection (extrapolated_intersection)
 
 Vector2
 -------
@@ -92,6 +93,10 @@ Axis-Aligned Rectangle
     :special-members:
     :private-members:
 
-
+Extrapolated Intersection
+-------------------------
+
+.. automodule:: pygorithm.geometry.extrapolated_intersection
+    :members:
 
 
diff --git a/imgs/test_geometry/test_extrapolated_intersection/__init__.py b/imgs/test_geometry/test_extrapolated_intersection/__init__.py
diff --git a/imgs/test_geometry/test_extrapolated_intersection/aa_test_point_line_no_intr.py b/imgs/test_geometry/test_extrapolated_intersection/aa_test_point_line_no_intr.py
@@ -0,0 +1,31 @@
+from utils import create_newfig, create_moving_point, create_still_segment, run_or_export
+
+def setup_fig01():
+    fig, ax, renderer = create_newfig('aa01')
+
+    create_moving_point(fig, ax, renderer, 1, 1, 6, 1)
+    create_still_segment(fig, ax, renderer, (2, 4), (6, 2))
+    return fig, ax, 'aa01_test_point_line_no_intr'
+
+def setup_fig02():
+    fig, ax, renderer = create_newfig('aa02')
+
+    create_moving_point(fig, ax, renderer, 1, 1, 1, 4)
+    create_still_segment(fig, ax, renderer, (2, 4), (6, 2), 'topright')
+    return fig, ax, 'aa02_test_point_line_no_intr'
+
+def setup_fig03():
+    fig, ax, renderer = create_newfig('aa03')
+
+    create_moving_point(fig, ax, renderer, 4, 1, 1, 4)
+    create_still_segment(fig, ax, renderer, (2, 4), (6, 4), 'topright')
+    return fig, ax, 'aa03_test_point_line_no_intr'
+
+def setup_fig04():
+    fig, ax, renderer = create_newfig('aa04')
+
+    create_moving_point(fig, ax, renderer, 2, 1, 6, 4)
+    create_still_segment(fig, ax, renderer, (1, 2), (5, 4), 'topleft')
+    return fig, ax, 'aa04_test_point_line_no_intr'
+
+run_or_export(setup_fig01, setup_fig02, setup_fig03, setup_fig04)
diff --git a/imgs/test_geometry/test_extrapolated_intersection/ab_test_point_line_touching.py b/imgs/test_geometry/test_extrapolated_intersection/ab_test_point_line_touching.py
@@ -0,0 +1,34 @@
+from utils import create_newfig, create_moving_point, create_still_segment, run_or_export
+
+func_code = 'ab'
+func_name = 'test_point_line_touching'
+
+def setup_fig01():
+    fig, ax, renderer = create_newfig('{}01'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 1, 1, 2, 4)
+    create_still_segment(fig, ax, renderer, (2, 4), (6, 2), 'topright')
+    return fig, ax, '{}01_{}'.format(func_code, func_name)
+
+def setup_fig02():
+    fig, ax, renderer = create_newfig('{}02'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 2, 1, 6, 2)
+    create_still_segment(fig, ax, renderer, (2, 0), (6, 2), 'botright')
+    return fig, ax, '{}02_{}'.format(func_code, func_name)
+
+def setup_fig03():
+    fig, ax, renderer = create_newfig('{}03'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 2, 1, 2, 0)
+    create_still_segment(fig, ax, renderer, (2, 0), (6, 2), 'botright')
+    return fig, ax, '{}03_{}'.format(func_code, func_name)
+
+def setup_fig04():
+    fig, ax, renderer = create_newfig('{}04'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 6.25, 3, 2, 0, 'topright')
+    create_still_segment(fig, ax, renderer, (2, 0), (6, 2), 'botright')
+    return fig, ax, '{}04_{}'.format(func_code, func_name)
+
+run_or_export(setup_fig01, setup_fig02, setup_fig03, setup_fig04)
diff --git a/imgs/test_geometry/test_extrapolated_intersection/ac_test_point_line_touching_at_start.py b/imgs/test_geometry/test_extrapolated_intersection/ac_test_point_line_touching_at_start.py
@@ -0,0 +1,34 @@
+from utils import create_newfig, create_moving_point, create_still_segment, run_or_export
+
+func_code = 'ac'
+func_name = 'test_point_line_touching_at_start'
+
+def setup_fig01():
+    fig, ax, renderer = create_newfig('{}01'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 4, 1, 3, 2, 'top')
+    create_still_segment(fig, ax, renderer, (2, 0), (6, 2), 'botright')
+    return fig, ax, '{}01_{}'.format(func_code, func_name)
+
+def setup_fig02():
+    fig, ax, renderer = create_newfig('{}02'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 2, 2, 1, 2, 'top')
+    create_still_segment(fig, ax, renderer, (2, 2), (6, 2), 'botright')
+    return fig, ax, '{}02_{}'.format(func_code, func_name)
+
+def setup_fig03():
+    fig, ax, renderer = create_newfig('{}03'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 3, 1, 4, 2, 'left')
+    create_still_segment(fig, ax, renderer, (3, 0), (3, 4), 'botright')
+    return fig, ax, '{}03_{}'.format(func_code, func_name)
+
+def setup_fig04():
+    fig, ax, renderer = create_newfig('{}04'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 3, 4, 2, 4, 'top')
+    create_still_segment(fig, ax, renderer, (3, 0), (3, 4), 'botright')
+    return fig, ax, '{}04_{}'.format(func_code, func_name)
+
+run_or_export(setup_fig01, setup_fig02, setup_fig03, setup_fig04)
diff --git a/imgs/test_geometry/test_extrapolated_intersection/ad_test_point_line_intr_later.py b/imgs/test_geometry/test_extrapolated_intersection/ad_test_point_line_intr_later.py
@@ -0,0 +1,34 @@
+from utils import create_newfig, create_moving_point, create_still_segment, run_or_export
+
+func_code = 'ad'
+func_name = 'test_point_line_intr_later'
+
+def setup_fig01():
+    fig, ax, renderer = create_newfig('{}01'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 0, 2, 3, 1, 'topright')
+    create_still_segment(fig, ax, renderer, (3, 0), (3, 4), 'botright')
+    return fig, ax, '{}01_{}'.format(func_code, func_name)
+
+def setup_fig02():
+    fig, ax, renderer = create_newfig('{}02'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 6, 2, 3, 2, 'top')
+    create_still_segment(fig, ax, renderer, (3, 0), (3, 4), 'botright')
+    return fig, ax, '{}02_{}'.format(func_code, func_name)
+
+def setup_fig03():
+    fig, ax, renderer = create_newfig('{}03'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 6, 2, 3, 2, 'top')
+    create_still_segment(fig, ax, renderer, (1, 1), (5, 3), 'botright')
+    return fig, ax, '{}03_{}'.format(func_code, func_name)
+
+def setup_fig04():
+    fig, ax, renderer = create_newfig('{}04'.format(func_code))
+
+    create_moving_point(fig, ax, renderer, 6, 4, 3, 2, 'top')
+    create_still_segment(fig, ax, renderer, (1, 1), (5, 3), 'botright')
+    return fig, ax, '{}04_{}'.format(func_code, func_name)
+
+run_or_export(setup_fig01, setup_fig02, setup_fig03, setup_fig04)
diff --git a/imgs/test_geometry/test_extrapolated_intersection/ae_test_line_line_no_intr.py b/imgs/test_geometry/test_extrapolated_intersection/ae_test_line_line_no_intr.py
@@ -0,0 +1,34 @@
+from utils import create_newfig, create_moving_line, create_still_segment, run_or_export
+
+func_code = 'ae'
+func_name = 'test_line_line_no_intr'
+
+def setup_fig01():
+    fig, ax, renderer = create_newfig('{}01'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (1, 4), (1, 3), (2, 0), 'botright')
+    create_still_segment(fig, ax, renderer, (1, 1), (3, 2), 'bot')
+    return fig, ax, '{}01_{}'.format(func_code, func_name)
+
+def setup_fig02():
+    fig, ax, renderer = create_newfig('{}02'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (1, 3), (2, 4), (3, -3), 'topleft')
+    create_still_segment(fig, ax, renderer, (1, 0.5), (3, 0.5), 'bot')
+    return fig, ax, '{}02_{}'.format(func_code, func_name)
+
+def setup_fig03():
+    fig, ax, renderer = create_newfig('{}03'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (1, 3), (2, 4), (3, -3), 'topleft')
+    create_still_segment(fig, ax, renderer, (4, 3), (6, 4), 'botright')
+    return fig, ax, '{}03_{}'.format(func_code, func_name)
+
+def setup_fig04():
+    fig, ax, renderer = create_newfig('{}04'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (1, 3), (2, 3), (3, -3), 'bot')
+    create_still_segment(fig, ax, renderer, (0, 4), (3, 3), 'topright')
+    return fig, ax, '{}04_{}'.format(func_code, func_name)
+
+run_or_export(setup_fig01, setup_fig02, setup_fig03, setup_fig04)
diff --git a/imgs/test_geometry/test_extrapolated_intersection/af_test_line_line_touching.py b/imgs/test_geometry/test_extrapolated_intersection/af_test_line_line_touching.py
@@ -0,0 +1,34 @@
+from utils import create_newfig, create_moving_line, create_still_segment, run_or_export
+
+func_code = 'af'
+func_name = 'test_line_line_touching'
+
+def setup_fig01():
+    fig, ax, renderer = create_newfig('{}01'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (1, 3), (2, 3), (3, -3), 'top')
+    create_still_segment(fig, ax, renderer, (3, 3), (5, 0), 'topright')
+    return fig, ax, '{}01_{}'.format(func_code, func_name)
+
+def setup_fig02():
+    fig, ax, renderer = create_newfig('{}02'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (1, 1), (2, 1), (1, 1), 'bot')
+    create_still_segment(fig, ax, renderer, (3, 2), (3, 3), 'right')
+    return fig, ax, '{}02_{}'.format(func_code, func_name)
+
+def setup_fig03():
+    fig, ax, renderer = create_newfig('{}03'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (1, 1), (2, 1), (2, 2), 'bot')
+    create_still_segment(fig, ax, renderer, (2, 3), (3, 3), 'top')
+    return fig, ax, '{}03_{}'.format(func_code, func_name)
+
+def setup_fig04():
+    fig, ax, renderer = create_newfig('{}04'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (1, 1), (2, 1), (0, 2), 'bot')
+    create_still_segment(fig, ax, renderer, (2, 3), (3, 3), 'top')
+    return fig, ax, '{}04_{}'.format(func_code, func_name)
+
+run_or_export(setup_fig01, setup_fig02, setup_fig03, setup_fig04)
diff --git a/imgs/test_geometry/test_extrapolated_intersection/ag_test_line_line_touching_at_start.py b/imgs/test_geometry/test_extrapolated_intersection/ag_test_line_line_touching_at_start.py
@@ -0,0 +1,34 @@
+from utils import create_newfig, create_moving_line, create_still_segment, run_or_export
+
+func_code = 'ag'
+func_name = 'test_line_line_touching_at_start'
+
+def setup_fig01():
+    fig, ax, renderer = create_newfig('{}01'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (1, 1), (2, 1), (0, 2), 'botleft')
+    create_still_segment(fig, ax, renderer, (2, 1), (3, 0), 'topright')
+    return fig, ax, '{}01_{}'.format(func_code, func_name)
+
+def setup_fig02():
+    fig, ax, renderer = create_newfig('{}02'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (1, 1), (1, 3), (2, 0), 'left')
+    create_still_segment(fig, ax, renderer, (1, 2), (2, 2), 'topright')
+    return fig, ax, '{}02_{}'.format(func_code, func_name)
+
+def setup_fig03():
+    fig, ax, renderer = create_newfig('{}03'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (1, 1), (2, 0), (2, 0), 'topright')
+    create_still_segment(fig, ax, renderer, (0, 1), (1.5, 0.5), 'botleft')
+    return fig, ax, '{}03_{}'.format(func_code, func_name)
+
+def setup_fig04():
+    fig, ax, renderer = create_newfig('{}04'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (5, 4), (6, 3), (-2, -2), 'topright')
+    create_still_segment(fig, ax, renderer, (5.5, 3.5), (6, 4), 'botleft', 'botright')
+    return fig, ax, '{}04_{}'.format(func_code, func_name)
+
+run_or_export(setup_fig01, setup_fig02, setup_fig03, setup_fig04)
diff --git a/imgs/test_geometry/test_extrapolated_intersection/ah_test_line_line_intr_later.py b/imgs/test_geometry/test_extrapolated_intersection/ah_test_line_line_intr_later.py
@@ -0,0 +1,34 @@
+from utils import create_newfig, create_moving_line, create_still_segment, run_or_export
+
+func_code = 'ah'
+func_name = 'test_line_line_intr_later'
+
+def setup_fig01():
+    fig, ax, renderer = create_newfig('{}01'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (5, 4), (6, 3), (-2, -2), 'topright')
+    create_still_segment(fig, ax, renderer, (3.5, 1.5), (3.5, 0), 'botleft', 'bot')
+    return fig, ax, '{}01_{}'.format(func_code, func_name)
+
+def setup_fig02():
+    fig, ax, renderer = create_newfig('{}02'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (5, 4), (5, 3), (-2, -2), 'topright')
+    create_still_segment(fig, ax, renderer, (3, 3), (3, 0), 'left')
+    return fig, ax, '{}02_{}'.format(func_code, func_name)
+
+def setup_fig03():
+    fig, ax, renderer = create_newfig('{}03'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (5, 4), (5, 3), (-2, 0), 'right')
+    create_still_segment(fig, ax, renderer, (1, 1), (3, 3.5), 'left')
+    return fig, ax, '{}03_{}'.format(func_code, func_name)
+
+def setup_fig04():
+    fig, ax, renderer = create_newfig('{}04'.format(func_code))
+
+    create_moving_line(fig, ax, renderer, (0, 1), (1, 0), (1, 2), 'topright')
+    create_still_segment(fig, ax, renderer, (2, 1), (2, 4), 'right')
+    return fig, ax, '{}04_{}'.format(func_code, func_name)
+
+run_or_export(setup_fig01, setup_fig02, setup_fig03, setup_fig04)
diff --git a/...test_geometry/test_extrapolated_intersection/ai_test_one_moving_one_stationary_no_intr.py b/...test_geometry/test_extrapolated_intersection/ai_test_one_moving_one_stationary_no_intr.py
@@ -0,0 +1,34 @@
+from utils import create_newfig, create_moving_polygon, create_still_polygon, run_or_export
+
+func_code = 'ai'
+func_name = 'test_one_moving_one_stationary_no_intr'
+
+def setup_fig01():
+    fig, ax, renderer = create_newfig('{}01'.format(func_code))
+
+    create_moving_polygon(fig, ax, renderer, ((0, 1, 'right'), (1, 2, 'bot'), (2, 1, 'left'), (1, 0, 'top')), (0, 2))
+    create_still_polygon(fig, ax, renderer, ((3, 1), (3, 2), (4, 1)), 'botleft')
+    return fig, ax, '{}01_{}'.format(func_code, func_name)
+
+def setup_fig02():
+    fig, ax, renderer = create_newfig('{}02'.format(func_code))
+
+    create_moving_polygon(fig, ax, renderer, ((0, 1, 'right'), (1, 2, 'bot'), (2, 1, 'left'), (1, 0, 'top')), (1, 2))
+    create_still_polygon(fig, ax, renderer, ((3, 1), (3, 2), (4, 1)), 'botleft')
+    return fig, ax, '{}02_{}'.format(func_code, func_name)
+
+def setup_fig03():
+    fig, ax, renderer = create_newfig('{}03'.format(func_code))
+
+    create_moving_polygon(fig, ax, renderer, ((4, 4), (5, 3.5), (5.5, 2.5), (4, 3)), (-2, 0), 'topright')
+    create_still_polygon(fig, ax, renderer, ((3, 1), (3, 2), (4, 1)), 'botleft')
+    return fig, ax, '{}03_{}'.format(func_code, func_name)
+
+def setup_fig04():
+    fig, ax, renderer = create_newfig('{}04'.format(func_code))
+
+    create_moving_polygon(fig, ax, renderer, ((3, 1), (3, 2), (4, 1)), (2, 0), 'botleft')
+    create_still_polygon(fig, ax, renderer, ((4, 4), (5, 3.5), (5.5, 2.5), (4, 3)), 'topright')
+    return fig, ax, '{}04_{}'.format(func_code, func_name)
+
+run_or_export(setup_fig01, setup_fig02, setup_fig03, setup_fig04)
diff --git a/...est_geometry/test_extrapolated_intersection/aj_test_one_moving_one_stationary_touching.py b/...est_geometry/test_extrapolated_intersection/aj_test_one_moving_one_stationary_touching.py
@@ -0,0 +1,34 @@
+from utils import create_newfig, create_moving_polygon, create_still_polygon, run_or_export
+
+func_code = 'aj'
+func_name = 'test_one_moving_one_stationary_touching'
+
+def setup_fig01():
+    fig, ax, renderer = create_newfig('{}01'.format(func_code))
+
+    create_moving_polygon(fig, ax, renderer, ((4, 2), (3, 3), (4, 4), (5, 3.5), (5.5, 2.5)), (-3, 0), 'topright')
+    create_still_polygon(fig, ax, renderer, ((0, 1), (1, 2), (2, 1), (1, 0)), 'botleft')
+    return fig, ax, '{}01_{}'.format(func_code, func_name)
+
+def setup_fig02():
+    fig, ax, renderer = create_newfig('{}02'.format(func_code))
+
+    create_moving_polygon(fig, ax, renderer, ((4, 2), (3, 3), (4, 4), (5, 3.5), (5.5, 2.5)), (-1, -2), 'topright')
+    create_still_polygon(fig, ax, renderer, ((0, 1), (1, 2), (2, 1), (1, 0)), 'botleft')
+    return fig, ax, '{}02_{}'.format(func_code, func_name)
+
+def setup_fig03():
+    fig, ax, renderer = create_newfig('{}03'.format(func_code))
+
+    create_moving_polygon(fig, ax, renderer, ((0, 1), (1, 1), (1, 0), (0, 0)), (1, 2), 'topright')
+    create_still_polygon(fig, ax, renderer, ((2, 2), (3, 3), (4, 2)), 'topright')
+    return fig, ax, '{}03_{}'.format(func_code, func_name)
+
+def setup_fig04():
+    fig, ax, renderer = create_newfig('{}04'.format(func_code))
+
+    create_moving_polygon(fig, ax, renderer, ((0, 1), (1, 1), (1, 0), (0, 0)), (4, 1), 'topright')
+    create_still_polygon(fig, ax, renderer, ((2, 2), (3, 3), (4, 2)), 'topright')
+    return fig, ax, '{}04_{}'.format(func_code, func_name)
+
+run_or_export(setup_fig01, setup_fig02, setup_fig03, setup_fig04)