Fix isFlipNeeded

[artem-ogre]

Thank you for this PR @Islam0mar!

One remark:

if (iVert < 3 && iVopo < 3) // both traingles touch super-triangle

I think this is impossible as each super-triangle edge can only have one adjacent triangle (this is also mentioned in the paper by Žalik et al.)

I used the opportunity to re-factor isFlipNeeded function. Here's what I got:

/*!
 * Handles super-triangle vertices.
 * Super-tri points are not infinitely far and influence the input points
 * Three cases are possible:
 *  1.  If one of the opposed vertices is super-tri: no flip needed
 *  2.  One of the shared vertices is super-tri:
 *      check if on point is same side of line formed by non-super-tri vertices
 *      as the non-super-tri shared vertex
 *  3.  None of the vertices are super-tri: normal circumcircle test
 */
template <typename T, typename TNearPointLocator>
bool Triangulation<T, TNearPointLocator>::isFlipNeeded(
    const V2d<T>& v,
    const TriInd iT,
    const TriInd iTopo,
    const VertInd iV) const
{
    /*
     *                       v3         original edge: (v1, v3)
     *                      /|\   flip-candidate edge: (v,  v2)
     *                    /  |  \
     *                  /    |    \
     *                /      |      \
     * new vertex--> v       |       v2
     *                \      |      /
     *                  \    |    /
     *                    \  |  /
     *                      \|/
     *                       v1
     */
    const Triangle& tOpo = triangles[iTopo];
    const Index i = opposedVertexInd(tOpo, iT);
    const VertInd iV2 = tOpo.vertices[i];
    const VertInd iV1 = tOpo.vertices[cw(i)];
    const VertInd iV3 = tOpo.vertices[ccw(i)];
    const V2d<T>& v1 = vertices[iV1];
    const V2d<T>& v2 = vertices[iV2];
    const V2d<T>& v3 = vertices[iV3];
    if(m_superGeomType == SuperGeometryType::SuperTriangle)
    {
        // If flip-candidate edge touches super-triangle in-circumference test
        // has to be replaced with orient2d test against the line formed by two
        // non-artificial vertices (that don't belong to super-triangle)
        if(iV < 3) // flip-candidate edge touches super-triangle
        {
            // does original edge also touch super-triangle?
            if(iV1 < 3)
                return locatePointLine(v1, v2, v3) ==
                       locatePointLine(v, v2, v3);
            if(iV3 < 3)
                return locatePointLine(v3, v1, v2) ==
                       locatePointLine(v, v1, v2);
            return false; // original edge does not touch super-triangle
        }
        if(iV2 < 3) // flip-candidate edge touches super-triangle
        {
            // does original edge also touch super-triangle?
            if(iV1 < 3)
                return locatePointLine(v1, v, v3) == locatePointLine(v2, v, v3);
            if(iV3 < 3)
                return locatePointLine(v3, v1, v) == locatePointLine(v2, v1, v);
            return false; // original edge does not touch super-triangle
        }
        // flip-candidate edge does not touch super-triangle
        if(iV1 < 3)
            return locatePointLine(v1, v2, v3) == locatePointLine(v, v2, v3);
        if(iV3 < 3)
            return locatePointLine(v3, v1, v2) == locatePointLine(v, v1, v2);
    }
    return isInCircumcircle(v, v1, v2, v3);
}

Could you take another look at it and it it's fine could you put this into your PR, so that I can merge it?

[artem-ogre]

Also could you please add this new test file to visualizer/data folder: issue-65-wrong-edges.txt

[Islam0mar]

Done! You are absolutely right about (iV < 3 && iV2 < 3). Should I squash commits?

[artem-ogre]

Thanks, @Islam0mar

[Islam0mar]

You are welcome and thanks for sharing this great library :+1: