# Geometric Algorithms

These algorithms are designed to solve Geometric Problems. They requires in-depth knowledge of different mathematical subjects like combinatorics, topology, algebra, differential geometry etc.

#### Concept of Orientation

Orientation of an ordered triplet of points in the plane can be:

• Clockwise
• Anti-clockwise
• Collinear  ## 1. Check if 2 line segements intersect***

###### Problem:

Given two line segments (p1, q1) and (p2, q2), find if the given line segments intersect with each other.

Examples:

Input:   Line-1:   p1 = {1, 1}, q1 = {10, 1}   Line-2:   p1 = {1, 2}, q1 = {10, 2}

Output: No

Input:   Line-1:   p1 = {10, 0}, q1 = {0, 10}   Line-2:   p1 = {0, 0}, q1 = {10, 10}

Output: Yes

Input:   Line-1:   p1 = {-5, -5}, q1 = {0, 0}   Line-2:   p1 = {1, 1}, q1 = {10, 10}

Output: No

#### Intersection of 2 line segments

Two segments (p1,q1) and (p2,q2) intersect if and only if one of the following two conditions is verified:

##### Case-1: General Case
• (p1, q1, p2) and (p1, q1, q2) have different orientations and
• (p2, q2, p1) and (p2, q2, q1) have different orientations. ##### Case-2: Special Case
• (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and
• the x-projections of (p1, q1) and (p2, q2) intersect
• the y-projections of (p1, q1) and (p2, q2) intersect ###### Implementation:
``````def orientation(a, b, c):
val = (b-a)*(c-b) - (b-a)*(c-b)

if val == 0:
return 0
elif val > 0:
return 1
else:
return -1

def on_segment(a, b, c):
if (b <= max(a, c) and b >= min(a, c) and
b <= max(a, c) and b >= min(a, c)):
return True

return False

def check_2_line_segments_intersection(line1, line2):
p1 = line1; q1 = line1
p2 = line2; q2 = line2

# All 4 different orientation
#   • p1, q1, p2 = o1 and p1, q1, q2 = o2 --> Should be different
#   • p2, q2, p1 = o3 and p2, q2, q1 = o4 --> Should be different
o1 = orientation(p1, q1, p2)
o2 = orientation(p1, q1, q2)
o3 = orientation(p2, q2, p1)
o4 = orientation(p2, q2, q1)

result = False

### General Case
if o1 != o2 and o3 != o4:
result = True

### Case-2: Special Cases
# p1, q1 and p2 are collinear and p2 lies on segment p1q1
if o1 == 0 and on_segment(p1, p2, q1):
result = True

# p1, q1 and q2 are collinear and q2 lies on segment p1q1
if o2 == 0 and on_segment(p1, q2, q1):
result = True

# p2, q2 and p1 are collinear and p1 lies on segment p2q2
if o3 == 0 and on_segment(p2, p1, q2):
result = True

# p2, q2 and q1 are collinear and q1 lies on segment p2q2
if o4 == 0 and on_segment(p2, q1, q2):
result = True

if(result):
print("Yes")
else:
print("No")

print("Example-1: check_2_line_segments_intersection([(1,1), (10,1)], [(1,2), (10,2)])")
check_2_line_segments_intersection([(1,1), (10,1)], [(1,2), (10,2)])

print("\nExample-2: check_2_line_segments_intersection([(10,0), (0,10)], [(0,0), (10,10)])")
check_2_line_segments_intersection([(10,0), (0,10)], [(0,0), (10,10)])

print("\nExample-3: check_2_line_segments_intersection([(-5,-5), (0,0)], [(1,1), (10,10)])")
check_2_line_segments_intersection([(-5,-5), (0,0)], [(1,1), (10,10)])
``````

Output: ###### Complexity:
• Time: O(1)
• Auxilliary Space: O(1)

## 2. Check if Point lies inside triangle

###### Problem:

Given three corner points of a triangle, and one more point P. Check if the p lies inside the triangle. ###### Approach: Simple
• Get the area of ∆ABC and check if it equals ∆PAB + ∆PAC + ∆PBC.
• If they equal then point P lies inside the triangle.
###### Implementation:
``````def triangle_area(x1, y1, x2, y2, x3, y3):
return abs(0.5*(x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2)))

