Клуб API Карт

Клуб API Карт

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

Пост в архиве.

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


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

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

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