001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.math3.geometry.euclidean.twod.hull; 018 019import java.io.Serializable; 020 021import org.apache.commons.math3.exception.InsufficientDataException; 022import org.apache.commons.math3.exception.MathIllegalArgumentException; 023import org.apache.commons.math3.exception.util.LocalizedFormats; 024import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D; 025import org.apache.commons.math3.geometry.euclidean.twod.Line; 026import org.apache.commons.math3.geometry.euclidean.twod.Segment; 027import org.apache.commons.math3.geometry.euclidean.twod.Vector2D; 028import org.apache.commons.math3.geometry.hull.ConvexHull; 029import org.apache.commons.math3.geometry.partitioning.Region; 030import org.apache.commons.math3.geometry.partitioning.RegionFactory; 031import org.apache.commons.math3.util.MathArrays; 032import org.apache.commons.math3.util.Precision; 033 034/** 035 * This class represents a convex hull in an two-dimensional euclidean space. 036 * 037 * @since 3.3 038 */ 039public class ConvexHull2D implements ConvexHull<Euclidean2D, Vector2D>, Serializable { 040 041 /** Serializable UID. */ 042 private static final long serialVersionUID = 20140129L; 043 044 /** Vertices of the hull. */ 045 private final Vector2D[] vertices; 046 047 /** Tolerance threshold used during creation of the hull vertices. */ 048 private final double tolerance; 049 050 /** 051 * Line segments of the hull. 052 * The array is not serialized and will be created from the vertices on first access. 053 */ 054 private transient Segment[] lineSegments; 055 056 /** 057 * Simple constructor. 058 * @param vertices the vertices of the convex hull, must be ordered 059 * @param tolerance tolerance below which points are considered identical 060 * @throws MathIllegalArgumentException if the vertices do not form a convex hull 061 */ 062 public ConvexHull2D(final Vector2D[] vertices, final double tolerance) 063 throws MathIllegalArgumentException { 064 065 // assign tolerance as it will be used by the isConvex method 066 this.tolerance = tolerance; 067 068 if (!isConvex(vertices)) { 069 throw new MathIllegalArgumentException(LocalizedFormats.NOT_CONVEX); 070 } 071 072 this.vertices = vertices.clone(); 073 } 074 075 /** 076 * Checks whether the given hull vertices form a convex hull. 077 * @param hullVertices the hull vertices 078 * @return {@code true} if the vertices form a convex hull, {@code false} otherwise 079 */ 080 private boolean isConvex(final Vector2D[] hullVertices) { 081 if (hullVertices.length < 3) { 082 return true; 083 } 084 085 int sign = 0; 086 for (int i = 0; i < hullVertices.length; i++) { 087 final Vector2D p1 = hullVertices[i == 0 ? hullVertices.length - 1 : i - 1]; 088 final Vector2D p2 = hullVertices[i]; 089 final Vector2D p3 = hullVertices[i == hullVertices.length - 1 ? 0 : i + 1]; 090 091 final Vector2D d1 = p2.subtract(p1); 092 final Vector2D d2 = p3.subtract(p2); 093 094 final double crossProduct = MathArrays.linearCombination(d1.getX(), d2.getY(), -d1.getY(), d2.getX()); 095 final int cmp = Precision.compareTo(crossProduct, 0.0, tolerance); 096 // in case of collinear points the cross product will be zero 097 if (cmp != 0.0) { 098 if (sign != 0.0 && cmp != sign) { 099 return false; 100 } 101 sign = cmp; 102 } 103 } 104 105 return true; 106 } 107 108 /** {@inheritDoc} */ 109 public Vector2D[] getVertices() { 110 return vertices.clone(); 111 } 112 113 /** 114 * Get the line segments of the convex hull, ordered. 115 * @return the line segments of the convex hull 116 */ 117 public Segment[] getLineSegments() { 118 return retrieveLineSegments().clone(); 119 } 120 121 /** 122 * Retrieve the line segments from the cached array or create them if needed. 123 * 124 * @return the array of line segments 125 */ 126 private Segment[] retrieveLineSegments() { 127 if (lineSegments == null) { 128 // construct the line segments - handle special cases of 1 or 2 points 129 final int size = vertices.length; 130 if (size <= 1) { 131 this.lineSegments = new Segment[0]; 132 } else if (size == 2) { 133 this.lineSegments = new Segment[1]; 134 final Vector2D p1 = vertices[0]; 135 final Vector2D p2 = vertices[1]; 136 this.lineSegments[0] = new Segment(p1, p2, new Line(p1, p2, tolerance)); 137 } else { 138 this.lineSegments = new Segment[size]; 139 Vector2D firstPoint = null; 140 Vector2D lastPoint = null; 141 int index = 0; 142 for (Vector2D point : vertices) { 143 if (lastPoint == null) { 144 firstPoint = point; 145 lastPoint = point; 146 } else { 147 this.lineSegments[index++] = 148 new Segment(lastPoint, point, new Line(lastPoint, point, tolerance)); 149 lastPoint = point; 150 } 151 } 152 this.lineSegments[index] = 153 new Segment(lastPoint, firstPoint, new Line(lastPoint, firstPoint, tolerance)); 154 } 155 } 156 return lineSegments; 157 } 158 159 /** {@inheritDoc} */ 160 public Region<Euclidean2D> createRegion() throws InsufficientDataException { 161 if (vertices.length < 3) { 162 throw new InsufficientDataException(); 163 } 164 final RegionFactory<Euclidean2D> factory = new RegionFactory<Euclidean2D>(); 165 final Segment[] segments = retrieveLineSegments(); 166 final Line[] lineArray = new Line[segments.length]; 167 for (int i = 0; i < segments.length; i++) { 168 lineArray[i] = segments[i].getLine(); 169 } 170 return factory.buildConvex(lineArray); 171 } 172}