|
Рис. 5.4. Построение касательной к дуге (касательная изображена пунктиром). Алгоритм построения касательной к дуге состоит из трех шагов: 1. Одна из точек (в приведенном случае точка А) выбирается в качестве начала координат. 2. Рассматриваются вершины ломаной, лежащие между текущими вершинами, включая ту текущую точку (В), которая не принята за начало координат, и среди них выбирается вершина с максимальным (минимальным) полярным углом по отношению к текущему началу координат (Э). Эта вершина делается второй текущей точкой. 3. Если при проходе по дуге от первой точки (начала координат) ко второй точке дуга загибается по часовой стрелке, то берется максимальный полярный угол, в противном случае минимальный. (Под полярным углом вершины подразумевается угол, описываемый вектором, движущимся вдоль кривой от текущего начала координат до рассматриваемой точки.) Если вектор описывает полный круг, появляется вероятность того, что полярный угол может стать больше 360 градусов. В этом случае текущие точки меняются местами, и процедура повторяется. Алгоритм заканчивает работу тогда, когда положение точек перестает изменяться. Для случая, приведенного на рис. 5.4., последовательность приближений к касательной имеет вид: [А, О], [Э, С], [С, Е]. 106 |
Выделение дуги При прослеживании дуги проверяется правильность направления выпуклости, которую добавляемый отрезок образует с предшествующей частью дуги. В случае отрицательного результата проверки отрезок все равно может быть добавлен к прослеженному пути, если получаемое при этом нарушение выпуклости меньше заданного в эталоне порога. Если же у дуги зафиксировано самопересечение, процесс ее выделения останавливается. Алгоритм выделения дуги основывается на построении касательной к ней (рис. 5.11). Он работает каждый раз с двумя текущими вершинами дуги. Изначально в качестве текущих вершин выбираются концы дуги (А и В). По окончании работы алгоритма текущими вершинами становятся концы касательной (С и О). Рис. 3.12. Построение касательной к дуге (касательная изображена пунктиром). Шаг 1. Одна из точек (в данном случае точка А) выбирается в качестве начала координат. Шаг 2. Рассматриваются вершины ломаной, лежащие между теку щими вершинами, включая ту текущую точку (В), которая не принята за начало координат, и среди них выбирается вершина с максимальным (минимальным) полярным углом по отношению к текущему началу координат (О); эта вершина делается второй текущей точкой. 74 Шаг 3. Если при проходе по дуге от первой точки (начала координат) ко второй точке дута загибается по часовой езрелке, то берется максимальный полярный угол, в противном случаем минимальный. (Под полярным углом вершины подразумевается угол, описываемый вектором, движу щимся вдоль кривой от текущего начала координат до рассматриваемой точки.) Если вектор описывает полный круг, полярный угол может стать больше 360 градусов. В этом случае текущие точки меняются местами и процедура повторяется. Алгоритм заканчивает работу' тогда, когда положение точек перестает изменяться. Для случая, приведенного на рис. 5.11, последовательность приближений к касательной имеет вид: [А, И], [Э, С], [С, Е]. Выделение кольца Выделение кольца базируется на алгоритме выделения дуги. Для выделения колец запускается слегка модифицированный механизм прослеживания дуг. При этом используются только два критерия останова по невозможности продолжить выделение и по изолированному концу. Рис. 3.13. Замыкание кольца. В ходе работы алгоритма делается попытка из каждого полученного варианта дуги сформировать кольцо. Для этого у дуги по очереди отсекается начальная и конечная часть. Для полученного остатка проверяются условия принадлежности к кольцу строгость, кривизна, размер общей части и т. д. Необходимость вырезания кольца из 75 |