Generated triangles use point out of bounds

[icedevelopment]

In particular configurations the generated triangles use the SweepContext::head and SweepContext::tail points in the final triangles list. These points are out of bound.

Here is the smallest test case I have found.

#include <iostream>
#include "poly2tri/poly2tri.h"

int main() {
  // Fill contour
  std::vector < p2t::Point * > contourPoints;

  contourPoints.push_back(new p2t::Point(0, -1200));
  contourPoints.push_back(new p2t::Point(0, -2600));
  contourPoints.push_back(new p2t::Point(-2280, -2600));

  p2t::CDT myCDT(contourPoints);

  // Add steiner points
  std::vector < p2t::Point * > steinerPoints;

  steinerPoints.push_back(new p2t::Point(0, -2560));
  myCDT.AddPoint(steinerPoints.back());

  // Launch triangulate
  myCDT.Triangulate();

  // Check the result
  auto Triangles = myCDT.GetTriangles();
  auto triangleIt(Triangles.cbegin());
  auto endIt(Triangles.cend());

  auto xMin(-2280), xMax(0);
  auto yMin(-2600), yMax(-1200);
  size_t triangleIndex(0), triangleCount(Triangles.size());

  std::cout << "Triangles count: " << triangleCount << "\n";

  auto CheckValidity = [ & ](p2t::Point * pPoint) {
    if (pPoint -> x < xMin || pPoint -> x > xMax || pPoint -> y < yMin || pPoint -> y > yMax) {
      std::cout << "!!! Point out of bound x " << pPoint -> x;
      std::cout << " y " << pPoint -> y << "\n";
    } else {
      std::cout << "Point in bound x " << pPoint -> x;
      std::cout << " y " << pPoint -> y << "\n";
    }
  };

  for (triangleIndex = 0; triangleIndex < triangleCount; ++triangleIndex) {
    std::cout << "Triangle index " << triangleIndex << "\n";
    auto pTriangle(Triangles[triangleIndex]);

    CheckValidity(pTriangle->GetPoint(0));
    CheckValidity(pTriangle->GetPoint(1));
    CheckValidity(pTriangle->GetPoint(2));
  }
}

Did I miss something?

[Kimbatt]

I also encountered this issue, managed to narrow it down: this issue only happens if there is a steiner point on a boundary edge, and the point is sorted in a specific way internally so that in the Sweep::EdgeEvent function, the if (o1 == COLLINEAR) { ... branch is entered. If the other branch, if (o2 == COLLINEAR) { ... is entered, then it works fine.

Some examples:

1) Bad triangulation Input points: (1, 3) (3, 3) (3, 1) Steiner point: (3, 2)

2) Good triangulation Input points: (1, 3) (3, 3) (5, 3) (3, 1) Steiner point: (3, 2)

3) Good triangulation Input points: (1, 3) (3, 3) (5, 3) (3, 1) Steiner point: (2, 2)

4) Bad triangulation Input points: (1, 3) (3, 3) (5, 3) (3, 1) Steiner point: (4, 2)