Клуб API Карт

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

Пост в архиве.
EFRRR
17 апреля 2010, 13:08

Добрый день всем.


Вопрос в след.:

есть ли в АПИ возможность проверять пересечение установленных многоугольников(количество вершин фиксированно у обоих, многоугольники могут быть любыми, т.е. не только выпуклыми)?

8 комментариев
Эм... ни у кого не появилось идей, или ответов?)
В API нет стандартной функции определения пересечения многоугольников. Ее необходимо программировать самим, в интеренте можно найти много готовых реализованных алгоритмов.
Плохо :(
Как частный случай, можно использовать функцию поиска точки в многоугольнике:
http://ru.wikipedia.org/wiki/Алгоритм_точки_в_многоугольнике
Проверяем каждую вершину первого многоугольника на нахождение внутри второго, и наоборот.
Правда, могут быть случаи когда этот алгоритм не работает, например в случае пересечения двух треугольников как на звезде Давида. Но такое бывает достаточно редко.
Можно проверить пересечения ребёр. Многоугольники пересекаются тогда и только тогда, когда хотя бы одно ребро первого многоугольника пересекает хотя бы одно ребро второго многоугольника.
Да, так даже быстрее будет.
Спасибо за совет, как раз так и сделал:) По поводу проверки точки в многоугольнике - этот метод не сработает даже очень часто, например когда два ребра одного пересекают два ребра другого.Тогда ни одной точки ни одного из многоугольников не попадут друг в друга:)
По-поводу пересечения рёбер, я бы мог ссылочку оставить на алгоритм, чтобы последующие поколения долго не искали, но не знаю не запрещено ли здесь это...
Не запрещено, можете свободно давать ссылку.