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