Vector2D.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.geometry.euclidean.twod;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.function.UnaryOperator;
import org.apache.commons.geometry.core.internal.DoubleFunction2N;
import org.apache.commons.geometry.core.internal.SimpleTupleFormat;
import org.apache.commons.geometry.euclidean.EuclideanVectorSum;
import org.apache.commons.geometry.euclidean.MultiDimensionalEuclideanVector;
import org.apache.commons.geometry.euclidean.internal.Vectors;
import org.apache.commons.numbers.core.Precision;
/** This class represents vectors and points in two-dimensional Euclidean space.
* Instances of this class are guaranteed to be immutable.
*/
public class Vector2D extends MultiDimensionalEuclideanVector<Vector2D> {
/** Zero vector (coordinates: 0, 0). */
public static final Vector2D ZERO = new Vector2D(0, 0);
/** A vector with all coordinates set to NaN. */
public static final Vector2D NaN = new Vector2D(Double.NaN, Double.NaN);
/** A vector with all coordinates set to positive infinity. */
public static final Vector2D POSITIVE_INFINITY =
new Vector2D(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
/** A vector with all coordinates set to negative infinity. */
public static final Vector2D NEGATIVE_INFINITY =
new Vector2D(Double.NEGATIVE_INFINITY, Double.NEGATIVE_INFINITY);
/** Comparator that sorts vectors in component-wise ascending order.
* Vectors are only considered equal if their coordinates match exactly.
* Null arguments are evaluated as being greater than non-null arguments.
*/
public static final Comparator<Vector2D> COORDINATE_ASCENDING_ORDER = (a, b) -> {
int cmp = 0;
if (a != null && b != null) {
cmp = Double.compare(a.getX(), b.getX());
if (cmp == 0) {
cmp = Double.compare(a.getY(), b.getY());
}
} else if (a != null) {
cmp = -1;
} else if (b != null) {
cmp = 1;
}
return cmp;
};
/** Abscissa (first coordinate). */
private final double x;
/** Ordinate (second coordinate). */
private final double y;
/** Simple constructor.
* @param x abscissa (first coordinate)
* @param y ordinate (second coordinate)
*/
private Vector2D(final double x, final double y) {
this.x = x;
this.y = y;
}
/** Returns the abscissa (first coordinate value) of the instance.
* @return the abscissa
*/
public double getX() {
return x;
}
/** Returns the ordinate (second coordinate value) of the instance.
* @return the ordinate
*/
public double getY() {
return y;
}
/** Get the coordinates for this instance as a dimension 2 array.
* @return coordinates for this instance
*/
public double[] toArray() {
return new double[]{x, y};
}
/** {@inheritDoc} */
@Override
public int getDimension() {
return 2;
}
/** {@inheritDoc} */
@Override
public boolean isNaN() {
return Double.isNaN(x) || Double.isNaN(y);
}
/** {@inheritDoc} */
@Override
public boolean isInfinite() {
return !isNaN() && (Double.isInfinite(x) || Double.isInfinite(y));
}
/** {@inheritDoc} */
@Override
public boolean isFinite() {
return Double.isFinite(x) && Double.isFinite(y);
}
/** {@inheritDoc} */
@Override
public Vector2D vectorTo(final Vector2D v) {
return v.subtract(this);
}
/** {@inheritDoc} */
@Override
public Unit directionTo(final Vector2D v) {
return vectorTo(v).normalize();
}
/** {@inheritDoc} */
@Override
public Vector2D lerp(final Vector2D p, final double t) {
return Sum.create()
.addScaled(1.0 - t, this)
.addScaled(t, p).get();
}
/** {@inheritDoc} */
@Override
public Vector2D getZero() {
return ZERO;
}
/** {@inheritDoc} */
@Override
public double norm() {
return Vectors.norm(x, y);
}
/** {@inheritDoc} */
@Override
public double normSq() {
return Vectors.normSq(x, y);
}
/** {@inheritDoc} */
@Override
public Vector2D withNorm(final double magnitude) {
final double invNorm = 1.0 / getCheckedNorm();
return new Vector2D(
magnitude * x * invNorm,
magnitude * y * invNorm
);
}
/** {@inheritDoc} */
@Override
public Vector2D add(final Vector2D v) {
return new Vector2D(x + v.x, y + v.y);
}
/** {@inheritDoc} */
@Override
public Vector2D add(final double factor, final Vector2D v) {
return new Vector2D(x + (factor * v.x), y + (factor * v.y));
}
/** {@inheritDoc} */
@Override
public Vector2D subtract(final Vector2D v) {
return new Vector2D(x - v.x, y - v.y);
}
/** {@inheritDoc} */
@Override
public Vector2D subtract(final double factor, final Vector2D v) {
return new Vector2D(x - (factor * v.x), y - (factor * v.y));
}
/** {@inheritDoc} */
@Override
public Vector2D negate() {
return new Vector2D(-x, -y);
}
/** {@inheritDoc} */
@Override
public Unit normalize() {
return Unit.from(x, y);
}
/** {@inheritDoc} */
@Override
public Unit normalizeOrNull() {
return Unit.tryCreateNormalized(x, y, false);
}
/** {@inheritDoc} */
@Override
public Vector2D multiply(final double a) {
return new Vector2D(a * x, a * y);
}
/** {@inheritDoc} */
@Override
public double distance(final Vector2D v) {
return Vectors.norm(x - v.x, y - v.y);
}
/** {@inheritDoc} */
@Override
public double distanceSq(final Vector2D v) {
return Vectors.normSq(x - v.x, y - v.y);
}
/** {@inheritDoc} */
@Override
public double dot(final Vector2D v) {
return Vectors.linearCombination(x, v.x, y, v.y);
}
/** {@inheritDoc}
* <p>This method computes the angular separation between the two
* vectors using the dot product for well separated vectors and the
* cross product for almost aligned vectors. This allows to have a
* good accuracy in all cases, even for vectors very close to each
* other.</p>
*/
@Override
public double angle(final Vector2D v) {
final double normProduct = getCheckedNorm() * v.getCheckedNorm();
final double dot = dot(v);
final double threshold = normProduct * 0.9999;
if ((dot < -threshold) || (dot > threshold)) {
// the vectors are almost aligned, compute using the sine
final double n = Math.abs(Vectors.linearCombination(x, v.y, -y, v.x));
if (dot >= 0) {
return Math.asin(n / normProduct);
}
return Math.PI - Math.asin(n / normProduct);
}
// the vectors are sufficiently separated to use the cosine
return Math.acos(dot / normProduct);
}
/** {@inheritDoc} */
@Override
public Vector2D project(final Vector2D base) {
return getComponent(base, false, Vector2D::new);
}
/** {@inheritDoc} */
@Override
public Vector2D reject(final Vector2D base) {
return getComponent(base, true, Vector2D::new);
}
/** {@inheritDoc}
* The returned vector is computed by rotating the current instance {@code pi/2} radians
* counterclockwise around the origin and normalizing. For example, if this method is
* called on a vector pointing along the positive x-axis, then a unit vector representing
* the positive y-axis is returned.
* @return a unit vector orthogonal to the current instance
* @throws IllegalArgumentException if the norm of the current instance is zero, NaN, or infinite
*/
@Override
public Vector2D.Unit orthogonal() {
return Unit.from(-y, x);
}
/** {@inheritDoc} */
@Override
public Vector2D.Unit orthogonal(final Vector2D dir) {
return dir.getComponent(this, true, Vector2D.Unit::from);
}
/** Compute the signed area of the parallelogram with sides formed by this instance
* and the given vector.
*
* <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 signedArea(final Vector2D v) {
return Vectors.linearCombination(
x, v.y,
-y, v.x);
}
/** Convenience method to apply a function to this vector. This
* can be used to transform the vector inline with other methods.
* @param fn the function to apply
* @return the transformed vector
*/
public Vector2D transform(final UnaryOperator<Vector2D> fn) {
return fn.apply(this);
}
/** {@inheritDoc} */
@Override
public boolean eq(final Vector2D vec, final Precision.DoubleEquivalence precision) {
return precision.eq(x, vec.x) &&
precision.eq(y, vec.y);
}
/**
* Get a hashCode for the 2D coordinates.
* <p>
* All NaN values have the same hash code.</p>
*
* @return a hash code value for this object
*/
@Override
public int hashCode() {
if (isNaN()) {
return 542;
}
return 122 * (76 * Double.hashCode(x) + Double.hashCode(y));
}
/**
* Test for the equality of two vector instances.
* <p>
* If all coordinates of two vectors are exactly the same, and none are
* <code>Double.NaN</code>, the two instances are considered to be equal.
* </p>
* <p>
* <code>NaN</code> coordinates are considered to globally affect the vector
* and be equal to each other - i.e, if either (or all) coordinates of the
* vector are equal to <code>Double.NaN</code>, the vector is equal to
* {@link #NaN}.
* </p>
*
* @param other Object to test for equality to this
* @return true if two Vector2D objects are equal, false if
* object is null, not an instance of Vector2D, or
* not equal to this Vector2D instance
*
*/
@Override
public boolean equals(final Object other) {
if (this == other) {
return true;
}
if (other instanceof Vector2D) {
final Vector2D rhs = (Vector2D) other;
if (rhs.isNaN()) {
return this.isNaN();
}
return Double.compare(x, rhs.x) == 0 &&
Double.compare(y, rhs.y) == 0;
}
return false;
}
/** {@inheritDoc} */
@Override
public String toString() {
return SimpleTupleFormat.getDefault().format(x, y);
}
/** Returns a component of the current instance relative to the given base
* vector. If {@code reject} is true, the vector rejection is returned; otherwise,
* the projection is returned.
* @param base The base vector
* @param reject If true, the rejection of this instance from {@code base} is
* returned. If false, the projection of this instance onto {@code base}
* is returned.
* @param factory factory function used to build the final vector
* @param <T> Vector implementation type
* @return The projection or rejection of this instance relative to {@code base},
* depending on the value of {@code reject}.
* @throws IllegalArgumentException if {@code base} has a zero, NaN, or infinite norm
*/
private <T extends Vector2D> T getComponent(final Vector2D base, final boolean reject,
final DoubleFunction2N<T> factory) {
final double aDotB = dot(base);
// We need to check the norm value here to ensure that it's legal. However, we don't
// want to incur the cost or floating point error of getting the actual norm and then
// multiplying it again to get the square norm. So, we'll just check the squared norm
// directly. This will produce the same error result as checking the actual norm since
// Math.sqrt(0.0) == 0.0, Math.sqrt(Double.NaN) == Double.NaN and
// Math.sqrt(Double.POSITIVE_INFINITY) == Double.POSITIVE_INFINITY.
final double baseMagSq = Vectors.checkedNorm(base.normSq());
final double scale = aDotB / baseMagSq;
final double projX = scale * base.x;
final double projY = scale * base.y;
if (reject) {
return factory.apply(x - projX, y - projY);
}
return factory.apply(projX, projY);
}
/** Returns a vector with the given coordinate values.
* @param x abscissa (first coordinate value)
* @param y abscissa (second coordinate value)
* @return vector instance
*/
public static Vector2D of(final double x, final double y) {
return new Vector2D(x, y);
}
/** Creates a vector from the coordinates in the given 2-element array.
* @param v coordinates array
* @return new vector
* @exception IllegalArgumentException if the array does not have 2 elements
*/
public static Vector2D of(final double[] v) {
if (v.length != 2) {
throw new IllegalArgumentException("Dimension mismatch: " + v.length + " != 2");
}
return new Vector2D(v[0], v[1]);
}
/** Parses the given string and returns a new vector instance. The expected string
* format is the same as that returned by {@link #toString()}.
* @param str the string to parse
* @return vector instance represented by the string
* @throws IllegalArgumentException if the given string has an invalid format
*/
public static Vector2D parse(final String str) {
return SimpleTupleFormat.getDefault().parse(str, Vector2D::new);
}
/** Return a vector containing the maximum component values from all input vectors.
* @param first first vector
* @param more additional vectors
* @return a vector containing the maximum component values from all input vectors
*/
public static Vector2D max(final Vector2D first, final Vector2D... more) {
return computeMax(first, Arrays.asList(more).iterator());
}
/** Return a vector containing the maximum component values from all input vectors.
* @param vecs input vectors
* @return a vector containing the maximum component values from all input vectors
* @throws IllegalArgumentException if the argument does not contain any vectors
*/
public static Vector2D max(final Iterable<Vector2D> vecs) {
final Iterator<Vector2D> it = vecs.iterator();
if (!it.hasNext()) {
throw new IllegalArgumentException("Cannot compute vector max: no vectors given");
}
return computeMax(it.next(), it);
}
/** Internal method for computing a max vector.
* @param first first vector
* @param more iterator with additional vectors
* @return vector containing the maximum component values of all input vectors
*/
private static Vector2D computeMax(final Vector2D first, final Iterator<? extends Vector2D> more) {
double x = first.getX();
double y = first.getY();
Vector2D vec;
while (more.hasNext()) {
vec = more.next();
x = Math.max(x, vec.getX());
y = Math.max(y, vec.getY());
}
return Vector2D.of(x, y);
}
/** Return a vector containing the minimum component values from all input vectors.
* @param first first vector
* @param more more vectors
* @return a vector containing the minimum component values from all input vectors
*/
public static Vector2D min(final Vector2D first, final Vector2D... more) {
return computeMin(first, Arrays.asList(more).iterator());
}
/** Return a vector containing the minimum component values from all input vectors.
* @param vecs input vectors
* @return a vector containing the minimum component values from all input vectors
* @throws IllegalArgumentException if the argument does not contain any vectors
*/
public static Vector2D min(final Iterable<Vector2D> vecs) {
final Iterator<Vector2D> it = vecs.iterator();
if (!it.hasNext()) {
throw new IllegalArgumentException("Cannot compute vector min: no vectors given");
}
return computeMin(it.next(), it);
}
/** Internal method for computing a min vector.
* @param first first vector
* @param more iterator with additional vectors
* @return vector containing the minimum component values of all input vectors
*/
private static Vector2D computeMin(final Vector2D first, final Iterator<? extends Vector2D> more) {
double x = first.getX();
double y = first.getY();
Vector2D vec;
while (more.hasNext()) {
vec = more.next();
x = Math.min(x, vec.getX());
y = Math.min(y, vec.getY());
}
return Vector2D.of(x, y);
}
/** Compute the centroid of the given points. The centroid is the arithmetic mean position of a set
* of points.
* @param first first point
* @param more additional points
* @return the centroid of the given points
*/
public static Vector2D centroid(final Vector2D first, final Vector2D... more) {
return computeCentroid(first, Arrays.asList(more).iterator());
}
/** Compute the centroid of the given points. The centroid is the arithmetic mean position of a set
* of points.
* @param pts the points to compute the centroid of
* @return the centroid of the given points
* @throws IllegalArgumentException if the argument contains no points
*/
public static Vector2D centroid(final Iterable<Vector2D> pts) {
final Iterator<Vector2D> it = pts.iterator();
if (!it.hasNext()) {
throw new IllegalArgumentException("Cannot compute centroid: no points given");
}
return computeCentroid(it.next(), it);
}
/** Internal method for computing the centroid of a set of points.
* @param first first point
* @param more iterator with additional points
* @return the centroid of the point set
*/
private static Vector2D computeCentroid(final Vector2D first, final Iterator<? extends Vector2D> more) {
final Sum sum = Sum.of(first);
int count = 1;
while (more.hasNext()) {
sum.add(more.next());
++count;
}
return sum.get().multiply(1.0 / count);
}
/**
* Represents unit vectors.
* This allows optimizations for certain operations.
*/
public static final class Unit extends Vector2D {
/** Unit vector (coordinates: 1, 0). */
public static final Unit PLUS_X = new Unit(1d, 0d);
/** Negation of unit vector (coordinates: -1, 0). */
public static final Unit MINUS_X = new Unit(-1d, 0d);
/** Unit vector (coordinates: 0, 1). */
public static final Unit PLUS_Y = new Unit(0d, 1d);
/** Negation of unit vector (coordinates: 0, -1). */
public static final Unit MINUS_Y = new Unit(0d, -1d);
/** Maximum coordinate value for computing normalized vectors
* with raw, unscaled values.
*/
private static final double UNSCALED_MAX = 0x1.0p+500;
/** Factor used to scale up coordinate values in order to produce
* normalized coordinates without overflow or underflow.
*/
private static final double SCALE_UP_FACTOR = 0x1.0p+600;
/** Factor used to scale down coordinate values in order to produce
* normalized coordinates without overflow or underflow.
*/
private static final double SCALE_DOWN_FACTOR = 0x1.0p-600;
/** Simple constructor. Callers are responsible for ensuring that the given
* values represent a normalized vector.
* @param x abscissa (first coordinate value)
* @param y abscissa (second coordinate value)
*/
private Unit(final double x, final double y) {
super(x, y);
}
/** {@inheritDoc} */
@Override
public double norm() {
return 1;
}
/** {@inheritDoc} */
@Override
public double normSq() {
return 1;
}
/** {@inheritDoc} */
@Override
public Unit normalize() {
return this;
}
/** {@inheritDoc} */
@Override
public Unit normalizeOrNull() {
return this;
}
/** {@inheritDoc} */
@Override
public Vector2D.Unit orthogonal() {
return new Unit(-getY(), getX());
}
/** {@inheritDoc} */
@Override
public Vector2D withNorm(final double mag) {
return multiply(mag);
}
/** {@inheritDoc} */
@Override
public Unit negate() {
return new Unit(-getX(), -getY());
}
/** Create a normalized vector.
* @param x Vector coordinate.
* @param y Vector coordinate.
* @return a vector whose norm is 1.
* @throws IllegalArgumentException if the norm of the given value is zero, NaN,
* or infinite
*/
public static Unit from(final double x, final double y) {
return tryCreateNormalized(x, y, true);
}
/** Create a normalized vector.
* @param v Vector.
* @return a vector whose norm is 1.
* @throws IllegalArgumentException if the norm of the given value is zero, NaN,
* or infinite
*/
public static Unit from(final Vector2D v) {
return v instanceof Unit ?
(Unit) v :
from(v.getX(), v.getY());
}
/** Attempt to create a normalized vector from the given coordinate values. If {@code throwOnFailure}
* is true, an exception is thrown if a normalized vector cannot be created. Otherwise, null
* is returned.
* @param x x coordinate
* @param y y coordinate
* @param throwOnFailure if true, an exception will be thrown if a normalized vector cannot be created
* @return normalized vector or null if one cannot be created and {@code throwOnFailure}
* is false
* @throws IllegalArgumentException if the computed norm is zero, NaN, or infinite
*/
private static Unit tryCreateNormalized(final double x, final double y, final boolean throwOnFailure) {
// Compute the inverse norm directly. If the result is a non-zero real number,
// then we can go ahead and construct the unit vector immediately. If not,
// we'll do some extra work for edge cases.
final double norm = Vectors.norm(x, y);
final double normInv = 1.0 / norm;
if (Vectors.isRealNonZero(normInv)) {
return new Unit(
x * normInv,
y * normInv);
}
// Direct computation did not work. Try scaled versions of the coordinates
// to handle overflow and underflow.
final double scaledX;
final double scaledY;
final double maxCoord = Math.max(Math.abs(x), Math.abs(y));
if (maxCoord > UNSCALED_MAX) {
scaledX = x * SCALE_DOWN_FACTOR;
scaledY = y * SCALE_DOWN_FACTOR;
} else {
scaledX = x * SCALE_UP_FACTOR;
scaledY = y * SCALE_UP_FACTOR;
}
final double scaledNormInv = 1.0 / Vectors.norm(scaledX, scaledY);
if (Vectors.isRealNonZero(scaledNormInv)) {
return new Unit(
scaledX * scaledNormInv,
scaledY * scaledNormInv);
} else if (throwOnFailure) {
throw Vectors.illegalNorm(norm);
}
return null;
}
}
/** Class used to create high-accuracy sums of vectors. Each vector component is
* summed using an instance of {@link org.apache.commons.numbers.core.Sum}.
*
* <p>This class is mutable and not thread-safe.
* @see org.apache.commons.numbers.core.Sum
*/
public static final class Sum extends EuclideanVectorSum<Vector2D> {
/** X component sum. */
private final org.apache.commons.numbers.core.Sum xsum;
/** Y component sum. */
private final org.apache.commons.numbers.core.Sum ysum;
/** Construct a new instance with the given initial value.
* @param initial initial value
*/
Sum(final Vector2D initial) {
this.xsum = org.apache.commons.numbers.core.Sum.of(initial.x);
this.ysum = org.apache.commons.numbers.core.Sum.of(initial.y);
}
/** {@inheritDoc} */
@Override
public Sum add(final Vector2D vec) {
xsum.add(vec.x);
ysum.add(vec.y);
return this;
}
/** {@inheritDoc} */
@Override
public Sum addScaled(final double scale, final Vector2D vec) {
xsum.addProduct(scale, vec.x);
ysum.addProduct(scale, vec.y);
return this;
}
/** {@inheritDoc} */
@Override
public Vector2D get() {
return Vector2D.of(
xsum.getAsDouble(),
ysum.getAsDouble());
}
/** Create a new instance with an initial value set to the {@link Vector2D#ZERO zero vector}.
* @return new instance set to zero
*/
public static Sum create() {
return new Sum(Vector2D.ZERO);
}
/** Construct a new instance with an initial value set to the argument.
* @param initial initial sum value
* @return new instance
*/
public static Sum of(final Vector2D initial) {
return new Sum(initial);
}
/** Construct a new instance from multiple values.
* @param first first vector
* @param more additional vectors
* @return new instance
*/
public static Sum of(final Vector2D first, final Vector2D... more) {
final Sum s = new Sum(first);
for (final Vector2D v : more) {
s.add(v);
}
return s;
}
}
}