Оверлеи многоугольников

Алгоритм построения оверлеев многоугольников.

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

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

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

Определения

Ребром называется направленный отрезок или кривая. Ребро, начинающееся в точка a и заканчивающееся в точке b обозначается как E(a,b).

Контуром называется множество ребер { E0, E1 … En-1 }, такое, что n > 1 и каждые два последовательных ребра в списке являются смежными, т.е. Ei-1 = E(vi-1, vi), Ei = E(vi, vi+1) . (В контуре может быть два ребра, если хотя бы одно из них - кривая, иначе ребер должно быть не менее трех). Точка vi , для которой ребра Ei-1 и Ei являются соответственно входящим и выходящим, считается i-й вершиной контура. Последнее ребро контура является смежным с первым ребром. Порядок обхода ребер контура с увеличением индекса i будем считать прямым направлением обхода, противоположный ему - обратным.

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

Окрестности ребра

Окрестностью ребра назовем некоторую область с одной стороны ребра, такую, что другие ребра полигона не пересекают эту область. Соответственно, окрестность может быть левой ( φ+ ) и правой ( φ- ) (если смотреть в направлении ребра).

На рисунке ниже для исходных полигонов A и B показаны результаты выполнения операций. (Все рисунки к статье получены с применением описанного алгоритма и дают представление о его возможностях.)







Исходные полигоныОбъединениеПересечениеРазностьСимметрическая разность

Ограничения на входные данные

Входными данными для алгоритма являются два полигона. Каждый из них - набор не пересекающихся контуров. Включение или исключение внутренней части контура задается направлением обхода его ребер (по часовой - исключение, против часовой - включение).



Многоугольник A Многоугольник B

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

Полигон A задан двумя контурами. Для внешнего контура ребра перечислены против часов стрелки, для внутреннего - по часовой.

Полигон B можно рассматривать или как один контур, с перечислением ребер против часовой стрелки, или как два контура, касающиеся друг друга в одной точке. В любом случае для внутреннего контура ребра перечисляются по часовой стрелке. Оба способа задания приемлемы для нашего алгоритма.

A1. Определение точек пересечения




Точки пересечения исходных полигоновИсходные полигоны с точками пересечения

Наложим исходные полигоны A и B друг на друга. Форма исходных полигонов и способ наложения подобраны так, чтобы отразить бо́льшую часть возможных вариантов взаимного расположения ребер двух полигонов.

Найдем все точки пересечения двух полигонов. На рисунке точки пересечения показаны зеленым цветом. Разобьем ребра исходных полигонов на части точками пересечения. Добавление новых вершин не изменит исходные полигоны, увеличится только количество ребер. Исходные полигоны с добавленными точками пересечения показаны на рисунке.



При реализации поиска точек пересечения особое внимание нужно уделять пересечениям двух кривых Безье, в частности их точкам касания и близким участкам.

A2. Создание списка вершин и ребер

Создадим список всех вершин исходных полигонов. В список включаются и вершины пересечения.

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

Для каждой вершины создадим список всех входящих и исходящих из нее ребер. Совпадающие ребра считаются одним ребром.

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


Ребра вершины v1

Возьмем, например, точку v1 . Входящие и исходящие ребра для этой вершины показаны на рисунке. Ребра в списке будут отсортированы и расположены в следующем порядке: E0, E1, E2, E3, E4

Угол легко вычисляется для отрезков. Для кривых нам нужна некоторая характеристика, которая позволит сравнить ее с другим ребром и правильно расположить в списке ребер. Пусть, например, мы сравниваем отрезок E3 и кривую E4 . Проведем окружность с центром в точке v1 так, чтобы она пересекала оба ребра E3 и E4 . (Из точек пересечения кривой и окружности берем ближайшую к точке v1 ). Теперь сравниваем направления из точки v1 на полученные точки пересечения и расположим ребра в списке в соответствии с углами этих направлений.

Для каждого ребра, добавляемого в список сохраняем следующие характеристики:

