private Collection findHullVertices()

in commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/hull/ConvexHull2D.java [351:391]

28 lines of code
6 McCabe index (conditional complexity)


        private Collection<Vector2D> findHullVertices(final Collection<Vector2D> points) {

            final List<Vector2D> pointsSortedByXAxis = new ArrayList<>(points);

            // sort the points in increasing order on the x-axis
            pointsSortedByXAxis.sort((o1, o2) -> {
                // need to take the tolerance value into account, otherwise collinear points
                // will not be handled correctly when building the upper/lower hull
                final int cmp = precision.compare(o1.getX(), o2.getX());
                if (cmp == 0) {
                    return precision.compare(o1.getY(), o2.getY());
                } else {
                    return cmp;
                }
            });

            // build lower hull
            final List<Vector2D> lowerHull = new ArrayList<>();
            for (final Vector2D p : pointsSortedByXAxis) {
                updateHull(p, lowerHull);
            }

            // build upper hull
            final List<Vector2D> upperHull = new ArrayList<>();
            for (int idx = pointsSortedByXAxis.size() - 1; idx >= 0; idx--) {
                final Vector2D p = pointsSortedByXAxis.get(idx);
                updateHull(p, upperHull);
            }

            // concatenate the lower and upper hulls
            // the first point of each list is omitted as it is repeated at the end of the other list
            final List<Vector2D> hullVertices = new ArrayList<>(lowerHull.size() + upperHull.size() - 2);
            for (int idx = 1; idx < lowerHull.size(); idx++) {
                hullVertices.add(lowerHull.get(idx));
            }
            for (int idx = 1; idx < upperHull.size(); idx++) {
                hullVertices.add(upperHull.get(idx));
            }

            return hullVertices;
        }