ihmcrobotics / euclid

Vector math, geometry, reference frame, and shapes 2D & 3D
Apache License 2.0
31 stars 9 forks source link

FrameConvexPolygon2D (and likely other classes) can't handle out of order vertices #17

Closed rjgriffin42 closed 6 years ago

rjgriffin42 commented 6 years ago

The following test passes:

Point2D pointA = EuclidCoreRandomTools.nextPoint2D(random, 10.0);
Point2D pointB = EuclidCoreRandomTools.nextPoint2D(random, 10.0);

FrameConvexPolygon2D polygon = new FrameConvexPolygon2D();
polygon.addVertex(pointA);
polygon.addVertex(pointA);
polygon.addVertex(pointB);
polygon.addVertex(pointB);

polygon.update();

assertEquals(2, polygon.getNumberOfVertices());

while the following test fails:

Point2D pointA = EuclidCoreRandomTools.nextPoint2D(random, 10.0);
Point2D pointB = EuclidCoreRandomTools.nextPoint2D(random, 10.0);

FrameConvexPolygon2D polygon = new FrameConvexPolygon2D();
polygon.addVertex(pointA);
polygon.addVertex(pointB);
polygon.addVertex(pointA);
polygon.addVertex(pointB);

polygon.update();

assertEquals(2, polygon.getNumberOfVertices());

Something in the giftwrapping of the vertices is not functioning properly.

rjgriffin42 commented 6 years ago

This test additionally fails, which should pass. It is likely the cause of the other failure.


      for (int i = 0; i < ITERATIONS; i++)
      {
         Point2D pointA = EuclidCoreRandomTools.nextPoint2D(random, 10.0);
         Point2D pointB = EuclidCoreRandomTools.nextPoint2D(random, 10.0);
         List<Point2D> points = new ArrayList<>();
         points.add(pointA);
         points.add(pointB);
         points.add(pointA);
         points.add(pointB);

         int expectedHullSize = EuclidGeometryPolygonTools.inPlaceGiftWrapConvexHull2D(points, 4);
         assertEquals(2, expectedHullSize);
      }
SylvainBertrand commented 6 years ago

Ok thanks for the test, I'll work on a fix.

SylvainBertrand commented 6 years ago

Addressed in ed4cc900f5ef121370cae3494b8dd2dd71657224