Письменный отчёт по выбору алгоритмов

[kapitangeorge]

➤ Валерия commented:

1. Если мы построим диаграмму Вороного с помощью алгоритма Форчуна, у нас получится внутренний скелет среза. Для того чтобы разделить срез по цветам, мы должны взять точку граничащего цвета и соединить с ближайшей точкой внутреннего скелета. Алгоритм поиска ближайшей точки как раз реализуется с помощью диаграммы Вороного. Но ближайшая точка должна будет находиться в ячейке Вороного. А нам нужны будут точки, лежащие на ребрах ячеек Вороного. И еще одним существенным минусом является сложная реализация данного алгоритма.
   2. Алгоритм водораздела является основным инструментом математической морфологии для сегментации изображений. На нашем примере, мы бы сегментировали полученный срез по цветам. Но так как изображения — это растровая графика, а мы работаем с векторной, работа с этим алгоритмом затруднена.

[kapitangeorge]

➤ Титов Георгий commented:

1. Алгоритм водораздела с переводом среза из векторной графики в растровую. 1) Расторизация. Перевод из векторной графики в растровую. Проходим по точкам по часовой стрелке и преобразуем точки слоя в пиксели попутно рисуя прямые, но так как алгоритм водораздела работает с цветными пространствами, нам необходимо разукрашивать внутренние треугольники, которых у нас нет, поэтому придется воспользоваться алгоритмом треангуляции Делоне, а потом только разукрасить треугольники, не говоря о том, что далее сам алгоритм водораздела и перевод из растра в векторы. Вывод: реализации алгоритмов есть, но очень долго
   2. Алгоритм с использованием нормалей. 1)Находим середину слоя, сортируем точки по часовой стрелке относительно середины и началом в одной из крайних точек. 2) Берём первую и последнюю точку в массиве соединяем их отрезком. Опускаем нормаль из крайней точки на полученный отрезок. Если первая и последняя точка разных цветов, то мы точку пересечения нормали и отрезка отмечаем, как границу и строим отрезок , соединяя эту точку и первую в массиве 3) Со второй точки в массиве, строим отрезок противоположенный нормали, находим точку пересечения его с контуром слоя. Находим длину этого отрезка. И теперь на длине 1/5 длины отрезка от первоначальной точки отмечаем точку внутреннего слоя, тем самым формируя внутренний дефолтный слой. 4) Перебирая слои запоминаем точки внутренней границы слоя и границы цветов. При переходе на следующий слой и его обработки, соединяем в треугольники границы цветов и внутреннего слоя, получая тем самым внутренние вертикальное обрамление (эти треугольники дублируем)

[kapitangeorge]

➤ Валерия commented:

https://docs.google.com/document/d/1saJn7OEpnon7mughV5i2L3pG3xefnaw6nNvXcn7N42g/edit