public Collection findHullVertices()

in commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/MonotoneChain.java [63:109]
32 lines of code
8 McCabe index (conditional complexity)

    public 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) -> {
            final Precision.DoubleEquivalence precision = getPrecision();
            // 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 last point of each list is omitted as it is repeated at the beginning of the other list
        final List<Vector2D> hullVertices = new ArrayList<>(lowerHull.size() + upperHull.size() - 2);
        for (int idx = 0; idx < lowerHull.size() - 1; idx++) {
            hullVertices.add(lowerHull.get(idx));
        }
        for (int idx = 0; idx < upperHull.size() - 1; idx++) {
            hullVertices.add(upperHull.get(idx));
        }

        // special case: if the lower and upper hull may contain only 1 point if all are identical
        if (hullVertices.isEmpty() && !lowerHull.isEmpty()) {
            hullVertices.add(lowerHull.get(0));
        }

        return hullVertices;
    }