def point_lies_inside_triangle(x1, y1, x2, y2, x3, y3, x, y):
# Calculate Areas
area_ABC = triangle_area(x1, y1, x2, y2, x3, y3)
area_PAB = triangle_area(x, y, x1, y1, x2, y2)
area_PAC = triangle_area(x, y, x1, y1, x3, y3)
area_PBC = triangle_area(x, y, x2, y2, x3, y3)

if(area_ABC == area_PAB + area_PAC + area_PBC):
print("Inside")
else:
print("Outside")

print("Example-1: point_lies_inside_triangle(0, 0, 10, 30, 20, 0, 10, 15)")
point_lies_inside_triangle(0, 0, 10, 30, 20, 0, 10, 15)

print("\nExample-2: point_lies_inside_triangle(0, 0, 10, 30, 20, 0, 18, 25)")
point_lies_inside_triangle(0, 0, 10, 30, 20, 0, 15, 25)
``````

Output: ###### Complexity:
• Time: O(1)
• Auxilliary Space: O(1)

## 3. Check if 4 Points form Square***

###### Problem:

Given coordinates of four points in a plane, find if the four points form a square or not. ###### Approach:
• Pick any point and calculate its distance from the rest of the points. Let the picked point be ‘p’.
• To form a square, the distance of two points must be the same from ‘p’, let this distance be d.
• The distance from third point must be equal to √2d. Let this point with different distance be ‘q’.
• The above condition is not good enough as the point with different distance can be on the other side.
• Check that q is at the same distance from 2 other points and this distance is the same as d.
###### Implementation:
``````def square_distance(a, b):
return (b-a)*(b-a) + (b-a)*(b-a)

def check_square(p1, p2, p3, p4):
is_square = False

## Calculate distances from p1
d2 = square_distance(p1, p2) # from p1 to p2
d3 = square_distance(p1, p3) # from p1 to p3
d4 = square_distance(p1, p4) # from p1 to p4

# If lengths of (p1, p2) and (p1, p3) are same, then following conditions must meet to form a square:
#   • 1) Square of length of (p1, p4) is same as twice the square of (p1, p2)
#   • 2) Square of length of (p2, p3) is same as twice the square of (p2, p4)

if (d2 == d3 and 2*d2 == d4 and 2*square_distance(p2, p4) == square_distance(p2, p3)):
is_square = True

# Cases similar to above case
if (d3 == d4 and 2*d3 == d2 and 2*square_distance(p3, p2) == square_distance(p3, p4)):
is_square = True

if (d2 == d4 and 2*d2 == d3 and 2*square_distance(p2, p3) == square_distance(p2, p4)):
is_square = True

if(is_square):
print("Square")
else:
print("Not Square")

print("Example-1: check_square((20, 10), (10, 20), (20, 20), (10, 10))")
check_square((20, 10), (10, 20), (20, 20), (10, 10))

print("\nExample-2: check_square((20, 10), (10, 20), (20, 20), (10, 20))")
check_square((20, 10), (10, 20), (20, 20), (10, 20))
``````

Output: ###### Complexity:
• Time: O(1)
• Auxilliary Space: O(1)

## 4. Check if Point lies inside Polygon***

###### Problem:

Given a polygon and a point p, check if p lies inside the polygon or not.

