/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.math3.geometry.euclidean.twod.hull;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

import org.apache.commons.math3.exception.NullArgumentException;
import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
import org.apache.commons.math3.geometry.partitioning.Region;
import org.apache.commons.math3.geometry.partitioning.Region.Location;
import org.apache.commons.math3.random.MersenneTwister;
import org.apache.commons.math3.random.RandomGenerator;
import org.apache.commons.math3.util.FastMath;
import org.apache.commons.math3.util.MathArrays;
import org.apache.commons.math3.util.Precision;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

/**
 * Abstract base test class for 2D convex hull generators.
 *
 */
public abstract class ConvexHullGenerator2DAbstractTest {

    protected ConvexHullGenerator2D generator;
    protected RandomGenerator random;

    protected abstract ConvexHullGenerator2D createConvexHullGenerator(boolean includeCollinearPoints);

    protected Collection<Vector2D> reducePoints(Collection<Vector2D> points) {
        // do nothing by default, may be overridden by other tests
        return points;
    }

    @Before
    public void setUp() {
        // by default, do not include collinear points
        generator = createConvexHullGenerator(false);
        random = new MersenneTwister(10);
    }

    // ------------------------------------------------------------------------------

    @Test(expected = NullArgumentException.class)
    public void testNullArgument() {
        generator.generate(null);
    }

    @Test
    public void testEmpty() {
        ConvexHull2D hull = generator.generate(Collections.<Vector2D>emptyList());
        Assert.assertTrue(hull.getVertices().length == 0);
        Assert.assertTrue(hull.getLineSegments().length == 0);
    }

    @Test
    public void testOnePoint() {
        List<Vector2D> points = createRandomPoints(1);
        ConvexHull2D hull = generator.generate(points);
        Assert.assertTrue(hull.getVertices().length == 1);
        Assert.assertTrue(hull.getLineSegments().length == 0);
    }

    @Test
    public void testTwoPoints() {
        List<Vector2D> points = createRandomPoints(2);
        ConvexHull2D hull = generator.generate(points);
        Assert.assertTrue(hull.getVertices().length == 2);
        Assert.assertTrue(hull.getLineSegments().length == 1);
    }

    @Test
    public void testAllIdentical() {
        final Collection<Vector2D> points = new ArrayList<Vector2D>();
        points.add(new Vector2D(1, 1));
        points.add(new Vector2D(1, 1));
        points.add(new Vector2D(1, 1));
        points.add(new Vector2D(1, 1));

        final ConvexHull2D hull = generator.generate(points);
        Assert.assertTrue(hull.getVertices().length == 1);
    }

    @Test
    public void testConvexHull() {
        // execute 100 random variations
        for (int i = 0; i < 100; i++) {
            // randomize the size from 4 to 100
            int size = (int) FastMath.floor(random.nextDouble() * 96.0 + 4.0);

            List<Vector2D> points = createRandomPoints(size);
            ConvexHull2D hull = generator.generate(reducePoints(points));
            checkConvexHull(points, hull);
        }
    }

    @Test
    public void testCollinearPoints() {
        final Collection<Vector2D> points = new ArrayList<Vector2D>();
        points.add(new Vector2D(1, 1));
        points.add(new Vector2D(2, 2));
        points.add(new Vector2D(2, 4));
        points.add(new Vector2D(4, 1));
        points.add(new Vector2D(10, 1));

        final ConvexHull2D hull = generator.generate(points);
        checkConvexHull(points, hull);
    }

    @Test
    public void testCollinearPointsReverse() {
        final Collection<Vector2D> points = new ArrayList<Vector2D>();
        points.add(new Vector2D(1, 1));
        points.add(new Vector2D(2, 2));
        points.add(new Vector2D(2, 4));
        points.add(new Vector2D(10, 1));
        points.add(new Vector2D(4, 1));

        final ConvexHull2D hull = generator.generate(points);
        checkConvexHull(points, hull);
    }

    @Test
    public void testCollinearPointsIncluded() {
        final Collection<Vector2D> points = new ArrayList<Vector2D>();
        points.add(new Vector2D(1, 1));
        points.add(new Vector2D(2, 2));
        points.add(new Vector2D(2, 4));
        points.add(new Vector2D(4, 1));
        points.add(new Vector2D(10, 1));

        final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
        checkConvexHull(points, hull, true);
    }

    @Test
    public void testCollinearPointsIncludedReverse() {
        final Collection<Vector2D> points = new ArrayList<Vector2D>();
        points.add(new Vector2D(1, 1));
        points.add(new Vector2D(2, 2));
        points.add(new Vector2D(2, 4));
        points.add(new Vector2D(10, 1));
        points.add(new Vector2D(4, 1));

        final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
        checkConvexHull(points, hull, true);
    }

