Как подключить точки двух типов с линиями без пересечения?

Question

Как подключить точки из двух наборов координат с линиями, не пересекая ни одну из пересекающихся линий?

У меня есть два типа точек (a1, a2, ..., an, b1, b2, ..., bn) и их координаты (x,y).

Каждая точка в a и точках b должна быть соединена прямой линией сразу, чтобы ни одна из линий не пересекалась.

Как это можно сделать?

вход (тип, х, у):

a x y b x y a x y b x y 

выход (Ax, Ay, Bx, By):

ax ay bx by ax ay bx, by 

Answer 1

Это уже ответ косвенно здесь: How do you detect where two line segments intersect?

Вам легко испытать любую комбинацию подключенных точек и че ck, если они пересекаются или нет!

Answer 2

Я не уверен, как это доказать, но он считает правильным, что всегда должна существовать хотя бы одна пара точек (ax1, ay1) -> (bx1, by1), которые определяют линию, которая подразделяет пространство на две отдельные половины. Каждая половина имеет одинаковое количество непарных а и b точек. Я не могу придумать схему точек, для которых это не так.

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

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

Answer 3

Проблема евклидова двуполярного соответствия (EBM) в теории графов (Google it) направлена ​​на сопоставление синих и красных точек, чтобы минимизировать сумму всех длин кромок. Его можно решить, используя Hungarian Algorithm. Чтобы увидеть, что это бесплатный график, просто подумайте о своей «плохой» и «хорошей» картине. Сумма длин ребер всегда меньше в «хорошем» изображении. (Здесь a slightly more detailed argument.)

Вот еще SO answer, который дает более подробную информацию.

И вот an interesting article about how EBM is used on Android to track multi-touch.

Answer 4

Вот такой подход, который я считаю многообещающим. Создайте сопряжение красных и синих точек (R1, B1), (R2, B2), .. (Rn, Bn). Затем перейдите в список и для каждого (Rj, Bj) проведем прямую Rj - Bj. Если эта линия пересекает любую другую линию Ri-Bi, уже нарисованную, «пересечь» эти строки, заменив их Ri-Bj и Rj-Bi (фактически изменив вашу «плохую» картину на вашу «хорошую» картинку).

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

Как отмечено в my other answer, сопряжение красных и синих точек, которое сводит к минимуму общую длину края, также будет без перекрестков. В подходе, указанном в этом ответе, обратите внимание, что каждый раз, когда вы «пересекаете» края, вы уменьшаете общее количество всех длин кромок. Алгоритм, скорее всего, не достигнет конфигурации сопряжения с минимальной суммой длин ребер. Однако тот факт, что общая длина ребер уменьшается при каждом подкачке, означает, что алгоритм всегда будет заканчиваться (т. Е. Вы не попадете в повторяющуюся последовательность реберных свопов).