public static Collection reducePoints()

in commons-geometry-hull/src/main/java/org/apache/commons/geometry/hull/euclidean/twod/AklToussaintHeuristic.java [52:96]

• 36 lines of code
• 14 McCabe index (conditional complexity)

    public static Collection<Vector2D> reducePoints(final Collection<Vector2D> points) {

        // find the leftmost point
        int size = 0;
        Vector2D minX = null;
        Vector2D maxX = null;
        Vector2D minY = null;
        Vector2D maxY = null;
        for (final Vector2D p : points) {
            if (minX == null || p.getX() < minX.getX()) {
                minX = p;
            }
            if (maxX == null || p.getX() > maxX.getX()) {
                maxX = p;
            }
            if (minY == null || p.getY() < minY.getY()) {
                minY = p;
            }
            if (maxY == null || p.getY() > maxY.getY()) {
                maxY = p;
            }
            size++;
        }

        if (size < 4) {
            return points;
        }

        final List<Vector2D> quadrilateral = buildQuadrilateral(minY, maxX, maxY, minX);
        // if the quadrilateral is not well formed, e.g. only 2 points, do not attempt to reduce
        if (quadrilateral.size() < 3) {
            return points;
        }

        final List<Vector2D> reducedPoints = new ArrayList<>(quadrilateral);
        for (final Vector2D p : points) {
            // check all points if they are within the quadrilateral
            // in which case they can not be part of the convex hull
            if (!insideQuadrilateral(p, quadrilateral)) {
                reducedPoints.add(p);
            }
        }

        return reducedPoints;
    }