View Javadoc

    1   /*
    2    * Licensed to the Apache Software Foundation (ASF) under one or more
    3    * contributor license agreements.  See the NOTICE file distributed with
    4    * this work for additional information regarding copyright ownership.
    5    * The ASF licenses this file to You under the Apache License, Version 2.0
    6    * (the "License"); you may not use this file except in compliance with
    7    * the License.  You may obtain a copy of the License at
    8    *
    9    *      http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    16   */
    17  package org.apache.commons.geometry.euclidean.twod.shape;
    18
    19  import java.util.ArrayList;
    20  import java.util.Comparator;
    21  import java.util.List;
    22
    23  import org.apache.commons.geometry.core.GeometryTestUtils;
    24  import org.apache.commons.geometry.core.RegionLocation;
    25  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    26  import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
    27  import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
    28  import org.apache.commons.geometry.euclidean.twod.Line;
    29  import org.apache.commons.geometry.euclidean.twod.LineConvexSubset;
    30  import org.apache.commons.geometry.euclidean.twod.LinecastPoint2D;
    31  import org.apache.commons.geometry.euclidean.twod.Lines;
    32  import org.apache.commons.geometry.euclidean.twod.PolarCoordinates;
    33  import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
    34  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    35  import org.apache.commons.geometry.euclidean.twod.path.LinePath;
    36  import org.apache.commons.numbers.angle.PlaneAngleRadians;
    37  import org.junit.Assert;
    38  import org.junit.Test;
    39
    40  public class CircleTest {
    41
    42      private static final double TEST_EPS = 1e-10;
    43
    44      private static final DoublePrecisionContext TEST_PRECISION =
    45              new EpsilonDoublePrecisionContext(TEST_EPS);
    46
    47      private static final Comparator<LineConvexSubset> SEGMENT_DIRECTION_COMPARATOR =
    48          (a, b) -> Vector2D.COORDINATE_ASCENDING_ORDER.compare(
    49              a.getLine().getDirection(),
    50              b.getLine().getDirection());
    51
    52      @Test
    53      public void testFrom() {
    54          // arrange
    55          final Vector2D center = Vector2D.of(1, 2);
    56
    57          // act
    58          final Circle c = Circle.from(center, 3, TEST_PRECISION);
    59
    60          // act/assert
    61          Assert.assertFalse(c.isFull());
    62          Assert.assertFalse(c.isEmpty());
    63
    64          Assert.assertSame(center, c.getCenter());
    65          Assert.assertSame(center, c.getCentroid());
    66
    67          Assert.assertEquals(3, c.getRadius(), 0.0);
    68
    69          Assert.assertSame(TEST_PRECISION, c.getPrecision());
    70      }
    71
    72      @Test
    73      public void testFrom_illegalCenter() {
    74          // act/assert
    75          GeometryTestUtils.assertThrows(() -> Circle.from(Vector2D.of(Double.POSITIVE_INFINITY, 1), 1, TEST_PRECISION),
    76                  IllegalArgumentException.class);
    77          GeometryTestUtils.assertThrows(() -> Circle.from(Vector2D.of(Double.NaN, 1), 1, TEST_PRECISION),
    78                  IllegalArgumentException.class);
    79      }
    80
    81      @Test
    82      public void testFrom_illegalRadius() {
    83          // arrange
    84          final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-2);
    85
    86          // act/assert
    87          GeometryTestUtils.assertThrows(() -> Circle.from(Vector2D.ZERO, -1, TEST_PRECISION),
    88                  IllegalArgumentException.class);
    89          GeometryTestUtils.assertThrows(() -> Circle.from(Vector2D.ZERO, 0, TEST_PRECISION),
    90                  IllegalArgumentException.class);
    91          GeometryTestUtils.assertThrows(() -> Circle.from(Vector2D.ZERO, Double.POSITIVE_INFINITY, TEST_PRECISION),
    92                  IllegalArgumentException.class);
    93          GeometryTestUtils.assertThrows(() -> Circle.from(Vector2D.ZERO, Double.NaN, TEST_PRECISION),
    94                  IllegalArgumentException.class);
    95
    96          GeometryTestUtils.assertThrows(() -> Circle.from(Vector2D.ZERO, 1e-3, precision),
    97                  IllegalArgumentException.class);
    98      }
    99
    100     @Test
    101     public void testGeometricProperties() {
    102         // arrange
    103         final double r = 2;
    104         final Circle c = Circle.from(Vector2D.of(1, 2), r, TEST_PRECISION);
    105
    106         // act/assert
    107         Assert.assertEquals(2 * Math.PI * r, c.getBoundarySize(), TEST_EPS);
    108         Assert.assertEquals(Math.PI * r * r, c.getSize(), TEST_EPS);
    109     }
    110
    111     @Test
    112     public void testClassify() {
    113         // arrange
    114         final Circle c = Circle.from(Vector2D.of(1, 2), 1, TEST_PRECISION);
    115
    116         // act/assert
    117         EuclideanTestUtils.assertRegionLocation(c, RegionLocation.INSIDE,
    118                 Vector2D.of(1, 2),
    119                 Vector2D.of(0.5, 2), Vector2D.of(1.5, 2),
    120                 Vector2D.of(1, 1.5), Vector2D.of(1, 2.5),
    121                 Vector2D.of(0.5, 1.5), Vector2D.of(1.5, 2.5),
    122                 Vector2D.of(0.5, 2.5), Vector2D.of(1.5, 1.5));
    123
    124         EuclideanTestUtils.assertRegionLocation(c, RegionLocation.OUTSIDE,
    125                 Vector2D.of(-0.5, 2), Vector2D.of(2.5, 2),
    126                 Vector2D.of(1, 0.5), Vector2D.of(1, 3.5),
    127                 Vector2D.of(0.25, 1.25), Vector2D.of(1.75, 2.75),
    128                 Vector2D.of(0.25, 2.75), Vector2D.of(1.75, 1.25));
    129
    130         for (double angle = 0; angle < PlaneAngleRadians.TWO_PI; angle += 0.1) {
    131             EuclideanTestUtils.assertRegionLocation(c, RegionLocation.BOUNDARY,
    132                     c.getCenter().add(PolarCoordinates.of(1, angle).toCartesian()));
    133         }
    134     }
    135
    136     @Test
    137     public void testContains() {
    138         // arrange
    139         final Circle c = Circle.from(Vector2D.of(1, 2), 1, TEST_PRECISION);
    140
    141         // act/assert
    142         checkContains(c, true,
    143                 Vector2D.of(1, 2),
    144                 Vector2D.of(0.5, 2), Vector2D.of(1.5, 2),
    145                 Vector2D.of(1, 1.5), Vector2D.of(1, 2.5),
    146                 Vector2D.of(0.5, 1.5), Vector2D.of(1.5, 2.5),
    147                 Vector2D.of(0.5, 2.5), Vector2D.of(1.5, 1.5));
    148
    149         for (double angle = 0; angle < PlaneAngleRadians.TWO_PI; angle += 0.1) {
    150             checkContains(c, true,
    151                     c.getCenter().add(PolarCoordinates.of(1, angle).toCartesian()));
    152         }
    153
    154         checkContains(c, false,
    155                 Vector2D.of(-0.5, 2), Vector2D.of(2.5, 2),
    156                 Vector2D.of(1, 0.5), Vector2D.of(1, 3.5),
    157                 Vector2D.of(0.25, 1.25), Vector2D.of(1.75, 2.75),
    158                 Vector2D.of(0.25, 2.75), Vector2D.of(1.75, 1.25));
    159     }
    160
    161     @Test
    162     public void testProject() {
    163         // arrange
    164         final Vector2D center = Vector2D.of(1.5, 2.5);
    165         final double radius = 3;
    166         final Circle c = Circle.from(center, radius, TEST_PRECISION);
    167
    168         EuclideanTestUtils.permute(-4, 4, 1, (x, y) -> {
    169             final Vector2D pt = Vector2D.of(x, y);
    170
    171             // act
    172             final Vector2D projection = c.project(pt);
    173
    174             // assert
    175             Assert.assertEquals(radius, center.distance(projection), TEST_EPS);
    176             EuclideanTestUtils.assertCoordinatesEqual(center.directionTo(pt),
    177                     center.directionTo(projection), TEST_EPS);
    178         });
    179     }
    180
    181     @Test
    182     public void testProject_argumentEqualsCenter() {
    183         // arrange
    184         final Circle c = Circle.from(Vector2D.of(1, 2), 2, TEST_PRECISION);
    185
    186         // act
    187         final Vector2D projection = c.project(Vector2D.of(1, 2));
    188
    189         // assert
    190         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(3, 2), projection, TEST_EPS);
    191     }
    192
    193     @Test
    194     public void testIntersections() {
    195         // --- arrange
    196         final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
    197         final double sqrt3 = Math.sqrt(3);
    198
    199         // --- act/assert
    200         // descending horizontal lines
    201         checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, 4), Vector2D.of(5, 4), TEST_PRECISION));
    202         checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, 3), Vector2D.of(5, 3), TEST_PRECISION),
    203                 Vector2D.of(2, 3));
    204         checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, 2), Vector2D.of(5, 2), TEST_PRECISION),
    205                 Vector2D.of(2 - sqrt3, 2), Vector2D.of(2 + sqrt3, 2));
    206         checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, 1), Vector2D.of(5, 1), TEST_PRECISION),
    207                 Vector2D.of(0, 1), Vector2D.of(4, 1));
    208         checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, 0), Vector2D.of(5, 0), TEST_PRECISION),
    209                 Vector2D.of(2 - sqrt3, 0), Vector2D.of(2 + sqrt3, 0));
    210         checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, -1), Vector2D.of(5, -1), TEST_PRECISION),
    211                 Vector2D.of(2, -1));
    212         checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, -2), Vector2D.of(5, -2), TEST_PRECISION));
    213
    214         // ascending vertical lines
    215         checkIntersections(c, Lines.fromPoints(Vector2D.of(-1, -2), Vector2D.of(-1, 5), TEST_PRECISION));
    216         checkIntersections(c, Lines.fromPoints(Vector2D.of(0, -2), Vector2D.of(0, 5), TEST_PRECISION),
    217                 Vector2D.of(0, 1));
    218         checkIntersections(c, Lines.fromPoints(Vector2D.of(1, -2), Vector2D.of(1, 5), TEST_PRECISION),
    219                 Vector2D.of(1, 1 - sqrt3), Vector2D.of(1, 1 + sqrt3));
    220         checkIntersections(c, Lines.fromPoints(Vector2D.of(2, -2), Vector2D.of(2, 5), TEST_PRECISION),
    221                 Vector2D.of(2, -1), Vector2D.of(2, 3));
    222         checkIntersections(c, Lines.fromPoints(Vector2D.of(3, -2), Vector2D.of(3, 5), TEST_PRECISION),
    223                 Vector2D.of(3, 1 - sqrt3), Vector2D.of(3, 1 + sqrt3));
    224         checkIntersections(c, Lines.fromPoints(Vector2D.of(4, -2), Vector2D.of(4, 5), TEST_PRECISION),
    225                 Vector2D.of(4, 1));
    226         checkIntersections(c, Lines.fromPoints(Vector2D.of(5, -2), Vector2D.of(5, 5), TEST_PRECISION));
    227
    228         // diagonal from origin
    229         final Vector2D center = c.getCenter();
    230         checkIntersections(c, Lines.fromPoints(Vector2D.ZERO, c.getCenter(), TEST_PRECISION),
    231                 center.withNorm(center.norm() - c.getRadius()), center.withNorm(center.norm() + c.getRadius()));
    232     }
    233
    234     @Test
    235     public void testLinecast() {
    236         // arrange
    237         final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
    238         final double sqrt3 = Math.sqrt(3);
    239
    240         // act/assert
    241         checkLinecast(c, Lines.segmentFromPoints(Vector2D.of(-1, 0), Vector2D.of(5, 0), TEST_PRECISION),
    242                 Vector2D.of(2 - sqrt3, 0), Vector2D.of(2 + sqrt3, 0));
    243         checkLinecast(c, Lines.segmentFromPoints(Vector2D.of(-1, 3), Vector2D.of(5, 3), TEST_PRECISION),
    244                 Vector2D.of(2, 3));
    245         checkLinecast(c, Lines.segmentFromPoints(Vector2D.of(-1, -2), Vector2D.of(5, -2), TEST_PRECISION));
    246     }
    247
    248     @Test
    249     public void testLinecast_intersectionsNotInSegment() {
    250         // arrange
    251         final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
    252         final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION);
    253
    254         // act/assert
    255         checkLinecast(c, line.segment(-1, 0));
    256         checkLinecast(c, line.segment(1.5, 2.5));
    257         checkLinecast(c, line.segment(1.5, 2.5));
    258         checkLinecast(c, line.segment(4, 5));
    259     }
    260
    261     @Test
    262     public void testLinecast_segmentPointOnBoundary() {
    263         // arrange
    264         final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
    265         final Line line = Lines.fromPointAndAngle(Vector2D.ZERO, 0, TEST_PRECISION);
    266         final double sqrt3 = Math.sqrt(3);
    267         final double start = 2 - sqrt3;
    268         final double end = 2 + sqrt3;
    269
    270         // act/assert
    271         checkLinecast(c, line.segment(start, 2), Vector2D.of(start, 0));
    272         checkLinecast(c, line.segment(start, end), Vector2D.of(start, 0), Vector2D.of(end, 0));
    273         checkLinecast(c, line.segment(end, 5), Vector2D.of(end, 0));
    274     }
    275
    276     @Test
    277     public void testToTree_threeSegments() {
    278         // arrange
    279         final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
    280
    281         // act
    282         final RegionBSPTree2D tree = c.toTree(3);
    283
    284         // assert
    285         checkBasicApproximationProperties(c, tree);
    286
    287         final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
    288         segments.sort(SEGMENT_DIRECTION_COMPARATOR);
    289
    290         Assert.assertEquals(3, segments.size());
    291
    292         final double inc = PlaneAngleRadians.TWO_PI / 3.0;
    293         final Vector2D p0 = Vector2D.of(4, 1);
    294         final Vector2D p1 = Vector2D.of(
    295                 (2 * Math.cos(inc)) + 2,
    296                 (2 * Math.sin(inc)) + 1);
    297         final Vector2D p2 = Vector2D.of(
    298                 (2 * Math.cos(2 * inc)) + 2,
    299                 (2 * Math.sin(2 * inc)) + 1);
    300
    301         assertFiniteSegment(segments.get(0), p0, p1);
    302         assertFiniteSegment(segments.get(1), p1, p2);
    303         assertFiniteSegment(segments.get(2), p2, p0);
    304     }
    305
    306     @Test
    307     public void testToTree_fourSegments() {
    308         // arrange
    309         final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
    310
    311         // act
    312         final RegionBSPTree2D tree = c.toTree(4);
    313
    314         // assert
    315         checkBasicApproximationProperties(c, tree);
    316
    317         final List<LineConvexSubset> segments = new ArrayList<>(tree.getBoundaries());
    318         segments.sort(SEGMENT_DIRECTION_COMPARATOR);
    319
    320         Assert.assertEquals(4, segments.size());
    321
    322         final Vector2D p0 = Vector2D.of(4, 1);
    323         final Vector2D p1 = Vector2D.of(2, 3);
    324         final Vector2D p2 = Vector2D.of(0, 1);
    325         final Vector2D p3 = Vector2D.of(2, -1);
    326
    327         assertFiniteSegment(segments.get(0), p1, p2);
    328         assertFiniteSegment(segments.get(1), p0, p1);
    329         assertFiniteSegment(segments.get(2), p2, p3);
    330         assertFiniteSegment(segments.get(3), p3, p0);
    331     }
    332
    333     @Test
    334     public void testToTree_multipleApproximationSizes() {
    335         // -- arrange
    336         final Circle c = Circle.from(Vector2D.of(-3, 5), 10, TEST_PRECISION);
    337
    338         final int min = 5;
    339         final int max = 100;
    340
    341         RegionBSPTree2D tree;
    342
    343         double sizeDiff;
    344         double prevSizeDiff = Double.POSITIVE_INFINITY;
    345
    346         for (int n = min; n <= max; ++n) {
    347             // -- act
    348             tree = c.toTree(n);
    349
    350             // -- assert
    351             checkBasicApproximationProperties(c, tree);
    352
    353             // check that we get closer and closer to the correct size as we add more segments
    354             sizeDiff = c.getSize() - tree.getSize();
    355             Assert.assertTrue("Expected size difference to decrease", sizeDiff < prevSizeDiff);
    356
    357             prevSizeDiff = sizeDiff;
    358         }
    359     }
    360
    361     @Test
    362     public void testToTree_closeApproximation() {
    363         // arrange
    364         final Circle c = Circle.from(Vector2D.of(-2, 0), 1, TEST_PRECISION);
    365
    366         // act
    367         final RegionBSPTree2D tree = c.toTree(100);
    368
    369         // assert
    370         checkBasicApproximationProperties(c, tree);
    371
    372         final double eps = 5e-3;
    373         Assert.assertEquals(c.getSize(), tree.getSize(), eps);
    374         Assert.assertEquals(c.getBoundarySize(), tree.getBoundarySize(), eps);
    375         EuclideanTestUtils.assertCoordinatesEqual(c.getCentroid(), tree.getCentroid(), eps);
    376     }
    377
    378     @Test
    379     public void testToTree_invalidSegmentCount() {
    380         // arrange
    381         final Circle c = Circle.from(Vector2D.of(2, 1), 2, TEST_PRECISION);
    382         final String baseMsg = "Circle approximation segment number must be greater than or equal to 3; was ";
    383
    384         // act/assert
    385         GeometryTestUtils.assertThrows(() -> {
    386             c.toTree(2);
    387         }, IllegalArgumentException.class, baseMsg + "2");
    388         GeometryTestUtils.assertThrows(() -> {
    389             c.toTree(-1);
    390         }, IllegalArgumentException.class, baseMsg + "-1");
    391     }
    392
    393     @Test
    394     public void testHashCode() {
    395         // arrange
    396         final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-2);
    397
    398         final Circle a = Circle.from(Vector2D.of(1, 2), 3, TEST_PRECISION);
    399         final Circle b = Circle.from(Vector2D.of(1, 1), 3, TEST_PRECISION);
    400         final Circle c = Circle.from(Vector2D.of(1, 2), 4, TEST_PRECISION);
    401         final Circle d = Circle.from(Vector2D.of(1, 2), 3, precision);
    402         final Circle e = Circle.from(Vector2D.of(1, 2), 3, TEST_PRECISION);
    403
    404         // act
    405         final int hash = a.hashCode();
    406
    407         // act/assert
    408         Assert.assertEquals(hash, a.hashCode());
    409
    410         Assert.assertNotEquals(hash, b.hashCode());
    411         Assert.assertNotEquals(hash, c.hashCode());
    412         Assert.assertNotEquals(hash, d.hashCode());
    413
    414         Assert.assertEquals(hash, e.hashCode());
    415     }
    416
    417     @Test
    418     public void testEquals() {
    419         // arrange
    420         final DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-2);
    421
    422         final Circle a = Circle.from(Vector2D.of(1, 2), 3, TEST_PRECISION);
    423         final Circle b = Circle.from(Vector2D.of(1, 1), 3, TEST_PRECISION);
    424         final Circle c = Circle.from(Vector2D.of(1, 2), 4, TEST_PRECISION);
    425         final Circle d = Circle.from(Vector2D.of(1, 2), 3, precision);
    426         final Circle e = Circle.from(Vector2D.of(1, 2), 3, TEST_PRECISION);
    427
    428         // act/assert
    429         Assert.assertEquals(a, a);
    430
    431         Assert.assertFalse(a.equals(null));
    432         Assert.assertFalse(a.equals(new Object()));
    433
    434         Assert.assertNotEquals(a, b);
    435         Assert.assertNotEquals(a, c);
    436         Assert.assertNotEquals(a, d);
    437
    438         Assert.assertEquals(a, e);
    439     }
    440
    441     @Test
    442     public void testToString() {
    443         // arrange
    444         final Circle c = Circle.from(Vector2D.of(1, 2), 3, TEST_PRECISION);
    445
    446         // act
    447         final String str = c.toString();
    448
    449         // assert
    450         Assert.assertEquals("Circle[center= (1.0, 2.0), radius= 3.0]", str);
    451     }
    452
    453     private static void checkContains(final Circle circle, final boolean contains, final Vector2D... pts) {
    454         for (final Vector2D pt : pts) {
    455             Assert.assertEquals("Expected circle to " + (contains ? "" : "not") + "contain point " + pt,
    456                     contains, circle.contains(pt));
    457         }
    458     }
    459
    460     private static void checkIntersections(final Circle circle, final Line line, final Vector2D... expectedPts) {
    461         // --- act
    462         // compute the intersections forward and reverse
    463         final List<Vector2D> actualPtsForward = circle.intersections(line);
    464         final List<Vector2D> actualPtsReverse = circle.intersections(line.reverse());
    465
    466         final Vector2D actualFirstForward = circle.firstIntersection(line);
    467         final Vector2D actualFirstReverse = circle.firstIntersection(line.reverse());
    468
    469         // --- assert
    470         final int len = expectedPts.length;
    471
    472         // check the lists
    473         Assert.assertEquals(len, actualPtsForward.size());
    474         Assert.assertEquals(len, actualPtsReverse.size());
    475
    476         for (int i = 0; i < len; ++i) {
    477             EuclideanTestUtils.assertCoordinatesEqual(expectedPts[i], actualPtsForward.get(i), TEST_EPS);
    478             Assert.assertEquals(circle.getRadius(), circle.getCenter().distance(actualPtsForward.get(i)), TEST_EPS);
    479
    480             EuclideanTestUtils.assertCoordinatesEqual(expectedPts[len - i - 1], actualPtsReverse.get(i), TEST_EPS);
    481             Assert.assertEquals(circle.getRadius(), circle.getCenter().distance(actualPtsReverse.get(i)), TEST_EPS);
    482         }
    483
    484         // check the single intersection points
    485         if (len > 0) {
    486             Assert.assertNotNull(actualFirstForward);
    487             Assert.assertNotNull(actualFirstReverse);
    488
    489             EuclideanTestUtils.assertCoordinatesEqual(expectedPts[0], actualFirstForward, TEST_EPS);
    490             EuclideanTestUtils.assertCoordinatesEqual(expectedPts[len - 1], actualFirstReverse, TEST_EPS);
    491         } else {
    492             Assert.assertNull(actualFirstForward);
    493             Assert.assertNull(actualFirstReverse);
    494         }
    495     }
    496
    497     private static void checkLinecast(final Circle c, final LineConvexSubset segment, final Vector2D... expectedPts) {
    498         // check linecast
    499         final List<LinecastPoint2D> results = c.linecast(segment);
    500         Assert.assertEquals(expectedPts.length, results.size());
    501
    502         LinecastPoint2D actual;
    503         Vector2D expected;
    504         for (int i = 0; i < expectedPts.length; ++i) {
    505             expected = expectedPts[i];
    506             actual = results.get(i);
    507
    508             EuclideanTestUtils.assertCoordinatesEqual(expected, actual.getPoint(), TEST_EPS);
    509             EuclideanTestUtils.assertCoordinatesEqual(c.getCenter().directionTo(expected), actual.getNormal(), TEST_EPS);
    510             Assert.assertSame(segment.getLine(), actual.getLine());
    511         }
    512
    513         // check linecastFirst
    514         final LinecastPoint2D firstResult = c.linecastFirst(segment);
    515         if (expectedPts.length > 0) {
    516             Assert.assertEquals(results.get(0), firstResult);
    517         } else {
    518             Assert.assertNull(firstResult);
    519         }
    520     }
    521
    522     /**
    523      * Check a number of standard properties for bsp trees generated as circle approximations.
    524      */
    525     private static void checkBasicApproximationProperties(final Circle c, final RegionBSPTree2D tree) {
    526         Assert.assertFalse(tree.isFull());
    527         Assert.assertFalse(tree.isEmpty());
    528
    529         // all vertices must be inside the circle or on the boundary
    530         final List<LinePath> paths = tree.getBoundaryPaths();
    531         Assert.assertEquals(1, paths.size());
    532
    533         final LinePath path = paths.get(0);
    534         Assert.assertTrue(path.isFinite());
    535
    536         for (final Vector2D vertex : path.getVertexSequence()) {
    537             Assert.assertTrue("Expected vertex to be contained in circle: " + vertex, c.contains(vertex));
    538         }
    539
    540         // circle must contain centroid
    541         EuclideanTestUtils.assertRegionLocation(c, RegionLocation.INSIDE, tree.getCentroid());
    542
    543         // area must be less than the circle
    544         Assert.assertTrue("Expected approximation area to be less than circle", tree.getSize() < c.getSize());
    545     }
    546
    547     private static void assertFiniteSegment(final LineConvexSubset segment, final Vector2D start, final Vector2D end) {
    548         Assert.assertFalse(segment.isInfinite());
    549         Assert.assertTrue(segment.isFinite());
    550
    551         EuclideanTestUtils.assertCoordinatesEqual(start, segment.getStartPoint(), TEST_EPS);
    552         EuclideanTestUtils.assertCoordinatesEqual(end, segment.getEndPoint(), TEST_EPS);
    553     }
    554 }