Найти все точки пересечения в группе отрезков?

Question

У меня есть массив объектов (Линии) и бинарная операция (пересечение), которая возвращает истину / ложь. Грубая сила состоит в том, чтобы продублировать массив, запущенный для вложенного для l oop.

for (Line line : linesArray) {
            for (int j = 0; j < linesArray.length; j++) {
                if (line.isIntersecting(linesArray[j])) {
                    Point intersection = line.intersectionWith(linesArray[j]);
                    d.drawCircle(intersection.getXInt(), intersection.getYInt(), 3);
                    d.fillCircle(intersection.getXInt(), intersection.getYInt(), 3);
                }
            }
        }

Но порядок там не имеет значения, поэтому я подумал о создании подмножеств размера 2 и проверял каждый подмножество, но сложное, оно не кажется лучше

Есть ли эффективный (время выполнения) для этого?

Answer 1

Вы правы, что перечисление всех подмножеств размера два и проверка каждого из них не будет улучшением по сравнению с существующим алгоритмом. Фактически, это просто повторение того, что делает ваш алгоритм.

Существуют более быстрые алгоритмы для решения проблемы поиска всех пересечений в коллекции отрезков. Наиболее известным из них является алгоритм Бентли-Оттмана , который работает путем сортировки отрезков по их координатам x и протягивания линии по точкам слева направо. Он работает во времени O ((n + k) log n), где n - количество отрезков, а k - количество пересечений.

Существуют и другие, более современные алгоритмы для решения этой проблемы еще быстрее, но это, вероятно, послужит хорошей отправной точкой.

Надеюсь, это поможет!