Added check_if_point_inside_polygon and one more resources

Meto Trajkovski · Meto Trajkovski · commit 3d3e72858ea2 · 2019-12-17T19:07:59.000+01:00
diff --git a/Math/check_if_point_inside_polygon.py b/Math/check_if_point_inside_polygon.py
@@ -0,0 +1,70 @@
+'''
+Check if Point is Inside Polygon
+
+Given a polygon (created by counterclockwise ordered points, more than 2 points) and a point "p", find if "p" lies inside the polygon or not. 
+The points lying on the border are considered inside.
+
+Input: [(0, 0), (3, 0), (3, 2), (0, 2)], (1, 1)
+Output: True
+Output explanation: In this example the polygon is a rectangle parallel with the X axis.
+
+=========================================
+To check if a point is inside a polygon you'll need to draw a straight line (in any of the 4 directions: up, right, down, left),
+and count the number of times the line intersects with polygon edges. If the number of intersections is odd then the point
+is inside or lies on an edge of the polygon, otherwise the point is outside.
+    Time Complexity:    O(N)
+    Space Complexity:   O(1)
+'''
+
+
+############
+# Solution #
+############
+
+def check_if_point_inside_polygon(polygon, p):
+    n = len(polygon)
+    # add the first point as last to avoid checking, using modulo (polygon[(i + 1) % n]) or duplicate code for the last point
+    polygon.append(polygon[0])
+    is_inside = False   # or you can use counter and return (counter % 2) == 1
+
+    for i in range(n):
+        if intersect(polygon[i], polygon[i + 1], p):
+            is_inside = not is_inside
+
+    return is_inside
+
+def intersect(a, b, p):
+    # Y coordinate of p should be between Y coordinates
+    # this can be written like (a[1] > p[1]) != (b[1] > p[1])
+    if p[1] < max(a[1], b[1]) and p[1] >= min(a[1], b[1]):
+        ''' 
+        Equation of line:   
+        y = (x - x0) * ((y1 - y0) / (x1 - x0)) + y0
+        This formula is computed using the gradients (slopes, changes in the coordinates)
+        Modify this formula to find X instead Y (because you already have Y)
+        '''
+        x_intersect = (p[1] - a[1]) * ((b[0] - a[0]) / (b[1] - a[1])) + a[0]
+
+        # check if the point is on the left of the intersection (because in this case you're drawing a line to the right)
+        return x_intersect <= p[1]
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => True
+print(check_if_point_inside_polygon([(0, 0), (3, 0), (3, 2), (0, 2)], (1, 1)))
+
+# Test 2
+# Correct result => True
+print(check_if_point_inside_polygon([(0, 0), (3, 0), (3, 2), (0, 2)], (1, 0)))
+
+# Test 3
+# Correct result => True
+print(check_if_point_inside_polygon([(0, 0), (3, 0), (3, 2), (0, 2)], (3, 1)))
+
+# Test 3
+# Correct result => False
+print(check_if_point_inside_polygon([(0, 0), (3, 0), (3, 2), (0, 2)], (3, 3)))
diff --git a/README.md b/README.md
@@ -200,7 +200,8 @@ If the problems from [LeetCode](https://leetcode.com/) are not enough and you ne
 
 1. [Geeks For Geeks](https://www.geeksforgeeks.org/) - The site which **all** interested in algorithms (no matter if beginners or experts) should know!
 2. [The Algorithms - Python](https://github.com/TheAlgorithms/Python) - Great GitHub repo with many algorithms written in Python ([Link](https://github.com/TheAlgorithms) from the same repo written in other programming languages).
-3. [KhanAcademy - Algorithms](https://www.khanacademy.org/computing/computer-science/algorithms) - Good explanations for some basic algorithms.
-4. HackerRank - YouTube tutorials
+3. [CP Algorithms](http://cp-algorithms.com/) - Great page with excellent explanations for various algorithms.
+4. [KhanAcademy - Algorithms](https://www.khanacademy.org/computing/computer-science/algorithms) - Good explanations for some basic algorithms.
+5. HackerRank - YouTube tutorials
     - [Algorithms](https://www.youtube.com/playlist?list=PLI1t_8YX-ApvMthLj56t1Rf-Buio5Y8KL)
     - [Data Structures](https://www.youtube.com/playlist?list=PLI1t_8YX-Apv-UiRlnZwqqrRT8D1RhriX)
