Implement a query function

[Debitsch]

I want to implement a simple query function on a finalized triangulation. The function should find a triangle for a given point. The triangle will be used for a interpolation. E.g. of a z coordinate.

Is it possible to make the walkTriangles function public?

Thanks
Rasmus

[artem-ogre]

Hello, Rasmus @Debitsch

It will be tricky to expose walking triangles, so I personally prefer to keep it as an implementation detail to minimize the risk of misuse.

• If triangulation is finalized with eraseXXX method, walking the triangles will not work anymore (because there now can be gaps in the triangulation).
• To find a nearest point for the arbitrary query point (where triangle walk starts from) nearest point locator needs to be initialized with tryInitNearestPointLocator. By default it is not initialized during the first insertVertices call because it uses a clever breadth-first traversal of a Kd-tree for initial bulk-load.

I don't know your problem in detail, but maybe you could instead insert triangles of a finalized triangulation into a space-partitioning data structure (e.g., k-d tree, R-tree or Octree). You could then quickly find triangles hit by a point using orient2d predicate. This would enable an efficient triangle lookup without exposing too much of CDT guts. What do you think?

[Debitsch]

Hello Artem, thank you for the explantion. My app should follow a mouse cursor over a triangulation and display the height (stored in custom vertices). I will not delete any triangles. Therefore there are no holes or islands and the triangle walk should work. And there will be a very good start triangle for the search in most cases. But I see your point and will try one of your solutions. I want to precompute the triangulation and store it somehow. So I have to find a suitable data structure for storing the result anyway. Thanks Rasmus From: Artem Amirkhanov Sent: Tuesday, November 7, 2023 10:51 AM To: artem-ogre/CDT Cc: Debitsch ; Mention Subject: Re: [artem-ogre/CDT] Implement a query function (Discussion #157) Hello, Rasmus @Debitsch It will be tricky to expose walking triangles, so I personally prefer to keep it as an implementation detail to minimize the risk of misuse. a.. If triangulation is finalized with eraseXXX method, walking the triangles will not work anymore (because there now can be gaps in triangulation). b.. To find a nearest point for the arbitrary query point (where triangle walk starts from) nearest point locator needs to be initialized with tryInitNearestPointLocator. By default it is not initialized during the first insertVertices call because it uses a clever breadth-first traversal of a Kd-tree for initial bulk-load. I don't know your problem in detail, but maybe you could instead insert triangles of a finalized triangulation into a space-partitioning data structure (e.g., k-d tree, R-tree or Octree). You could then quickly find triangles hit by a point using orient2d predicate. This would enable an efficient triangle lookup without exposing too much of CDT guts. What do you think? — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.Message ID: ***@***.***>