Деление полигона линиями на множество полигонов

[венди спенсер]

Есть класс Polygon, в котором хранятся координаты вершин (с обходом против часовой стрелки).
Сам полигон по себе может быть выпуклым многоугольником, а может и не выпуклым. Но стороны его друг друга не пересекают, ну это понятное дело.
Есть класс Line, в котором хранятся два параметра, определяющие прямую (y=kx+b).

Нужно написать функцию:
Polygon* function(Poigon poly,Line* line),
в которую передается полигон и массив прямых.
И нужно вернуть массив полигонов, на которые исходный полигон поделится этими прямыми.

Я просто с геометрией не в ладах еще со школы, а с вычислительной геометрией и того =(

Пока что считаю, что полигон у меня изначально задан верно (то есть безо всяких проверок на пересечения и прочее).

Но проблема с алгоритмом.
Например полигон и одна прямая:
1) найти точки пересечения сторон полигона и прямой (тут маленькая проблема из разряда - точку пересечения прямых я найду без проблем, но мне нужна точка пересечения прямой и отрезка. как можно провести такое ограничение?)
2) беру первую точку пересечения. иду тоже с обходом против часовой. получается, что должна быть как минимум одна вершина между двумя точками пересечения.
но мне не понятно, как сделать условие того, что я беру именно нужную мне вершину нового полигона.
и не понятно, как сделать проверку на то, что полигон новый у меня получился и его можно передать в массив...
и в какой момент мне выделить память для массива, в который я передаю новые полигоны? я же не знаю их количество до того, пока не найду количество точек пересечения...

не то, чтобы в панике, но в растерянности...

@темы: Вопрос, C++, Алгоритм

Comments

[greetty]

Catch By Madness, ровным счетом ничего. просто интересно было.

[венди спенсер]

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

[greetty]

Catch By Madness,скорее интересно где так образовывают.

[венди спенсер]

Catch By Madness,скорее интересно где так образовывают.

ну я как бы догадываюсь, что "так" - это значит "так - =("

[greetty]

Catch By Madness, задачавообще не плохая, но я вообще считала, что механикам геометрия очень даже нужна. может не всем, но многим.

[венди спенсер]

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

[венди спенсер]

Прошу конкретной помощи. Нужно одно условие: проверка на то, параллельны две прямые или нет.
Одна прямая задана коэффициентами: Ax+By+C==0
Другая построена по двум точкам: (y2-y1)x+(x1-x2)y+x2y1-x1y2==0

Проблема такая.
Да, я вроде как знаю, что прямые параллельны, если коэффициенты при х и у пропорциональны с коэффициентом пропорциаональности k, а свободные члены не пропорциональны с коэффициентом пропорциональности k.

Но мне нужно как-то это условие записать без деления. Потому что бывают случаи, когда делится на нуль и прога ругается от этого.
Писать что-то наподобие A*(x1-x2)==B*(y2-y1) и В*(x2y1-x1y2)!=С*(x1-x2) тоже как-то не очень, потому что так тоже не работает...

В общем я что-то завис

[Vj_o-oy]

прямые параллельны, если у них в уравнениях:
y = k1x + b1
y = k2x + b2
k1 = k2, b1 != b2. если b1 = b2 - они совпадают. по двум точкам уравнение восстанавливается легко.

[венди спенсер]

Vj_o-oy это всё очень здорово, спасибо, что уделили время, но у меня прямые заданы не в виде y=kx+b
А в виде Ax+By+C=0

Как написать условие параллельности для y=kx+b я знаю.
проблема именно с общим уравнением прямой на плоскости.

А взял я такое задание прямой на плоскости не просто так, а чтобы можно было задавать прямые вида х=t.
Потому что такие прямые уравнением y=kx+b не задаются...

[greetty]

Catch By Madness, а вставить проверку на равно ли B нулю? В случае если равно то второе уранение тоже должно быть вида х=t. а если не равно то можно сравнивать. как для kx+b

[венди спенсер]

greetty это хорошо, спасибо.
но так как у меня две прямые такие, то это не ограничивается случаем: B1==0

еще может быть B1==0 B2!=0
B1!=0 B2!=0
B1==0 B2==0

а еще может быть и A1==0 B2==0

и многие другие - просто не знаю, как их объединить.
я не думаю, что нужно рассмотреть все возможные варианты. Наверняка многие из них как-то можно приводить друг к другу...
наверно..

[венди спенсер]

Ладно, вопрос снят. буду делать что-нибудь другое..

[Vj_o-oy]

здорово, спасибо, что уделили время, но у меня прямые заданы не в виде y=kx+b
А в виде Ax+By+C=0

раздели всю эту ботву на B и получишь уравнение того вида, что я указывал выше. k = -A/B, b = - C/B

[венди спенсер]

Vj_o-oy это тоже всё круто, но когда B==0 , то прога не работает.
так как деление на нуль.

я про это писал уже:

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

Насчет того, что

раздели всю эту ботву на B и получишь уравнение того вида, что я указывал выше. k = -A/B, b = - C/B

я с этим всецело согласен, но это всё для случаев, когда мы не задаем прямую вида x=a.
А мне нужно учитывать и эти прямые тоже.

[greetty]

Catch By Madness, вставь не один а 2 if
if( b1 == 0 )
if( b2 == 0 )
или одинаковые или параллельные
else
не параллельны
else
if( b2 == 0)
не параллельны
else
дели на b сколько хочешь.

чем так плохо?

[Vj_o-oy]

if((b1 == 0 && b2 == 0) || (/* условие общего вида */))
{

}
как гласят правила проверки условных выражений: если a || b, a == true, b - не проверяем. если a && b, a == false, b - не проверяем. либо можно сделать проверку отдельно в случае, если b1 == 0.

либо можно поиграть в пропорции:
a1/b1 = a2/b2 эквивалентно
a1*b2 = a2*b1

[венди спенсер]

greetty , Vj_o-oy спасибо.
я к задаче подошел с другой стороны, чтобы обминуть эту проблему.
и я ее обошел.

единственное замечу, что

a1/b1 = a2/b2 эквивалентно a1*b2 = a2*b1

неверно.
Потому что они, вообще говоря, неэквивалентны...

ну да не суть