DSA - Geometric Algorithms
Geometric algorithms are defined as a procedure used for solving problems related to geometric shapes and their properties. These algorithms can be applied to shapes like points, lines, polygons, and other geometric figures. We can find its applications in various fields such as computer graphics, computer-aided design, robotics, and geographical information systems.
Problems related to Geometric Algorithms
Some of the common problems that can be solved using geometric algorithms are −
It can be used to solve area of different polygons, such as triangle, rectangle and so on.
We can use geometric algorithm to find intersection of two lines.
Computing convex hull problem.
Finding a point inside different geometric shapes.
Geometric algorithms can solve triangulation of polygon problem.
Important Geometric Algorithms
Some of the important geometric algorithms are −
Graham Scan Algorithm
Sweep Line Algorithm
Graham Scan Algorithm
The Graham Scan Algorithm was developed by Ronald Graham in 1972. This algorithm is primarily used to solve Convex Hull problem and Maximum distance problem. Its application can be seen in other fields also, such as image processing, robotics, delivery systems and many more.
The following steps explain the working Graham Scan algorithm −
First, find the point with the lowest y-coordinate. If multiple points share the lowest y-coordinate, choose the one with the lowest x-coordinate.
Sort the remaining points based on their polar angle with respect to the lowest point.
After sorting the points, start with the lowest point and other two additional points. These three points form the initial part of the convex hull.
For each new point, determine whether travelling from the two preceding points constitutes a left turn or a right turn. If it's a right turn, the second-to-last point is not inside the convex hull.
Repeat this process until a left turn set is encountered.
Example
The following example practically demonstrates how Graham Scan algorithm works.
#include <stdio.h>
#include <stdlib.h>
// Structure for a point
struct Point2D {
int x, y;
};
// Global variable for the initial point
struct Point2D initialPoint;
// Function to get the second top element
struct Point2D getSecondTop(struct Point2D Stack[], int* top) {
return Stack[(*top)-1];
}
// Function to calculate square of distance between two points
int calcDistSq(struct Point2D p1, struct Point2D p2) {
return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
// Function to find orientation of ordered triplet of points
int getOrientation(struct Point2D p, struct Point2D q, struct Point2D r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0;
return (val > 0)? 1: 2;
}
// Function to compare two points
int comparePoints(const void *vp1, const void *vp2) {
struct Point2D *p1 = (struct Point2D *)vp1;
struct Point2D *p2 = (struct Point2D *)vp2;
int o = getOrientation(initialPoint, *p1, *p2);
if (o == 0)
return (calcDistSq(initialPoint, *p2) >= calcDistSq(initialPoint, *p1))? -1 : 1;
return (o == 2)? -1: 1;
}
// Function to compute the convex hull
void computeConvexHull(struct Point2D points[], int n) {
int ymin = points[0].y, min = 0;
for (int i = 1; i < n; i++) {
int y = points[i].y;
if ((y < ymin) || (ymin == y && points[i].x < points[min].x))
ymin = points[i].y, min = i;
}
// Swapping
struct Point2D temp = points[0];
points[0] = points[min];
points[min] = temp;
// Initial point
initialPoint = points[0];
// Sort array of points
qsort(&points[1], n-1, sizeof(struct Point2D), comparePoints);
int m = 1;
for (int i=1; i<n; i++) {
while (i < n-1 && getOrientation(initialPoint, points[i], points[i+1]) == 0)
i++;
points[m] = points[i];
m++;
}
if (m < 3) return;
// Stack to store the points on the convex hull
struct Point2D Stack[n];
int top = -1;
// Push the first three points into the stack
Stack[++top] = points[0];
Stack[++top] = points[1];
Stack[++top] = points[2];
// For the rest of the points
for (int i = 3; i < m; i++) {
while (getOrientation(getSecondTop(Stack, &top), Stack[top], points[i]) != 2)
top--;
Stack[++top] = points[i];
}
// Print the point
while (top != -1) {
struct Point2D p = Stack[top--];
printf("(%d, %d)
", p.x, p.y);
}
}
int main() {
struct Point2D points[] = {{0, 1}, {1, 2}, {2, 3}, {4, 5}, {0, 0}, {2, 1}, {3, 1}, {3, 3}};
int n = sizeof(points)/ sizeof(points[0]);
computeConvexHull(points, n);
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// structure for a point
struct Point2D {
int x, y;
};
// initial point
Point2D initialPoint;
// Function to get the next top element
Point2D getSecondTop(vector<Point2D> &Stack) {
return Stack[Stack.size()-2];
}
// Function to calculate square of distance between two points
int calcDistSq(Point2D p1, Point2D p2) {
return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
// Function to find orientation of ordered triplet of points
int getOrientation(Point2D p, Point2D q, Point2D r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0;
// checking clock or counterclock wise
return (val > 0)? 1: 2;
}
// Function to compare two points
int comparePoints(const void *vp1, const void *vp2) {
Point2D *p1 = (Point2D *)vp1;
Point2D *p2 = (Point2D *)vp2;
int o = getOrientation(initialPoint, *p1, *p2);
if (o == 0)
return (calcDistSq(initialPoint, *p2) >= calcDistSq(initialPoint, *p1))? -1 : 1;
return (o == 2)? -1: 1;
}
// Function to compute the convex hull
void computeConvexHull(Point2D points[], int n) {
int ymin = points[0].y, min = 0;
for (int i = 1; i < n; i++) {
int y = points[i].y;
if ((y < ymin) || (ymin == y && points[i].x < points[min].x))
ymin = points[i].y, min = i;
}
// swapping
swap(points[0], points[min]);
// initial point
initialPoint = points[0];
// Sort array of points
qsort(&points[1], n-1, sizeof(Point2D), comparePoints);
int m = 1;
for (int i=1; i<n; i++) {
while (i < n-1 && getOrientation(initialPoint, points[i], points[i+1]) == 0)
i++;
points[m] = points[i];
m++;
}
if (m < 3) return;
// stack to store the points on the convex hull
vector<Point2D> Stack;
// Push the first three points into the stack
Stack.push_back(points[0]);
Stack.push_back(points[1]);
Stack.push_back(points[2]);
// For the rest of the points
for (int i = 3; i < m; i++) {
while (getOrientation(getSecondTop(Stack), Stack.back(), points[i]) != 2)
Stack.pop_back();
Stack.push_back(points[i]);
}
// Print the point
while (!Stack.empty()) {
Point2D p = Stack.back();
cout << "(" << p.x << ", " << p.y <<")" << endl;
Stack.pop_back();
}
}
int main() {
Point2D points[] = {{0, 1}, {1, 2}, {2, 3}, {4, 5}, {0, 0}, {2, 1}, {3, 1}, {3, 3}};
int n = sizeof(points)/ sizeof(points[0]);
computeConvexHull(points, n);
return 0;
}
import java.util.*;
// class to represent points with x and y coordinates
class Cords {
int xCoord, yCoord;
// Constructor
Cords(int x, int y) {
this.xCoord = x;
this.yCoord = y;
}
}
// class to find the convex hull
public class ConvexHullFinder {
// initial point
Cords initialPoint;
// Method to get the next to top element
Cords getSecondTop(Stack<Cords> stack) {
Cords temp = stack.pop();
Cords result = stack.peek();
stack.push(temp);
return result;
}
// Method to swap two points
void swapPoints(Cords p1, Cords p2) {
Cords temp = p1;
p1 = p2;
p2 = temp;
}
// Method to calculate the square of the distance between two points
int distanceSquare(Cords p1, Cords p2) {
return (p1.xCoord - p2.xCoord)*(p1.xCoord - p2.xCoord) + (p1.yCoord - p2.yCoord)*(p1.yCoord - p2.yCoord);
}
// Method to find the orientation of an ordered triplet of points
int findOrientation(Cords p, Cords q, Cords r) {
int value = (q.yCoord - p.yCoord) * (r.xCoord - q.xCoord) - (q.xCoord - p.xCoord) * (r.yCoord - q.yCoord);
if (value == 0) return 0;
// checking clock or counterclock wise
return (value > 0)? 1: 2;
}
// Method to check if two points have same slope
boolean sameSlope(Cords p1, Cords p2, Cords p3) {
return (p2.yCoord - p1.yCoord) * (p3.xCoord - p2.xCoord) == (p3.yCoord - p2.yCoord) * (p2.xCoord - p1.xCoord);
}
// method to calculate convex hull
void calculateConvexHull(Cords points[], int n) {
int yMin = points[0].yCoord, min = 0;
for (int i = 1; i < n; i++) {
int y = points[i].yCoord;
if ((y < yMin) || (yMin == y && points[i].xCoord < points[min].xCoord)) {
yMin = points[i].yCoord;
min = i;
}
}
// Swapping
swapPoints(points[0], points[min]);
// initial point
initialPoint = points[0];
// Sort array of points
Arrays.sort(points, new Comparator<Cords>() {
@Override
public int compare(Cords p1, Cords p2) {
if (sameSlope(initialPoint, p1, p2)) {
if (distanceSquare(initialPoint, p2) >= distanceSquare(initialPoint, p1)) {
return -1;
} else {
return 1;
}
}
if (findOrientation(initialPoint, p1, p2) == 2) {
return -1;
} else {
return 1;
}
}
});
// Create a stack and push the first three points into it
Stack<Cords> stack = new Stack<>();
stack.push(points[0]);
stack.push(points[1]);
stack.push(points[2]);
// keep removing top of stack while we get a clockwise turn
for (int i = 3; i < n; i++) {
while (stack.size() > 1 && findOrientation(getSecondTop(stack), stack.peek(), points[i]) != 2)
stack.pop();
stack.push(points[i]);
}
// print result
while (!stack.empty()) {
Cords p = stack.peek();
System.out.println("(" + p.xCoord + ", " + p.yCoord + ")");
stack.pop();
}
}
public static void main(String[] args) {
// points
Cords points[] = {new Cords(0, 1), new Cords(1, 2), new Cords(2, 3), new Cords(4, 5),
new Cords(0, 0), new Cords(2, 1), new Cords(3, 1), new Cords(3, 3)};
int n = points.length;
ConvexHullFinder finder = new ConvexHullFinder();
finder.calculateConvexHull(points, n);
}
}
from functools import cmp_to_key
import math
# Class to represent points with x and y coordinates
class Cords:
def __init__(self, x, y):
self.xCoord = x
self.yCoord = y
# Class to find the convex hull
class ConvexHullFinder:
# Initial point
initialPoint = None
# Method to get the next to top element
def getSecondTop(self, stack):
return stack[-2]
# Method to swap two points
def swapPoints(self, p1, p2):
return p2, p1
# Method to calculate the square of the distance between two points
def distanceSquare(self, p1, p2):
return (p1.xCoord - p2.xCoord)**2 + (p1.yCoord - p2.yCoord)**2
# Method to find the orientation of an ordered triplet of points
def findOrientation(self, p, q, r):
value = (q.yCoord - p.yCoord) * (r.xCoord - q.xCoord) - (q.xCoord - p.xCoord) * (r.yCoord - q.yCoord)
if value == 0: return 0
return 1 if value > 0 else 2
# Method to check if two points have same slope
def sameSlope(self, p1, p2, p3):
return (p2.yCoord - p1.yCoord) * (p3.xCoord - p2.xCoord) == (p3.yCoord - p2.yCoord) * (p2.xCoord - p1.xCoord)
# Method to calculate convex hull
def calculateConvexHull(self, points):
n = len(points)
ymin = points[0].yCoord
min = 0
for i in range(1, n):
y = points[i].yCoord
if (y < ymin) or (ymin == y and points[i].xCoord < points[min].xCoord):
ymin = points[i].yCoord
min = i
# Swapping
points[0], points[min] = self.swapPoints(points[0], points[min])
# Initial point
self.initialPoint = points[0]
# Sort array of points
def compare(p1, p2):
if self.sameSlope(self.initialPoint, p1, p2):
if self.distanceSquare(self.initialPoint, p2) >= self.distanceSquare(self.initialPoint, p1):
return -1
else:
return 1
if self.findOrientation(self.initialPoint, p1, p2) == 2:
return -1
else:
return 1
points = sorted(points, key=cmp_to_key(compare))
# Create a stack and push the first three points into it
stack = []
stack.append(points[0])
stack.append(points[1])
stack.append(points[2])
# Keep removing top of stack while we get a clockwise turn
for i in range(3, n):
while len(stack) > 1 and self.findOrientation(self.getSecondTop(stack), stack[-1], points[i]) != 2:
stack.pop()
stack.append(points[i])
# Print result
while stack:
p = stack[-1]
print("(", p.xCoord, ", ", p.yCoord, ")")
stack.pop()
# Points
points = [Cords(0, 1), Cords(1, 2), Cords(2, 3), Cords(4, 5),
Cords(0, 0), Cords(2, 1), Cords(3, 1), Cords(3, 3)]
finder = ConvexHullFinder()
finder.calculateConvexHull(points)
Output
(0, 1) (4, 5) (3, 1) (0, 0)
Sweep Line Algorithm
The Sweep Line Algorithm is used to solve geometric and other problems involving dynamic sets of objects moving in a specific direction. Suppose a vertical line (say it sweep line) moving from left to right across the plane. As the sweep line encounters endpoints of line segments, we track which segments intersect at each point in time. By analyzing the interactions, we can efficiently solve various problems.
Following are the steps involved in Sweep Line Algorithm −
The sweep line starts at one end of the problem space and moves towards the other.
At regular intervals, the algorithm update a suitable data structure depending on the problem. Based on the current configuration of the sweep line position, it calculates distances, intersections, areas, or other desired outputs.
The final data structures or accumulated results provide the solution to the problem.
Example
Following is the example illustrating sweep line algorithm in various programming language.
#include <stdio.h>
#include <math.h>
// Structure to represent a coordinate
typedef struct {
double a, b;
} Coordinate;
// Structure to represent a line segment
typedef struct {
Coordinate start, end;
} Segment;
// Function to check if two line segments intersect
int checkIntersection(Segment s1, Segment s2) {
//
return 0;
}
// Function to find the intersection point of two line segments
Coordinate findIntersection(Segment s1, Segment s2) {
// coordinates of the start and end points of the first line segment
double a1 = s1.start.a, b1 = s1.start.b;
double a2 = s1.end.a, b2 = s1.end.b;
// coordinates of the start and end points of the second line segment
double a3 = s2.start.a, b3 = s2.start.b;
double a4 = s2.end.a, b4 = s2.end.b;
// Calculate the denominator of the intersection formula
double denominator = (b4 - b3) * (a2 - a1) - (a4 - a3) * (b2 - b1);
double numerator1 = (a4 - a3) * (b1 - b3) - (b4 - b3) * (a1 - a3);
double numerator2 = (a2 - a1) * (b1 - b3) - (b2 - b1) * (a1 - a3);
// If the denominator is zero, the lines are parallel
if (denominator == 0) {
return (Coordinate){ INFINITY, INFINITY };
}
double u = numerator1 / denominator;
double v = numerator2 / denominator;
if (u >= 0 && u <= 1 && v >= 0 && v <= 1) {
double a = a1 + u * (a2 - a1);
double b = b1 + u * (b2 - b1);
return (Coordinate){ a, b };
}
return (Coordinate){ INFINITY, INFINITY };
}
int main() {
// line segments
Segment s1 = { { 1, 2 }, { 3, 2 } };
Segment s2 = { { 2, 1 }, { 2, 3 } };
// If the line segments intersect
if (checkIntersection(s1, s2)) {
// Find the intersection point
Coordinate c = findIntersection(s1, s2);
printf("Intersection point: (%f, %f)
", c.a, c.b);
} else {
printf("Segments do not intersect
");
}
return 0;
}
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// structure to represent a coordinate
struct Coordinate {
double a, b;
};
// structure to represent a line segment
struct Segment {
Coordinate start, end;
};
// Function to check if two line segments intersect
bool checkIntersection(Segment s1, Segment s2)
{
//
}
// Function to find the intersection point of two line segments
Coordinate findIntersection(Segment s1, Segment s2) {
// coordinates of the start and end points of the first line segment
double a1 = s1.start.a, b1 = s1.start.b;
double a2 = s1.end.a, b2 = s1.end.b;
// coordinates of the start and end points of the second line segment
double a3 = s2.start.a, b3 = s2.start.b;
double a4 = s2.end.a, b4 = s2.end.b;
// Calculate the denominator of the intersection formula
double denominator = (b4 - b3) * (a2 - a1) - (a4 - a3) * (b2 - b1);
// Calculate the numerators of the intersection formula
double numerator1 = (a4 - a3) * (b1 - b3) - (b4 - b3) * (a1 - a3);
double numerator2 = (a2 - a1) * (b1 - b3) - (b2 - b1) * (a1 - a3);
// If the denominator is zero, the lines are parallel
if (denominator == 0) {
return { INFINITY, INFINITY };
}
double u = numerator1 / denominator;
double v = numerator2 / denominator;
// If u and v are both between 0 and 1, the line segments intersect
if (u >= 0 && u <= 1 && v >= 0 && v <= 1) {
// Calculate the coordinates of the intersection point
double a = a1 + u * (a2 - a1);
double b = b1 + u * (b2 - b1);
return { a, b };
}
// If u or v is not between 0 and 1, the line segments do not intersect
return { INFINITY, INFINITY };
}
int main(){
// line segments
Segment s1 = { { 1, 2 }, { 3, 2 } };
Segment s2 = { { 2, 1 }, { 2, 3 } };
// If the line segments intersect
if (checkIntersection(s1, s2)) {
// Find the intersection point
Coordinate c = findIntersection(s1, s2);
// Print the intersection point
cout << "Intersection point: (" << c.a << ", " << c.b << ")" << endl;
} else {
cout << "Segments do not intersect" << endl;
}
return 0;
}
public class Main {
// Class to represent a coordinate
static class Coordinate {
double a, b;
Coordinate(double a, double b) {
this.a = a;
this.b = b;
}
}
// Class to represent a line segment
static class Segment {
Coordinate start, end;
Segment(Coordinate start, Coordinate end) {
this.start = start;
this.end = end;
}
}
// Method to check if two line segments intersect
static boolean checkIntersection(Segment s1, Segment s2) {
return false;
}
// Method to find the intersection point of two line segments
static Coordinate findIntersection(Segment s1, Segment s2) {
double a1 = s1.start.a, b1 = s1.start.b;
double a2 = s1.end.a, b2 = s1.end.b;
double a3 = s2.start.a, b3 = s2.start.b;
double a4 = s2.end.a, b4 = s2.end.b;
double denominator = (b4 - b3) * (a2 - a1) - (a4 - a3) * (b2 - b1);
double numerator1 = (a4 - a3) * (b1 - b3) - (b4 - b3) * (a1 - a3);
double numerator2 = (a2 - a1) * (b1 - b3) - (b2 - b1) * (a1 - a3);
if (denominator == 0) {
return new Coordinate(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
}
double u = numerator1 / denominator;
double v = numerator2 / denominator;
if (u >= 0 && u <= 1 && v >= 0 && v <= 1) {
double a = a1 + u * (a2 - a1);
double b = b1 + u * (b2 - b1);
return new Coordinate(a, b);
}
return new Coordinate(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
}
public static void main(String[] args) {
Segment s1 = new Segment(new Coordinate(1, 2), new Coordinate(3, 2));
Segment s2 = new Segment(new Coordinate(2, 1), new Coordinate(2, 3));
if (checkIntersection(s1, s2)) {
Coordinate c = findIntersection(s1, s2);
System.out.println("Intersection point: (" + c.a + ", " + c.b + ")");
} else {
System.out.println("Segments do not intersect");
}
}
}
import math
# Class to represent a coordinate
class Coordinate:
def __init__(self, a, b):
self.a = a
self.b = b
# Class to represent a line segment
class Segment:
def __init__(self, start, end):
self.start = start
self.end = end
# Function to check if two line segments intersect
def checkIntersection(s1, s2):
# Implement intersection checking algorithm here
return False # Placeholder return statement
# Function to find the intersection point of two line segments
def findIntersection(s1, s2):
a1, b1 = s1.start.a, s1.start.b
a2, b2 = s1.end.a, s1.end.b
a3, b3 = s2.start.a, s2.start.b
a4, b4 = s2.end.a, s2.end.b
denominator = (b4 - b3) * (a2 - a1) - (a4 - a3) * (b2 - b1)
numerator1 = (a4 - a3) * (b1 - b3) - (b4 - b3) * (a1 - a3)
numerator2 = (a2 - a1) * (b1 - b3) - (b2 - b1) * (a1 - a3)
if denominator == 0:
return Coordinate(math.inf, math.inf)
u = numerator1 / denominator
v = numerator2 / denominator
if 0 <= u <= 1 and 0 <= v <= 1:
a = a1 + u * (a2 - a1)
b = b1 + u * (b2 - b1)
return Coordinate(a, b)
return Coordinate(math.inf, math.inf)
# Test the functions
s1 = Segment(Coordinate(1, 2), Coordinate(3, 2))
s2 = Segment(Coordinate(2, 1), Coordinate(2, 3))
if checkIntersection(s1, s2):
c = findIntersection(s1, s2)
print(f"Intersection point: ({c.a}, {c.b})")
else:
print("Segments do not intersect")
Output
Segments do not intersect