pa, pb - ссылки на начальную и конечную точки ребра. Эти точки определяют направление ребра и по ним мы можем определить является ли ребро входящим или исходящим для точки, в список которой мы добавили это ребро. Например, для точки v1 ребро E0 является исходящим, а E4 входящим.

fl, fr - для поля, определяющие левую и правую окрестности ребра. Для каждого поля возможны следующие значения:

  0 - окрестность не принадлежит ни одному полигону
  1 - окрестность принадлежит полигону A
  2 - окрестность принадлежит полигону B
  3 - окрестность принадлежит обоим полигонам

Для принятого способа задания полигона направление ребра однозначно определяет положение его окрестностей. А именно, левая окрестность ребра всегда принадлежит полигону.

Пусть первыми мы обрабатываем все ребра полигона A . Для каждого ребра мы можем сразу установить fl=1. Далее обрабатываем все ребра полигона B . Если ребра еще нет в списке, мы также можем установить признак fl=2. Ребро полигона B может совпасть с уже включенным в список ребром полигона A . Для совпадающих ребер возможны два варианта. Если направление ребер в обоих полигонах совпадает, изменяем признак fl (fl = fl + 2). (На рисунке ребро E1 принадлежит обоим полигонам и направление в полигонах A и B совпадают). Если ребра направлены в разные стороны, то для уже включенного ребра мы не можем изменить направление, поэтому меняем местами окрестности и помечаем признак fr=2.

После завершения этого этапа алгоритма возможны следующие комбинации признаков.

 fl fr
 1  0   - левая окрестность ребра принадлежит полигону A
 2  0   - левая окрестность ребра принадлежит полигону B
 3  0   - левая окрестность ребра принадлежит полигонам A и B
 1  2   - левая окрестность ребра принадлежит полигону A,
          правая окрестность принадлежит полигону B

A3. Маркировка ребер

Для каждого ребра в списке, с окрестностями одного полигона, проверим отношение его окрестностей к другому полигону.

Пусть, например, окрестность очередного ребра отмечена признаком 1 (принадлежит к полигону A ). Возьмем любую из точек этого ребра. Для этой точки в списке ребер и найдем ближайшее слева (против часовой стрелки) и справа (по часовой) ребра, окрестности которых помечены признаком 2. Если такие ребра не найдены, пробуем вторую точку ребра.

Если ребро найдено слева, проверим признаки. Если ребро входящее и fl=2 или ребро исходящее и fr=2, то и текущее ребро принадлежит полигону B (помечаем обе его окрестности).

Если ребро найдено справа, наоборот, если ребро входящее и fr=2 или ребро исходящее и fl=2, то и текущее ребро принадлежит полигону B .

То-же самое выполняется и для ребра, окрестность которого принадлежит полигону B (в этом случае ищем ближайшие ребра, принадлежащие полигону A ).

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

comment
Чтобы было понятнее, приведу часть кода:

pascal
procedure TPathOverlays.MarkEdges;
var E:TEdge;
    i, T : integer;
begin
   for i := 0 to Edges.Count - 1 do begin
      E := Edges[i];    // Это очередное ребро

      // Отмеченные полуокрестности ребра (1 = A, 2 = B)
      T := (E.FL + E.FR) and 3;

      // Если ребро отмечено обоими фигурами, проверок не требуется
      if T = 3 then continue;

      // Выполняем маркировку для точки A, а если она не выполнена, 
      // делаем то-же самое для точки B 
      // Сама точка передается как параметр, чтобы получить ее список ребер, 
      // а вторым параметром идет признак окрестности, который проверяется 
      // для A -> B(2) и для B -> A(1), соответственно 
      if not MarkEdge(E, E.PA, 3-T)
      then MarkEdge(E, E.PB, 3-T)
   end;
   // Проверка вершин - вторая часть этого этапа.
   while MarkPointEdges do {};
end;

Надеюсь, такое дополнение не запутает описание.

A4. Маркировка вершин



Исходные полигоныи их разность

После выполнения маркировки ребер могут остаться вершины, которые попадают в другой полигон (вместе со своими ребрами), но еще не отмечены. Типичный пример на рисунке. Здесь контуры полигонов не имеют пересечений и операций, выполненных на шаге A3 недостаточно для определения принадлежности ребер.

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

