This is an automated email from the ASF dual-hosted git repository.
mattjuntunen pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
commit ede440fd38b666d07628f5d140bf6ec0ea917fbf
Author: Andreas Goß <andreas.goss1...@gmail.com>
AuthorDate: Thu Jul 20 22:06:53 2023 +0200
GEOMETRY-144
Codereview Part1
---
.../geometry/euclidean/twod/hull/ConvexHull2D.java | 41 +++++++++++++---------
1 file changed, 24 insertions(+), 17 deletions(-)
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2D.java
index 099abd29..565f68fb 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2D.java
@@ -126,16 +126,16 @@ public final class ConvexHull2D implements
ConvexHull<Vector2D> {
*/
public static final class Builder {
- /** Corner of triangle with minimal x coordinate. */
+ /** Corner of quadrilateral with minimal x coordinate. */
private Vector2D minX;
- /** Corner of triangle with maximal x coordinate. */
+ /** Corner of quadrilateral with maximal x coordinate. */
private Vector2D maxX;
- /** Corner of triangle with minimal y coordinate. */
+ /** Corner of quadrilateral with minimal y coordinate. */
private Vector2D minY;
- /** Corner of triangle with maximal y coordinate. */
+ /** Corner of quadrilateral with maximal y coordinate. */
private Vector2D maxY;
/** Collection of all remaining candidates for a convex hull. */
@@ -149,7 +149,7 @@ public final class ConvexHull2D implements
ConvexHull<Vector2D> {
*/
private final boolean includeCollinearPoints;
- /**Return a {@link Builder} instance configured with the given
precision
+ /** Return a {@link Builder} instance configured with the given
precision
* context. The precision context is used when comparing points.
*
* @param builderPrecision precision context to use when
building a convex
@@ -172,10 +172,10 @@ public final class ConvexHull2D implements
ConvexHull<Vector2D> {
*/
public Builder append(Vector2D point) {
- //Checks if the given point supersedes one of the corners.
+ // Checks if the given point supersedes one of the corners.
checkCorners(point);
- //Only proceed if the quadrilateral is complete.
+ // Only proceed if the quadrilateral is complete.
if (candidates.size() < 4) {
return this;
}
@@ -252,19 +252,24 @@ public final class ConvexHull2D implements
ConvexHull<Vector2D> {
* @param point a given point.
*/
private void checkCorners(Vector2D point) {
- if (minX == null || point.getX() < minX.getX()) {
+ if(minX == null) {
+ minX = minY = maxX = maxY = point;
+ candidates.add(point);
+ return;
+ }
+ if (point.getX() < minX.getX()) {
minX = point;
candidates.add(point);
}
- if (maxX == null || point.getX() > maxX.getX()) {
+ if (point.getX() > maxX.getX()) {
maxX = point;
candidates.add(point);
}
- if (minY == null || point.getY() < minY.getY()) {
+ if (point.getY() < minY.getY()) {
minY = point;
candidates.add(point);
}
- if (maxY == null || point.getY() > maxY.getY()) {
+ if (point.getY() > maxY.getY()) {
maxY = point;
candidates.add(point);
}
@@ -275,11 +280,10 @@ public final class ConvexHull2D implements
ConvexHull<Vector2D> {
* @param quadrilateralPoints the convex quadrilateral, represented by
4 points
* @return {@code true} if the point is inside the quadrilateral,
{@code false} otherwise
*/
- private boolean insideQuadrilateral(final Vector2D point,
- final List<? extends
Vector2D> quadrilateralPoints) {
+ private boolean insideQuadrilateral(final Vector2D point, final List<?
extends Vector2D> quadrilateralPoints) {
- Vector2D v1 = quadrilateralPoints.get(0);
- Vector2D v2 = quadrilateralPoints.get(1);
+ Vector2D v1 = quadrilateralPoints.get(quadrilateralPoints.size() -
1);
+ Vector2D v2 = quadrilateralPoints.get(0);
if (point.equals(v1) || point.equals(v2)) {
return true;
@@ -298,7 +302,7 @@ public final class ConvexHull2D implements
ConvexHull<Vector2D> {
// loop through the rest of the vertices
for (int i = 1; i < size; i++) {
v1 = v2;
- v2 = quadrilateralPoints.get((i + 1) == size ? 0 : i + 1);
+ v2 = quadrilateralPoints.get(i);
if (point.equals(v2)) {
return true;
@@ -307,7 +311,10 @@ public final class ConvexHull2D implements
ConvexHull<Vector2D> {
// 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 * signedAreaPoints(v1, v2, point) < 0) {
+ double signedArea = signedAreaPoints(v1, v2, point);
+ // three collinear points have an area of zero. If we include
collinear points
+ // we have to consider this case.
+ if (last * signedArea < 0 || precision.eq(signedArea, 0.0) &&
includeCollinearPoints) {
return false;
}
}
