The Graham scan algorithm is a simple and efficient method for computing the convex hull of a set of 2-dimensional points. Let’s break down how it works:
Convex Hull:
A convex hull is the smallest convex polygon that encloses a given set of points.
It’s a fundamental concept in computational geometry and has applications in fields like computer graphics, image processing, and collision detection.
A convex polygon is one where all interior angles are less than 180 degrees.
Algorithm Overview:
The Graham scan algorithm constructs the convex hull by iteratively adding points to it until all points are included.
Here’s how it works step by step:
Find the Starting Point:
Begin by finding the point with the smallest y-coordinate. This point is always on the convex hull.
Sort Points by Polar Angle:
Sort the remaining points based on their polar angle with respect to the starting point.
The polar angle is calculated relative to the starting point.
Iteratively Add Points:
Starting with the smallest polar angle, iteratively add points to the convex hull.
At each step, check whether the last two points added form a right turn.
If they do, remove the last point from the convex hull; otherwise, add the next point from the sorted list.
Termination:
The algorithm stops when all points have been added to the convex hull.
Implementation Phases:
Phase 1 (Sort Points):
Sort the points by their polar angle with respect to the starting point.
Add the starting point to the convex hull.
Phase 2 (Accept or Reject Points):
Traverse the closed path formed by the sorted points.
Remove any concave points from this path.
Use orientation to decide which points to keep:
If the orientation of three consecutive points (prev, curr, next) is counterclockwise, keep curr; otherwise, discard it.
Time Complexity:
The Graham scan algorithm runs in O(n log n) time due to the sorting step.
/*
* Copyright (c) 2010-2022 William Bittle http://www.dyn4j.org/
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without modification, are permitted
* provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice, this list of conditions
* and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright notice, this list of conditions
* and the following disclaimer in the documentation and/or other materials provided with the
* distribution.
* * Neither the name of the copyright holder nor the names of its contributors may be used to endorse or
* promote products derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
* FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
* IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
package org.dyn4j.geometry.hull;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import org.dyn4j.exception.ArgumentNullException;
import org.dyn4j.exception.NullElementException;
import org.dyn4j.geometry.RobustGeometry;
import org.dyn4j.geometry.Vector2;
/**
* Implementation of the Graham Scan convex hull algorithm.
* <p>
* This algorithm handles coincident and colinear points by ignoring them during processing. This ensures
* the produced hull will not have coincident or colinear vertices.
* <p>
* This algorithm is O(n log n) where n is the number of input points.
* @author William Bittle
* @version 5.0.0
* @since 2.2.0
*/
public class GrahamScan extends AbstractHullGenerator implements HullGenerator {
/* (non-Javadoc)
* @see org.dyn4j.geometry.hull.HullGenerator#generate(org.dyn4j.geometry.Vector2[])
*/
@Override
public Vector2[] generate(Vector2... points) {
// check for null points array
if (points == null)
throw new ArgumentNullException("points");
// get the size
int size = points.length;
// check the size
if (size <= 2) return points;
// find the point of minimum y (choose the point of minimum x if there is a tie)
Vector2 minY = points[0];
for (int i = 1; i < size; i++) {
Vector2 p = points[i];
// make sure the point is not null
if (p == null)
throw new NullElementException("points", i);
if (p.y < minY.y) {
minY = p;
} else if (p.y == minY.y) {
if (p.x > minY.x) {
minY = p;
}
}
}
// create the comparator for the array
ReferencePointComparator pc = new ReferencePointComparator(minY);
// sort the array by angle
Arrays.sort(points, pc);
// build the hull
List<Vector2> stack = new ArrayList<Vector2>();
// push
stack.add(points[0]);
stack.add(points[1]);
int i = 2;
while (i < size) {
int sSize = stack.size();
// if the stack size is one then just
// push the current point onto the stack
// thereby making a line segment
if (sSize == 1) {
// push
stack.add(points[i]);
i++;
continue;
}
// otherwise get the top two items off the stack
Vector2 p1 = stack.get(sSize - 2);
Vector2 p2 = stack.get(sSize - 1);
// get the current point
Vector2 p3 = points[i];
// test if the current point is to the left of the line
// created by the top two items in the stack (the last edge
// on the current convex hull)
// Use the robust side of line test because otherwise this algorithm
// can produce incorrect results in edge cases
// The order of parameters here must match the one in ReferenceComparator
// in order to obtain correct results and winding
double location = RobustGeometry.getLocation(p3, p2, p1);
if (location < 0.0) {
// if its to the left, then push the new point on
// the stack since it maintains convexity
stack.add(p3);
i++;
} else {
// otherwise the pop the previous point off the stack
// since this indicates that if we added the current
// point to the stack we would make a concave section
// pop
stack.remove(sSize - 1);
}
}
// finally copy all the stack items into the array to return
Vector2[] hull = new Vector2[stack.size()];
stack.toArray(hull);
// return the array
return hull;
}
}Useful Refernces
Comments