Пересечение многоугольников

[_PROGRAMM_]

Добрый день. Собственно, из названия темы видно о чем будет идти речь. Вбив сабж в гугле сразу попадаем сюда. Но оформление статьи оставляет желать лучшего. поэтому рекомендую читать тут. На нашем форуме нашел одну "безответную" тему, на других советуют простой перебор. Я не могу сказать, что он меня не устраивает, скорее всего это спортивный интерес. Т.к. мне требуется проверять пересечение квадратов с 4-х, 5-и, 6-и угольниками. Хочется узнать, насколько приведенный мной выше алгоритм улучшит производительность(скажу, что хотелось бы оптимизировать вычисления, используя SSE), в сравнении с простым перебором.

Теперь по алгоритму, я застопорился на формулировке окна полигона. Что это? Данное понятие не дает мне понять смысл действий, зачем перемещать окна? На чем вообще основан этот метод? Дальше задавать вопросы нет смысла так так в общей сути, из-за ступора они будут развернуто спрашивать: как работает алгоритм.

Заранее спасибо.

[DiemonStar]

Т.к. мне требуется проверять пересечение квадратов с 4-х, 5-и, 6-и угольниками.

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

[_PROGRAMM_]

Факт пересечения, только и всего, но, наверное, будут не квадраты с многоугольником, а многоугольник с многоугольником.

[DiemonStar]

Самый простой вариант - искать пересечение сторон. Если присутствует, то и фигуры пересекаются. Можно через перебор проверять (что нерационально при большом количестве сторон) или через сканирование относительно оси.

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

[_PROGRAMM_]

2. для следующей вершины определяем значения Y прямых в данной точке

Немного не пойму. Y для прямых, которые исходят из минимальной вершины?

Пока не могу определить насколько этот алгоритм эффективнее.

[DiemonStar]

Сообщение от _PROGRAMM_

Немного не пойму. Y для прямых, которые исходят из минимальной вершины?

сначала из минимальной, а при достижении второй точки отрезка уравнение прямой пересчитывается для него.

Пока не могу определить насколько этот алгоритм эффективнее.

есть подозрение, что прирост будет при n>50... хотя многое зависит от конкретной реализации..

[_PROGRAMM_]

есть подозрение, что прирост будет при n>50... хотя многое зависит от конкретной реализации..

Ну вершин у меня больше 10 не будет, да и, мне кажется, я больше выиграю за счет SSE(где-то в 2-4 раза).