Даны в координатах две фигуры на плоскости (увы, одна фигура может быть и невыпуклая, произвольная, иногда даже очень сложной формы, вторая всегда - прямоугольник)
Нужно на основе этих фигур построить третюю (в координатах), которая есть пересечение двух первых фигур.
В принципе уже сделано, но так неоптимизированно, и код очень огромный (сколько условий, исключений, мрак), хотелось бы по теории какой-нибудь реализовать

Интересно, что такое пересечение фигур?

Поделить на треугольники. Найти все пересечения. При необходимости собрать обратно в единую фигуру.

либо

Рассчитать все точки пересечения. Потом сделать обход по сложной фигуре, фиксируя вход-выход.
Добавлено @ 09:58
Следует учитывать что область пересечения может быть совокупностью нескольких непересекающихся фигур.

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

и так у нас есть две ломанных
берем одну ломанную
берем на ней начальную точку
начинаем идти последовательно по точкам ломанной
как только встречаем точку пересечения (назовем ее A), "раздваиваемся":
1. идем по первой ломанной до следующей точки пересечения (B)
2. запоминаем точку, чтобы продолжить движение потом
3. возвращаемся в A уже по второй ломанной
4. таким образом получаем замкнутый путь A-B-A, который описывает одну из фигур пересечения (их может быть несколько)
5. продолжаем прерванное движение из точки B по первой ломанной до следующего пересечения...

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

замечания:
1. выбор начальной точки: начинать нужно с точки, которая находится снаружи другой фигуры (если другая фигура - прямоугольник, задача поиска такой точки - трививальная)
2. направление обхода: должно быть синхронизированным, т.е. если мы идем по первой ломанной "по часовой стрелке", то возвращаться по второй надо "против"
3. в принципе на пути возвращения опять могут встретиться пересечения - на них можно просто временно перескочить на другую ломанную, потом на следующей "пересадке" вернуться и забыть эту часть мы найдем позже...

Вот такое решение. Конечно, у него есть недостатки, но уж больно решение простое.
Рисуем на экране первую фигуру и красим её первым цветом. Рисуем на экране вторую фигуру и начинаем красить её вторым цветом. Если текущий окрашиваемый пиксель окрашен уже первым цветом, то красим его третьим цветом. В результате получаем область пересечения фигур, окрашенных этим самым третьим цветом. Ну вот и имеем пересечение фигур, окрашенным третьим цветом.
Окраску в разные цвета я просто решил использовать для наглядности, в реальности же, все это делается путём заполнения матриц.
Мне могут сказать, что вот, значит, фигуры могут быть очень большие, и памяти не хватит или очень маленькие, что потеряем точность.
Отвечу:
1. Если очень большие - режем на маленькие, чтобы памяти хватило.
2. Если очень маленькие - увеличиваем разрешение внутреннего массива.
Ну, вот так.

Цитата(val @ 19.8.2005, 14:51)

1. Если очень большие - режем на маленькие, чтобы памяти хватило. 2. Если очень маленькие - увеличиваем разрешение внутреннего массива.

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

А как фиксируется вход выход?

ps еще вопрос, в каком виде лучше сохранить информацию о пересечения? Я сделал двухмерный массив в котором указываю номера отрезков которые пересекаются, но вот как дальше сформировать обрезанную фигуру не пойму.

Это сообщение отредактировал(а) bugz7771 - 24.11.2008, 16:22

Мой алгоиртм, работает для любых многоугольников:
1) сгенерить все отрезки, получающиеся при наложении одного многоугольника на другой;
2) для каждого отрезка проверить входимость его в обе фигуры - через векторное произведение, оно должно быть одного знака (и ноль тоже может быть);
3) из отфильтрованных отрезков аккуратно собрать фигуру. Это и есть результат.
Код предоставить не могу, под рукой нет ничего, но его будет строк 40-60, не больше.

40-60 это много, у меня довольно простая задача и все уложилось в несколько циклов и условий, спасибо за ответ

а отрезок на что умножать?

ps все же хочется по человечески сделать  

Это сообщение отредактировал(а) bugz7771 - 25.11.2008, 19:05

отрезок умножаем на сторону многоугольника

Для частного случая отсечения прямоугольником можно построить более простой и эффективный алгоритм.

Если прямоугольник прямой (т.е. стороны параллельны осям координат), выполнем отсечение многоугольника. Примерно так: отсекаем поочередно по каждой прямой, проходящей через сторону прямоугольника. Отсекаем так: оцениваем каждое ребро многоугольника на предмет справа, слева или пересекает прямую (т.к. прямая параллельна оси, это тривиально).  Если отрезок полностью справа или слева (зависит от  того, какую сторону прямоугольника рассматриваем), оставлем его, иначе выбрасываем. Если отрезок пересекает прямую, то берем ту его часть, которая лежит с нужной стороны. 

Если прямоугольник наклонный, сначала меняем систему координат (чтобы прямоугольник стал прямым), потом отсекаем.

Это алгоритм Сазерленда-Ходжмана, хорошо описан в книге М.Ласло, "Вычислительная геометрия и компьютерная графика на C++"
Есть реализация на C++, старая, но работающая, для прямого прямоугольника. Надо?

Добавлено через 1 минуту и 48 секунд
Ой, это оказывается старую тему реанимировали... ну, может, кому пригодится.