-
Сергей-4030: Все сообщения за 27 Апреля 2007 года
| Пн | Вт | Ср | Чт | Пт | Сб | Вс |
|---|---|---|---|---|---|---|
| 1 | ||||||
| 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| 23 | 24 | 25 | 26 | 27 | 28 | 29 |
| 30 |
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 20:06 
ЗЫ Машина иногда очень оригинально расставляет точки дабы максимизировать площадь.
инфо
инструменты
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 20:08
XPoint.java (скачать)
[915 Б]
XLine.java (скачать)
[3,2 кБ]
Это сообщение редактировалось 27.04.2007 в 20:20
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 20:19 @haleev#27.04.2007 20:14
haleev> Туплю, туплю... Голова садовая.
haleev> С пяти утра на ногах. Если полигон без взаимопересечений, то можно сначала построить из подмножества точек выпуклый многоугольник, а потом, перебирая оставшиеся точки отрезать от этого выпуклого многоугольника треугольники. Сложность получится... ээээ... N*N*N
Боюсь, вы ошибаетесь. Даже если вам не нужно максимальную площадь сложность будет факториальная.
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 20:20
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 20:21
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 20:30 @AidarM#26.04.2007 18:34
Из каждой пары пересекающихся ребер нужно выбрать одно, но это одно может отвалить много других ребер из данной вершины. А, вот, если уберем другое, то это множество может остаться — какое продолжение выберем?AidarM> А я откуда знаю? Идея Сергея-4030 состоит в том, чтобы перебирать все, но прекращать работу с неподходящими на достаточно раннем этапе (если повезет). Т.е. он при постройке анализирует, не грозит ли ему слепить самопересекающееся чудо. А я просто предложил часть важной для такого анализа инфы запасти заранее.
Уже сама постройка будет факториальной сложности. Т.е. если даже если она (постройка) и позволит нам сделать, скажем, алгоритм сложности N (а она не позволит), то сам факториальный механизм постройки все испортит.
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 20:48 @haleev#27.04.2007 20:37
Я просто не понял вас сначала. В таком изложении - реализуется. Но такой метод приведет нас к "звездам", которые совсем и близко не будут максимальной площади. Более того - к минимальной будут ближе.
ЗЫ Алгоритмы, основанные на максимальном выпуклом подмножестве уже высказывались.
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 20:50
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 20:53
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 21:26 @AidarM#27.04.2007 21:04
Вот тут хороший пример - я не додумался до этих стен с вершинами в 0 и в 10. Сложно биологическим разумам оценить где площадь больше - в длинном узком треугольнике или в коротком, но "полном". И кучу разбиений оценить сложно.
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 21:37
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 22:07
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 22:35
Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек. #27.04.2007 23:33
Ну еще бы, кто ж с вами спорит. Вы, похоже, немного не понимаете, в чем спор. Конечно, Меньшов с вашей точки зрения правильно очень поступил. Разоблачил, понимаешь, врагов народа.
А то, что на договоренности с устроителями наплевал - большое дело! Более того, если б он еще поссал бы там со сцены, это бы еще более отложилось в памяти народной. Средства ничто, цель все. Но что нам поделать если нас, поганых косполитов, тошнит от таких средств. ЗЫ Если, конечно, не иметь в виду тщательную инсценировку.
Copyright © Balancer 1997..2024
Связь с владельцами и администрацией сайта: anonisimov@gmail.com, rwasp1957@yandex.ru и admin@balancer.ru.
Связь с владельцами и администрацией сайта: anonisimov@gmail.com, rwasp1957@yandex.ru и admin@balancer.ru.
