Отрисовка строк между двумя таблицами с помощью React

Во время разработки GiraffQL, скрипта схемы GraphQL в браузере, встроенной в React, нам нужен был способ динамически визуализировать отношения между таблицами и полями, которые бы играли с желаемым пользовательским интерфейсом перетаскивания. Мы хотели предоставить пользователям простой способ создания таблиц и установления связей между ними и их свойствами с помощью строк, отображаемых в React.

Проблема
Точная визуализация строк между таблицами / свойствами "на лету", когда пользователи создают и редактируют свою схему GraphQL.

Условия
Пользователи должны иметь возможность устанавливать связь между свойством и таблицей, просто щелкая строку и перетаскивая ее по целевой таблице. Таблицы отображаются в HTML внутри div. За таблицами div помещается HTML-элемент SVG. Здесь мы нарисуем отношения. Когда позиции стола меняются, наши строки нужно перерисовывать.

Цель
‌ • Точная и элегантная визуализация взаимосвязей.
‌ • Линии не должны перекрываться с другими таблицами.

Возникает вопрос , как рисовать линии?

Подход

Используйте алгоритм A *.

Классический алгоритм A * - это не что иное, как поиск в ширину (BFS) с эвристикой, которая улучшает время его выполнения за счет определения приоритета обнаруженных точек, ближайших к месту назначения.

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

Под капотом мы используем классическую BFS, которая игнорирует точки, перекрывающие таблицы.

Правила
Мы будем использовать алгоритм A * и сосредоточим его на двух точках слева и справа от HTML-элемента в качестве отправной точки.

Допустимые места назначения определяются как восемь точек на границе таблицы.

Обе точки будут использовать алгоритм A * для поиска пути к связанной таблице. В результате они выберут кратчайший путь и нарисуют его.

Но как мы узнаем, что все готово?

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

Посмотрите, как это работает, на GitHub.

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