forked from williamfiset/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ConvexPolygonArea.java
81 lines (63 loc) · 2.41 KB
/
ConvexPolygonArea.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
* This file contains code that can find the area of a convex polygon if the points are given in CW
* or CCW order.
*
* <p>Time Complexity: O(n)
*
* @author William Fiset, william.alexandre.fiset@gmail.com
*/
package com.williamfiset.algorithms.geometry;
import java.awt.geom.Point2D;
public class ConvexPolygonArea {
// Given a set of points in CW of CCW order this method finds the area
// of the convex polygon defined by those points. The input to this
// method is an array of N+1 points where points[0] = points[N]
public static double convexPolygonArea(Point2D[] points) {
int N = points.length - 1;
if (N < 3 || points[0] != points[N])
throw new IllegalArgumentException(
"Make sure N >= 3 and that the points array has n+1 points and points[0] = points[N]");
// Let the first point be the fixed point
Point2D fp = points[0];
double area = 0, fpx = fp.getX(), fpy = fp.getY();
for (int i = 1; i < N; i++) {
Point2D pt1 = points[i];
Point2D pt2 = points[i + 1];
// Find the components of the vectors <a, c>
// and <b, d> which are the vectors from the
// fixed point to the points 'pt1' and 'pt2'
double a = pt1.getX() - fpx;
double b = pt2.getX() - fpx;
double c = pt1.getY() - fpy;
double d = pt2.getY() - fpy;
// Sum the signed area of the parallelograms formed by
// the vectors using formula for the determinant of
// two vectors in R2 which is: ad - bc.
area += a * d - b * c;
}
// Return half the area (since we were summing parallelograms)
return Math.abs(area) / 2.0;
}
// Example of finding polygon area
public static void main(String[] args) {
int N = 5;
// Make sure you allocate n+1 elements!
Point2D[] points = new Point2D[N + 1];
// Clockwise order
points[0] = new Point2D.Double(0, 0);
points[1] = new Point2D.Double(0, 2);
points[2] = new Point2D.Double(1, 3);
points[3] = new Point2D.Double(2, 2);
points[4] = new Point2D.Double(2, 0);
points[N] = points[0];
System.out.println(convexPolygonArea(points));
// Counterclockwise
points[0] = new Point2D.Double(0, 0);
points[1] = new Point2D.Double(2, 0);
points[2] = new Point2D.Double(2, 2);
points[3] = new Point2D.Double(1, 3);
points[4] = new Point2D.Double(0, 2);
points[N] = points[0];
System.out.println(convexPolygonArea(points));
}
}