Примечание: я очень опытный программист, а не математик. Это станет очевидным очень быстро.
Предположим, у меня ограниченное n-мерное пространство - например, здесь я буду использовать n = 2. В этом пространстве у меня есть набор предопределенных точек. (Как это происходит, я делаю что-то сомнительное с алгоритмами Geneti c для нахождения минимумов в нематематически разрешимых уравнениях, но это не имеет прямого отношения).
Далее, я определил новую точку в это 2D пространство. Я хочу знать, какие три (n + 1) точки образуют наименьший (или, возможно, ближайший?) Треугольник, который содержит эту точку. Иллюстрация здесь:
Теперь, как показывает эта иллюстрация, я не совсем уверен в том, что я делаю, потому что я не смог адекватно описать критерии, по которым оцениваются потенциальные треугольники - например, точки 10, 5 и 8 будут заключать точку в треугольник меньшей площади. Это потому, что эти особенности несколько гибки. Что меня действительно волнует, так это:
- Эффективность вычислений: потенциально я мог бы в конечном итоге масштабировать этот алгоритм до тысяч точек в сотне измерений. Поэтому мне нужно решение, которое лучше, чем исчерпывающее тестирование каждой потенциальной выпуклой оболочки в соответствии с конкретным уравнением c, а в идеале - с приличной системой обозначений big-O. Предположительно мне понадобится более интеллектуальная структура, чем большой неупорядоченный список, чтобы сделать это.
- Если у меня были предпочтительные критерии, это близость вершин корпуса к контрольной точке. Однако, если проще построить алгоритм, который судит по площади / объему или чему-то еще, я могу с этим смириться.
- Мне нужно иметь возможность обрабатывать крайние случаи, где есть контрольная точка для Например, на границе между двумя вершинами.
С чего мне вообще начинать? Некоторые беглые поиски в Google показывают, что диаграммы Вороного могут быть шагом в правильном направлении, верно? Каковы правильные инструменты для этой работы? Любая помощь будет принята с благодарностью.