| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Самопересикающиеся полигон |
| Автор: FataList 18.7.2006, 11:40 |
| День добрый! Это самопересикающийся полигон. ************************ * * * ***** * * * * * * * **** ** * ******* * * * * * * * * * * * * * * * * * *************** * * * * * * * * * * * * * ******* * * * * ***** * * * ************************ Как найти красную точку с минимум затрат? Есть вариант, когда все ребра (от вершины 1 до вершмны 2 и т.д.) сравнивать друг с другом и тем самым находить эту точку, но получается 0(n*n). А это плохо! Нужно быстрее. Какие будут мысли? |
| Автор: Earnest 19.7.2006, 09:53 |
| Используй метод сканирующей линии. Он дает (кажется) O(n*log n). Быстрее, по-моему, не получится. Метод сканирующей линии вкратце: все ребра сортируем, скажем по x, слева направо. Начальные и конечные х-координаты ребер составляют список точек-событий. Вертикальная сканирующая линия переходит от одного события к другому, слева направо. В каждый момент времени рассматриваются только те ребра, которые пересекают сканирующую линию. Причем эти ребра (называемые активными) сортируются по y-координате пересечения сканирующей линии. Так что нужно проверять пересечения только соседних в списке ребер. Хорошее и подробное описание этого алгоритма можно найти в книге Ласло "Вычислительная геометрия и компьютерная графика на С++". Но следует иметь в виду, что реализация алгоритма значительно сложнее, чем квадратичная проверка пересечений всех ребер, а за счет сортировок и подготовительной работы выгрыш будет только при большом числе ребер. Я думаю, от сотни. Если ребер 2 десятка, проще попарно сравнить. Добавлено @ 09:54 Если полигон именно такой, как на рисунке, т.е. состоит только из вертикальных и горизонтальных линий, думаю процесс можно существенно упростить и ускорить. |
| Автор: FataList 21.7.2006, 09:46 | ||
| Спасибо! Просто нужно определить эту точку, которая принадлежит обоим отрезкам (сторонам). На первый взгляд это легко, но когда копнешь глубже... A' * * * * A************B * * * * B' Получется куча условий и они работают по отдельности.
Это 1 / 4 от всех условий. Первое, это когда рассматривается отрезок (сторона) A'B' и (AB или BA) А второе - B'A' и (AB или BA). И так с каджой стороны (учитываются и то, что под любым углом пересекаются прямые). Видимо надо от этого отказаться, или нацти альтернативу. |