A5. Выполнение операции

На этом этапе для окрестностей каждого ребра выполняется заданная операция. Ребро будет входить в результирующий полигон M , если после операции только одна его окрестность принадлежит полигону. Если это правая окрестность, то ребро нужно развернуть в противоположную сторону. Ребра, для которых после выполнения операции обе окрестности входят в M или обе окрестности лежат вне M , сразу помечаются выбранными (или исключаются из списка). В таблицу сведены возможные комбинации окрестностей после шага A4 и отношение ребер к полигону M после выполнения операции.

flfrОбъединениеПересечениеРазностьСимметрическая разность
A+0+-++
B+0+--+
A+B+--+-
A+B+0++--
A+B+A+-+<><>
A+B+B+-+-<>

Обозначения в таблице:

 +  включение ребра в полигон M
 -  исключение ребра 
 <> включение развернутого ребра в полигон M

A6. Выборка ребер

Это самый простой этап алгоритма.

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

Продолжаем выборку контуров, пока есть хотя-бы одно не выбранное ребро.

Результат выполнения операций для исходных полигонов A и B





ОбъединениеПересечениеРазностьСимметрическая разность

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

Нормализация

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

Замыкание контуров


Незамкнутые контуры

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

Устранение самопересечений


Самопересекающиеся полигоны
Для устранения самопересечений нужно проверить пересечение всех ребер с другими ребрами полигона и добавить новые вершины. Эти вершины разобьют соответствующие им ребра на части. На рисунке слева добавленные вершины показаны красным цветом.

Определение принадлежности точки полигону

Для определения принадлежности точки полигону обычно используются одно из следующих правил.



nonzero rule even-odd rule

nonzero rule . В GDI+ этому правилу соответствует константа FillModeWinding и этот способ используется по умолчанию. Для определения принадлежности точки полигону из точки проводится луч. Каждый раз, когда этот луч пересекает контур пути, к счетчику (изначально установленному в ноль) добавляется единица, если пересекаемое ребро идет по часовой стрелке и вычитается, если против часовой стрелки. Точка принадлежит полигону, если в конце счетчик равен нулю.

even-odd rule . В GDI+ этому правилу соответствует константа FillModeAlternate. Как и в первом методе, из точки проводится луч и подсчитывается количество пересекаемых путей, но без учета их направления. Точка считается принадлежащей области, если в результате получается нечетное число.

На рисунках слева оба полигона сформированы одинаково - и внешний и внутренний контуры по часовой стрелке, но при заливке использованы разные правила.

Оба правила несложно реализовать или, в случае если путь уже описан средствами GDI+, воспользоваться вызовом соответствующего метода пути.

Восстановление направлений ребер полигона

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


Выбор точек в окрестностях ребра

Для этого для каждого ребра выбираем произвольные точки в его окрестностях vl и vr . И для отрезка и для кривой Безье можно выбрать равноотстоящие точки от его середины. Расстояние этих точек от ребра не должно быть слишком большим. Например, можно выбрать один пункт. Существует вероятность, что полигон будет содержать мелкие детали и эти точки окажутся вне окрестности ребра. Можно дополнительно проверить пересечение отрезка между выбранной точкой и серединой ребра с другими ребрами полигона. Другой вариант - перед нормализацией увеличить весь полигон в 5-10 раз, а после нормализации уменьшить.

Для точек vl и vr определяем их принадлежность полигону. Если обе точки принадлежат или обе точки не принадлежат полигону, ребро игнорируется. Если правая точка принадлежит полигону, меняем направление ребра. Выбранные ребра и их вершины добавляются в список также, как это делалось на шаге A2 алгоритма. То есть в список ребра добавляются в правильном направлении. Остается сформировать контуры полигона. Для этого можно использовать шаг A6 алгоритма. После его выполнения мы получим полигон, удовлетворяющий всем требованиям для использования в качестве входных данных алгоритма.

Вместо заключения : Другие алгоритмы построения оверлеев многоугольников

