Computational Geometry – Algorithms for Geometry
Computational geometry is a field of study that focuses on developing algorithms and data structures for solving problems that involve geometric shapes and structures. The field has applications in a variety of areas, including computer graphics, robotics, geographic information systems, and more.
In this article, we will explore some of the key concepts and applications of computational geometry.
Geometric Problems:
One of the key goals of computational geometry is to find efficient solutions to geometric problems that arise in various fields. Some common geometric problems include:
- The intersection of two lines or planes
- Convex hull of a set of points
- Triangulation of a polygon
- Voronoi diagram of a set of points
- Delaunay triangulation of a set of points
- Point location in a planar subdivision
The solution to these Geometric Problems:
To solve these problems, computational geometry uses a variety of algorithms and data structures, the most commonly used algorithms include:
A method for solving a wide range of geometric problems, including computing the intersection of two lines or planes and triangulating a polygon. The algorithm works by sweeping a line or plane across the geometry and updating a data structure as it goes.
Use Cases:
- Closest pair of points problem: Finding the closest pair of points among a set of points in a 2D plane.
- Line segment intersection problem: Finding whether two or more line segments intersect in a 2D plane.
- Rectangle intersection problem: Finding whether two or more rectangles intersect in a 2D plane.
- Bentley-Ottmann algorithm: Computing the intersection of line segments in a plane.
Line segment intersection problem using Sweep line algorithm:
C++
// C++ code to implement the sweep // line algorithm #include <bits/stdc++.h> using namespace std; struct Point { double x, y; }; struct Line { Point p, q; }; // Function to check if two // lines intersect bool doIntersect(Line l1, Line l2) { // Implementation of intersection // checking algorithm } // Function to compute the intersection // point of two lines Point computeIntersection(Line l1, Line l2) { double x1 = l1.p.x, y1 = l1.p.y; double x2 = l1.q.x, y2 = l1.q.y; double x3 = l2.p.x, y3 = l2.p.y; double x4 = l2.q.x, y4 = l2.q.y; double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1); double num1 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3); double num2 = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3); if (denom == 0) { // Lines are parallel return { INFINITY, INFINITY }; } double ua = num1 / denom; double ub = num2 / denom; if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) { // Intersection point lies on // both line segments double x = x1 + ua * (x2 - x1); double y = y1 + ua * (y2 - y1); return { x, y }; } // Lines do not intersect return { INFINITY, INFINITY }; } // Driver's code int main() { Line l1 = { { 0, 0 }, { 1, 1 } }; Line l2 = { { 0, 1 }, { 1, 0 } }; if (doIntersect(l1, l2)) { // Function call Point p = computeIntersection(l1, l2); cout << "Intersection point: (" << p.x << ", " << p.y << ")" << endl; } else { cout << "Lines do not intersect" << endl; } return 0; } |
Java
class Point { double x, y; Point( double x, double y) { this .x = x; this .y = y; } } class Line { Point p, q; Line(Point p, Point q) { this .p = p; this .q = q; } } public class Main { // Function to check if two lines intersect static boolean doIntersect(Line l1, Line l2) { return false ; } // Function to compute the intersection point of two lines static Point computeIntersection(Line l1, Line l2) { double x1 = l1.p.x, y1 = l1.p.y; double x2 = l1.q.x, y2 = l1.q.y; double x3 = l2.p.x, y3 = l2.p.y; double x4 = l2.q.x, y4 = l2.q.y; double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1); double num1 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3); double num2 = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3); if (denom == 0 ) { // Lines are parallel return new Point(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } double ua = num1 / denom; double ub = num2 / denom; if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1 ) { // Intersection point lies on both line segments double x = x1 + ua * (x2 - x1); double y = y1 + ua * (y2 - y1); return new Point(x, y); } // Lines do not intersect return new Point(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } // Driver's code public static void main(String[] args) { Line l1 = new Line( new Point( 0 , 0 ), new Point( 1 , 1 )); Line l2 = new Line( new Point( 0 , 1 ), new Point( 1 , 0 )); if (doIntersect(l1, l2)) { // Function call Point p = computeIntersection(l1, l2); System.out.println( "Intersection point: (" + p.x + ", " + p.y + ")" ); } else { System.out.println( "Lines do not intersect" ); } } } |
Python
# Python Code to implement the Sweep Line Algorithm class Point: def __init__( self , x, y): self .x = x self .y = y class Line: def __init__( self , p, q): self .p = p self .q = q def doIntersect(l1, l2): # Implementation of intersection checking algorithm pass # You can implement this function as needed def computeIntersection(l1, l2): x1, y1 = l1.p.x, l1.p.y x2, y2 = l1.q.x, l1.q.y x3, y3 = l2.p.x, l2.p.y x4, y4 = l2.q.x, l2.q.y denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1) num1 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3) num2 = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3) if denom = = 0 : # Lines are parallel return float ( 'inf' ), float ( 'inf' ) ua = num1 / denom ub = num2 / denom if 0 < = ua < = 1 and 0 < = ub < = 1 : # Intersection point lies on both line segments x = x1 + ua * (x2 - x1) y = y1 + ua * (y2 - y1) return x, y # Lines do not intersect return float ( 'inf' ), float ( 'inf' ) # Driver's code if __name__ = = "__main__" : l1 = Line(Point( 0 , 0 ), Point( 1 , 1 )) l2 = Line(Point( 0 , 1 ), Point( 1 , 0 )) if doIntersect(l1, l2): # Function call p = computeIntersection(l1, l2) print ( "Intersection point: ({}, {})" . format (p[ 0 ], p[ 1 ])) else : print ( "Lines do not intersect" ) |
C#
using System; public class Point { public double x, y; public Point( double x, double y) { this .x = x; this .y = y; } } public class Line { public Point p, q; public Line(Point p, Point q) { this .p = p; this .q = q; } } public class MainClass { // Function to check if two lines intersect static bool DoIntersect(Line l1, Line l2) { return false ; // Placeholder return, needs implementation } // Function to compute the intersection point of two lines static Point ComputeIntersection(Line l1, Line l2) { double x1 = l1.p.x, y1 = l1.p.y; double x2 = l1.q.x, y2 = l1.q.y; double x3 = l2.p.x, y3 = l2.p.y; double x4 = l2.q.x, y4 = l2.q.y; double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1); double num1 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3); double num2 = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3); if (denom == 0) { // Lines are parallel return new Point( double .PositiveInfinity, double .PositiveInfinity); } double ua = num1 / denom; double ub = num2 / denom; if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) { // Intersection point lies on both line segments double x = x1 + ua * (x2 - x1); double y = y1 + ua * (y2 - y1); return new Point(x, y); } // Lines do not intersect return new Point( double .PositiveInfinity, double .PositiveInfinity); } // Driver's code public static void Main( string [] args) { // Creating two lines Line l1 = new Line( new Point(0, 0), new Point(1, 1)); Line l2 = new Line( new Point(0, 1), new Point(1, 0)); if (DoIntersect(l1, l2)) { // Function call to compute intersection point Point p = ComputeIntersection(l1, l2); Console.WriteLine( "Intersection point: (" + p.x + ", " + p.y + ")" ); } else { Console.WriteLine( "Lines do not intersect" ); } } } |
Javascript
class Point { constructor(x, y) { this .x = x; this .y = y; } } class Line { constructor(p, q) { this .p = p; this .q = q; } } function doIntersect(l1, l2) { return false ; } function computeIntersection(l1, l2) { const x1 = l1.p.x, y1 = l1.p.y; const x2 = l1.q.x, y2 = l1.q.y; const x3 = l2.p.x, y3 = l2.p.y; const x4 = l2.q.x, y4 = l2.q.y; const denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1); const num1 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3); const num2 = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3); if (denom === 0) { // Lines are parallel return new Point(Infinity, Infinity); } const ua = num1 / denom; const ub = num2 / denom; if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) { // Intersection point lies on both line segments const x = x1 + ua * (x2 - x1); const y = y1 + ua * (y2 - y1); return new Point(x, y); } // Lines do not intersect return new Point(Infinity, Infinity); } // Driver's code const l1 = new Line( new Point(0, 0), new Point(1, 1)); const l2 = new Line( new Point(0, 1), new Point(1, 0)); if (doIntersect(l1, l2)) { // Function call const p = computeIntersection(l1, l2); console.log(`Intersection point: (${p.x}, ${p.y})`); } else { console.log( "Lines do not intersect" ); } |
Intersection point: (0.5, 0.5)
Limitations of the Sweep line algorithm:
- The sweep line algorithm assumes that the objects being swept are not overlapping in the same event point. If this assumption is violated, the algorithm may fail.
- The algorithm may require sorting and searching operations that have a high computational cost.
- Graham scan is a well-known algorithm in computational geometry that is used to find the convex hull of a given set of points. The algorithm was proposed by Ronald Graham in 1972.
- The basic idea of the algorithm is to start with the point with the lowest y-coordinate (and lowest x-coordinate in case of a tie), and then sort the remaining points in order of the angle they make with the horizontal line passing through the starting point. This can be done using the polar angle of each point with respect to the starting point.
- Once the points are sorted, the algorithm proceeds in a clockwise direction around the points, adding each point to the convex hull if it does not create a counter-clockwise turn with the last two points in the hull. If it does create a counter-clockwise turn, then the last point added to the hull is removed, and the process is repeated until the new point does not create a counter-clockwise turn.
- The Graham scan algorithm has a time complexity of O(n log n), where n is the number of input points. The algorithm is widely used in applications such as computer graphics, geographic information systems, and robotics.
Use Cases:
- Convex hull problem: Finding the convex hull of a set of points in a 2D plane.
- Rotating calipers algorithm: Finding the width and diameter of a convex polygon.
- Maximum distance problem: Finding the maximum distance between any two points in a set of points in a 2D plane.
Let’s see the implementation of Graham’s algorithm for the convex hull problem:
C++
// C++ code to implement the graham // scan algorithm #include <algorithm> #include <iostream> #include <stack> #include <vector> using namespace std; struct Point { int x, y; }; Point p0; // Comparator function for sorting points // in counterclockwise order around p0 int compare( const void * vp1, const void * vp2) { Point* p1 = (Point*)vp1; Point* p2 = (Point*)vp2; int orientation = (p1->y - p0.y) * (p2->x - p1->x) - (p1->x - p0.x) * (p2->y - p1->y); if (orientation == 0) { return (p1->x + p1->y < p2->x + p2->y) ? -1 : 1; } return (orientation < 0) ? -1 : 1; } // Returns the square of the Euclidean // distance between two points int distSq(Point p1, Point p2) { return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y); } // Returns the orientation of three // points (p, q, r) int orientation(Point p, Point q, Point 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; } // Computes the convex hull of a set of n // points using the Graham's // Scan algorithm void convexHull(Point points[], int n) { // Find the point with the // lowest y-coordinate int ymin = points[0].y; int 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; } } // Swap the lowest point with // the first point swap(points[0], points[min]); p0 = points[0]; // Sort the remaining points in // counterclockwise order around p0 qsort (&points[1], n - 1, sizeof (Point), compare); // If two or more points have the same // angle with p0, remove all but // the farthest int m = 1; for ( int i = 1; i < n; i++) { while (i < n - 1 && orientation(p0, points[i], points[i + 1]) == 0) { i++; } points[m] = points[i]; m++; } // If there are less than 3 unique // points, there is no convex hull if (m < 3) { return ; } // Use a stack to keep track of the // vertices of the convex hull stack<Point> hull; hull.push(points[0]); hull.push(points[1]); hull.push(points[2]); // Process the remaining points for ( int i = 3; i < n; i++) { while (hull.size() > 1 && orientation(hull.top(), hull.top(), points[i]) != 2) { hull.pop(); } hull.push(points[i]); } // Print the vertices of the // convex hull while (!hull.empty()) { Point p = hull.top(); cout << "(" << p.x << ", " << p.y << ")" << endl; hull.pop(); } } // Driver's code int main() { // Test the algorithm with a set of points Point points[] = { { 0, 3 }, { 1, 1 }, { 2, 2 }, { 4, 4 }, { 0, 0 }, { 1, 2 }, { 3, 1 }, { 3, 3 } }; int n = sizeof (points) / sizeof (points[0]); cout << "Vertices of the convex hull:" << endl; convexHull(points, n); return 0; } |
Java
import java.util.Arrays; import java.util.Stack; // Class representing a 2D point class Point { int x, y; Point( int x, int y) { this .x = x; this .y = y; } } public class ConvexHullGrahamScan { static Point p0; // Reference point for sorting and orientation // Function to compare two points based on their polar angles static int compare(Point p1, Point p2) { // Calculate orientation using cross product of vectors p0p1 and p0p2 int orientation = (p1.y - p0.y) * (p2.x - p1.x) - (p1.x - p0.x) * (p2.y - p1.y); // If points are collinear, sort by distance from p0 if (orientation == 0 ) { return Integer.compare(p1.x + p1.y, p2.x + p2.y); } return (orientation < 0 ) ? - 1 : 1 ; } // Function to determine orientation of three points static int orientation(Point p, Point q, Point r) { int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val == 0 ) { return 0 ; // Collinear } return (val > 0 ) ? 1 : 2 ; // 1 for clockwise, 2 for counterclockwise } // Function to find the convex hull of a set of points static void convexHull(Point[] points) { int n = points.length; // Find the point with the lowest y-coordinate (and leftmost if ties) int ymin = points[ 0 ].y; int 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; } } // Swap the lowest point with the first point Point temp = points[ 0 ]; points[ 0 ] = points[min]; points[min] = temp; // Set the lowest point as the reference point p0 = points[ 0 ]; // Sort the points based on polar angle with respect to p0 Arrays.sort(points, 1 , n, ConvexHullGrahamScan::compare); int m = 1 ; // Initialize the modified size of points[] after removing collinear points // Remove collinear points except for the farthest for ( int i = 1 ; i < n; i++) { while (i < n - 1 && orientation(p0, points[i], points[i + 1 ]) == 0 ) { i++; } points[m] = points[i]; m++; } if (m < 3 ) { return ; // Convex hull not possible with less than 3 points } // Create a stack to store points on the convex hull Stack<Point> hull = new Stack<>(); hull.push(points[ 0 ]); hull.push(points[ 1 ]); hull.push(points[ 2 ]); // Process remaining points to find the convex hull for ( int i = 3 ; i < n; i++) { while (hull.size() > 1 && orientation(hull.get(hull.size() - 2 ), hull.peek(), points[i]) != 2 ) { hull.pop(); } hull.push(points[i]); } // Print vertices of the convex hull System.out.println( "Vertices of the convex hull:" ); while (!hull.isEmpty()) { Point p = hull.pop(); System.out.println( "(" + p.x + ", " + p.y + ")" ); } } public static void main(String[] args) { // Test points Point[] points = { new Point( 0 , 3 ), new Point( 1 , 1 ), new Point( 2 , 2 ), new Point( 4 , 4 ), new Point( 0 , 0 ), new Point( 1 , 2 ), new Point( 3 , 1 ), new Point( 3 , 3 ) }; // Find and print the convex hull of the points convexHull(points); } } |
Python3
import functools class Point: def __init__( self , x, y): self .x = x self .y = y p0 = Point( 0 , 0 ) # Comparator function for sorting points # in counterclockwise order around p0 def compare(p1, p2): orientation = (p1.y - p0.y) * (p2.x - p1.x) - (p1.x - p0.x) * (p2.y - p1.y) if orientation = = 0 : return - 1 if p1.x + p1.y < p2.x + p2.y else 1 return - 1 if orientation < 0 else 1 # Returns the square of the Euclidean # distance between two points def dist_sq(p1, p2): return (p2.x - p1.x) * * 2 + (p2.y - p1.y) * * 2 # Returns the orientation of three # points (p, q, r) def orientation(p, q, r): val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y) if val = = 0 : return 0 return 1 if val > 0 else 2 # Computes the convex hull of a set of n # points using Graham's Scan algorithm def convex_hull(points): global p0 n = len (points) # Find the point with the lowest y-coordinate ymin = points[ 0 ].y min_idx = 0 for i in range ( 1 , n): y = points[i].y if y < ymin or (ymin = = y and points[i].x < points[min_idx].x): ymin = points[i].y min_idx = i # Swap the lowest point with the first point points[ 0 ], points[min_idx] = points[min_idx], points[ 0 ] p0 = points[ 0 ] # Sort the remaining points in counterclockwise order around p0 points[ 1 :] = sorted (points[ 1 :], key = functools.cmp_to_key(compare)) # If two or more points have the same # angle with p0, remove all but the farthest m = 1 i = 1 while i < n: while i < n - 1 and orientation(p0, points[i], points[i + 1 ]) = = 0 : i + = 1 points[m] = points[i] m + = 1 i + = 1 # If there are less than 3 unique # points, there is no convex hull if m < 3 : return # Use a stack to keep track of the # vertices of the convex hull hull = [points[ 0 ], points[ 1 ], points[ 2 ]] # Process the remaining points for i in range ( 3 , n): while len (hull) > 1 and orientation(hull[ - 2 ], hull[ - 1 ], points[i]) ! = 2 : hull.pop() hull.append(points[i]) # Print the vertices of the # convex hull print ( "Vertices of the convex hull:" ) for p in reversed (hull): print (f "({p.x}, {p.y})" ) # Driver's code if __name__ = = "__main__" : # Test the algorithm with a set of points points = [Point( 0 , 3 ), Point( 1 , 1 ), Point( 2 , 2 ), Point( 4 , 4 ), Point( 0 , 0 ), Point( 1 , 2 ), Point( 3 , 1 ), Point( 3 , 3 )] print ( "Vertices of the convex hull:" ) convex_hull(points) |
C#
using System; using System.Collections.Generic; using System.Linq; public struct Point { public int x, y; } public class Program { static Point p0; static void Main() { Point[] points = new Point[] { new Point { x = 0, y = 3 }, new Point { x = 1, y = 1 }, new Point { x = 2, y = 2 }, new Point { x = 4, y = 4 }, new Point { x = 0, y = 0 }, new Point { x = 1, y = 2 }, new Point { x = 3, y = 1 }, new Point { x = 3, y = 3 } }; Console.WriteLine( "Vertices of the convex hull:" ); ConvexHull(points, points.Length); } static int Orientation(Point p, Point q, Point r) { int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val == 0) return 0; // collinear return (val > 0) ? 2 : 1; // clock or counterclock wise } static int Compare(Point p1, Point p2) { int o = Orientation(p0, p1, p2); if (o == 0) return (DistSq(p0, p2) >= DistSq(p0, p1)) ? -1 : 1; return (o == 2) ? -1 : 1; } static int DistSq(Point p1, Point p2) { return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y); } static void ConvexHull(Point[] 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; } var temp = points[0]; points[0] = points[min]; points[min] = temp; p0 = points[0]; Array.Sort(points, Compare); int m = 1; for ( int i = 1; i < n; i++) { while (i < n - 1 && Orientation(p0, points[i], points[i + 1]) == 0) i++; points[m] = points[i]; m++; } if (m < 3) return ; Stack<Point> hull = new Stack<Point>(); hull.Push(points[0]); hull.Push(points[1]); hull.Push(points[2]); for ( int i = 3; i < m; i++) { while (hull.Count > 1 && Orientation(NextToTop(hull), hull.Peek(), points[i]) != 2) hull.Pop(); hull.Push(points[i]); } while (hull.Any()) { Point p = hull.Peek(); Console.WriteLine( "(" + p.x + ", " + p.y + ")" ); hull.Pop(); } } static Point NextToTop(Stack<Point> S) { Point p = S.Pop(); Point res = S.Peek(); S.Push(p); return res; } } |
Javascript
class Point { constructor(x, y) { this .x = x; this .y = y; } } // Function to compare two points' orientations function compare(p1, p2) { // Calculate orientation using cross product let orientation = (p1.y - p0.y) * (p2.x - p1.x) - (p1.x - p0.x) * (p2.y - p1.y); if (orientation === 0) { // If collinear, compare based on distance return p1.x + p1.y - (p2.x + p2.y); } return orientation < 0 ? -1 : 1; // Return orientation } // Function to determine orientation of three points (p, q, r) function orientation(p, q, r) { let val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val === 0) { return 0; // Collinear } return val > 0 ? 1 : 2; // Clockwise or counterclockwise } // Function to find the convex hull of a set of points function convexHull(points) { let n = points.length; // Find the point with the lowest y-coordinate let ymin = points[0].y; let min = 0; for (let i = 1; i < n; i++) { let y = points[i].y; if ((y < ymin) || (ymin === y && points[i].x < points[min].x)) { ymin = points[i].y; min = i; } } // Swap the lowest point with the first point let temp = points[0]; points[0] = points[min]; points[min] = temp; p0 = points[0]; // Set the first point as the reference point // Sort the points based on their polar angles with respect to p0 points.sort((a, b) => compare(a, b)); let m = 1; // Eliminate collinear points for (let i = 1; i < n; i++) { while (i < n - 1 && orientation(p0, points[i], points[i + 1]) === 0) { i++; } points[m] = points[i]; m++; } if (m < 3) { return []; // Convex hull not possible with less than 3 points } let hull = []; hull.push(points[0]); hull.push(points[1]); hull.push(points[2]); // Compute the convex hull using Graham's scan for (let i = 3; i < n; i++) { while (hull.length > 1 && orientation(hull[hull.length - 2], hull[hull.length - 1], points[i]) !== 2) { hull.pop(); } hull.push(points[i]); } // Store the vertices of the convex hull let convexHullVertices = []; while (hull.length > 0) { let p = hull.pop(); convexHullVertices.push({ x: p.x, y: p.y }); } return convexHullVertices; } // Test points let points = [ new Point(0, 3), new Point(1, 1), new Point(2, 2), new Point(4, 4), new Point(0, 0), new Point(1, 2), new Point(3, 1), new Point(3, 3) ]; // Find the convex hull of the points let convexHullPoints = convexHull(points); // Print vertices of the convex hull console.log( "Vertices of the convex hull:" ); convexHullPoints.forEach(p => console.log(`(${p.x}, ${p.y})`)); |
Vertices of the convex hull: (0, 3) (0, 0)
Limitations of the Graham scan algorithm:
- The Graham scan algorithm only works for 2D convex hull problems.
- The algorithm has a computational complexity of O(n*logn), which can be a limiting factor for large datasets.
- The algorithm is sensitive to degenerate cases where many points lie in a straight line.