Построить полигоны слева и справа от ломаной

#cpp #алгоритм #геометрия

У меня есть некоторая ломаная на плоскости, необходимо слева и справа от нее построить
два многоугольника на заданных расстояниях.

Например:

Пусть задана красным цветом ломаная, относительно нее необходимо отстроить левый
и правый полигон А и В. Таким образом, полигоны А и В как бы стыкуются в заданной ломаной.
Для построения полигонов, с сохранением кривизны ломаной, задаются два расстояния,
для левой и правой частей.



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

Ограничения исходных данных: 
1) Ломаная без самопересечений 
2) Ломаная не может быть загнута, т.е. например на одном значении оси X или Y лежит
строго одна точка

Пишу на c++

Подкиньте идею)
    

Ответы

Ответ 1

Допустим, имеются точки C = [(x1, y1), (x2, y2), ..., (xn, yn)] - это ломаная.

Отрезок (x1, y1) - (xn, yn) соединяет первую и последнюю точки. Сделаем из него вектор
направления ломаной v:

(vx, vy) = (xn - x1, yn - y1)

И повернём на 90 градусов:

               | 0  -1 |
d = (vx, vy) * |       | =  (-vy, vx)
               | 1   0 |


Это вектор с абы какой длиной, повернутый перпендикулярно "направлению" ломаной.
Тут будет куча нюансов, но о них позже. Пока нормализуем (приведём к длине 1):

vL = sqrt(vx*vx + vy*vy)
dN = d / vL = (-vy / vL, vx / vL)


Собственно, теперь, имея расстояния, на которые надо отступить "слева" и "справа"
(p, q), смешаем каждую точку и получаем новые ломаные:

 L= C + dN * p = [(x1 + dN.x * p, y1 + dN.y * p), ...]
 R= C - dN * q = [(x1 - dN.x * q, y1 - dN.y * q), ...]


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

 M1 = [L1, L2, ..., Ln, Cn, Cn-1, ... C1]
 M2 = [R1, R2, ..., Rn, Cn, Cn-1, ... C1]


Теперь нюансы.


"Лево" и "право" очень относительные понятия, зависят от порядка точек в исходной
ломаной. Если они заданы по проекции на плоскость, возможно, их придётся перевернуть.
Возможны ситуации, когда смещённая ломаная пересечётся с оригинальной, либо будет
невозможно соединить прямыми начальные и конечные точки с оригинальной ломаной, чтобы
получить непересекающийся полигон.


Пример второй ситуации:


Красная при перемещении налезла на оригинальную; с зелёной не удаётся сделать полигон
без пересечений.