В [1] приводится обзор нескольких алгоритмов построения оверлеев многоугольников. Бо́льшая часть из них не реализует замкнутого набора операций. Из тех, что работают с произвольными многоугольниками, интерес представляет алгоритм триангуляции [2]. Однако, при использовании этого алгоритма кривые Безье будут разбиты на ломаные и обратное восстановление кривой вряд ли будет возможно.

Приведенный в статье алгоритм в целом похож на алгоритм Леонова[3], но используется другой метод маркировки ребер и работает с ребрами, заданными кривыми Безье.


22 апреля 2011

Comments
26.05.2011 12:58 Anon
 Здравствуйте.
 Поясните, пожалуйста, пункт А3.
 
 "Пусть, например, окрестность очередного ребра отмечена признаком 1 (принадлежит к полигону A )." 
 Вы проверяете ребра полигона А относительно В.
 
 Далее в тексте
 "То-же самое выполняется и для ребра, окрестность которого принадлежит полигону A 
 (в этом случае ищем ближайшие ребра, принадлежащие полигону B )."
 Т.е. вы опять проверяете ребра полигона А относительно В?
 Это опечатка? Или я не понял алгоритм?
 
27.05.2011 03:31 alexBlack
 Это опечатка. Спасибо за замечание, исправил. Заодно добавил кусок кода. 
 
15.02.2013 11:38 Lev
 Спасибо, Алекс.
 
 Алгоритм после минимальных изменений очень пригодился. Работает отлично. 
 Единственная проблема возникает при обработке касаний дуг и дуг с отрезками (в силу специфики 
 задачи работаю с дугами, а не с кривыми Безье). Подскажите пожалуйста, где можно посмотреть 
 принципы обработки таких вырожденных случаев. Простые приёмы выбора заданной точности 
 не всегда помогают.
 
17.02.2013 10:08 alexBlack
 А дуги как заданы ? Проблемы с точностью при вычислении точек каcания ? 
 Предлагаю обсудить вопрос в переписке по e-mail.
 
21.02.2013 11:42 Сергей
 Здравствуйте.
 Спасибо Вам!
 
 Вопрос:
 Есть 2 многоугольника. У каждого задано правило (одно из двух: Winding, Alternate)
 Их нужно объединить. Для чего нужна нормализация?
 Почему нельзя отбросить "ребра" каждого многоугольника,
 находящегося внутри другого по правилу этого другого.
 Потом уже соединять оставшиеся по ближайшим углам ?
 
21.02.2013 11:46 Сергей
 Ошибся:
  Почему нельзя отбросить "ребра" каждого многоугольника,
  НАХОДЯЩИЕСЯ внутри другого по правилу этого другого.
  Потом уже соединять оставшиеся по ближайшим углам ?
 
22.02.2013 10:17 alexBlack
 Нормализация нужна чтобы привести оба многоугольника к одному порядку обхода, закрыть 
 незамкнутые контуры, удалить самопересечения. 
 >Почему нельзя отбросить "ребра" каждого многоугольника...
 Многоугольники могут быть с дырками, ребра могут совпадать (полностью или частично).
 
22.02.2013 12:21 Сергей
 Конечно с дырками и незамкнутыми.
 Незамкнутые с точки зрения точности (в смысле расстояние начало-конец)
 или просто смысла не имеют, отбрасываются или замыкются (как опция алгоритма).
 Когда хуждожник создаёт области, они выглядят с его точки зрения правильно,
 потому что однозначно заливаются по правилам Winding или Alternate.
 
22.02.2013 12:23 Сергей
 В Adobe Illustrator, например,  правила заполнения можно задать.
 Порезанные на части контуры нужно отбрасывать (в случае объединения) по очевидному 
 признаку: любая точка >внутри< контура (это значит, что хотя бы одна) лежит в залитой области.
 (для вычитания, пересечения по-другому, но тоже однозначно) (500 не хватает)
 
