Вырезать полигон из полигона

← →
2222 (2012-02-06 15:11) [0]

Здрасти. А что бы мне такого почитать по сабжу. Желательно на великом и могучем.

ТЗ. Имеются, допустим, два слоя. На каждом из них находится по 2D полигону, требуется из нижнего слоя вырезать верхний. Причем на слоях могут лежать и как самопересекающиеся полигоны так и полиполигоны. Сразу поясню объекты на слоях находятся друг над другом - тоесть пересекаются.

ЗЫ. Платформозависемые решения не подходят. И потому придется кодить все это с нуля.

← →
Димка На (2012-02-06 15:15) [1]

Математику? :)

← →
Dimka Maslov © (2012-02-06 15:17) [2]

Аналитическая геометрия на плоскости. Очень даже платформенно независимо

← →
Inovet © (2012-02-06 15:28) [3]

> [2] Dimka Maslov © (06.02.12 15:17)
> Аналитическая геометрия на плоскости. Очень даже платформенно
> независимо

Даже если считать платформой Вселенную.

← →
Dimka Maslov © (2012-02-06 15:54) [4]

>
> Даже если считать платформой Вселенную.

Вселенная непрямолинейна.

← →
Inovet © (2012-02-06 16:06) [5]

> [4] Dimka Maslov © (06.02.12 15:54)
> Вселенная непрямолинейна.

Ну и что. От её непрямолинейности прямая геометрия не перестаёт быть прямой, как и в другой Вселенной с совсем другими метриками.

← →
Anatoly Podgoretsky © (2012-02-06 16:07) [6]

> Inovet (06.02.2012 15:28:03) [3]

Применимо даже в альтернативной вселенной

← →
Dimka Maslov © (2012-02-06 16:20) [7]

> Anatoly Podgoretsky © (06.02.12 16:07) [6]

В альтернативной вселенной, как известно, полигоны программируют вырезание людей.

← →
Anatoly Podgoretsky © (2012-02-06 16:35) [8]

> Dimka Maslov (06.02.2012 16:20:07) [7]

Земля находится в альтернативной вселенной (LEXX)

← →
Dimka Maslov © (2012-02-06 16:37) [9]

> Anatoly Podgoretsky © (06.02.12 16:35) [8]

Вообще никакой Вселенной нет. Нам просто показывают красивые картинки из фотошопа.

← →
TUser © (2012-02-06 18:14) [10]

Имхо, надо построить триангуляции этих полигонов и искать пересекающиеся треугодники.

> Причем на слоях могут лежать и как самопересекающиеся полигоны

У самопересекающегося полигона - как внутрь и наружа определены?

← →
Виктор Щербаков © (2012-02-06 23:12) [11]

Почитать можно вот это: http://www.inf.tsu.ru/library/Publications/2004/46.pdf
Для реализации вполне достаточно.

У самопересекающегося многоугольника внутреннюю точку от внешней можно отличить по четности кол-ва пересечений луча и границы.

← →
Виктор Щербаков © (2012-02-06 23:18) [12]

Ну или вот http://www.inf.tsu.ru/library/Publications/2002/30.pdf
Можно прям по статье реализовать. Места где грабли помечены флажками.

библиотека
Clipper by Angus Johnson

> Не работают ссылки. Обе. А хотелось бы почитать.

Работают. Обе.

← →
2222 (2012-02-07 09:41) [16]

> У самопересекающегося полигона - как внутрь и наружа определены?

Пока нет. Но при построение заливки имеется соответствующий код. Так что это не проблема.

> Виктор Щербаков ©

Спасибо почитаю

← →
2222 (2012-02-07 09:46) [17]

> > У самопересекающегося полигона - как внутрь и наружа определены?
> Пока нет. Но при построение заливки имеется соответствующий
> код.

Да и логика "определения" [11] здесь правильно описана

Да, у меня на работе тоже ссылки не пашут, с ДНС что-то...
Тем у кого не работает, а почитать охота - вбивать в гугль:
"скворцов обзор алгоритмов построения оверлеев" и
"скворцов линейно-узловой алгоритм построения оверлеев".

Вырезать полигон из полигона Найти похожие ветки