Locate triangle containing point (Make walkTriangles public?)

[robinchrist]

Love this library, great work!

Would it be possible to add a function to locate the triangle containing an arbitrary point?

I think this functionality already exists in function walkTriangles, but this function is not public.

Are there any strong reasons for not making this function public?

[artem-ogre]

Hi, @robinchrist,
Thank you for creating the issue.

The reason for hiding this functionality is that finding such triangle does not always come for free. Let me try to explain.

walkTriangles takes the vertex index to start the walk from (startVertex).
CDT uses KD-tree for finding the nearest point but it skips creating the tree for the first bulk of points added with insertVertices when vertex insertion order is Auto.

There are several ways to implement your request but none are straight-forward:

1. Call tryInitNearestPointLocator to create the tree. This will add an overhead on the first call.
2. Implement getting the near point for the first bulk relying on KD-tree internally constructed in insertVertices_KDTreeBFS. This means we need to keep that tree in memory and implement getting the nearest point code for this kind of tree.

First approach is easier to implement but has an overhead of constructing KD-tree after the triangulation is built.
Second approach is harder to implement, will not have runtime overhead, but will have some memory overhead as Triangulation will need to store at least the bounding box and the vector of vertex indices:

KDTreeData_from_insertVertices_KDTreeBFS
{
    Box2d<T> box;
    std::vector<VertInd> vertex_indices;
};

Please let me know if you have questions to this explanation.

[robinchrist]

Wouldn't the better option to let the user decide?

As far as I can say walkTriangles does not use the NearestPointLocator internally, it's only fed with a result from the NearestPointLocator as start vertex in common usage in the library.
So there is no inherent overhead from exposing or using walkTriangles?

The user could decide between
a) Construct the kd tree via tryInitNearestPointLocator and use it to accelerate walkTriangles by giving a good start triangle
b) Feed walkTriangles with a startTriangle determined by some other means, potentially slow

This would mean exposing:

• walkTriangles
• tryInitNearestPointLocator
• m_nearPtLocator

Are there any reasons to not make these public?

[artem-ogre]

The methods are private because they contain implementation details that I want to be able to change without affecting the public API. While exposing walkTriangles would be straightforward, it's not directly usable without a starting vertex.

What is your use case?
Do you actually need:

TriInd walkTriangles(const VertInd startVertex, const V2d<T>& pos);

or do you need:

array<TriInd, 2> locateTriangles(const V2d<T>& pos);

[robinchrist]

While exposing walkTriangles would be straightforward, it's not directly usable without a starting vertex.

I think that’s the least problem.

What is your use case?

I need locateTriangle but ideally with the addition of getting the closest triangle (last triangle in the walk) when the point is outside the mesh

[artem-ogre]

Looks like your case is very specific, so I don't think it makes sense to change public API for it.
But I have another suggestion. What if I add a cmake/pre-processor flag CDT_MAKE_IMPLEMENTATION_DETAILS_PUBLIC and do:

#ifdef CDT_MAKE_IMPLEMENTATION_DETAILS_PUBLIC
public:
#else
private:
#endif
    /*____ Detail __*/

It goes without saying that you'd need to opt-in 😉

What do you think?