    @Test
    public void testIdenticalPoints() {
        final Collection<Vector2D> points = new ArrayList<Vector2D>();
        points.add(new Vector2D(1, 1));
        points.add(new Vector2D(2, 2));
        points.add(new Vector2D(2, 4));
        points.add(new Vector2D(4, 1));
        points.add(new Vector2D(1, 1));

        final ConvexHull2D hull = generator.generate(points);
        checkConvexHull(points, hull);
    }

    @Test
    public void testIdenticalPoints2() {
        final Collection<Vector2D> points = new ArrayList<Vector2D>();
        points.add(new Vector2D(1, 1));
        points.add(new Vector2D(2, 2));
        points.add(new Vector2D(2, 4));
        points.add(new Vector2D(4, 1));
        points.add(new Vector2D(1, 1));

        final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
        checkConvexHull(points, hull, true);
    }

    @Test
    public void testClosePoints() {
        final Collection<Vector2D> points = new ArrayList<Vector2D>();
        points.add(new Vector2D(1, 1));
        points.add(new Vector2D(2, 2));
        points.add(new Vector2D(2, 4));
        points.add(new Vector2D(4, 1));
        points.add(new Vector2D(1.00001, 1));

        final ConvexHull2D hull = generator.generate(points);
        checkConvexHull(points, hull);
    }

    @Test
    public void testCollinearPointOnExistingBoundary() {
        // MATH-1135: check that collinear points on the hull are handled correctly
        //            when only a minimal hull shall be constructed
        final Collection<Vector2D> points = new ArrayList<Vector2D>();
        points.add(new Vector2D(7.3152, 34.7472));
        points.add(new Vector2D(6.400799999999997, 34.747199999999985));
        points.add(new Vector2D(5.486399999999997, 34.7472));
        points.add(new Vector2D(4.876799999999999, 34.7472));
        points.add(new Vector2D(4.876799999999999, 34.1376));
        points.add(new Vector2D(4.876799999999999, 30.48));
        points.add(new Vector2D(6.0959999999999965, 30.48));
        points.add(new Vector2D(6.0959999999999965, 34.1376));
        points.add(new Vector2D(7.315199999999996, 34.1376));
        points.add(new Vector2D(7.3152, 30.48));

        final ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
        checkConvexHull(points, hull);
    }

    @Test
    public void testCollinearPointsInAnyOrder() {
        // MATH-1148: collinear points on the hull might be in any order
        //            make sure that they are processed in the proper order
        //            for each algorithm.

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

        // first case: 3 points are collinear
        points.add(new Vector2D(16.078200000000184, -36.52519999989808));
        points.add(new Vector2D(19.164300000000186, -36.52519999989808));
        points.add(new Vector2D(19.1643, -25.28136477910407));
        points.add(new Vector2D(19.1643, -17.678400000004157));

        ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
        checkConvexHull(points, hull);

        hull = createConvexHullGenerator(true).generate(points);
        checkConvexHull(points, hull, true);

        points.clear();

        // second case: multiple points are collinear
        points.add(new Vector2D(0, -29.959696875));
        points.add(new Vector2D(0, -31.621809375));
        points.add(new Vector2D(0, -28.435696875));
        points.add(new Vector2D(0, -33.145809375));
        points.add(new Vector2D(3.048, -33.145809375));
        points.add(new Vector2D(3.048, -31.621809375));
        points.add(new Vector2D(3.048, -29.959696875));
        points.add(new Vector2D(4.572, -33.145809375));
        points.add(new Vector2D(4.572, -28.435696875));

        hull = createConvexHullGenerator(false).generate(points);
        checkConvexHull(points, hull);

        hull = createConvexHullGenerator(true).generate(points);
        checkConvexHull(points, hull, true);
    }

