Triangle search algorithm

[helviett]

Your search algorithm (crossing the dividing edge) requires triangulation to be delaunay (not constrained delaunay). But you can use stochastic walk instead of using data structure to store visitted.

[artem-ogre]

Hello, yes, I'm aware of this limitation.

The triangulation should be created by first inserting vertices followed by edge (constraints) insertion. So when inserting vertices the triangulation is Delaunay.

So as you mentioned inserting vertices in constrained triangulation is not supported. But there is also another reason for that: when inserting vertices edges are flipped to ensure Delaunay property. And the algorithm does not currently handle constraints at this point.

[helviett]

Alright, wasn't sure that your implementation is for offline use only so decided to point out potential issue. I have halfe edge delaunay triangulation implementation that can perform operations in runtime and had to deal with that kind of issues.

[artem-ogre]

Please disregard my previous message.
I double-checked and we use a remembering stochastic walk.
So it should work with arbitrary triangulations.

Here's the code

template <typename T>
TriInd Triangulation<T>::walkTriangles(
    const VertInd startVertex,
    const V2d<T>& pos) const
{
    // begin walk in search of triangle at pos
    TriInd currTri = vertices[startVertex].triangles[0];
#ifdef CDT_USE_BOOST
    TriIndFlatUSet visited;
#else
    TriIndUSet visited;
#endif
    bool found = false;
    while(!found)
    {
        const Triangle& t = triangles[currTri];
        found = true;
        // stochastic offset to randomize which edge we check first
        const Index offset(detail::randGen() % 3);
        for(Index i_(0); i_ < Index(3); ++i_)
        {
            const Index i((i_ + offset) % 3);
            const V2d<T> vStart = vertices[t.vertices[i]].pos;
            const V2d<T> vEnd = vertices[t.vertices[ccw(i)]].pos;
            const PtLineLocation::Enum edgeCheck =
                locatePointLine(pos, vStart, vEnd);
            if(edgeCheck == PtLineLocation::Right &&
               t.neighbors[i] != noNeighbor &&
               visited.insert(t.neighbors[i]).second)
            {
                found = false;
                currTri = t.neighbors[i];
                break;
            }
        }
    }
    return currTri;
}

Flipping a fixed edge could still be a problem. How does your implementation handle this?

[helviett]

I track what edges are constrained. Constrained edges are not getting flipped. You can play with Spine. They use CDT to interactively create meshes.

[artem-ogre]

Thanks. If it's just this single check then it should be really easy to add.

[artem-ogre]

#44
Fix for not flipping fixed edges is merged to master.