divide_and_conquer.closest_pair_of_points
=========================================

.. py:module:: divide_and_conquer.closest_pair_of_points

.. autoapi-nested-parse::

   The algorithm finds distance between closest pair of points
   in the given n points.
   Approach used -> Divide and conquer
   The points are sorted based on Xco-ords and
   then based on Yco-ords separately.
   And by applying divide and conquer approach,
   minimum distance is obtained recursively.

   >> Closest points can lie on different sides of partition.
   This case handled by forming a strip of points
   whose Xco-ords distance is less than closest_pair_dis
   from mid-point's Xco-ords. Points sorted based on Yco-ords
   are used in this step to reduce sorting time.
   Closest pair distance is found in the strip of points. (closest_in_strip)

   min(closest_pair_dis, closest_in_strip) would be the final answer.

   Time complexity: O(n * log n)



Attributes
----------

.. autoapisummary::

   divide_and_conquer.closest_pair_of_points.points


Functions
---------

.. autoapisummary::

   divide_and_conquer.closest_pair_of_points.closest_pair_of_points
   divide_and_conquer.closest_pair_of_points.closest_pair_of_points_sqr
   divide_and_conquer.closest_pair_of_points.column_based_sort
   divide_and_conquer.closest_pair_of_points.dis_between_closest_in_strip
   divide_and_conquer.closest_pair_of_points.dis_between_closest_pair
   divide_and_conquer.closest_pair_of_points.euclidean_distance_sqr


Module Contents
---------------

.. py:function:: closest_pair_of_points(points, points_counts)

   >>> closest_pair_of_points([(2, 3), (12, 30)], len([(2, 3), (12, 30)]))
   28.792360097775937


.. py:function:: closest_pair_of_points_sqr(points_sorted_on_x, points_sorted_on_y, points_counts)

   divide and conquer approach

   Parameters :
   points, points_count (list(tuple(int, int)), int)

   Returns :
   (float):  distance btw closest pair of points

   >>> closest_pair_of_points_sqr([(1, 2), (3, 4)], [(5, 6), (7, 8)], 2)
   8


.. py:function:: column_based_sort(array, column=0)

   >>> column_based_sort([(5, 1), (4, 2), (3, 0)], 1)
   [(3, 0), (5, 1), (4, 2)]


.. py:function:: dis_between_closest_in_strip(points, points_counts, min_dis=float('inf'))

   closest pair of points in strip

   Parameters :
   points, points_count, min_dis (list(tuple(int, int)), int, int)

   Returns :
   min_dis (float):  distance btw closest pair of points in the strip (< min_dis)

   >>> dis_between_closest_in_strip([[1,2],[2,4],[5,7],[8,9],[11,0]],5)
   85


.. py:function:: dis_between_closest_pair(points, points_counts, min_dis=float('inf'))

   brute force approach to find distance between closest pair points

   Parameters :
   points, points_count, min_dis (list(tuple(int, int)), int, int)

   Returns :
   min_dis (float):  distance between closest pair of points

   >>> dis_between_closest_pair([[1,2],[2,4],[5,7],[8,9],[11,0]],5)
   5



.. py:function:: euclidean_distance_sqr(point1, point2)

   >>> euclidean_distance_sqr([1,2],[2,4])
   5


.. py:data:: points
   :value: [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]