    @Test
    public void testIssue1123() {

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

        int[][] data = new int[][] { { -11, -1 }, { -11, 0 }, { -11, 1 },
                { -10, -3 }, { -10, -2 }, { -10, -1 }, { -10, 0 }, { -10, 1 },
                { -10, 2 }, { -10, 3 }, { -9, -4 }, { -9, -3 }, { -9, -2 },
                { -9, -1 }, { -9, 0 }, { -9, 1 }, { -9, 2 }, { -9, 3 },
                { -9, 4 }, { -8, -5 }, { -8, -4 }, { -8, -3 }, { -8, -2 },
                { -8, -1 }, { -8, 0 }, { -8, 1 }, { -8, 2 }, { -8, 3 },
                { -8, 4 }, { -8, 5 }, { -7, -6 }, { -7, -5 }, { -7, -4 },
                { -7, -3 }, { -7, -2 }, { -7, -1 }, { -7, 0 }, { -7, 1 },
                { -7, 2 }, { -7, 3 }, { -7, 4 }, { -7, 5 }, { -7, 6 },
                { -6, -7 }, { -6, -6 }, { -6, -5 }, { -6, -4 }, { -6, -3 },
                { -6, -2 }, { -6, -1 }, { -6, 0 }, { -6, 1 }, { -6, 2 },
                { -6, 3 }, { -6, 4 }, { -6, 5 }, { -6, 6 }, { -6, 7 },
                { -5, -7 }, { -5, -6 }, { -5, -5 }, { -5, -4 }, { -5, -3 },
                { -5, -2 }, { -5, 4 }, { -5, 5 }, { -5, 6 }, { -5, 7 },
                { -4, -7 }, { -4, -6 }, { -4, -5 }, { -4, -4 }, { -4, -3 },
                { -4, -2 }, { -4, 4 }, { -4, 5 }, { -4, 6 }, { -4, 7 },
                { -3, -8 }, { -3, -7 }, { -3, -6 }, { -3, -5 }, { -3, -4 },
                { -3, -3 }, { -3, -2 }, { -3, 4 }, { -3, 5 }, { -3, 6 },
                { -3, 7 }, { -3, 8 }, { -2, -8 }, { -2, -7 }, { -2, -6 },
                { -2, -5 }, { -2, -4 }, { -2, -3 }, { -2, -2 }, { -2, 4 },
                { -2, 5 }, { -2, 6 }, { -2, 7 }, { -2, 8 }, { -1, -8 },
                { -1, -7 }, { -1, -6 }, { -1, -5 }, { -1, -4 }, { -1, -3 },
                { -1, -2 }, { -1, 4 }, { -1, 5 }, { -1, 6 }, { -1, 7 },
                { -1, 8 }, { 0, -8 }, { 0, -7 }, { 0, -6 }, { 0, -5 },
                { 0, -4 }, { 0, -3 }, { 0, -2 }, { 0, 4 }, { 0, 5 }, { 0, 6 },
                { 0, 7 }, { 0, 8 }, { 1, -8 }, { 1, -7 }, { 1, -6 }, { 1, -5 },
                { 1, -4 }, { 1, -3 }, { 1, -2 }, { 1, -1 }, { 1, 0 }, { 1, 1 },
                { 1, 2 }, { 1, 3 }, { 1, 4 }, { 1, 5 }, { 1, 6 }, { 1, 7 },
                { 1, 8 }, { 2, -8 }, { 2, -7 }, { 2, -6 }, { 2, -5 },
                { 2, -4 }, { 2, -3 }, { 2, -2 }, { 2, -1 }, { 2, 0 }, { 2, 1 },
                { 2, 2 }, { 2, 3 }, { 2, 4 }, { 2, 5 }, { 2, 6 }, { 2, 7 },
                { 2, 8 }, { 3, -8 }, { 3, -7 }, { 3, -6 }, { 3, -5 },
                { 3, -4 }, { 3, -3 }, { 3, -2 }, { 3, -1 }, { 3, 0 }, { 3, 1 },
                { 3, 2 }, { 3, 3 }, { 3, 4 }, { 3, 5 }, { 3, 6 }, { 3, 7 },
                { 3, 8 }, { 4, -7 }, { 4, -6 }, { 4, -5 }, { 4, -4 },
                { 4, -3 }, { 4, -2 }, { 4, -1 }, { 4, 0 }, { 4, 1 }, { 4, 2 },
                { 4, 3 }, { 4, 4 }, { 4, 5 }, { 4, 6 }, { 4, 7 }, { 5, -7 },
                { 5, -6 }, { 5, -5 }, { 5, -4 }, { 5, -3 }, { 5, -2 },
                { 5, -1 }, { 5, 0 }, { 5, 1 }, { 5, 2 }, { 5, 3 }, { 5, 4 },
                { 5, 5 }, { 5, 6 }, { 5, 7 }, { 6, -7 }, { 6, -6 }, { 6, -5 },
                { 6, -4 }, { 6, -3 }, { 6, -2 }, { 6, -1 }, { 6, 0 }, { 6, 1 },
                { 6, 2 }, { 6, 3 }, { 6, 4 }, { 6, 5 }, { 6, 6 }, { 6, 7 },
                { 7, -6 }, { 7, -5 }, { 7, -4 }, { 7, -3 }, { 7, -2 },
                { 7, -1 }, { 7, 0 }, { 7, 1 }, { 7, 2 }, { 7, 3 }, { 7, 4 },
                { 7, 5 }, { 7, 6 }, { 8, -5 }, { 8, -4 }, { 8, -3 }, { 8, -2 },
                { 8, -1 }, { 8, 0 }, { 8, 1 }, { 8, 2 }, { 8, 3 }, { 8, 4 },
                { 8, 5 }, { 9, -4 }, { 9, -3 }, { 9, -2 }, { 9, -1 }, { 9, 0 },
                { 9, 1 }, { 9, 2 }, { 9, 3 }, { 9, 4 }, { 10, -3 }, { 10, -2 },
                { 10, -1 }, { 10, 0 }, { 10, 1 }, { 10, 2 }, { 10, 3 },
                { 11, -1 }, { 11, 0 }, { 11, 1 } };

        for (int[] line : data) {
            points.add(new Vector2D(line[0], line[1]));
        }

        Vector2D[] referenceHull = new Vector2D[] {
            new Vector2D(-11.0, -1.0),
            new Vector2D(-10.0, -3.0),
            new Vector2D( -6.0, -7.0),
            new Vector2D( -3.0, -8.0),
            new Vector2D(  3.0, -8.0),
            new Vector2D(  6.0, -7.0),
            new Vector2D( 10.0, -3.0),
            new Vector2D( 11.0, -1.0),
            new Vector2D( 11.0,  1.0),
            new Vector2D( 10.0,  3.0),
            new Vector2D(  6.0,  7.0),
            new Vector2D(  3.0,  8.0),
            new Vector2D( -3.0,  8.0),
            new Vector2D( -6.0,  7.0),
            new Vector2D(-10.0,  3.0),
            new Vector2D(-11.0,  1.0),
        };

        ConvexHull2D convHull = generator.generate(points);
        Region<Euclidean2D> hullRegion = convHull.createRegion();

        Assert.assertEquals(274.0, hullRegion.getSize(), 1.0e-12);
        double perimeter = 0;
        for (int i = 0; i < referenceHull.length; ++i) {
            perimeter += Vector2D.distance(referenceHull[i],
                                           referenceHull[(i + 1) % referenceHull.length]);
        }
        Assert.assertEquals(perimeter, hullRegion.getBoundarySize(), 1.0e-12);

        for (int i = 0; i < referenceHull.length; ++i) {
            Assert.assertEquals(Location.BOUNDARY, hullRegion.checkPoint(referenceHull[i]));
        }

    }

