arthur2 писал(а):На отрезке от синей до синей точки алгоритм выполняется, а вот от синей до зеленой - нет, хотя зеленая - ну никак не вершина. Я понимаю, что чего-то недопонял
Зря, это особенность алгоритма. Действительно, проблема есть, но она не такая страшная: можно после обхода пройтись по списку вершин и удалить все коллинеарные тройки. Это не сложно, если точек много, а вершин — мало. Другой способ: вместо того, чтобы ждать первого неуспешного BCT, обходишь список точек с конца до первого успешного BCT. Тогда до зелёной вершины дело не дойдёт, а ложных срабатываний (
если нет смыкающихся участков контура вообще не будет никогда) не произойдёт. Но здесь ́б́ольшая вычислительная сложность. Третий вариант: так видиозменить дифференциальный BCT, что для зелёной точки срабатывания не произойдёт. И ещё вариант: вместо того, чтобы действовать при первом 1-пиксельном сбое BCT, замечать такие сбои, но не останавливаться на них, а идти дальше до 2-пиксельного сбоя BCT. При двухпиксельном сбое останавливаться и брать во внимание как вершину from-точку, которая дала последний успешный BCT. При таком случае зелёная точка «обнаружится», но проскочится, и выполнение дойдёт до истинной вершины (она зафиксируется как «последняя успешная»), а потом после этой точки как ни крути произойдёт 2-px-сбой BCT. Последний вариант при правильной реализации выглядит наиболее привлекательным. В общем, вариантов я предложил море.
arthur2 писал(а):А с порядком добавления вершин - вообще не понял
Список вершин надо реализовывать не как список пар координат точек, а как список указателей/индексов на элементы отсортированного списка точек. При добавлении элемента в список вершин надо перебирать его с начала до пункта, значение (а это указатель/индекс элемента в др. списке (точек)) которого будет меньше или равно порядковому номеру элемента списка точек, который (элемент) соответствует текущей точке, то есть точке, которая детектирована как вершина и как раз сейчас добавляется в список.
Фразу «перебирать его с начала» надо воспринимать условно. Конечно, так можно делать, формально это праивльно, но страшно неэффективно по той причине, что нет смысла в следующий раз перебирать список с начала, потому до уже обойдённого элемента ничего гарантированно измениться не может. Иначе получается «алгоритм маляра Шлемеля» (прочитать о явлении можно
тут).
В принципе, можно «не заморачиваться» на этом, а добавлять вершины в список вершин в том порядке, в котором они находятся (обнаруживаются). В конце обхода просто отсортировать этот список по значениям элементов (это указатели/индексы). Но и это неэффективно. Любая сортировка превращает хаос в порядок. Вместо того, чтобы сначала преднамеренно создавать хаос, а потом вынужденно устранять его, я предлагаю изначально создавать порядок, а потом не тратить ресурсы на его создание (он уже есть) из хаоса.
В общем, на шаге фильтрации списка точек, очень вероятно, возникнут неустранимые тупики. Они будут разрешены (resolved), а как побочный эффект — в списке вершин ещё до циклических BCT уже появятся вершины. К моменту начала этапа циклических BCT нужно завести указатель/индекс на элемент списка вершин и установить его на первый элемент списка (если он есть, потому что список запросто может к этому моменту быть пока ещё пустым).
В момент добавления вершины в список вершин нужно сдвигать этот указатель (можно называть его «курсором вставки» (insertion cursor) вперёд до тех пор, пока элемент, на который он указывает, не станет по значение больше индекса текущей точки. При этом (сдвигах курсора) элементы в списке вершин могут кончиться, в этом случае курсорный указатель/индекс нужно обнулить, т.е. привести его в такое состояние, как если бы список вершин вообще был изначально пуст.
А после этого:
- курсор сброшен (список вершин был пуст или достигнут его конец) — добавляем новый элемент в конец списка.
- курсор установлен на какой-то элемент — проверяем, отличается ли индекс добавляемой точки от значения элемента, на который указывает курсор:
- отличается — вставляем в список вершин новый элемент до элемента, на который указывает курсор
- не отличается — ничего не добавляем (нет смысла плодить дубли), но сдвигаем указатель на следующий элемент списка, либо сбрасываем курсор, если дальше ничего нет.
Ну, надеюсь, теперь понятно? Я уже не знаю, как более доступно разжевать.
arthur2 писал(а):То есть, если этим способом векторизировать растровую окружность, а потом увеличить - получится многоугольник.
Увы и ах: это не практически, а теоретически неразрешимая проблема. Извлечь из растра информацию, которой там в принципе нет, — невозможно. Что на самом деле нарисовано — окружность или 10-угольник — не может достоверно сказать никто, кроме растеризатора, если такой был.
Впрочем, можно и это решить: после векторизации полигон превратив в Безье-сплайн, подобрав длину «усиков» по специальному хитрому алгоритму.