This is an automated email from the ASF dual-hosted git repository.
erans pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
The following commit(s) were added to refs/heads/master by this push:
new eba3a8e GEOMETRY-42: Adding Vector2D.signedArea(Vector2D) method;
removing Vector2D.cross() method since the cross product is not defined in two
dimensions
new 1f334d1 Merge branch 'GEOMETRY-42__matt'
eba3a8e is described below
commit eba3a8e286cf960d93b6b896592eb95120b3d6a2
Author: Matt Juntunen <[email protected]>
AuthorDate: Wed Feb 6 00:25:35 2019 -0500
GEOMETRY-42: Adding Vector2D.signedArea(Vector2D) method; removing
Vector2D.cross() method since the cross product is not defined in two dimensions
---
.../commons/geometry/euclidean/twod/Vector2D.java | 40 ++++++++-----------
.../geometry/euclidean/twod/Vector2DTest.java | 45 +++++++++++++++++-----
.../euclidean/twod/hull/AklToussaintHeuristic.java | 15 +++++++-
3 files changed, 65 insertions(+), 35 deletions(-)
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Vector2D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Vector2D.java
index 08b4f1f..b5c1356 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Vector2D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Vector2D.java
@@ -281,32 +281,24 @@ public class Vector2D extends
MultiDimensionalEuclideanVector<Vector2D> {
return dir.getComponent(this, true, Vector2D::normalize);
}
- /**
- * Compute the cross-product of the instance and the given vector.
- * <p>
- * The cross product can be used to determine the location of a point
- * with regard to the line formed by (p1, p2) and is calculated as:
- * \[
- * P = (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)
- * \]
- * with \(p3 = (x_3, y_3)\) being this instance.
- * <p>
- * If the result is 0, the points are collinear, i.e. lie on a single
straight line L;
- * if it is positive, this point lies to the left, otherwise to the right
of the line
- * formed by (p1, p2).
- *
- * @param p1 first point of the line
- * @param p2 second point of the line
- * @return the cross-product
+ /** Compute the signed area of the parallelogram with sides formed by this
instance
+ * and the given vector.
*
- * @see <a href="http://mathworld.wolfram.com/CrossProduct.html";>Cross
product (Mathworld)</a>
+ * <p>The parallelogram in question can be visualized by taking the
current instance as the
+ * first side and placing {@code v} at the end of it to create the second.
The other sides
+ * are formed by lines parallel to these two vectors. If {@code v} points
to the <em>left</em> of
+ * the current instance (ie, the parallelogram is wound
counter-clockwise), then the
+ * returned area is positive. If {@code v} points to the <em>right</em> of
the current instance,
+ * (ie, the parallelogram is wound clockwise), then the returned area is
negative. If
+ * the vectors are collinear (ie, they lie on the same line), then 0 is
returned. The area of
+ * the triangle formed by the two vectors is exactly half of the returned
value.
+ * @param v vector representing the second side of the constructed
parallelogram
+ * @return the signed area of the parallelogram formed by this instance
and the given vector
*/
- public double cross(final Vector2D p1, final Vector2D p2) {
- final double x1 = p2.x - p1.x;
- final double y1 = y - p1.y;
- final double x2 = x - p1.x;
- final double y2 = p2.y - p1.y;
- return LinearCombination.value(x1, y1, -x2, y2);
+ public double signedArea(final Vector2D v) {
+ return LinearCombination.value(
+ x, v.y,
+ -y, v.x);
}
/** Apply the given transform to this vector, returning the result as a
diff --git
a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/Vector2DTest.java
b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/Vector2DTest.java
index 5a4c268..aac0f5d 100644
---
a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/Vector2DTest.java
+++
b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/Vector2DTest.java
@@ -513,19 +513,46 @@ public class Vector2DTest {
}
@Test
- public void testCrossProduct() {
+ public void testSignedArea() {
// arrange
- Vector2D p1 = Vector2D.of(1, 1);
- Vector2D p2 = Vector2D.of(2, 2);
+ double eps = 1e-10;
- Vector2D p3 = Vector2D.of(3, 3);
- Vector2D p4 = Vector2D.of(1, 2);
- Vector2D p5 = Vector2D.of(2, 1);
+ Vector2D a = Vector2D.PLUS_X;
+ Vector2D b = Vector2D.PLUS_Y;
+ Vector2D c = Vector2D.of(1, 1).withNorm(2.0);
+ Vector2D d = Vector2D.of(-1, 1).withNorm(3.0);
// act/assert
- Assert.assertEquals(0.0, p3.cross(p1, p2), EPS);
- Assert.assertEquals(1.0, p4.cross(p1, p2), EPS);
- Assert.assertEquals(-1.0, p5.cross(p1, p2), EPS);
+ Assert.assertEquals(1.0, a.signedArea(b), eps);
+ Assert.assertEquals(-1.0, b.signedArea(a), eps);
+
+ double xAxisAndCArea = 2 * Math.cos(0.25 * Geometry.PI);
+ Assert.assertEquals(xAxisAndCArea, a.signedArea(c), eps);
+ Assert.assertEquals(-xAxisAndCArea, c.signedArea(a), eps);
+
+ double xAxisAndDArea = 3 * Math.cos(0.25 * Geometry.PI);
+ Assert.assertEquals(xAxisAndDArea, a.signedArea(d), eps);
+ Assert.assertEquals(-xAxisAndDArea, d.signedArea(a), eps);
+
+ Assert.assertEquals(6.0, c.signedArea(d), eps);
+ Assert.assertEquals(-6.0, d.signedArea(c), eps);
+ }
+
+ @Test
+ public void testSignedArea_collinear() {
+ // arrange
+ Vector2D a = Vector2D.PLUS_X;
+ Vector2D b = Vector2D.PLUS_Y;
+ Vector2D c = Vector2D.of(-3, 8);
+
+ // act/assert
+ Assert.assertEquals(0.0, a.signedArea(a), EPS);
+ Assert.assertEquals(0.0, b.signedArea(b), EPS);
+ Assert.assertEquals(0.0, c.signedArea(c), EPS);
+
+ Assert.assertEquals(0.0, a.signedArea(a.multiply(100.0)), EPS);
+ Assert.assertEquals(0.0, b.signedArea(b.negate()), EPS);
+ Assert.assertEquals(0.0, c.signedArea(c.multiply(-0.03)), EPS);
}
@Test
diff --git
a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/AklToussaintHeuristic.java
b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/AklToussaintHeuristic.java
index af3c034..27e42b6 100644
---
a/commons-geometry-hull/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/AklToussaintHeuristic.java
+++
b/commons-geometry-hull/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/AklToussaintHeuristic.java
@@ -129,7 +129,7 @@ public final class AklToussaintHeuristic {
}
// get the location of the point relative to the first two vertices
- final double last = v0.cross(v1, v2);
+ final double last = signedAreaPoints(v1, v2, v0);
final int size = quadrilateralPoints.size();
// loop through the rest of the vertices
for (int i = 1; i < size; i++) {
@@ -143,11 +143,22 @@ public final class AklToussaintHeuristic {
// do side of line test: multiply the last location with this
location
// if they are the same sign then the operation will yield a
positive result
// -x * -y = +xy, x * y = +xy, -x * y = -xy, x * -y = -xy
- if (last * v0.cross(v1, v2) < 0) {
+ if (last * signedAreaPoints(v1, v2, v0) < 0) {
return false;
}
}
return true;
}
+ /** Compute the signed area of the parallelogram formed by vectors between
the given points. The first
+ * vector points from {@code p0} to {@code p1} and the second from {@code
p0} to {@code p3}.
+ * @param p0 first point
+ * @param p1 second point
+ * @param p2 third point
+ * @return signed area of parallelogram formed by vectors between the
given points
+ */
+ private static double signedAreaPoints(final Vector2D p0, final Vector2D
p1, final Vector2D p2) {
+ return p0.vectorTo(p1).signedArea(p0.vectorTo(p2));
+ }
+
}