    // ------------------------------------------------------------------------------

    protected final List<Vector2D> createRandomPoints(int size) {
        // create the cloud container
        List<Vector2D> points = new ArrayList<Vector2D>(size);
        // fill the cloud with a random distribution of points
        for (int i = 0; i < size; i++) {
            points.add(new Vector2D(random.nextDouble() * 2.0 - 1.0, random.nextDouble() * 2.0 - 1.0));
        }
        return points;
    }

    protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull) {
        checkConvexHull(points, hull, false);
    }

    protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull,
                                         final boolean includesCollinearPoints) {
        checkConvexHull(points, hull, includesCollinearPoints, 1e-10);
    }

    protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull,
                                         final boolean includesCollinearPoints, final double tolerance) {
        Assert.assertNotNull(hull);
        Assert.assertTrue(isConvex(hull, includesCollinearPoints, tolerance));
        checkPointsInsideHullRegion(points, hull, includesCollinearPoints);
    }

    // verify that the constructed hull is really convex
    protected final boolean isConvex(final ConvexHull2D hull, final boolean includesCollinearPoints,
                                     final double tolerance) {

        final Vector2D[] points = hull.getVertices();
        int sign = 0;

        for (int i = 0; i < points.length; i++) {
            Vector2D p1 = points[i == 0 ? points.length - 1 : i - 1];
            Vector2D p2 = points[i];
            Vector2D p3 = points[i == points.length - 1 ? 0 : i + 1];

            Vector2D d1 = p2.subtract(p1);
            Vector2D d2 = p3.subtract(p2);

            Assert.assertTrue(d1.getNorm() > 1e-10);
            Assert.assertTrue(d2.getNorm() > 1e-10);

            final double cross = MathArrays.linearCombination(d1.getX(), d2.getY(), -d1.getY(), d2.getX());
            final int cmp = Precision.compareTo(cross, 0.0, tolerance);

            if (sign != 0 && cmp != sign) {
                if (includesCollinearPoints && cmp == 0) {
                    // in case of collinear points the cross product will be zero
                } else {
                    return false;
                }
            }

            sign = cmp;
        }

        return true;
    }

    // verify that all points are inside the convex hull region
    protected final void checkPointsInsideHullRegion(final Collection<Vector2D> points,
                                                     final ConvexHull2D hull,
                                                     final boolean includesCollinearPoints) {

        final Collection<Vector2D> hullVertices = Arrays.asList(hull.getVertices());
        final Region<Euclidean2D> region = hull.createRegion();

        for (final Vector2D p : points) {
            Location location = region.checkPoint(p);
            Assert.assertTrue(location != Location.OUTSIDE);

            if (location == Location.BOUNDARY && includesCollinearPoints) {
                Assert.assertTrue(hullVertices.contains(p));
            }
        }
    }
}