The points lying on the border are considered inside. ###### Approach:
• Draw a horizontal line to the right of each point and extend it to infinity.
• Count the number of times the line intersects with polygon edges.
• A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon.
• If none of the conditions is true, then point lies outside. ##### Handling cases such as of point b
• Note: We need to return true if the point lies on the line or same as one of the vertices of the given polygon.
• To handle this, after checking if the line from ‘p’ to extreme intersects:
• Check whether ‘p’ is collinear with vertices of current line of polygon.
• If it is collinear, then we check if the point ‘p’ lies on current side of polygon, if it lies, we return true, else false.
###### Implementation:
``````import sys

def orientation(a, b, c):
val = (b-a)*(c-b) - (b-a)*(c-b)

if val == 0:
return 0
elif val > 0:
return 1
else:
return -1

def on_segment(a, b, c):
if (b <= max(a, c) and b >= min(a, c) and
b <= max(a, c) and b >= min(a, c)):
return True

return False

def check_2_line_segments_intersection(line1, line2):
p1 = line1; q1 = line1
p2 = line2; q2 = line2

# All 4 different orientation
#   • p1, q1, p2 = o1 and p1, q1, q2 = o2 --> Should be different
#   • p2, q2, p1 = o3 and p2, q2, q1 = o4 --> Should be different
o1 = orientation(p1, q1, p2)
o2 = orientation(p1, q1, q2)
o3 = orientation(p2, q2, p1)
o4 = orientation(p2, q2, q1)

result = False

### General Case
if o1 != o2 and o3 != o4:
result = True

### Case-2: Special Cases
# p1, q1 and p2 are collinear and p2 lies on segment p1q1
if o1 == 0 and on_segment(p1, p2, q1):
result = True

# p1, q1 and q2 are collinear and q2 lies on segment p1q1
if o2 == 0 and on_segment(p1, q2, q1):
result = True

# p2, q2 and p1 are collinear and p1 lies on segment p2q2
if o3 == 0 and on_segment(p2, p1, q2):
result = True

# p2, q2 and q1 are collinear and q1 lies on segment p2q2
if o4 == 0 and on_segment(p2, q1, q2):
result = True

return result

def check_point_inside_polygon(polygon, p):
n = len(polygon)
# Not a polynomial
if n < 3:
print("Outside")
return

# Extreme point will have x as "infinity" and y same as point p
extreme = (sys.maxsize, p)

# Count for counting intersections
count = 0

result = False
for i in range(n):
current_vertex = polygon[i]
next_vertex = polygon[(i+1)%n]

# Check if the line segment from 'p' to 'extreme' intersects
# with the line segment polygon's current_vertex to next_vertex
if check_2_line_segments_intersection((current_vertex,next_vertex), (p,extreme)):
# If the point 'p' is collinear with line segment current_vertex---next_vertex
# Check if it lies on segment return true if it lies, otherwise false
if (orientation(current_vertex, p, next_vertex) == 0) :
result = on_segment(current_vertex, p, next_vertex)
count = 0
break

count += 1

if(result or count%2 == 1):
print("Inside")
else:
print("Outside")

polygon1 = [(0, 0), (10, 0), (10, 10), (0, 10)]
polygon2 = [(0, 0), (5, 5), (5, 0)]
print("Example-1: check_point_inside_polygon(polygon1, (20, 20))")
check_point_inside_polygon(polygon1, (20, 20))

print("\nExample-2: check_point_inside_polygon(polygon1, (5, 5))")
check_point_inside_polygon(polygon1, (5, 5))

print("\nExample-3: check_point_inside_polygon(polygon1, (-1, 10))")
check_point_inside_polygon(polygon1, (-1, 10))

print("\nExample-4: check_point_inside_polygon(polygon2, (3, 3))")
check_point_inside_polygon(polygon2, (3, 3))

print("\nExample-5: check_point_inside_polygon(polygon2, (5, 1))")
check_point_inside_polygon(polygon2, (5, 1))

print("\nExample-6: check_point_inside_polygon(polygon2, (8, 1))")
check_point_inside_polygon(polygon2, (8, 1))
``````

Output: ###### Complexity:
• Time: O(n) : Size of polygon is n.
• Auxilliary Space: O(1)