Задачки по алгоритмам на MAXScript, интереса ради Опции

[kolts]

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

Сообщение отредактировал kolts - 06/02/2012, 14:39

[SIL]

Ну понятно, что задача не перехитрить задачу а решить ее

[Karba]

Это пока без приза, а просто для привлечения внимания, НО, если будет много участников, можно будет подумать и о награждении (но это уже потом). Насчет С++ - отрицательно, ибо конкурс только по макскрипту. Так что придется ломать голову насчет миллиона, сишный брутфорс недопустим)

Тогда я вне конкурса. Я все равно скрипт не знаю.
В Си это не обязательно тупой перебор. Там гораздо шире поле для алгоритма.

[1асс]

А никто тут не занимается демагогией. У меня есть мой старый неоптимизированный алгоритм этой задачи, на миллионе он помрет, да собсна не для мну эта задача (ну т.е. я озадачиваю, но сам не соревнуюсь).

2 Karba: это пока еще не конкурс, а предвариловка, участие добровольное, собственно делать C++ никто не запрещает, но сравнивать со скриптом смысла нет. Кто хочет и есть время - сделайте на С, потом сравним производительность.

[1асс]

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

Сообщение отредактировал 1асс - 07/02/2012, 20:21

[Aperon]

В макскрипте 2 дня отроду, как должен выглядеть код не знаю. Предполагаю, что самый простой и не факт, что рабочий вариант решения будет следующим:
надо отсортировать точки по одной из осей например по "Y". Взять точку с самым большим значением "Y" и от неё начать строить, исключая точки с меньшим значением по "X" и так для каждой последющей точки по "Y". Должна получиться 1\4 часть облака. Нужно будет отсортировать подобным образом оставшиеся 3/4.

[[Vitus]]

Не утерплю и приведу в качестве спойлера следующее утверждение: "Если имеется диаграмма Вороного множества из N точек на плоскости, то выпуклая оболочка этого множества может быть найдена за линейное время." Да опять Вороной, которым мы тут сильно увлекались одно время. Впрочем это характерно для прикладных задач, когда известные алгоритмы вылезают в самых неожиданных местах. И конечно есть готовые оптимальные решения, но не стану давать ссылок, а то будет совсем неинтересно.

[Karba]

Не утерплю и приведу в качестве спойлера следующее утверждение: "Если имеется диаграмма Вороного множества из N точек на плоскости, то выпуклая оболочка этого множества может быть найдена за линейное время." Да опять Вороной, которым мы тут сильно увлекались одно время. Впрочем это характерно для прикладных задач, когда известные алгоритмы вылезают в самых неожиданных местах. И конечно есть готовые оптимальные решения, но не стану давать ссылок, а то будет совсем неинтересно.

Осталось только вороного по быстрому пощитать для миллиона точек и дело в шляпе

[ECXIMER]

вброшу для размышления http://matlab.exponenta.ru/spline/book1/9.php

[[Vitus]]

Осталось только вороного по быстрому пощитать для миллиона точек и дело в шляпе

Андрей, в том-то и дело, что посчитать вороного для миллиона точек не есть проблема. По крайней мере для 2D случая это будет быстро.
В том же matlab-e используется qhull, с открытыми исходниками.
Есть ещё прекрасная библиотека CGAL (Computational Geometry Algorithms Library). В ней не только вороной, но и несколько очень интересных штук. Полюбопытствуй, с твоими возможностями, её использование может породить новые мощные плагины.

[Karba]

Андрей, в том-то и дело, что посчитать вороного для миллиона точек не есть проблема. По крайней мере для 2D случая это будет быстро.
В том же matlab-e используется qhull, с открытыми исходниками.
Есть ещё прекрасная библиотека CGAL (Computational Geometry Algorithms Library). В ней не только вороной, но и несколько очень интересных штук. Полюбопытствуй, с твоими возможностями, её использование может породить новые мощные плагины.

Дело в том, что посчитать контур напрямую без вороного можно гораздо быстрее (причем как минимум 3мя разными алгоритмами), чем считать вороного.

Сообщение отредактировал Karba - 09/02/2012, 22:01

[Karba]

Куча желающих с готовой реализацией задачи на max script.
Тема сдохла неуспев появиться.

Первая подсказка.
Найти самую крайнюю точку (непример самую правую, у которой x координата самая большая).
Это точка будет гарантировано принадлежать внешнему контуру.

Вторая подсказака.
Какими свойствами должна обладать следующая точка контура по отношению к первой?

Сообщение отредактировал Karba - 13/02/2012, 02:41

[[Vitus]]

Дело в том, что посчитать контур напрямую без вороного можно гораздо быстрее (причем как минимум 3мя разными алгоритмами), чем считать вороного.

Дилетанту сложно спорить с профессионалом )
Те алгоритмы, о которых ты упомянул, если не ошибаюсь, имеют сложность O(log(N)*N). Не всегда верно, но порядок такой.
Современные алгоритмы для нахождения вороного, если не изменяет память, имеют такую-же сложность.

[Karba]

Дело в том, что посчитать контур напрямую без вороного можно гораздо быстрее (причем как минимум 3мя разными алгоритмами), чем считать вороного.

Дилетанту сложно спорить с профессионалом )
Те алгоритмы, о которых ты упомянул, если не ошибаюсь, имеют сложность O(log(N)*N). Не всегда верно, но порядок такой.
Современные алгоритмы для нахождения вороного, если не изменяет память, имеют такую-же сложность.

Смысла нет вычислять сначала вороного, если можно посчитать напрямую. Алгоритм будет проще, быстрее и стабильнее.

[1асс]

2 Karba: у вектора, направленного из крайней правой в эту точку должен быть минимальный угол с вертикальной осью

Еще моя оптимизация такая - найти 4 крайних точки (верх, низ, лево, право), выкинуть из расчета все точки, лежащие внутри треугольников с этими точками в вершинах. Потом можно приниматься за обход контура.