Аутстаф frontend разработчика в сервис 3D-моделирования окон
Клиент
Срок работы
NDA
6 месяцев
Задача
Усилить команду клиента, разработчиком который сможет решить задачу с прямой в пространстве.
Построить алгоритм на языке TypeScript деления выпуклого полигона линией, проходящей через две его стороны в двумерном пространстве.
01
02
Входные параметры:
массив вершин полигона [{x, y}]
координаты линии по двум точкам (которые лежат снаружи области полигона
Технологии
Typescript
Решение задачи
Решение на бумаге
Рассмотрели возможные ситуации деления выпуклого полигона линией.
Уравнение прямой по двум точкам:
На вход принимается массив вершин многоугольника и две точки независимой прямой. Для решения задачи каждый элемент массива проверяем на пересечение с независимой прямой.
Выходной параметр: массив вершин полигонов. При делении образуются два полигона, нужно получить массивы их вершин.
Приведем данное уравнение к уравнение прямой: y = ax + b
Таким образом получаем уравнение прямой вида y = ax+k.
Пересечение двух прямых образуют систему линейных алгебраических уравнений (далее СЛАУ) с двумя неизвестными: х и y.
Программирование алгоритма
Для каждой итерации (грани полигона) производится следующий алгоритм:
Функция checkPointBetween проверяет, что точка пересечения принадлежит отрезку между первой точкой включительно и второй точкой не включительно. Таким образом, корректируется результат с учетом того, что прямая может пересекать многоугольник в вершине или совпадать с гранью.
При пересечении прямой в двух точках возможны следующие ситуации.
При нахождении точки пересечения необходимо запомнить точку и индекс разрыва. Таким образом, получаем массив из двух (одного - при касании) элементов, который содержит точки разрыва для исходного полигона.
Далее на основании точки разрыва комбинируем два массива.
Далее на основании точки разрыва комбинируем два массива.
Алгоритм следующий
Так как точка разрыва может совпадать с вершиной многоугольника, то необходимо отфильтровать полученный результат
Тестирование
Полный код
Тестирование алгоритма
Для тестирования правильности работы программного кода, реализовали тестовый пример