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

Вы используете Internet Explorer устаревшей и не поддерживаемой более версии. Чтобы не было проблем с отображением сайтов или форумов обновите его до версии 7.0 или более новой. Ещё лучше - поставьте браузер Opera или Mozilla Firefox.

Обсудить и задать вопросы можно в этой теме.

• 1
• Ответить на сообщение

Balancer> Есть точки, составляющие выпуклый многоугольник. Они перемешаны случайным образом. Как отсортировать их так, чтобы их последовательность описывала выпуклый многоугольник? Balancer> Например, из: Balancer> 0,0 Balancer> 0,10 Balancer> 10,0 Balancer> 10,10 Balancer> получить: Balancer> 0,0 Balancer> 10,0 Balancer> 10,10 Balancer> 0,10

1. Определяем в наборе 4 точки - самую нижнюю, левую, верхнюю, правую 2. проверяем эти 4 точки на совпадения - точка одновременно может быть например и самой нижней и самой правой. 3. из выбранных точек строим двух, трёх или четырёхугольник. 4. оставшиеся точки проверяем на выход за грани получившегося многоугольника - выходит за грань - вставляем точку в многоугольник между вершинами этой грани. Т.к. по условию задачи точки принадлежат выпуклому многоугольнику, то никаких неоднозначностей здесь не будет 5. повторяем пока не кончатся точки

P.S. можно было бы ограничиться пунктами 3, 4, 5 начав с произвольных двух точек, но так немного побыстрее

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

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

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

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

• 4
• Ответить на сообщение

• 3
• Ответить на сообщение

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

Уже сама постройка будет факториальной сложности. Т.е. если даже если она (постройка) и позволит нам сделать, скажем, алгоритм сложности N (а она не позволит), то сам факториальный механизм постройки все испортит.

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

Хм. моё утверждение сводится к предположению, что для множества точек находящихся внутри многоугольника обязательно найдется такая, которая образует треугольник с его гранью так, что внутрь этого треугольника не попадает ни одна из других точек. Доказать этого моя макитра сейчас не может, но что это так "нутром чую" (С)

P.S. Если внутрь треугольника попала точка, то надо проверять её. Верхний цикл делать по рёбрам. Вот тут "нутром чую", что сложность будет N * N * sqrt(N)

• 2
• Ответить на сообщение

haleev> Хм. моё утверждение сводится к предположению, что для множества точек находящихся внутри многоугольника обязательно найдется такая, которая образует треугольник с его гранью так, что внутрь этого треугольника не попадает ни одна из других точек. Доказать этого моя макитра сейчас не может, но что это так "нутром чую" (С)

Я просто не понял вас сначала. В таком изложении - реализуется. Но такой метод приведет нас к "звездам", которые совсем и близко не будут максимальной площади. Более того - к минимальной будут ближе.

ЗЫ Алгоритмы, основанные на максимальном выпуклом подмножестве уже высказывались.

• 1
• Ответить на сообщение

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

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

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

• 2
• Ответить на сообщение

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

Вот тут хороший пример - я не додумался до этих стен с вершинами в 0 и в 10. Сложно биологическим разумам оценить где площадь больше - в длинном узком треугольнике или в коротком, но "полном". И кучу разбиений оценить сложно.

>>Требование площади приводит к тому, что машина проводит длинные узкие "стены" через весь многоугольник. AidarM> Что и херит аналогии с кругом. Непонятно, как сравнивать угловатость 2х фигур. Площадь хотя бы считать легко.

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

haleev>> Хм. моё утверждение сводится к предположению, что для множества точек находящихся внутри многоугольника обязательно найдется такая, которая образует треугольник с его гранью так, что внутрь этого треугольника не попадает ни одна из других точек. Доказать этого моя макитра сейчас не может, но что это так "нутром чую" (С) Сергей-4030> Я просто не понял вас сначала. В таком изложении - реализуется. Но такой метод приведет нас к "звездам", которые совсем и близко не будут максимальной площади. Более того - к минимальной будут ближе. Сергей-4030> ЗЫ Алгоритмы, основанные на максимальном выпуклом подмножестве уже высказывались.

Нет он не приведёт к звёздам т.к. рёбра получившиеся после вырезания треугольника тоже участвуют в процессе. Интересно что получится если выбирать для вырезания самый маленький треугольник. Да, и возможны варианты когда звезда - максимальная по площади фигура.

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

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

N 4 ) является по сути словариком матерн. запрещенных фигур. N 4 тоже не сахар, конечно.

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

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

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

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

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