Обнаружение столкновения 2 строк в Java (Android)

Question

Очень простой вопрос.Как добиться обнаружения коллизий с помощью линий, нарисованных на Java?Просто линии.Никаких прямоугольников, кругов или изображений, растровых изображений ... только линии.

Кстати, эти линии не прямые.Они построены из сотен очень маленьких линий, которые представляют движение игрока (их координаты GPS при движении), поэтому они ходят повсюду во время движения игрока.Все линии связаны.Конечная точка одной строки является начальной точкой следующей и так далее.Это непрерывная линия в этом отношении.Пробелов нет.

Я попытался сохранить значения x, y начальных точек линий в массиве, а затем повторил этот массив, чтобы определить, была ли точка посещена ранее.Это хорошо, если игрок снова посещает точные координаты, но что, если он находится на полпути между этими записанными точками?

Это фон проблемы, если это поможет.Но главный вопрос - мое внимание здесь.Как вы достигаете обнаружения столкновения линий в Java?

Answer 1

Если я правильно понимаю, ваша проблема не в строгом пересечении линий (которое легко найти в Интернете), а в том, как справиться с сотнями из них?

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

Вы будете проверять пересечения только на подмножестве всех ваших координат.

Answer 2

То, что вы называете линией, вы можете назвать List<Line2D> - список отрезков прямой линии.Если у вас есть List<Line2D> a и List<Line2D> b, то вы хотите сравнить каждую строку в a с каждой строкой в ​​b.Я предполагаю, что вы можете увидеть, как найти точку пересечения двух отрезков прямой линии - или Line2D даже сделает это за вас .Например:

for(Line2D line1 : a) {
   for(Line2D line2 : b) {
      if(a.intersectsLine(b)) {
         return true;
      }
   }
}
return false;

Теперь этот код не будет быстрым, но может быть достаточно быстрым.Если он слишком медленный, вам придется взглянуть на оптимизацию - это можно сделать несколькими способами, квадродерева или сортировка в одном измерении - это два очевидных простых шага.

Answer 3

Из того, что я знаю, вы делаете это правильно. Я бы посоветовал, возможно, хешировать строки через координаты, чтобы было меньше проверок строк. Вы также можете сократить количество проверок, если была проведена предполагаемая более крупная прямая линия (сделанная из среднего значения из более мелких линий) и использованная вместо нее для проверки.