@DeboshiR
Свободу разработчикам!!!

Существует ли быстрый алгоритм проверки пересечения линии полигона с собой?

Есть полигон, заданный некоторым массивом точек, образующих прямые (около 4000). Надо проверить,пересекаются ли эти линии с самими собой.
Метод перебора массива в массиве занимает очень много времени. Есть ли более быстрый способ?
  • Вопрос задан
  • 299 просмотров
Решения вопроса 1
FlashManiac
@FlashManiac
I am from Krypton!
Ну вообще есть хитрый способ ) Надо создать битмап(канвас) и отрисовать туда все эти линии например с альфой 0.5, И далее пройтись по всем точкам и проверить альфа координату и если она хотя бы в одном пикселе более 0.5 то значит в том месте примерно имеется пересечение. Естественно есть много тонкостей и настроек такого способа. И не факт что будет быстрей )

Потом при переборе массива с массивом может возникнуть ситуация двойной проверки. Например 100х200 и 200х100. Можно как минимум в пару раз сократить время расчетов:
for(var i = 0; i < 4000; i++)
{
    for(var j = i + 1; j < 4000; j++ )
    {
          // check i vs j
    }
}
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Известны ли какие-то особенности полигона, или каждая следующая вершина может оказаться где угодно?

В общем случае полигон ничем не отличается от набора независимых отрезков, где придётся проверить каждый-с-каждым, кроме смежных соседей. Можно оптимизировать: бить на подгруппы, сортировать и пр.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы