Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек.

Mishka>Только комбинаций из них опять факториал. Из каждой пары пересекающихся ребер нужно выбрать одно, но это одно может отвалить много других ребер из данной вершины. А, вот, если уберем другое, то это множество может остаться — какое продолжение выберем?
А я откуда знаю? Идея Сергея-4030 состоит в том, чтобы перебирать все, но прекращать работу с неподходящими на достаточно раннем этапе (если повезет). Т.е. он при постройке анализирует, не грозит ли ему слепить самопересекающееся чудо. А я просто предложил часть важной для такого анализа инфы запасти заранее.

Блин, интуиция орет, что так мы все возможные односвязные Nугольники переберем, но в фоновом режиме ничего в голову не приходит насчет как доказать. Попробую сконцентрироваться именно на этом позже. Или пускай кто-нить опровергнет. Уж очень заманчиво, подозрительно прямо.

AidarM>Блин, интуиция орет, что так мы все возможные односвязные Nугольники переберем,
Врет, собака. Адназначна. ИМХО не в ту степь ударился.

2 haleev
Условия задачи изменились. Исходную - решили.

В общем, вчера вечерком было нечего делать и мою идею я имплементировал. Результат такой - до 9 точек (на моей машине) делается меньше секунды. 12 точек - от 5 до 15 секунд. 14 точек - от 30 до 90 секунд. Что, кстати, радует - вроде как, зависимость все-таки уже не факториальная получается! Вот такие пироги. Если кому интересно - скидываю тексты. Документировать не буду, лень, и так три часа убил.

ЗЫ Машина иногда очень оригинально расставляет точки дабы максимизировать площадь.

Тут выложу исходники. Запускать класс samples.polygons.ui.Sketch

Звиняюсь
Туплю, туплю... Голова садовая.
С пяти утра на ногах. Если полигон без взаимопересечений, то можно сначала построить из подмножества точек выпуклый многоугольник, а потом, перебирая оставшиеся точки отрезать от этого выпуклого многоугольника треугольники. Сложность получится... ээээ... N*N*N
треугольник отрезаем, если в него не попадает ни одна из оставшихся точек. Если отсортировать точки по какой-либо оси или скажем по расстоянию от центра многоугольника, то можно получить некоторый прирост в скорости.

остальные исходники

еще исходники

Кстати, после экспериментов с программкой мне показалось, что критерием лучше делать не наибольшую площадь, а наименьшую угловатость. Требование площади приводит к тому, что машина проводит длинные узкие "стены" через весь многоугольник.

Кстати, насчет того, как наш мозг такие задачи решает. Не знаю у кого как, а мой при количестве точек>10 не справляется. Т.е. замкнутую площадь я построить могу, а вот чтоб максимальную площадь - не догоняю иногда. Впрочем, мой мозг невыдающийся в смысле геометрии и чисел, так что не показатель.

Сергей-4030>после экспериментов с программкой мне показалось, что критерием лучше делать не наибольшую площадь, а наименьшую угловатость.
Не понимаю. Про максимум площади - так Balancer задал. А насчет угловатости - вроде бы логично для плавных замкнутых кривых, т.к. это на дальнем фоне где-то стыкуется с максимальностью площади круга при заданной длине окружности. Но только у нас длина никак не лимитирована, и линии строго прямые.

>Требование площади приводит к тому, что машина проводит длинные узкие "стены" через весь многоугольник.
Что и херит аналогии с кругом. Непонятно, как сравнивать угловатость 2х фигур. Площадь хотя бы считать легко. Правда, по окончанию постройки, а не в процессе. А машина же ответ находит таким, с узкими стенами! Кстати, если узких стен всего 2, в смысле, одна точка такая особенная, то такой многоугольник способнен построить и тот навязший у меня в мозгах алгоритм про вращение башкой в одну сторону. Когда начало координат на эту точку придется.

>Кстати, насчет того, как наш мозг такие задачи решает.
Ага, я тогда поторопился с ответом. Какие-то варианты мы упускаем при поиске, и непонятно, по какому критерию отсев идет.

Или вот такая фигура. Когда машина нарисует - уже все понятно. А до того - хрен поймешь.

А вот такие козябры получаются если искать минимальную площадь вместо максимальной.

А вот такая примерно разница между максимальной и минимальной площадью на одном и том же наборе. Максимальный многоугольник - серый, минимальный - красный контур.

А вот ишшо прикольный образец творчества силиконового разума.

Cергей-4030>Это такая структура, которая имеет данную площадь при наименьшем - что? Правильно, при наименьшем периметре. Если поставить целевой функцией минимизацию периметра, "стены" уходят и все многоугольники получаются очень "человеческими" (см. вложение).
Да, если просто поиграть хочется, то конечно и с таким условием очень интересно играть. Вряд ли нас модеры обругают, если мы тему так поменяем.

Однако и задача от Balancer-а может стать насущной. Я пока играю с ней.
Текущие мысли примерно такие. В полном графе для N вершин имеем N(N-1)/2 ребер.
Значит, можно построить новый граф. Ребра старого - его точки. А ребра нового - пересечения старых. Таким образом, имея в исходном условии запрет на самопересечения, матрица смежности нового графа (размерчиком (N(N-1)*N(N-1)/4-N(N-1)/2)/2-> ~N⁴ ) является по сути словариком матерн... запрещенных фигур. N⁴ тоже не сахар, конечно.

ИМХО алгоритм проверки на пересечение (при условии целочисленности координат) тоже можно сделать полностью целочисленным.

Сразу ясно, что словарик избыточен, т.к. описывает полный граф. Но что делать, и как оптимизировать алгоритм в этой части, я пока не знаю.

Идея-то все та же, на максимально более раннем этапе отсеять самопересекающиеся замкнутые ломаные.

При постройке каждого из (N-1)!/2 многоугольников мы смотрим по словарику, нет ли в его наборе пересекающихся ребер. Если так дубово подойти, то все ускорение сведется к тому, что мы последовательно для каждого ребра просматриваем, нет ли хотя бы одного ненулевого элемента над главной диагональю по индексам, соответствующим остальным ребрам.

Но на самом-то деле, зная о факте пересечения какой-то конкретной пары ребер, из списка разрешенных фигур вылетает нафиг целый класс, содержащий эту пару. Сколько в этом классе фигур замкнутых ломаных, проходящих через все точки, ИМХО можно прикинуть. Но главное - надо придумать так организовать цикл, перебирающий эти (N-1)!/2 ломаных, чтобы из рассмотрения наиболее естественно исключались классы ломаных, а не отдельные штуки. ИМХО, в случае успеха это грозит сведение сложности задачи к полиномиальной.

я чувствовал, что будут грабли со слабоформализованной задачей.
и вот - работы Сергей-4030 показывают выпуклые многоугольники с глубокими разрезами.