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