Stack overflow in FlipEdgeEvent and FlipScanEdgeEvent

[Arthr702]

Hi,

I am currently facing an issue with the delauney triangulation algorithm. In more than the most cases I got an valid mesh, but for the following points/ holes, I get an stack overflow:

1. Add the following points in the main function:

polyline.push_back(new Point(150.375000, 174.000000)); polyline.push_back(new Point(132.000000, 175.000000)); polyline.push_back(new Point(133.125000, 179.500000)); polyline.push_back(new Point(137.500000, 179.000000)); polyline.push_back(new Point(140.750000, 187.000000)); polyline.push_back(new Point(136.375000, 187.000000)); polyline.push_back(new Point(138.875000, 191.000000)); polyline.push_back(new Point(142.500000, 190.500000)); polyline.push_back(new Point(142.625000, 190.500000)); polyline.push_back(new Point(150.625000, 189.500000)); polyline.push_back(new Point(149.125000, 190.500000)); polyline.push_back(new Point(146.750000, 190.500000)); polyline.push_back(new Point(147.125000, 191.500000)); polyline.push_back(new Point(143.375000, 192.000000)); polyline.push_back(new Point(142.500000, 190.500000)); polyline.push_back(new Point(140.125000, 191.000000)); polyline.push_back(new Point(138.375000, 190.500000)); polyline.push_back(new Point(132.125000, 191.500000)); polyline.push_back(new Point(133.625000, 196.500000)); polyline.push_back(new Point(134.375000, 196.000000)); polyline.push_back(new Point(136.625000, 201.000000)); polyline.push_back(new Point(143.250000, 201.000000)); polyline.push_back(new Point(144.000000, 200.000000)); polyline.push_back(new Point(146.875000, 200.500000)); polyline.push_back(new Point(146.625000, 199.000000)); polyline.push_back(new Point(150.250000, 199.500000)); polyline.push_back(new Point(151.250000, 200.000000)); polyline.push_back(new Point(153.750000, 200.000000)); polyline.push_back(new Point(154.625000, 200.500000)); polyline.push_back(new Point(156.125000, 200.000000)); polyline.push_back(new Point(157.125000, 200.500000)); polyline.push_back(new Point(153.500000, 200.500000)); polyline.push_back(new Point(153.125000, 200.000000)); polyline.push_back(new Point(149.500000, 200.000000)); polyline.push_back(new Point(152.125000, 205.500000)); polyline.push_back(new Point(155.750000, 205.500000)); polyline.push_back(new Point(155.875000, 205.000000)); polyline.push_back(new Point(157.625000, 205.000000)); polyline.push_back(new Point(158.750000, 205.500000)); polyline.push_back(new Point(164.000000, 205.500000));

2. Add the following points as one hole:

vector<Point*> hole;

hole.push_back(new Point(145.000000, 196.500000));
hole.push_back(new Point(144.625000, 196.000000));
hole.push_back(new Point(142.250000, 196.000000));
hole.push_back(new Point(141.125000, 195.500000));
hole.push_back(new Point(141.875000, 195.500000));
hole.push_back(new Point(144.250000, 195.000000));
hole.push_back(new Point(144.375000, 194.500000));
hole.push_back(new Point(148.000000, 194.500000));
hole.push_back(new Point(148.625000, 194.500000));
hole.push_back(new Point(151.000000, 195.000000));
hole.push_back(new Point(152.750000, 195.000000));
hole.push_back(new Point(151.250000, 195.500000));
hole.push_back(new Point(148.875000, 195.500000));
hole.push_back(new Point(149.375000, 196.500000));

cdt->AddHole(hole);

3. Execute the program and it will crash because of an buffer overflow.

The algorithm seem to be looping between FlipScanEdgeEvent (else-case because InScanArea is always false) and FlipEdgeEvent (InScanArea is also always false) infinitly. Is it an bug or am I missing something with the input points?

[Arthr702]

I did some debugging into this strange error, and it has nothing to do with the hole points. It even crashes, when I delete the bottom lines. As said, the algorithm keeps looping between FlipScanEdgeEvent and FlipEdgeEvent. Unfortunately, line 725 in sweep.cc

Point& newP = NextFlipPoint(ep, eq, ot, op);

creates always the same point (142,5; 190,5 in this example), so it just always flips the edge points again and again.

[jhasse]

If you are given input and aren't sure same point exist twice you need to check for this yourself.

You're adding (142.500000, 190.500000) twice ;)

[Arthr702]

Dammit, you are right! Thanks a lot anyway for your time!