Есть ли алгоритм, который может рассказать вам, какие точки для соединения, чтобы сформировать треугольник, заданный набором точек? Ни одна из соединительных линий не может пересекаться, однако треугольники могут быть внутри других треугольников.Учитывая набор точек, найдите максимальное количество треугольников
Я не уверен, что это именно то, что вы ищете, но это может иметь некоторую помощь: Graph Theory
Теория графов относится к абстрактной, невизуальной структуре. Хотя это можно сделать, рендеринг не влияет на базовый график. – Craig
Учитывая общий набор точек в R^dDelaunay triangulation часто является оптимальным выбором для тесселяции.
В частности, триангуляция Делоне будет тесселировать выпуклую оболочку набора точек в набор неперекрывающихся элементов, гарантируя, что радиус наибольшей окружности минимизирован - это означает, что триангуляция является оптимальной в терминах ее " компактность ", или, другими словами, генерируются элементы с хорошим соотношением сторон.
Эффективные алгоритмы построить Делоне триангуляции не являются тривиальными, но есть много хороших библиотек там - я могу рекомендовать Triangle, CGAL или Qhull (для высоких пространственных задач) также JDT, по-видимому реализация в Java, хотя я Он никогда не использовал его.
Я также пытаюсь решить эту проблему. This - это ссылка на ветку github того, кто работает над этим для игры Ingress, поэтому я заинтересован в решении. Однако, насколько мне известно, оптимальное решение обнаруживается с помощью грубой силы (возможно, я ошибаюсь) и имеет другие факторы, которые она максимизирует и сводит к минимуму. Также я думаю, что есть такие вещи, как принятие широты/долготы E6 и проекты на проекцию гномонов для определения кратчайших маршрутов, однако я думаю, что при просмотре кода это может быть уменьшено. Я не думаю, есть ваше решение в этом коде, но это может быть хорошим прыгающим пунктом для вас, меня и всех, кто смотрит на эту проблему.
Вы можете попробовать что-то, что выбирает ближайшую точку к краю набора данных, затем создает треугольник в двух ближайших точках, а затем повторяется. Это должно гарантировать, что в каких-либо созданных треугольника не будет смысла. – Craig