22.02.2013 08:50 alexBlack
 Ну хорошо, порезали контуры на части и лишние выкинули. 
 (Хотя и здесь не все гладко. Посмотрите на рисунок в A4. Красные ребра внутри синей фигуры, 
 но принадлежат результату, а не выкидываются). 
 Как теперь объединить полученные части контуров в серию замкнутых контуров ?
 По-моему так мы будем ходить по кругу. Вы можете написать полный алгоритм ?
22.02.2013 09:05 Сергей
 Как раз и тут всё правильно.
 Эти рёбра не выкидываются согласно операции "Вычитание"
 
22.02.2013 09:49 Сергей
 Полный алгоритм:
 Исходные данные:
 Два составных пути, состоящие из замкнутых контуров, число которых может быть равно 0.
 Для каждого из них задано правило построения (Alternate или Winding) и
 операция (объединение, пересечение, вычитание, исключение)
 На выходе составной путь, состоящий из замкнутых непересекающися контуров.
 c любым правилом построения.

 1. Найти все точки переречения
 2. Порезать контуры на части.
 3. Удалить контуры в соответствии с заданной операцией.
 4. Соединить оставшиеся контуры
 5. Реверсировать направления обходов полученных контуров в зависимости от уровня вложенности.
 
 
22.02.2013 11:02 alexBlack
 
 
 Ну, не знаю, может я не вижу очевидного. 
 Пример. Из квадрата вычитаем красную стрелку. И квадрат и стрелка 
 заданы контурами против часовой стрелки. Выполняем пункт 4. Для 
 правильного соединения ребер в контуры нужно знать направление обхода
 для ребер результирующей фигуры, а его можно определить проверкой 
 окрестностей как в пункте A5.

22.02.2013 11:29 Сергей
 Тут по-моему совсем просто.
 Может быть вы режете контуры в точках касания ?
 Этого не нужно делать.
 И даже если Вы режете контуры, всё равно получается.
 Причём 2 решения - три треугольника, либо прямоугольник и стрелка.
 Оба решения правильные.
 
22.02.2013 00:11 alexBlack
 Просто для человека. Почему не так, например ?:
 
 
 
23.02.2013 10:22 Сергей
 Не понял, что Вы изобразили.
 Возможно, я думал, что Вы умеете правильно соединять рёбра.
 У Вас что-то написано о сортировке рёбер в точке по углу.
 Если их уметь правильно соединять, то Ваши варианты получится не должны.
 
 Рёбра стыкуются так: (Это касается частных случаев, кроме Exclude, в Exclude остаются 
 практически все рёбра)
 Вы должны придерживаться одного направления стыковки
 По часовой стрелке или против.
 
 При этом Вы никогда не получите самопересечения новых контуров, либо того, что на 
 картинке: одно из рёбер внутри другого контура.
 
 В Вашем примере:
 Выбираем нижнее ребро квадрата.
 Правая нижняя точка - углы 30, 60, 90

 Выбираем  - 90 (max по часовой)
 Верхняя средняя 60, 120, 180
 Выбираем 180. (max по часовой)
 Получаем квадрат и стрелку.
 
 Если выбирать min по часовой, получим 3 треугольника
 
23.02.2013 01:32 alexBlack
 Вот я к тому и веду. Вам все-таки понадобились углы. 
 У Вас слишком общее описание алгоритма. Если начать разбираться в деталях, 
 то понадобится дополнительная информация, и получится не проще, чем описано 
 выше или в других алгоритмах, описанных в [1]. 
 С учетом этого и ответ на Ваш первоначальный вопрос: 
 > Почему нельзя отбросить "ребра" каждого многоугольника,
 > НАХОДЯЩИЕСЯ внутри другого по правилу этого другого.
 > Потом уже соединять оставшиеся по ближайшим углам ?
 потому, что в принципе шаги A2-A5 - это и есть <отбросить "ребра" каждого 
 многоугольника, НАХОДЯЩИЕСЯ внутри другого по правилу этого другого.>, только вместо 
 двух правил (Winding|Alternate) мы используем направление ребер, т.е. сводим их к одному 
 правилу. В любом случае <отбросить> -  довольно сложная операция. Я бы с удовольствием 
 посмотрел реализацию алгоритма, который проще чем описывается здесь. 


