Last active
September 10, 2015 11:27
-
-
Save daveallie/97ab1c774c4def7a3863 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
public class CompGeom { | |
public static void main(String[] args) { | |
List<Point> points = new ArrayList<Point>(); | |
// points.add(new Point(5, 4)); | |
// points.add(new Point(4, 2)); | |
// points.add(new Point(3, 3)); | |
// points.add(new Point(6, 1)); | |
// points.add(new Point(7, 4)); | |
// points.add(new Point(2, 1)); | |
// points.add(new Point(1, 3)); | |
points.add(new Point(0, 0)); | |
points.add(new Point(0, 1)); | |
points.add(new Point(1, 0)); | |
points.add(new Point(1, 1)); | |
points.add(new Point(0.5, 0.5)); | |
Polygon poly = Polygon.convexHull(points); | |
System.out.println(poly.area()); | |
System.out.println(poly.boundary); | |
System.out.println(poly.containsPoint(new Point(0.3, 0.1))); | |
} | |
/** | |
* Polygon class, holds an ordered list of points representing the boundary. | |
*/ | |
static class Polygon { | |
List<Point> boundary; | |
double minX, maxX, minY, maxY; | |
public Polygon(List<Point> boundary) { | |
this.boundary = boundary; | |
List<Point> boundPoints = new ArrayList<>(boundary); | |
Collections.sort(boundPoints, new Point.XYComparator()); | |
minX = boundPoints.get(0).x; | |
maxX = boundPoints.get(boundPoints.size() - 1).x; | |
Collections.sort(boundPoints, new Point.YXComparator()); | |
minY = boundPoints.get(0).y; | |
maxY = boundPoints.get(boundPoints.size() - 1).y; | |
} | |
/** | |
* Calculate and return the area of the Polygon. | |
* | |
* @return the area of the polygon | |
*/ | |
public double area() { | |
double area = 0; | |
Point p0 = boundary.get(0); | |
for (int i = 1; i < boundary.size() - 1; i++) { | |
area += Math.abs(new Vector(p0, boundary.get(i)).crossProductWith(new Vector(p0, boundary.get(i + 1)))) / 2.0; | |
} | |
return area; | |
} | |
/** | |
* Determine if a Point is in the polygon's bounding box. | |
* | |
* @param p the Point to test | |
* @return true, if the point is in the polygon's bounding box, false otherwise | |
*/ | |
public boolean inBoundingBox(Point p) { | |
return minX <= p.x && p.x <= maxX | |
&& minY <= p.y && p.y <= maxY; | |
} | |
/** | |
* Determine if a Point is in a polygon using inBoundingBox(Point) then ray casting. On the boundary is | |
* considered inside. | |
* | |
* @param p the Point to test | |
* @return true, if the point is in the polygon, false otherwise | |
*/ | |
public boolean containsPoint(Point p) { | |
if (inBoundingBox(p)) { | |
LineSegment ray = new LineSegment(p, new Point(minX - 1, p.y)); | |
int intersection = 0; | |
for (int i = 0; i < boundary.size(); i++) { | |
if (Point.intersectionOf(new LineSegment(boundary.get(i), boundary.get((i + 1) % boundary.size())), ray) != null) { | |
intersection++; | |
} | |
} | |
// If the number of intersections is odd, then the point is inside the polygon | |
return intersection % 2 == 1; | |
} | |
return false; | |
} | |
/** | |
* Cut a Polygon into two or more parts if the line intersects the polygon or just return the polygon otherwise. | |
* | |
* @param l the LineType used to cut the polygon | |
* @param <LineType> anything that extends Line (i.e. Line or LineSegment) | |
* @return either two polygons if the line intersected the polygon or the original polygon back | |
*/ | |
public <LineType extends Line> List<Polygon> cut(LineType l) { | |
// TODO: Implement | |
return null; | |
} | |
/** | |
* Find the convex hull from a list of Points and return the Polygon represented by it. | |
* | |
* @param points the list of points to calculate the convex hull from | |
* @return a new convex hull polygon from a list of points | |
*/ | |
public static Polygon convexHull(List<Point> points) { | |
Collections.sort(points, new Point.YXComparator()); | |
Collections.sort(points, new Point.PolarComparator(points.get(0))); | |
Iterator<Point> it = points.iterator(); | |
List<Point> boundary = new ArrayList<Point>(); | |
boundary.add(0, it.next()); | |
boundary.add(0, it.next()); | |
boundary.add(0, it.next()); | |
while (it.hasNext()) { | |
Point nextToTop = boundary.get(1); | |
Point top = boundary.get(0); | |
Point p = it.next(); | |
Vector v1 = new Vector(nextToTop, top); | |
Vector v2 = new Vector(top, p); | |
Vector.TurningDirection td = v1.turningDirectionOnto(v2); | |
while (td != Vector.TurningDirection.LEFT) { | |
boundary.remove(0); | |
top = nextToTop; | |
nextToTop = boundary.get(1); | |
v1 = new Vector(nextToTop, top); | |
v2 = new Vector(top, p); | |
td = v1.turningDirectionOnto(v2); | |
} | |
boundary.add(0, p); | |
} | |
return new Polygon(boundary); | |
} | |
} | |
/** | |
* Point class that holds an x and y co-ordinate. | |
*/ | |
static class Point { | |
double x, y; | |
public Point(double x, double y) { | |
this.x = x; | |
this.y = y; | |
} | |
@Override | |
public String toString() { | |
return "(" + x + ", " + y + ")"; | |
} | |
/** | |
* Compare points, ordered by lowest x first, then lowest y. | |
*/ | |
static class XYComparator implements Comparator<Point> { | |
@Override | |
public int compare(Point p1, Point p2) { | |
if (p1.x == p2.x) | |
return Double.compare(p1.y, p2.y); | |
return Double.compare(p1.x, p2.x); | |
} | |
} | |
/** | |
* Compare points, ordered by lowest y first, then lowest x. | |
*/ | |
static class YXComparator implements Comparator<Point> { | |
@Override | |
public int compare(Point p1, Point p2) { | |
if (p1.y == p2.y) | |
return Double.compare(p1.x, p2.x); | |
return Double.compare(p1.y, p2.y); | |
} | |
} | |
/** | |
* Compare points, ordered anti-clockwise rotationally from a single points. | |
*/ | |
static class PolarComparator implements Comparator<Point> { | |
Point p; | |
public PolarComparator(Point p) { | |
this.p = p; | |
} | |
@Override | |
public int compare(Point p1, Point p2) { | |
Vector v1 = new Vector(p, p1); | |
Vector v2 = new Vector(p, p2); | |
Vector.TurningDirection td = v1.turningDirectionOnto(v2); | |
if (td == Vector.TurningDirection.STRAIGHT) | |
return Double.compare(v1.length(), v2.length()); | |
else | |
return td.val; | |
} | |
} | |
/** | |
* Find the intersection of two LineTypes by determining if their bounding boxes intersect then comparing the | |
* signs of the cross products from one end of each line to the ends of the other line. | |
* | |
* @param l1 the first LineType | |
* @param l2 the second LineType | |
* @param <LineType> anything that extends Line (i.e. Line or LineSegment) | |
* @return the Point of intersection or null if the lines don't intersect or are parallel | |
*/ | |
static <LineType extends Line> Point intersectionOf(LineType l1, LineType l2) { | |
if (l1.boundingBoxIntersects(l2)) { | |
Vector v0, v1, v2; | |
Vector.TurningDirection v0ToV1, v0ToV2; | |
// Only check from l1 to the ends of l2 if l2 is a line segment | |
if (l2 instanceof LineSegment) { | |
v0 = new Vector(l1.p1, l1.p2); | |
v1 = new Vector(l1.p1, l2.p1); | |
v2 = new Vector(l1.p1, l2.p2); | |
v0ToV1 = v0.turningDirectionOnto(v1); | |
v0ToV2 = v0.turningDirectionOnto(v2); | |
if (v0ToV1 == v0ToV2 && v0ToV1 != Vector.TurningDirection.STRAIGHT) | |
return null; | |
} | |
// Only check from l2 to the ends of l1 if l1 is a line segment | |
if (l1 instanceof LineSegment) { | |
v0 = new Vector(l2.p1, l2.p2); | |
v1 = new Vector(l2.p1, l1.p1); | |
v2 = new Vector(l2.p1, l1.p2); | |
v0ToV1 = v0.turningDirectionOnto(v1); | |
v0ToV2 = v0.turningDirectionOnto(v2); | |
if (v0ToV1 == v0ToV2 && v0ToV1 != Vector.TurningDirection.STRAIGHT) | |
return null; | |
} | |
if ((l1.p1.y - l1.p2.y) / (l1.p1.x - l1.p2.x) == (l2.p1.y - l2.p2.y) / (l2.p1.x - l2.p2.x)) | |
return null; // co-linear lines | |
// https://en.wikipedia.org/wiki/Line–line_intersection#Given_two_points_on_each_line | |
// x = (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4) | |
// ----------------------------------------------------------------- | |
// (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4) | |
// y = (x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4) | |
// ----------------------------------------------------------------- | |
// (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4) | |
double x = ((l1.p1.x * l1.p2.y - l1.p1.y * l1.p2.x) * (l2.p1.x - l2.p2.x) - (l1.p1.x - l1.p2.x) * (l2.p1.x * l2.p2.y - l2.p1.y * l2.p2.x)) | |
/ ((l1.p1.x - l1.p2.x) * (l2.p1.y - l2.p2.y) - (l1.p1.y - l1.p2.y) * (l2.p1.x - l2.p2.x)); | |
double y = ((l1.p1.x * l1.p2.y - l1.p1.y * l1.p2.x) * (l2.p1.y - l2.p2.y) - (l1.p1.y - l1.p2.y) * (l2.p1.x * l2.p2.y - l2.p1.y * l2.p2.x)) | |
/ ((l1.p1.x - l1.p2.x) * (l2.p1.y - l2.p2.y) - (l1.p1.y - l1.p2.y) * (l2.p1.x - l2.p2.x)); | |
return new Point(x, y); | |
} | |
// Bounding boxes don't intersect | |
return null; | |
} | |
} | |
/** | |
* A vector from the origin to a Point. | |
*/ | |
static class Vector extends Point { | |
public Vector(double x, double y) { | |
super(x, y); | |
} | |
public Vector(Point p1, Point p2) { | |
super(p2.x - p1.x, p2.y - p1.y); | |
} | |
/** | |
* Calculate the cross product of this vector and a given vector | |
* | |
* @param v the second vector to calculate the cross product with | |
* @return the result of the this vector crossed with v | |
*/ | |
public double crossProductWith(Vector v) { | |
return x * v.y - v.x * y; | |
} | |
/** | |
* Calculate the length of this vector. | |
* | |
* @return the length of this vector | |
*/ | |
public double length() { | |
return Math.sqrt(x * x + y * y); | |
} | |
/** | |
* Determine the turning direction from this vector to another vector. | |
* | |
* @param v the vector we're turning onto | |
* @return the TurningDirection taken | |
*/ | |
public TurningDirection turningDirectionOnto(Vector v) { | |
return TurningDirection.turningDirectionFromCrossProduct(this.crossProductWith(v)); | |
} | |
/** | |
* TurningDirection enumerator, used to represent the turning direction from one Vector to the next. | |
*/ | |
enum TurningDirection { | |
LEFT(-1), | |
STRAIGHT(0), | |
RIGHT(1); | |
int val; | |
TurningDirection(int val) { | |
this.val = val; | |
} | |
/** | |
* Get the TurningDirection from the result of the cross product, RIGHT if negative, LEFT if positive, | |
* STRAIGHT if 0. | |
* | |
* @param crossProductResult result of the cross product | |
* @return the resultant TurningDirection | |
*/ | |
static TurningDirection turningDirectionFromCrossProduct(double crossProductResult) { | |
if (crossProductResult < 0) return RIGHT; | |
else if (crossProductResult == 0) return STRAIGHT; | |
else return LEFT; | |
} | |
} | |
} | |
/** | |
* Infinitely long line defined by two Points. | |
*/ | |
static class Line { | |
public Point p1, p2; | |
public Line(Point p1, Point p2) { | |
if (p2.y < p1.y || (p1.y == p2.y && p2.x < p1.x)) { | |
this.p1 = p2; | |
this.p2 = p1; | |
} else { | |
this.p1 = p1; | |
this.p2 = p2; | |
} | |
} | |
/** | |
* Determine if a LineType's bounding box intersect this' bounding box, always true if either this or l is a | |
* Line. | |
* | |
* @param l the LineType to test bounding boxes against | |
* @param <LineType> anything that extends Line (i.e. Line or LineSegment) | |
* @return true, if the bounding boxes intersect, false otherwise | |
*/ | |
public <LineType extends Line> boolean boundingBoxIntersects(LineType l) { | |
// Lines are infinite and therefore always have intersecting bounding boxes | |
return true; | |
} | |
} | |
/** | |
* Line that is contained between two points. | |
*/ | |
static class LineSegment extends Line { | |
public LineSegment(Point p1, Point p2) { | |
super(p1, p2); | |
} | |
@Override | |
public <LineType extends Line> boolean boundingBoxIntersects(LineType l) { | |
return !(l instanceof LineSegment) || // then l is a line | |
p2.x >= l.p1.x | |
&& l.p2.x >= p1.x | |
&& p2.y >= l.p1.y | |
&& l.p2.y >= p1.y; | |
} | |
/** | |
* Calculate and return the line segment's length. | |
* | |
* @return the line segment's length | |
*/ | |
public double length() { | |
return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment