8000 formatted geom · DontFearAlgorithms/Algorithms-1@4669a89 · GitHub
[go: up one dir, main page]
Skip to content
8000

Commit 4669a89

Browse files
williamfisetwilliamfiset
committed
formatted geom
1 parent 92fe58f commit 4669a89

File tree

4 files changed

+31
-13
lines changed

4 files changed

+31
-13
lines changed

‎com/williamfiset/algorithms/geometry/ConvexHullGrahamScan.java

Lines changed: 13 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -19,13 +19,23 @@ static Stack<Point2D> createConvexHull(Point2D[] pts) {
1919
Arrays.sort(pts, new PointOrder());
2020
Arrays.sort(pts, 1, N, new PolarOrder(pts[0]));
2121
hull.push(pts[0]);
22-
for (k1 = 1; k1 < N; k1++) if (!pts[0].equals(pts[k1])) break;
22+
for (k1 = 1; k1 < N; k1++) {
23+
if (!pts[0].equals(pts[k1])) {
24+
break;
25+
}
26+
}
2327
if (k1 == N) return null;
24-
for (k2 = k1 + 1; k2 < N; k2++) if (collinear(pts[0], pts[k1], pts[k2]) != 0) break;
28+
for (k2 = k1 + 1; k2 < N; k2++) {
29+
if (collinear(pts[0], pts[k1], pts[k2]) != 0) {
30+
break;
31+
}
32+
}
2533
hull.push(pts[k2 - 1]);
2634
for (int i = k2; i < N; i++) {
2735
Point2D top = hull.pop();
28-
while (collinear(hull.peek(), top, pts[i]) <= 0) top = hull.pop();
36+
while (collinear(hull.peek(), top, pts[i]) <= 0) {
37+
top = hull.pop();
38+
}
2939
hull.push(top);
3040
hull.push(pts[i]);
3141
}

‎com/williamfiset/algorithms/geometry/ConvexHullMonotoneChainsAlgorithm.java

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,7 +65,11 @@ public static Point2D[] convexHull(Point2D[] pts) {
6565
// Conserve only unique points.
6666
int index = 1;
6767
Point2D lastPt = hull[0];
68-
for (int i = 1; i < k - 1; i++) if (!hull[i].equals(lastPt)) hull[index++] = lastPt = hull[i];
68+
for (int i = 1; i < k - 1; i++) {
69+
if (!hull[i].equals(lastPt)) {
70+
hull[index++] = lastPt = hull[i];
71+
}
72+
}
6973

7074
return Arrays.copyOfRange(hull, 0, index);
7175
}

‎com/williamfiset/algorithms/geometry/ConvexPolygonContainsPoint.java

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -53,10 +53,11 @@ public static boolean containsPoint(Point2D[] hull, Point2D p) {
5353
// to the left from the frame of reference of standing at point a
5454
// and facing point b.
5555
public static int collinear(Point2D a, Point2D b, Point2D c) {
56-
double area =
57-
(b.getX() - a.getX()) * (c.getY() - a.getY())
58-
- (b.getY() - a.getY()) * (c.getX() - a.getX());
56+
double ax = a.getX(), ay = a.getY();
57+
double bx = b.getX(), by = b.getY();
58+
double cx = c.getX(), cy = c.getY();
59+
double area = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
5960
if (abs(area) < EPS) return 0;
60-
return (int) Math.signum(area);
61+
return (int) signum(area);
6162
}
6263
}

‎com/williamfiset/algorithms/geometry/PointInsideTriangle.java

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -23,8 +23,9 @@ public class PointInsideTriangle {
2323
public static boolean pointInsideTriangle(Point2D a, Point2D b, Point2D c, Point2D p) {
2424

2525
// Points a,b,c form a degenerate triangle
26-
if (collinear(a, b, c) == 0)
26+
if (collinear(a, b, c) == 0) {
2727
throw new IllegalArgumentException("points a,b,c do not form a triangle!");
28+
}
2829

2930
// Compute the directions the point 'p' is relative to
3031
// the three half planes formed by the points of the triangle
@@ -41,8 +42,9 @@ public static boolean pointInsideTriangle(Point2D a, Point2D b, Point2D c, Point
4142
public static boolean pointInsideTriangle2(Point2D a, Point2D b, Point2D c, Point2D p) {
4243

4344
// Points a,b,c form a degenerate triangle
44-
if (collinear(a, b, c) == 0)
45+
if (collinear(a, b, c) == 0) {
4546
throw new IllegalArgumentException("points a,b,c do not form a triangle!");
47+
}
4648

4749
// Change '<' to '<=' to exclude points on the boundary
4850
boolean dir1 = collinear(a, b, p) < 0;
@@ -58,9 +60,10 @@ public static boolean pointInsideTriangle2(Point2D a, Point2D b, Point2D c, Poin
5860
// to the left from the frame of reference of standing at point a
5961
// and facing point b.
6062
public static int collinear(Point2D a, Point2D b, Point2D c) {
61-
double area =
62-
(b.getX() - a.getX()) * (c.getY() - a.getY())
63-
- (b.getY() - a.getY()) * (c.getX() - a.getX());
63+
double ax = a.getX(), ay = a.getY();
64+
double bx = b.getX(), by = b.getY();
65+
double cx = c.getX(), cy = c.getY();
66+
double area = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
6467
if (abs(area) < EPS) return 0;
6568
return (int) signum(area);
6669
}

0 commit comments

Comments
 (0)
0