Как построить выпуклый многоугольник по известным связям вершин?
Есть некоторый список ребер между вершинами:
Например: [{A,B}, {B,C}, {C,A}]
Известно что длина каждого рёбра такого многоугольника должна стремиться к некоторой величине L. Т.е. быть может больше, или меньше -- но все же где то в тех районах )
Так вот, требуется по данной записи найти координаты вершин такого многоугольника, который бы был бы "максимально" выпуклым (где это возможно). Понятное дело, что решений удовлетворяющих такому условию может быть бесконечно много. Но с учетом всех поворотов, скорее всего оно всегда одно. Как его найти ?
Примеры записи:
[{A,B}, {B,C}, {C,A}] - равносторонний треугольник с длиной стороны L
[{A,B}, {B,C}, {C,D}, {D,A]] - квадрат c длиной стороны L.
[{A,B}, {B,C}, {C,D}, {D,E], {E,A}] - 5ти угольник с длиной стороны L.
[{A,B}, {B,C}, {C,D}, {D,E], {E,A}, {C,A}] - равносторонний треугольник соединенный с квадратом по одному из рёбер.
Можно взять, построить физическую модель отталкивания зарядов со связями в виде пружин, и итеративно придти к решению (которое может не удовлетворять начальным условиям). А что еще можно придумать тут ?
У вас есть набор вершин и ребер, по сути это неориентированный граф.
1. Координаты вершин фиксированы?
2. Могут ли исходные ребра пересекаться не в вершинах (планарный ли исходный граф)?
3. Нам нужно выбрать подмножество ребер, такое что они образуют максимально выпуклую фигуру?
4. Критерий минимальности для невыпуклости известен? Тут можно пробовать разные подходы. Например разность площадей с выпуклой оболочкой или количество/средний/максимальный диаметр "дырок".
5. Важно ли найти наибольший многоугольник или прото выпуклый? Если нужно выбирать между маленьким но выпуклым или побольше но с дырками?
6. Могут ли в ответе быть пересечения ребер?
tsarevfs,
1. Координаты одного из таких многоугольников требуется найти.
2. Могут
3. Скорее нужно максимизировать площадь под такой фигурой. Рёбра в общем случае могут пересекаться, т.к. это произвольная фигура.
4. Переиначил: на максимальную площадь фигуры при скорее всего минимальном периметре. Длины ребер как можно более приближаются к L.
5. Думаю ответил в 4.
6. Могут.
