commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/AbstractConvexHyperplaneBoundedRegionTest.java

/*
 * 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.geometry.core.partitioning;

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

import org.apache.commons.geometry.core.GeometryTestUtils;
import org.apache.commons.geometry.core.Region;
import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.core.exception.GeometryException;
import org.apache.commons.geometry.core.partition.test.PartitionTestUtils;
import org.apache.commons.geometry.core.partition.test.TestLine;
import org.apache.commons.geometry.core.partition.test.TestLineSegment;
import org.apache.commons.geometry.core.partition.test.TestPoint2D;
import org.apache.commons.geometry.core.partition.test.TestTransform2D;
import org.junit.Assert;
import org.junit.Test;

public class AbstractConvexHyperplaneBoundedRegionTest {

    @Test
    public void testBoundaries_areUnmodifiable() {
        // arrange
        StubRegion region = new StubRegion(new ArrayList<>());

        // act/assert
        GeometryTestUtils.assertThrows(() -> {
            region.getBoundaries().add(TestLine.X_AXIS.span());
        }, UnsupportedOperationException.class);
    }

    @Test
    public void testFull() {
        // act
        StubRegion region = new StubRegion(Collections.emptyList());

        // assert
        Assert.assertTrue(region.isFull());
        Assert.assertFalse(region.isEmpty());
    }

    @Test
    public void testGetBoundarySize() {
        // arrange
        TestPoint2D p1 = new TestPoint2D(1, 0);
        TestPoint2D p2 = new TestPoint2D(2, 0);
        TestPoint2D p3 = new TestPoint2D(1, 1);

        // act/assert
        Assert.assertEquals(0, new StubRegion(Collections.emptyList()).getBoundarySize(), PartitionTestUtils.EPS);
        GeometryTestUtils.assertPositiveInfinity(new StubRegion(Arrays.asList(TestLine.X_AXIS.span())).getBoundarySize());
        Assert.assertEquals(2 + Math.sqrt(2), new StubRegion(Arrays.asList(
                    new TestLineSegment(p1, p2),
                    new TestLineSegment(p2, p3),
                    new TestLineSegment(p3, p1)
                )).getBoundarySize(), PartitionTestUtils.EPS);
    }

    @Test
    public void testClassify() {
        // arrange
        TestPoint2D p1 = new TestPoint2D(1, 0);
        TestPoint2D p2 = new TestPoint2D(2, 0);
        TestPoint2D p3 = new TestPoint2D(1, 1);

        StubRegion full = new StubRegion(Collections.emptyList());
        StubRegion halfSpace = new StubRegion(Arrays.asList(TestLine.X_AXIS.span()));
        StubRegion triangle = new StubRegion(Arrays.asList(
                new TestLineSegment(p1, p2),
                new TestLineSegment(p2, p3),
                new TestLineSegment(p3, p1)
            ));

        // act/assert
        checkClassify(full, RegionLocation.INSIDE, TestPoint2D.ZERO, p1, p2, p3);

        checkClassify(halfSpace, RegionLocation.INSIDE, new TestPoint2D(0, 1));
        checkClassify(halfSpace, RegionLocation.OUTSIDE, new TestPoint2D(0, -1));
        checkClassify(halfSpace, RegionLocation.BOUNDARY,
                new TestPoint2D(-1, 0), new TestPoint2D(0, 0), new TestPoint2D(1, 0));

        checkClassify(triangle, RegionLocation.INSIDE, new TestPoint2D(1.25, 0.25));
        checkClassify(triangle, RegionLocation.OUTSIDE, new TestPoint2D(-1, 0), new TestPoint2D(0, 0), new TestPoint2D(3, 0));
        checkClassify(triangle, RegionLocation.BOUNDARY, p1, p2, p3);
    }

    @Test
    public void testProject() {
        // arrange
        TestPoint2D p1 = new TestPoint2D(1, 0);
        TestPoint2D p2 = new TestPoint2D(2, 0);
        TestPoint2D p3 = new TestPoint2D(1, 1);

        StubRegion full = new StubRegion(Collections.emptyList());
        StubRegion halfSpace = new StubRegion(Arrays.asList(TestLine.X_AXIS.span()));
        StubRegion triangle = new StubRegion(Arrays.asList(
                new TestLineSegment(p1, p2),
                new TestLineSegment(p2, p3),
                new TestLineSegment(p3, p1)
            ));

        // act/assert
        Assert.assertNull(full.project(TestPoint2D.ZERO));
        Assert.assertNull(full.project(new TestPoint2D(1, 1)));

        PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, halfSpace.project(new TestPoint2D(0, 1)));
        PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, halfSpace.project(new TestPoint2D(0, 0)));
        PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, halfSpace.project(new TestPoint2D(0, -1)));

        PartitionTestUtils.assertPointsEqual(new TestPoint2D(1.25, 0), triangle.project(new TestPoint2D(1.25, 0.1)));
        PartitionTestUtils.assertPointsEqual(p1, triangle.project(TestPoint2D.ZERO));
        PartitionTestUtils.assertPointsEqual(p3, triangle.project(new TestPoint2D(0, 10)));
    }

    @Test
    public void testTrim() {
        // arrange
        TestPoint2D p1 = new TestPoint2D(1, 0);
        TestPoint2D p2 = new TestPoint2D(2, 0);
        TestPoint2D p3 = new TestPoint2D(2, 1);
        TestPoint2D p4 = new TestPoint2D(1, 1);

        StubRegion full = new StubRegion(Collections.emptyList());
        StubRegion halfSpace = new StubRegion(Arrays.asList(TestLine.Y_AXIS.span()));
        StubRegion square = new StubRegion(Arrays.asList(
                new TestLineSegment(p1, p2),
                new TestLineSegment(p2, p3),
                new TestLineSegment(p3, p4),
                new TestLineSegment(p4, p1)
            ));

        TestLineSegment segment = new TestLineSegment(new TestPoint2D(-1, 0.5), new TestPoint2D(4, 0.5));

        // act/assert
        Assert.assertSame(segment, full.trim(segment));

        TestLineSegment trimmedA = halfSpace.trim(segment);
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(-1, 0.5), trimmedA.getStartPoint());
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 0.5), trimmedA.getEndPoint());

        TestLineSegment trimmedB = square.trim(segment);
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(1, 0.5), trimmedB.getStartPoint());
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 0.5), trimmedB.getEndPoint());
    }

    @Test
    public void testSplit_full() {
        // arrange
        StubRegion region = new StubRegion(Collections.emptyList());

        TestLine splitter = TestLine.X_AXIS;

        // act
        Split<StubRegion> split = region.split(splitter);

        // assert
        Assert.assertEquals(SplitLocation.BOTH, split.getLocation());

        StubRegion minus = split.getMinus();
        Assert.assertEquals(1, minus.getBoundaries().size());
        checkClassify(minus, RegionLocation.INSIDE, new TestPoint2D(0, 1));
        checkClassify(minus, RegionLocation.BOUNDARY, new TestPoint2D(0, 0));
        checkClassify(minus, RegionLocation.OUTSIDE, new TestPoint2D(0, -1));

        StubRegion plus = split.getPlus();
        Assert.assertEquals(1, plus.getBoundaries().size());
        checkClassify(plus, RegionLocation.OUTSIDE, new TestPoint2D(0, 1));
        checkClassify(plus, RegionLocation.BOUNDARY, new TestPoint2D(0, 0));
        checkClassify(plus, RegionLocation.INSIDE, new TestPoint2D(0, -1));
    }

    @Test
    public void testSplit_parallel_plusOnly() {
     // arrange
        StubRegion region = new StubRegion(
                Arrays.asList(new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(1, 1))));

        TestLine splitter = TestLine.X_AXIS.reverse();

        // act
        Split<StubRegion> split = region.split(splitter);

        // assert
        Assert.assertEquals(SplitLocation.PLUS, split.getLocation());

        Assert.assertNull(split.getMinus());
        Assert.assertSame(region, split.getPlus());
    }

    @Test
    public void testSplit_parallel_minusOnly() {
     // arrange
        StubRegion region = new StubRegion(
                Arrays.asList(new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(1, 1))));

        TestLine splitter = TestLine.X_AXIS;

        // act
        Split<StubRegion> split = region.split(splitter);

        // assert
        Assert.assertEquals(SplitLocation.MINUS, split.getLocation());

        Assert.assertSame(region, split.getMinus());
        Assert.assertNull(split.getPlus());
    }

    @Test
    public void testSplit_coincident_sameOrientation() {
     // arrange
        StubRegion region = new StubRegion(Arrays.asList(TestLine.X_AXIS.span()));

        TestLine splitter = TestLine.X_AXIS;

        // act
        Split<StubRegion> split = region.split(splitter);

        // assert
        Assert.assertEquals(SplitLocation.MINUS, split.getLocation());

        Assert.assertSame(region, split.getMinus());
        Assert.assertNull(split.getPlus());
    }

    @Test
    public void testSplit_coincident_oppositeOrientation() {
     // arrange
        StubRegion region = new StubRegion(Arrays.asList(TestLine.X_AXIS.span()));

        TestLine splitter = TestLine.X_AXIS.reverse();

        // act
        Split<StubRegion> split = region.split(splitter);

        // assert
        Assert.assertEquals(SplitLocation.PLUS, split.getLocation());

        Assert.assertNull(split.getMinus());
        Assert.assertSame(region, split.getPlus());
    }

    @Test
    public void testSplit_finite_both() {
        // arrange
        TestPoint2D p1 = new TestPoint2D(1, -0.5);
        TestPoint2D p2 = new TestPoint2D(2, -0.5);
        TestPoint2D p3 = new TestPoint2D(2, 0.5);
        TestPoint2D p4 = new TestPoint2D(1, 0.5);

        StubRegion region = new StubRegion(Arrays.asList(
                    new TestLineSegment(p1, p2),
                    new TestLineSegment(p2, p3),
                    new TestLineSegment(p3, p4),
                    new TestLineSegment(p4, p1)
                ));

        TestLine splitter = TestLine.X_AXIS;

        // act
        Split<StubRegion> split = region.split(splitter);

        // assert
        Assert.assertEquals(SplitLocation.BOTH, split.getLocation());

        StubRegion minus = split.getMinus();
        Assert.assertEquals(4, minus.getBoundaries().size());
        checkClassify(minus, RegionLocation.INSIDE, new TestPoint2D(1.5, 0.25));
        checkClassify(minus, RegionLocation.BOUNDARY, new TestPoint2D(1.5, 0));
        checkClassify(minus, RegionLocation.OUTSIDE, new TestPoint2D(1.5, -0.25));

        StubRegion plus = split.getPlus();
        Assert.assertEquals(4, plus.getBoundaries().size());
        checkClassify(plus, RegionLocation.OUTSIDE, new TestPoint2D(1.5, 0.25));
        checkClassify(plus, RegionLocation.BOUNDARY, new TestPoint2D(1.5, 0));
        checkClassify(plus, RegionLocation.INSIDE, new TestPoint2D(1.5, -0.25));
    }

    @Test
    public void testTransform_full() {
        // arrange
        StubRegion region = new StubRegion(Collections.emptyList());

        Transform<TestPoint2D> transform = new TestTransform2D(p -> new TestPoint2D(p.getX() + 1, p.getY() + 2));

        // act
        StubRegion transformed = region.transform(transform);

        // assert
        Assert.assertTrue(transformed.isFull());
        Assert.assertFalse(transformed.isEmpty());
    }

    @Test
    public void testTransform_infinite() {
        // arrange
        TestLine line = TestLine.Y_AXIS;

        StubRegion region = new StubRegion(Arrays.asList(
                line.span()
            ));

        Transform<TestPoint2D> transform = new TestTransform2D(p -> new TestPoint2D(p.getX() + 1, p.getY() + 2));

        // act
        StubRegion transformed = region.transform(transform);

        // assert
        List<TestLineSegment> boundaries = transformed.getBoundaries();

        Assert.assertEquals(1, boundaries.size());

        TestLineSegment a = boundaries.get(0);
        TestLine aLine = a.getHyperplane();
        PartitionTestUtils.assertPointsEqual(aLine.getOrigin(), new TestPoint2D(1, 0));
        Assert.assertEquals(0.0, aLine.getDirectionX(), PartitionTestUtils.EPS);
        Assert.assertEquals(1.0, aLine.getDirectionY(), PartitionTestUtils.EPS);

        GeometryTestUtils.assertNegativeInfinity(a.getStart());
        GeometryTestUtils.assertPositiveInfinity(a.getEnd());
    }

    @Test
    public void testTransform_finite() {
        // arrange
        TestPoint2D p1 = new TestPoint2D(1, 0);
        TestPoint2D p2 = new TestPoint2D(2, 0);
        TestPoint2D p3 = new TestPoint2D(1, 1);

        StubRegion region = new StubRegion(Arrays.asList(
                new TestLineSegment(p1, p2),
                new TestLineSegment(p2, p3),
                new TestLineSegment(p3, p1)
            ));

        Transform<TestPoint2D> transform = new TestTransform2D(p -> new TestPoint2D(p.getX() + 1, p.getY() + 2));

        // act
        StubRegion transformed = region.transform(transform);

        // assert
        List<TestLineSegment> boundaries = transformed.getBoundaries();

        Assert.assertEquals(3, boundaries.size());

        TestLineSegment a = boundaries.get(0);
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 2), a.getStartPoint());
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(3, 2), a.getEndPoint());

        TestLineSegment b = boundaries.get(1);
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(3, 2), b.getStartPoint());
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 3), b.getEndPoint());

        TestLineSegment c = boundaries.get(2);
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 3), c.getStartPoint());
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 2), c.getEndPoint());
    }

    @Test
    public void testTransform_reflection() {
        // arrange
        TestPoint2D p1 = new TestPoint2D(1, 0);
        TestPoint2D p2 = new TestPoint2D(2, 0);
        TestPoint2D p3 = new TestPoint2D(1, 1);

        StubRegion region = new StubRegion(Arrays.asList(
                new TestLineSegment(p1, p2),
                new TestLineSegment(p2, p3),
                new TestLineSegment(p3, p1)
            ));

        Transform<TestPoint2D> transform = new TestTransform2D(p -> new TestPoint2D(-p.getX(), p.getY()));

        // act
        StubRegion transformed = region.transform(transform);

        // assert
        List<TestLineSegment> boundaries = transformed.getBoundaries();

        Assert.assertEquals(3, boundaries.size());

        TestLineSegment a = boundaries.get(0);
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(-2, 0), a.getStartPoint());
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(-1, 0), a.getEndPoint());

        TestLineSegment b = boundaries.get(1);
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(-1, 1), b.getStartPoint());
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(-2, 0), b.getEndPoint());

        TestLineSegment c = boundaries.get(2);
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(-1, 0), c.getStartPoint());
        PartitionTestUtils.assertPointsEqual(new TestPoint2D(-1, 1), c.getEndPoint());
    }

    @Test
    public void testConvexRegionBoundaryBuilder_full() {
        // act
        StubRegion region = StubRegion.fromBounds(Collections.emptyList());

        // assert
        Assert.assertSame(StubRegion.FULL, region);
    }

    @Test
    public void testConvexRegionBoundaryBuilder_singleLine() {
        // act
        StubRegion region = StubRegion.fromBounds(Arrays.asList(TestLine.Y_AXIS));

        // assert
        Assert.assertEquals(1, region.getBoundaries().size());

        checkClassify(region, RegionLocation.INSIDE, new TestPoint2D(-1, 0));
        checkClassify(region, RegionLocation.BOUNDARY, new TestPoint2D(0, 0));
        checkClassify(region, RegionLocation.OUTSIDE, new TestPoint2D(1, 0));
    }

    @Test
    public void testConvexRegionBoundaryBuilder_multipleLines() {
        // act
        StubRegion region = StubRegion.fromBounds(Arrays.asList(
                    TestLine.X_AXIS,
                    new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, 1)),
                    TestLine.Y_AXIS.reverse()
                ));

        // assert
        Assert.assertEquals(3, region.getBoundaries().size());

        checkClassify(region, RegionLocation.INSIDE, new TestPoint2D(0.25, 0.25));

        checkClassify(region, RegionLocation.BOUNDARY,
                TestPoint2D.ZERO, new TestPoint2D(1, 0), new TestPoint2D(1, 0), new TestPoint2D(0.5, 0.5));

        checkClassify(region, RegionLocation.OUTSIDE,
                new TestPoint2D(-1, 0.5), new TestPoint2D(1, 0.5),
                new TestPoint2D(0.5, 1), new TestPoint2D(0.5, -1));
    }

    @Test
    public void testConvexRegionBoundaryBuilder_duplicateLines() {
        // act
        StubRegion region = StubRegion.fromBounds(Arrays.asList(
                TestLine.Y_AXIS,
                TestLine.Y_AXIS,
                new TestLine(new TestPoint2D(0, 0), new TestPoint2D(0, 1)),
                TestLine.Y_AXIS));

        // assert
        Assert.assertEquals(1, region.getBoundaries().size());

        checkClassify(region, RegionLocation.INSIDE, new TestPoint2D(-1, 0));
        checkClassify(region, RegionLocation.BOUNDARY, new TestPoint2D(0, 0));
        checkClassify(region, RegionLocation.OUTSIDE, new TestPoint2D(1, 0));
    }

    @Test
    public void testConvexRegionBoundaryBuilder() {
        // act/assert
        GeometryTestUtils.assertThrows(() -> {
            StubRegion.fromBounds(Arrays.asList(TestLine.X_AXIS, TestLine.X_AXIS.reverse()));
        }, GeometryException.class);

        GeometryTestUtils.assertThrows(() -> {
            StubRegion.fromBounds(Arrays.asList(
                    TestLine.X_AXIS,
                    TestLine.Y_AXIS,
                    new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, -1))));
        }, GeometryException.class);
    }

    @Test
    public void testToString() {
        // arrange
        StubRegion region = new StubRegion(Collections.emptyList());

        // act
        String str = region.toString();

        // assert
        Assert.assertTrue(str.contains("StubRegion"));
        Assert.assertTrue(str.contains("boundaries= "));
    }

    private static void checkClassify(Region<TestPoint2D> region, RegionLocation loc, TestPoint2D ... pts) {
        for (TestPoint2D pt : pts) {
            Assert.assertEquals("Unexpected location for point " + pt, loc, region.classify(pt));
        }
    }

    private static final class StubRegion extends AbstractConvexHyperplaneBoundedRegion<TestPoint2D, TestLineSegment>{

        private static final long serialVersionUID = 1L;

        private static final StubRegion FULL = new StubRegion(Collections.emptyList());

        StubRegion(List<TestLineSegment> boundaries) {
            super(boundaries);
        }

        public StubRegion transform(Transform<TestPoint2D> transform) {
            return transformInternal(transform, this, TestLineSegment.class, StubRegion::new);
        }

        @Override
        public Split<StubRegion> split(Hyperplane<TestPoint2D> splitter) {
            return splitInternal(splitter, this, TestLineSegment.class, StubRegion::new);
        }

        @Override
        public TestLineSegment trim(ConvexSubHyperplane<TestPoint2D> convexSubHyperplane) {
            return (TestLineSegment) super.trim(convexSubHyperplane);
        }

        @Override
        public double getSize() {
            throw new UnsupportedOperationException();
        }

        @Override
        public TestPoint2D getBarycenter() {
            throw new UnsupportedOperationException();
        }

        public static StubRegion fromBounds(Iterable<TestLine> boundingLines) {
            final List<TestLineSegment> segments = new ConvexRegionBoundaryBuilder<>(TestLineSegment.class).build(boundingLines);
            return segments.isEmpty() ? FULL : new StubRegion(segments);
        }
    }
}