You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2014/02/02 18:56:14 UTC
svn commit: r1563687 - in
/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull:
AklToussaintHeuristic.java ConvexHull2D.java GrahamScan.java
MonotoneChain.java
Author: tn
Date: Sun Feb 2 17:56:13 2014
New Revision: 1563687
URL: http://svn.apache.org/r1563687
Log:
[MATH-749] Use new method Vector2D.crossProduct, fix typos, return Segment instead of Line in ConvexHull2D.
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.java?rev=1563687&r1=1563686&r2=1563687&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.java Sun Feb 2 17:56:13 2014
@@ -130,7 +130,7 @@ public final class AklToussaintHeuristic
}
// get the location of the point relative to the first two vertices
- final double last = getLocation(point, p1, p2);
+ final double last = point.crossProduct(p1, p2);
final int size = quadrilateralPoints.size();
// loop through the rest of the vertices
for (int i = 1; i < size; i++) {
@@ -141,33 +141,14 @@ public final class AklToussaintHeuristic
return true;
}
- // do side of line test
- // multiply the last location with this location
+ // 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 * getLocation(point, p1, p2) < 0) {
+ if (last * point.crossProduct(p1, p2) < 0) {
return false;
}
}
return true;
}
- /**
- * Get the location of a point with regard to the given line.
- * <p>
- * Note: this method does the same as {@link Line#getOffset(Vector)} but is
- * faster, thus preferred for this heuristic.
- *
- * @param point the point to check
- * @param linePoint1 the first point of the line
- * @param linePoint2 the second point of the line
- * @return the location of the point with regard to the line
- */
- private static double getLocation(final Vector2D point,
- final Vector2D linePoint1,
- final Vector2D linePoint2) {
- return (linePoint2.getX() - linePoint1.getX()) * (point.getY() - linePoint1.getY()) -
- (point.getX() - linePoint1.getX()) * (linePoint2.getY() - linePoint1.getY());
- }
-
}
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java?rev=1563687&r1=1563686&r2=1563687&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java Sun Feb 2 17:56:13 2014
@@ -23,6 +23,7 @@ import java.util.Iterator;
import org.apache.commons.math3.exception.InsufficientDataException;
import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
import org.apache.commons.math3.geometry.euclidean.twod.Line;
+import org.apache.commons.math3.geometry.euclidean.twod.Segment;
import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
import org.apache.commons.math3.geometry.hull.ConvexHull;
import org.apache.commons.math3.geometry.partitioning.Region;
@@ -43,11 +44,11 @@ public class ConvexHull2D implements Con
private final Vector2D[] vertices;
/** Line segments of the hull. */
- private final Line[] lineSegments;
+ private final Segment[] lineSegments;
/**
* Simple constructor.
- * @param vertices the vertices of the convex hull
+ * @param vertices the vertices of the convex hull, must be ordered in CCW winding
* @param tolerance tolerance below which points are considered identical
*/
ConvexHull2D(final Collection<Vector2D> vertices, final double tolerance) {
@@ -56,13 +57,15 @@ public class ConvexHull2D implements Con
// construct the line segments - handle special cases of 1 or 2 points
final int size = vertices.size();
if (size <= 1) {
- this.lineSegments = new Line[0];
+ this.lineSegments = new Segment[0];
} else if (size == 2) {
- this.lineSegments = new Line[1];
+ this.lineSegments = new Segment[1];
final Iterator<Vector2D> it = vertices.iterator();
- this.lineSegments[0] = new Line(it.next(), it.next(), tolerance);
+ final Vector2D p1 = it.next();
+ final Vector2D p2 = it.next();
+ this.lineSegments[0] = new Segment(p1, p2, new Line(p1, p2, tolerance));
} else {
- this.lineSegments = new Line[size];
+ this.lineSegments = new Segment[size];
Vector2D firstPoint = null;
Vector2D lastPoint = null;
int index = 0;
@@ -71,11 +74,13 @@ public class ConvexHull2D implements Con
firstPoint = point;
lastPoint = point;
} else {
- this.lineSegments[index++] = new Line(lastPoint, point, tolerance);
+ this.lineSegments[index++] =
+ new Segment(lastPoint, point, new Line(lastPoint, point, tolerance));
lastPoint = point;
}
}
- this.lineSegments[index] = new Line(lastPoint, firstPoint, tolerance);
+ this.lineSegments[index] =
+ new Segment(lastPoint, firstPoint, new Line(lastPoint, firstPoint, tolerance));
}
}
@@ -85,10 +90,10 @@ public class ConvexHull2D implements Con
}
/**
- * Get the line segments of the convex hull, ordered in CCW direction.
+ * Get the line segments of the convex hull, ordered in CCW winding.
* @return the line segments of the convex hull
*/
- public Line[] getLineSegments() {
+ public Segment[] getLineSegments() {
return lineSegments.clone();
}
@@ -98,6 +103,10 @@ public class ConvexHull2D implements Con
throw new InsufficientDataException();
}
final RegionFactory<Euclidean2D> factory = new RegionFactory<Euclidean2D>();
- return factory.buildConvex(lineSegments);
+ final Line[] lineArray = new Line[lineSegments.length];
+ for (int i = 0; i < lineSegments.length; i++) {
+ lineArray[i] = lineSegments[i].getLine();
+ }
+ return factory.buildConvex(lineArray);
}
}
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan.java?rev=1563687&r1=1563686&r2=1563687&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan.java Sun Feb 2 17:56:13 2014
@@ -33,7 +33,7 @@ import org.apache.commons.math3.util.Mat
* Implements Graham's scan method to generate the convex hull of a finite set of
* points in the two-dimensional euclidean space.
* <p>
- * The implementation is not sensitive to colinear points. The runtime complexity
+ * The implementation is not sensitive to collinear points. The runtime complexity
* is O(n log n), with n being the number of input points.
*
* @see <a href="http://en.wikipedia.org/wiki/Graham_scan">Graham's scan algorithm (Wikipedia)</a>
@@ -127,7 +127,7 @@ public class GrahamScan implements Conve
hullVertices.add(currentPoint);
currentPoint = null;
} else {
- // otherwise, the point is either colinear or will create
+ // otherwise, the point is either collinear or will create
// a concave section, thus we need to remove the last point.
hullVertices.remove(size - 1);
}
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java?rev=1563687&r1=1563686&r2=1563687&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java Sun Feb 2 17:56:13 2014
@@ -31,7 +31,7 @@ import org.apache.commons.math3.util.Mat
* Implements Andrew's monotone chain method to generate the convex hull of a finite set of
* points in the two-dimensional euclidean space.
* <p>
- * The implementation is not sensitive to colinear points. The runtime complexity
+ * The implementation is not sensitive to collinear points. The runtime complexity
* is O(n log n), with n being the number of input points. If the point set is already
* sorted (by x-coordinate), the runtime complexity is O(n).
*
@@ -97,7 +97,7 @@ public class MonotoneChain implements Co
final Vector2D p1 = lowerHull.get(size - 2);
final Vector2D p2 = lowerHull.get(size - 1);
- if (getLocation(p, p1, p2) <= 0) {
+ if (p.crossProduct(p1, p2) <= 0) {
lowerHull.remove(size - 1);
} else {
break;
@@ -115,7 +115,7 @@ public class MonotoneChain implements Co
final Vector2D p1 = upperHull.get(size - 2);
final Vector2D p2 = upperHull.get(size - 1);
- if (getLocation(p, p1, p2) <= 0) {
+ if (p.crossProduct(p1, p2) <= 0) {
upperHull.remove(size - 1);
} else {
break;
@@ -137,22 +137,4 @@ public class MonotoneChain implements Co
return new ConvexHull2D(hullVertices, tolerance);
}
- /**
- * Get the location of a point with regard to the given line.
- * <p>
- * Note: this method does the same as {@link Line#getOffset(Vector)} but is
- * faster, thus preferred for this heuristic.
- *
- * @param point the point to check
- * @param linePoint1 the first point of the line
- * @param linePoint2 the second point of the line
- * @return the location of the point with regard to the line
- */
- private double getLocation(final Vector2D point,
- final Vector2D linePoint1,
- final Vector2D linePoint2) {
- return (linePoint2.getX() - linePoint1.getX()) * (point.getY() - linePoint1.getY()) -
- (point.getX() - linePoint1.getX()) * (linePoint2.getY() - linePoint1.getY());
- }
-
}