Есть класс Polygon, в котором хранятся координаты вершин (с обходом против часовой стрелки).
Сам полигон по себе может быть выпуклым многоугольником, а может и не выпуклым. Но стороны его друг друга не пересекают, ну это понятное дело.
Есть класс Line, в котором хранятся два параметра, определяющие прямую (y=kx+b).
Нужно написать функцию:
Polygon* function(Poigon poly,Line* line),
в которую передается полигон и массив прямых.
И нужно вернуть массив полигонов, на которые исходный полигон поделится этими прямыми.
Я просто с геометрией не в ладах еще со школы, а с вычислительной геометрией и того =(
Пока что считаю, что полигон у меня изначально задан верно (то есть безо всяких проверок на пересечения и прочее).
Но проблема с алгоритмом.
Например полигон и одна прямая:
1) найти точки пересечения сторон полигона и прямой (тут маленькая проблема из разряда - точку пересечения прямых я найду без проблем, но мне нужна точка пересечения прямой и отрезка. как можно провести такое ограничение?)
2) беру первую точку пересечения. иду тоже с обходом против часовой. получается, что должна быть как минимум одна вершина между двумя точками пересечения.
но мне не понятно, как сделать условие того, что я беру именно нужную мне вершину нового полигона.
и не понятно, как сделать проверку на то, что полигон новый у меня получился и его можно передать в массив...
и в какой момент мне выделить память для массива, в который я передаю новые полигоны? я же не знаю их количество до того, пока не найду количество точек пересечения...
не то, чтобы в панике, но в растерянности...