Кратко — идея: представить неизвестные вершины как координаты $v_i=(x_i,y_i)$, выписать уравнения, выражающие инварианты (углы, площади, барицентры, суммы углов вокруг внутренних вершин) и решить систему (линейную, если возможно, или нелинейную оптимизацией). Ниже — конкретные методы, формулы и замечания об разрешимости.
1) Общая модель (переменные)
- Переменные: $v_1,\dots ,v_n\in {\mathbb{R}}^2$.
- Для треугольника $(i,j,k)$: площадь $A_{ijk}=\frac{1}{2}|(v_j-v_i)\times (v_k-v_i)|$ где $(a,b)\times (c,d)=ad-bc$.
- Угол при вершине $i$ в треугольнике $(i,j,k)$: через скалярное произведение
$\cos {\theta }_i^{(ijk)}=\frac{(v_j-v_i)\cdot (v_k-v_i)}{\Vert v_j-v_i\Vert \Vert v_k-v_i\Vert }.$
2) Метод на основе барицентров треугольников (линейный плюс одна шкала)
- Для каждого треугольника $(i,j,k)$ барицентр $c_{ijk}=\frac{v_i+v_j+v_k}{3}$.
- Если известны все $c_{ijk}$ (или их измерения), это даёт линейные уравнения
$v_i+v_j+v_k=3c_{ijk}.$ - Количество уравнений: $2$ на каждый треугольник, итого $2(n-2)$. Число неизвестных координат: $2n$. Устранение трёх степеней свободы (сдвиг и поворот) даёт требуемые $2n-3$ условий, но у нас имеется только $2n-4$ — не хватает одной скалярной величины. Следствие:
- барицентры всех треугольников одни́м по себе определяют конфигурацию с одной дополнительной степенью свободы (например масштаб/ориентация знака площади);
- добавление одного числа (например суммарной площади полигона или одного ненайденного барицентра фиксирует решение).
- Алгоритм: решить разреженную линейную систему по $x$ и $y$ (фиксировать 3 DOF, напр., $v_1=(0,0),v_2=(1,0)$ и вращение), при необходимости подогнать масштаб через известную суммарную площадь $\sum A_{ijk}=A_{poly}$.
3) Использование площадей треугольников (полу‑линейно/нелинейно)
- Если известны площади всех треугольников $A_{ijk}$, то уравнения
$(v_j-v_i)\times (v_k-v_i)=\pm 2A_{ijk}$ дают нелинейные (квазилинейные по координатам) уравнения. Знак определяется ориентацией (из планарной встраиваемости).
- Комбинация барицентров и площадей даёт линейные уравнения для сумм координат плюс скалярные уравнения площадей — обычно достаточно для единственности (за изометрии).
- Практический подход: решить линейную систему от барицентров (получить пространство решений), затем подобрать масштаб/поворот/решение знаков площадей через малую систему скалярных уравнений — или сразу решать совместно методом наименьших квадратов.
4) Угловые суммы вокруг внутренних вершин (нелинейные уравнения, полезны при частичных длинах)
- Для внутренней вершины $i$ сумма углов всех прилегающих треугольников равна $2\pi$:
${\sum }_{t\ni i}{\theta }_i^{(t)}=2\pi .$ - Для граничной вершины сумма прилегающих внутренних углов равна внутреннему углу многоугольника (и в сумме по границе даёт $(n-2)\pi$).
- Углы выражаются через координаты или через длины сторон (закон косинусов):
$\cos \theta =\frac{b^2+c^2-a^2}{2bc}.$ - Если известны некоторые ребра длины, то эти уравнения связывают неизвестные длины; даются нелинейные условия, которые в сочетании с площадями/барицентрами могут обеспечить единственность.
5) Комбинация барицентров + углы/площади/частичные длины — практическая схема
- Шаг 1: извлечь из планарного триангуляционного графа структуру треугольников и границу.
- Шаг 2: собрать все линейные уравнения от барицентров (если известны) и зафиксировать 3 DOF (например задать $v_1,v_2$).
- Шаг 3: добавить скалярные уравнения: известные площади, сумма площадей (фиксирует масштаб), некоторые известные длины или углы.
- Шаг 4: решить систему методом наименьших квадратов (Levenberg–Marquardt) или последовательной линéarизации; если барицентры неизвестны, и есть только площади/длины — сразу решать нелинейную задачу по координатам.
- Инициализация: Тьюттово (Tutte) вложение или barycentric embedding даёт хорошее начальное приближение; затем уточнить по метрическим уравнениям.
6) Вопросы уникальности и требуемость дополнительных данных
- Граф триангуляции простого многоугольника (максимально внешне планарный) не является по умолчанию глобально жёстким в ${\mathbb{R}}^2$; поэтому одних лишь чисто комбинированных топологических связей обычно недостаточно.
- Требуются дополнительные метрические данные: достаточно, например, всех треугольных барицентров и суммарной площади (или всех площадей с ориентацией), либо достаточного набора длин ребер/диагоналей и/или углов.
- Количественный критерий: нужно не меньше чем $2n-3$ независимых скалярных условий (после удаления изометрий).
7) Практические рекомендации и устойчивость
- Использовать сначала все линейные инварианты (барицентры) для уменьшения размерности; далее решать нелинейную часть.
- Регуляризовать/штрафовать неконсистентности при шуме (Tikhonov или весовые штрафы).
- Проверять согласованность знаков площадей (ориентация) и поддерживать планарность (пересечения не допускаются).
- Если требуется гарантированная глобальная жёсткость, добавить контрольные длины (некоторые диагонали) до получения глобально-ригидного подграфа.
Короткое резюме: барицентры дают удобную линейную основу (но недоопределяют на одну величину), площади и суммы углов дают недостающие скалярные уравнения; в общем случае нужно решать совместную линейно‑нелинейную систему на координаты вершин с фиксированием трёх степеней свободы — практическая реализация через разрежённую линейную алгебру + нелинейную оптимизацию.