Есть нерегулярная триангуляция плоской области произвольной формы с произвольным количеством дырок опять таки произвольной формы. Она задана массивом точек (углов треугольников) и массивом треугольников (каждый из которых содержит три индекса образуюсчих точек). Их менять нельзя (либо надо иметь очень весомые аргументы).
На плоскость бросается точка. Надо быстро определить к какому треугольнику она принадлежит или сказать, что она вне области.
Треугольников много и искать надо часто. Как ето сделать побыстрее?
Пока единственное что приходит на ум -- ето покрыть область гридом и в каждой ячейке хранить индексы треугольников, которые пересекают её. Когда надо найти треугольник, то вначеле надо найти ячейку, а потом проверить все её треугольники. Но такой подход кажется все-таки не оптимальным ни в терминах памяти ни в терминах производительности.
