Здравствуйте, рыцари Кодсилы.
Заинтересовала одна задача (придумал ее сам) и надеюсь, вы мне поможете совершить маленький, но "крестовый" поход.
У нас есть многоугольники (простые, попарно непересекающиеся, если проблемно будет, то выпуклые) в двухмерном пространстве, заданные списками координат своих вершин. Назовем их (многоугольники) препятствиями. Есть стартовая точка. И поступают в online точки, которые являются финишными. Необходимо найти за log(n), где n — суммарное кол-во вершин многоугольников, кратчайший путь от стартовой до финишной точки, который непереcикается с препятствиями. Я вам выскажу свои мысли а вы уж решите присудить мне звание рыцаря(и возможно помочь) или изгнать. Я думал над таким: соединим отрезками все точки (стартовую и вершины многоугольников) и скажем что это ребра, а вершинами будут точки, которые соединялись ребрами. Ребра взвешенные, а их веса — евклидовое расстояние между точками соединенными ребром. Таким образом, мы получили граф. По нему мы можем найти кратчайшие пути до всех вершин (точек) от стартовой вершины (точки). Теперь я столкнулся с проблемой: подозреваю что нужно делать какое-то разбиение пространства (поиска), возможно, для того чтобы «быстро» локализировать точку (финишную) поступившую из потока, т.е. найти вершину, которая является предком финишной в кратчайшем пути в терминах графов. Вопрос к вам: может кто-то знает, какое разбиение пространства надо делать или надо решать проблему другим способом? Спасибо за прочтение.
BSP
P.S. Первое, что пришло в голову.
P.P.S. Вот еще.
А я не пойму чем мне это поможет. например по вики. У этого разбиения три осн. использования. Сортировка объектов в порядке удаления от наблюдателя, Отсечение невидимых поверхностей, поиск столкновений. Знания только о ближайшей вершине мне не помогут, отсечение невидимых поверхностей вроде бы тоже не нужно. А вот в поиске столкновений непонятно как выбирать радиус ограничивающей сферы, та и что мне даст это?. Могли бы вы пояснить, как мне поможет это?
P.S. Первое, что пришло в голову.А всегда ли реально это сделать за log(n)? Возможен же случай, когда существует много различных путей из начальной точки в конечную, которые приблизительно равны по длине. И, скажем, все запросы — в некоторой окрестности этой конечной точки, и при этом ответ — каждый раз новый путь. Как тогда найти его без проверки всех вершин многоугольников?..
Ну я не совсем осознал, что ты написал. Могу сказать что есть метод, который основан на продвижении волны(волнового фронта). Идея в том что у нас есть генираторы волны(вершины) и события. События такие например как: столкновения волны, столкновения волны о препятствие. И пользуясь этой информацией мы строим "bisector curve". По сути, эта кривая и есть необходимая нам граница, которая показывает геом. место точек, таких что: предок в оптимальном пути до этих точек(огр. "bisector curve") будет обязательно! вершина которая породила волну, которая, как следствие образовала "bisector curve". Проблема в том что я не представляю как это программировать и подозреваю что это очень не просто. Этот подход вродебы называется continuous Dijkstra c последующим построением shortest path map.
Ну чтобы построить такую штуку абсолютно точно, нужно знать уравнение этой кривой, что не совсем понятно как;) А если строить приближенно, то возможен случай, который я описал: грубо говоря, у нас есть точка, особым способом окруженная треугольниками, до которой есть N/3 путей одинаковой длины. И если эту точку сдвинуть на какой-нибудь eps, то кратчайший путь изменится в зависимости от того, в какую сторону ты ее сдвинул. И у тебя явно не хватит точности определить, в чью волну ты теперь попал.
Здесь в пункте 4 детально описано это, но я не смог понять 50 страниц определений и идеом на английском. Из книги: Klette "Euclidean shortest path" что там описывают кривую только как гоем. место точек, а явных уравнений кривой я ни разу не видел. Хотя такой подход у многих авторов.
Так как я осознаю что с этим врядли мне поможет кто-то (вопрос сложный), другой вопрос, более алгоритмический. Можно ли проверить быстрее алгоритма в лоб(проверка на пересечение с каждым отрезком из множества препятствий) такое: пересекается ли отрезок с множеством других отрезком(которые являются образующими многоугольников(мы назвали препятствиями))?