Randomly Incremental Approach for Delaunay Triangulation degenerated case 4 don't behave properly

Question

I am trying to implement the algorithm given in (1) for get a Delaunay Triangulation of a set of points, but I get stuck when I try it to handle degenerated cases. First at all, I implement an approach presented by Glenn Eguchi at The 6.838 Computational Geometry October 11, 2001 since this procedure use three starting point instead of the two proposed in the book and is more easy to handle the searching over the directed acyclic graph that stores the triangles. On the other hand, the explanation given in the book about how to handle the points belonging to the additional triangles is a little tricky and I don't understand at all.

Well, the problem is that according to this approach at the start of the procedure it is necessary to handle such case that has as vertices of the triangle any of the bounding points added to the original set of points given as result four degenerated cases:

Case 1) Indices i and j are both negative.

• (pi,pj) is an edge of the bounding triangle
• (pi,pj) is legal, want to preserve edges of bounding triangle

Case 2) Indices i, j, k, and l are all positive.

• This is the normal case.
• (pi,pj) is illegal iff pl lies inside the circumcircle of (pi,pj,pk)

Case 3) Exactly one of i, j, k, l is negative

• We don’t want our bounding triangle to destroy any Delaunay edges.
• If i or j is negative, pipj is illegal.
• Otherwise, pipj is legal.

Case 4) Exactly two of i, j, k, l are negative.

• k and l cannot both be negative (either pk or pl must be pr)
• i and j cannot both be negative
• One of i or j and one of k or l must be negative
• If negative index of i and j is smaller than negative index of k and l, (pi,pj) is legal.
• Otherwise (pi,pj) is illegal.

The three starting points proposed are:

• p-1 = (3M, 0)
• p-2 = (0, 3M)
• p-3 = (-3M, -3M)

M = maximum absolute value of any coordinate of a point in P

More additional help could be found here

References:

(1) De Berg, M., Van Kreveld, M., Overmars, M., & Schwarzkopf, O. C. (2000).Computational geometry (pp. 1-17). Springer Berlin Heidelberg.

I give you a simple test cases that don't behave properly if I put case 4 at the algorithm. The reason is that if I include such case then when I only have two points added from the set of points no is possible to find an edge that hold any of the legal parts of the above cases after it find an illegal edge due to case 4. For now, I remove this case of my implementation and the algorithm works, but I suppose that the algorithm is not finished if I not include this case because is important for some set of points. I still working in find it:

3 
0 0
4 0
0 4

First line, the number of points given. Then, the x and y coordinates of each point per line. The order of the inserted points (this is important, since in this approach the points are inserted randomly) is the following (0,4) -> (0,0) -> (4,0).

This is the function legalizeEdge that I have implemented, the lines commented belong to case 4:

/* Take into account that the symbolical points at the bounding triangle
* could be part of the edges to legalize */
void legalizeEdge(point pr, seg s) {
    bool ill = 0;
    int fn = 0, sn = 0;
    pair<int, int> adj = Q[s];
    point pl =
            contain(nodes[adj.first].t, pr) ?
                    getPoint(nodes[adj.second].t, s) :
                    getPoint(nodes[adj.first].t, s);

    if (s.first == p_1 || s.first == p_2 || s.first == p_3) {
        fn = s.first == p_3 ? -3 : s.first == p_1 ? -1 : -2;
        if (s.second == p_1 || s.second == p_2 || s.second == p_3) {
            return; // Case 1: is always legal
        }
    }

    if (s.second == p_1 || s.second == p_2 || s.second == p_3) {
        fn = s.first == p_3 ? -3 : s.first == p_1 ? -1 : -2;
    }

    if (pl == p_1 || pl == p_2 || pl == p_3) {
        // Case 4: both either(i,j) and l must be negative
        /*sn = pl == p_1 ? -3 : pl == p_1 ? -1 : -2;
        if(!fn) {
            return; // Case 3: is legal only when i or j are not negative
        }
        else if (fn < sn)
            return; // if min(i,j) < l
        else
            ill = 1;*/
        return;
    } else if(fn) {
        ill = 1; // Case 3 read above
    }

    if (ill || inCircle(pr, s.first, s.second, pl)) { // is illegal
        // Case 2 or illegal Case 3
        seg news;
        int firstt, secondd;
        pair<int, int> nadj;
        point pj = s.first, pi = s.second;

        // replace s(pj,pi) with s(pr,pl) flip edge!!!

        firstt = contain(nodes[adj.first].t,pl) ? adj.first:adj.second;
        secondd = firstt == adj.first ? adj.second:adj.first;

        Q.erase(s);
        news = getSeg(pr,pl);
        insTrang(pr, pj, pl), nadj.first = IDX,
        nodes[adj.first].son.push_back(IDX), nodes[adj.second].son.push_back(
        IDX);

        updateMap(pl,pj,firstt);
        updateMap(pr,pj,secondd);

        insTrang(pr, pl, pi), nadj.second = IDX,
        nodes[adj.first].son.push_back(IDX), nodes[adj.second].son.push_back(
        IDX);

        updateMap(pi,pr,secondd);
        updateMap(pi,pl,firstt);

        Q[news] = nadj;

        seg sa = getSeg(pi,pl);
        legalizeEdge(pr, sa);

        seg sb = getSeg(pj,pl);
        legalizeEdge(pr, sb);
    }
}

Thanks in advance.