Computational Geometry, Design and Analysis of Algorithms
Harsh Mishra
Posted on August 2, 2024
Introduction to Computational Geometry
Overview of Computational Geometry:
Computational Geometry is a branch of computer science and mathematics that deals with the study of geometric objects and the algorithms to handle them. It involves solving geometric problems using computational techniques and is foundational for various applications in computer graphics, computer-aided design (CAD), robotics, and geographic information systems (GIS).
Applications of Computational Geometry:
- Computer Graphics: Rendering and manipulating shapes and surfaces.
- Computer-Aided Design (CAD): Designing and analyzing mechanical parts and structures.
- Robotics: Path planning and motion analysis.
- Geographic Information Systems (GIS): Analyzing spatial data and geographic information.
- Pattern Recognition: Identifying patterns and shapes in image processing.
Basic Geometric Objects and Operations
Points, Lines, Line Segments, and Planes:
- Points: Fundamental units in geometry that represent a location in space.
- Lines: Extend infinitely in both directions and are defined by two points.
- Line Segments: A portion of a line defined by two endpoints.
- Planes: Flat surfaces extending infinitely in two dimensions.
Vectors and Vector Operations:
- Vectors: Represent quantities with both magnitude and direction. Used to describe translations and directions in space.
- Vector Operations: Include addition, subtraction, dot product, cross product, and scaling. These operations are used to perform geometric transformations and calculations.
Basic Geometric Transformations (Translation, Rotation, Scaling):
- Translation: Moving a geometric object from one location to another without altering its shape or size.
- Rotation: Rotating an object around a fixed point (or origin) by a certain angle.
- Scaling: Changing the size of an object while maintaining its shape, by enlarging or shrinking it.
Distance Metrics and Measure:
- Euclidean Distance: The straight-line distance between two points in Euclidean space.
- Manhattan Distance: The distance between two points measured along axes at right angles.
- Other Metrics: Includes Chebyshev distance and Minkowski distance, used in different geometric and application contexts.
Examples of Computational Geometry Algorithms
Computational geometry involves various algorithms to solve geometric problems efficiently. Here are examples of common algorithms implemented using the divide and conquer paradigm:
Closest Pair of Points (1D)
In 1D, finding the closest pair of points can be done efficiently using a divide and conquer approach. The idea is to recursively divide the points into smaller groups and find the closest pair in each group.
Python Implementation:
def closest_pair_1d(points):
def find_closest_pair(sorted_points):
# Base case: If there are only two points, return them
if len(sorted_points) == 2:
return sorted_points[0], sorted_points[1]
# Base case: If there are three points, return the closest pair
if len(sorted_points) == 3:
return min(
((sorted_points[0], sorted_points[1]),
(sorted_points[1], sorted_points[2]),
(sorted_points[0], sorted_points[2])),
key=lambda pair: abs(pair[1] - pair[0])
)
# Divide the points into two halves
mid = len(sorted_points) // 2
left_half = sorted_points[:mid]
right_half = sorted_points[mid:]
# Find the closest pair in each half
closest_pair_left = find_closest_pair(left_half)
closest_pair_right = find_closest_pair(right_half)
# Find the closest pair across the split
closest_pair_split = (left_half[-1], right_half[0])
# Return the overall closest pair
return min(closest_pair_left, closest_pair_right, closest_pair_split, key=lambda pair: abs(pair[1] - pair[0]))
if len(points) < 2:
raise ValueError("At least two points are required")
# Sort the points
sorted_points = sorted(points)
# Find the closest pair using divide and conquer
return find_closest_pair(sorted_points)
# Example usage
points = [0, 1, 3, 5, 7, 9, 11]
closest_points = closest_pair_1d(points)
print(f"The closest pair of points is: {closest_points}")
Closest Pair of Points (2D)
In 2D, the closest pair of points problem is more complex. It involves sorting the points and recursively finding the closest pair in divided sections, then checking across the split boundary.
Python Implementation:
import math
def distance(point1, point2):
return math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)
def closest_pair_2d(points):
def closest_pair_recursive(points_sorted_by_x, points_sorted_by_y):
n = len(points_sorted_by_x)
if n <= 3:
return brute_force_closest_pair(points_sorted_by_x)
mid = n // 2
left_half_x = points_sorted_by_x[:mid]
right_half_x = points_sorted_by_x[mid:]
midpoint = points_sorted_by_x[mid][0]
left_half_y = list(filter(lambda x: x[0] <= midpoint, points_sorted_by_y))
right_half_y = list(filter(lambda x: x[0] > midpoint, points_sorted_by_y))
(p1, q1, d1) = closest_pair_recursive(left_half_x, left_half_y)
(p2, q2, d2) = closest_pair_recursive(right_half_x, right_half_y)
if d1 < d2:
d = d1
min_pair = (p1, q1)
else:
d = d2
min_pair = (p2, q2)
(p3, q3, d3) = closest_split_pair(points_sorted_by_x, points_sorted_by_y, d, min_pair)
if d3 < d:
return (p3, q3, d3)
else:
return min_pair[0], min_pair[1], d
def brute_force_closest_pair(points):
min_dist = float('inf')
p1 = None
p2 = None
for i in range(len(points)):
for j in range(i + 1, len(points)):
d = distance(points[i], points[j])
if d < min_dist:
min_dist = d
p1, p2 = points[i], points[j]
return p1, p2, min_dist
def closest_split_pair(points_sorted_by_x, points_sorted_by_y, delta, best_pair):
n = len(points_sorted_by_x)
mid_x = points_sorted_by_x[n // 2][0]
Sy = [point for point in points_sorted_by_y if mid_x - delta <= point[0] <= mid_x + delta]
best = delta
len_Sy = len(Sy)
for i in range(len_Sy - 1):
for j in range(i + 1, min(i + 7, len_Sy)):
p, q = Sy[i], Sy[j]
dst = distance(p, q)
if dst < best:
best = dst
best_pair = (p, q)
return best_pair[0], best_pair[1], best
points_sorted_by_x = sorted(points, key=lambda x: x[0])
points_sorted_by_y = sorted(points, key=lambda x: x[1])
p1, p2, min_dist = closest_pair_recursive(points_sorted_by_x, points_sorted_by_y)
return p1, p2, min_dist
# Example usage
points = [(2, 3), (2, 4), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
closest_points = closest_pair_2d(points)
print(f"The closest pair of points is: {closest_points[0]} and {closest_points[1]} with a distance of {closest_points[2]}")
Graham Scan (Convex Hull)
Graham Scan is an algorithm to find the convex hull of a set of points in 2D. It sorts the points by polar angle with respect to a pivot and then constructs the convex hull.
Python Implementation:
import math
def graham_scan(points):
# Find the point with the lowest y-coordinate, break ties by x-coordinate
pivot = min(points, key=lambda p: (p[1], p[0]))
points.remove(pivot)
# Sort the points based on polar angle with the pivot
points.sort(key=lambda p: (math.atan2(p[1] - pivot[1], p[0] - pivot[0]), p[1], p[0]))
# Add the pivot back to the beginning
points.insert(0, pivot)
# Initialize the hull with the first two points
hull = [points[0], points[1]]
for p in points[2:]:
while len(hull) > 1 and orientation(hull[-2], hull[-1], p) != 2:
hull.pop()
hull.append(p)
return hull
def orientation(p, q, r):
# Function to find the orientation of the triplet (p, q, r)
# 0 -> p, q, and r are collinear
# 1 -> Clockwise
# 2 -> Counterclockwise
val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
if val == 0:
return 0
elif val > 0:
return 1
else:
return 2
# Sample points
points = [(0, 0), (1, 1), (2, 2), (2, 0), (0, 2), (0.5, 2.5), (2.5, 2)]
# Call the function
convex_hull = graham_scan(points)
# Print the result
print("Convex Hull:", convex_hull)
Jarvis March (Gift Wrapping) (Convex Hull)
Jarvis March (Gift Wrapping) is another algorithm for finding the convex hull. It starts from the leftmost point and wraps around the points to find the hull.
Python Implementation:
def gift_wrapping(points):
hull = []
start = min(points, key=lambda p: p[0]) # Find the leftmost point
on_hull = start
while True:
hull.append(on_hull)
next_point = points[0]
for p in points:
if (next_point == on_hull) or (orientation(on_hull, next_point, p) == 2):
next_point = p
on_hull = next_point
if on_hull == start:
break
return hull
def orientation(p, q, r):
# Function to find the orientation of the triplet (p, q, r)
# 0 -> p
, q, and r are collinear
# 1 -> Clockwise
# 2 -> Counterclockwise
val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
if val == 0:
return 0
elif val > 0:
return 1
else:
return 2
# Sample points
points = [(0, 0), (1, 1), (2, 2), (2, 0), (0, 2), (0.5, 2.5), (2.5, 2)]
# Call the function
convex_hull = gift_wrapping(points)
# Print the result
print("Convex Hull:", convex_hull)
These implementations provide a practical starting point for exploring computational geometry algorithms.
💖 💪 🙅 🚩
Harsh Mishra
Posted on August 2, 2024
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
