// Catalano Math Library
// The Catalano Framework
//
// Copyright © Diego Catalano, 2012-2016
// diego.catalano at live.com
//
// Copyright © Andrew Kirillov, 2007-2008
// andrew.kirillov at gmail.com
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
//
package Catalano.Math.Geometry;
import Catalano.Core.IntPoint;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* Graham scan algorithm for finding convex hull.
* @author Diego Catalano
*/
public class GrahamConvexHull {
/**
* Initializes a new instance of the class.
*/
public GrahamConvexHull() {
}
/**
* Find convex hull for the given set of points.
* @param points Set of points to search convex hull for.
* @return Set of points, which form a convex hull for the given points.
*/
public List FindHull(List points){
List pointsToProcess = new ArrayList();
for (IntPoint p : points) {
pointsToProcess.add(new PointToProcess(p));
}
int firstCornerIndex = 0;
PointToProcess firstCorner = pointsToProcess.get(0);
for ( int i = 1, n = pointsToProcess.size(); i < n; i++ ){
if ( ( pointsToProcess.get(i).x < firstCorner.x ) || ( ( pointsToProcess.get(i).x == firstCorner.x ) && ( pointsToProcess.get(i).y < firstCorner.y ) ) ){
firstCorner = pointsToProcess.get(i);
firstCornerIndex = i;
}
}
// remove the just found point
pointsToProcess.remove(firstCornerIndex);
// find K (tangent of line's angle) and distance to the first corner
for ( int i = 0, n = pointsToProcess.size(); i < n; i++ ){
int dx = pointsToProcess.get(i).x - firstCorner.x;
int dy = pointsToProcess.get(i).y - firstCorner.y;
// don't need square root, since it is not important in our case
pointsToProcess.get(i).distance = dx * dx + dy * dy;
// tangent of lines angle
pointsToProcess.get(i).k = ( dx == 0 ) ? Float.POSITIVE_INFINITY : (float) dy / dx;
}
// sort points by angle and distance
Collections.sort(pointsToProcess);
ArrayList convexHullTemp = new ArrayList();
// add first corner, which is always on the hull
convexHullTemp.add(firstCorner);
// add another point, which forms a line with lowest slope
convexHullTemp.add(pointsToProcess.get(0));
pointsToProcess.remove(0);
PointToProcess lastPoint = convexHullTemp.get(1);
PointToProcess prevPoint = convexHullTemp.get(0);
while (!pointsToProcess.isEmpty()){
PointToProcess newPoint = pointsToProcess.get(0);
// skip any point, which has the same slope as the last one or
// has 0 distance to the first point
if ( ( newPoint.k == lastPoint.k ) || ( newPoint.distance == 0 ) ){
pointsToProcess.remove( 0 );
continue;
}
// check if current point is on the left side from two last points
if ( ( newPoint.x - prevPoint.x ) * ( lastPoint.y - newPoint.y ) - ( lastPoint.x - newPoint.x ) * ( newPoint.y - prevPoint.y ) < 0 ){
// add the point to the hull
convexHullTemp.add( newPoint );
// and remove it from the list of points to process
pointsToProcess.remove( 0 );
prevPoint = lastPoint;
lastPoint = newPoint;
}
else{
// remove the last point from the hull
convexHullTemp.remove( convexHullTemp.size() - 1 );
lastPoint = prevPoint;
prevPoint = convexHullTemp.get(convexHullTemp.size() - 2);
}
}
// convert points back
ArrayList convexHull = new ArrayList();
for (PointToProcess p : convexHullTemp) {
convexHull.add(p.toPoint());
}
return convexHull;
}
}
class PointToProcess implements Comparable {
public int x;
public int y;
public float k;
public float distance;
public PointToProcess(IntPoint p) {
this.x = p.x;
this.y = p.y;
k = 0;
distance = 0;
}
@Override
public int compareTo(PointToProcess o) {
if (this.k == o.k) {
return 0;
}
else if ((this.k) > o.k) {
return 1;
}
else {
return -1;
}
}
public IntPoint toPoint(){
return new IntPoint(x,y);
}
}
Ads help maintain this website.