Соединение множества точек с горизонтально выровненными полилиниями без их пересечения

Question

Я пытался решить эту проблему уже несколько дней, но не могу найти хорошее решение.

У меня есть набор 2D точек, где все значения являются целыми числами. Нет очков идентичны. Я хочу нарисовать полилинии / пути / что угодно через все точки с некоторыми ограничениями:

1: линия всегда должна двигаться в положительном направлении х. p1.x

2: линии не могут пересекаться друг с другом.

3: все полилинии должны начинаться с x = 0 и заканчиваться с x-max.

4: он должен использовать как можно меньше полилиний (или число, определенное мной).

Я приложил изображение примера набора точек. И ручное решение, которое я нарисовал карандашом и линейкой.

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

Набор точек (без учета цветов)

Подключенные точки

Мое текущее решение состоит в том, чтобы пройти набор по оси X, а затем попробовать все возможные комбинации и выбрать ту, которая имеет наименьшее общее вертикальное движение. Это работает в некоторых случаях, но не во всех. И это, кажется, слишком усложняет проблему.

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

Для тех, кто интересуется, на самом деле эти пункты - это ноты на листовой музыке c. Ось X - это время, а ось Y - это шаг. Полилинии представляют движение роботов c пальцев, играющих на пианино.

Answer 1

Мы найдем решение, которое использует минимальное количество роботов c пальцев (наименьшее количество полилиний). Хитрость заключается в том, чтобы рассматривать ваш ввод как Частично упорядоченный набор (или poset). Каждая точка в вашем входе является элементом набора и с отношением (p1.x, p1.y) <(p2.x, p2.y) тогда и только тогда, когда p1.x <p2.x. Это в основном означает, что две точки, которые имеют одинаковую координату X, несопоставимы друг с другом. </p>

А пока давайте забудем это ограничение: «Линии никогда не могут пересекаться друг с другом». Мы вернемся к этому в конце.

То, что вы ищете, это разбиение этого набора на цепочки. Это делается с использованием теоремы Дилворта . Должно быть понятно, что если есть 5 точек с одинаковыми координатами x, то нам нужно как минимум 5 разных полилиний. Что говорит Дилворт, так это то, что если нет x-координаты с более чем 5 точками, то мы можем получить 5 полилиний (цепочек), которые охватывают все точки. И это также дает нам способ найти эти полилинии, которые я здесь кратко излагаю:

Вы просто создаете двудольный граф G = (U, V, E), где U = V = Набор всех входных точек и где (u, v) - ребро в G, если ux максимальное совпадение , M в этом графе и рассмотрите множество полилиний, образованных путем включения u и v в одной и той же ломаной линии, когда в M. есть ребро (u, v).

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

Сначала давайте предположим, что есть только две полилинии, L1 и L2. Вы найдете первый экземпляр (минимальная x-координата) их пересечения. Предположим, что два отрезка, которые пересекают друг друга, это AB и CD:

Мы удаляем AB и CD и вместо этого добавляем AD и CB:

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

[Случай края B, лежащий на сегменте CD, также обрабатывается точно так же]

Теперь предположим, что мы имеем k различных полилинии, которые нам дали максимальное соответствие: L1, L2, ..., Lk. WLOG, давайте предположим, что при x = 0 у-координата L1 ниже, чем у-координата L2, которая ниже, чем у L3 и т. Д.

Возьмите L1 и найдите первый раз, когда он пересекается с любым другая полилиния. На этом перекрестке применяется операция обмена, как указано выше. Продолжайте повторять это, пока L1 не пересечется с любой другой ломаной. Теперь L1 находится «внизу» и не пересекается ни с какой другой линией. Теперь мы выводим L1 как одну из последних полилиний и удаляем его из нашего al go. Затем мы повторяем тот же процесс с L2, а после вывода удаляем его и повторяем с L3 и т. Д.