PHD Discussions Logo

Ask, Learn and Accelerate in your PhD Research

Question Icon Post Your Answer

Question Icon

How can one determine which sub-simplices a point belongs to in a simplex triangulation?

I'm working with simplicial complexes and fine triangulations for numerical analysis. Given a point in the parent simplex, I need a robust algorithm to determine its containing sub-simplex without exhaustive search. This is critical for interpolation and finite element methods, and I'm weighing approaches like barycentric coordinate checks.

 

All Answers (2 Answers In All)

By Kumar Answered 1 year ago

For implementation, I consistently recommend using normalized barycentric coordinates relative to the original simplex's vertices. Compute the coordinates of your point; they will be non-negative and sum to 1. The key is that the triangulation pattern (like Kuhn's) corresponds to a unique ordering or permutation of these coordinates at the grid scale 1/q. By sorting or comparing these coordinate values, you can directly map to the specific sub-simplex index without geometric searches. It’s computationally elegant and robust.

By Kushi Gupta Answered 8 months ago

For a simplex with vertices v(1), v(2), …, v(n+1) and a grid of size 1/q, triangulation divides the simplex into sub-simplices. A point belongs to a sub-simplex if it lies within its vertices’ convex combination. This can be checked using barycentric coordinates or geometric inclusion tests.

Your Answer