23.02.2013 02:23 Сергей
 C учётом добавлений это довольно полное описание.
 Насчёт углов, вроде совсем не сложно.
 
 "Отбросить" - тоже ничего сложного. п.5 надо подправить: реверсировать в случае необходимости.

 У меня есть собственная реализация, которая на данный момент мне, к сожалению, недоступна.
 Постараюсь Вам её отправить, как предоставится такая  возможность.
 Мне понравилось то, что Вы делаете (сайт).
 Хотел Вам помочь.
 
 
23.02.2013 02:49 alexBlack
 Спасибо. С удовольствием посмотрю.
 
27.02.2013 12:02 Dima DD
 Здравствуйте!
 Понадобился такой алгоритм, сижу изучаю... :) Хотя кривые Безье для меня пока не актуальны, но сразу 
 возник вопрос по пункту A1, про сортировку рёбер по относительным углам. Почему бы для случая кривой 
 Безье (E4) не использовать непрямую её наклон в точке v1, как отношение производных по y и по x, 
 а не строить окружность и искать пересечения с нею? Вроде, выражения этих производных весьма 
 просты, надо только знать параметр t кривой в точке v1.
 
27.02.2013 10:38 alexBlack
 В принципе касательная там уже есть. Кривая Безье задана опорными точками, опорная точка с началом 
 кривой дает касательную. Но что если эта касательная совпадет с одним из ребер (или с касательной 
 другой кривой) ? По-моему в этом случае мы не сможем определить с какой стороны от 
 касательной находится кривая и какая из кривых встречается первой, если идти против часовой стрелки.  
 
 На самом деле строить окружность не обязательно. Достаточно взять точку на 
 кривой, недалеко от ее конца (она просто вычисляется по выбранному параметру). 
 Начало кривой с этой точкой дает отрезок и мы берем угол этого отрезка. Он будет 
 чуть меньше (или чуть больше) чем угол касательной и последовательность будет 
 видна. 

09.03.2013 11:14 mundus
 A2. "Ребра одной вершины сортируются по углу ребра относительно точки, в список которой добавляется это ребро."
 
 "угол ребра относительно точки" - это что-то интересное. 
 В целом не критично, конечно, но не делает понимание алгоритма проще - уж точно...
 
12.03.2013 11:14 alexBlack
 Спасибо за замечание. Согласен, изменю формулировку. 
 
17.06.2015 03:24 Альберт
 обОим полигонам

26.06.2015 11:26 alexBlack
 Спасибо за замечание.
 
18.06.2015 07:23 Альберт
 "Для кривых нам нужна некоторая характеристика, которая позволит сравнить ее с другим
  ребром и правильно расположить в списке ребер"
 А чем плоха касательная?
  
 
18.06.2015 07:38 Альберт
 Прочел про касательную. Не соглашусь с автором. Какая то точка на кривой не подходит т.к. 
 кривая может успеть сделать до этой точки несколько осцилляций. Если совпали касательные 
 (первые производные), то надо брать кривизны (вторые), затем третьи производные и т.п.
 
18.06.2015 07:42 Альберт
 Хм, как некрасиво выглядит открывающаяся скобка в конце строки, неужели я там 
 пробел поставил. А как править?
 
 
26.06.2015 11:31 alexBlack
 Править комментарии пока нельзя.
 По поводу касательных мне нужно подумать. 
 
 
05.12.2015 12:22 Ева
 А как определить точки, где не пресекаются фигуры (пустоты), то что внутри? Где фигуры А1 
 - там внутри е пересекаются, как это определить??
 
25.01.2016 09:28 Susik
 Комплексно исследована задача построения оверлеев многоугольников. Предложены два универсальных 
 вычислительно устойчивых алгоритма построения оверлеев на основе триангуляции и линейно-узловой 
 модели. Полученные алгоритмы могут быть использованы также для решения многих  других сложных 
 практических задач, например таких, как построение буферных зон. 
 
Вы можете оставить комментарий или задать вопрос
Ваше имя:

Текст сообщения:


Copyright © 2009-2014 by