КОМПЬЮТЕРНЫЙ СПОСОБ ФОРМИРОВАНИЯ ИЗОБРАЖЕНИЯ ЧАСТЕЙ ЛОМАНОЙ ЛИНИИ, ЛЕЖАЩИХ КАК ВНУТРИ, ТАК И ВНЕ МНОГОУГОЛЬНОЙ ОБЛАСТИ, И КОМПЬЮТЕРНЫЙ СПОСОБ ФОРМИРОВАНИЯ ИЗОБРАЖЕНИЯ ГРАНИЦ ОДНОЙ ИЛИ НЕСКОЛЬКИХ ОБЛАСТЕЙ, ПОЛУЧЕННЫХ В РЕЗУЛЬТАТЕ ПРИМЕНЕНИЯ ЗАДАННОЙ ЛОГИЧЕСКОЙ ОПЕРАЦИИ К ДВУМ МНОГОУГОЛЬНЫМ ОБЛАСТЯМ Российский патент 2008 года по МПК G06T11/00 G06F17/00 

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

В современных геоинформационных системах (ГИС) и земельно-информационных системах (ЗИС) актуальной является задача выполнения различных логических операций над объектами, представляющими собой векторные изображения материальных объектов в виде ломаных линий на плоскости (ниже - «ломаных линий») и областей на плоскости (ниже - «областей»). Для ломаной линии и области определены операции пересечения ломаной линии с областью и вычитания области из ломаной линии. Для областей определены операции объединения, пересечения и вычитания одной области из другой. Такие операции используются как при создании и проверке корректности топографических карт и планов, так и на этапе использования карт и планов в ГИС (ЗИС).

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

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

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

На этапе эксплуатации ГИС (ЗИС) выполнение логических операций над областями используется как при интеграции распределенных баз данных (создании единых векторных карт из нескольких тематических), так и при реализации запросов на выдачу геометрических свойств объектов и их сочетаний. Например, при объединении информации из топографических и из гидрографических карт (планов) необходимо получать границы тех частей земельных участков, которые соответственно заняты и не заняты объектами гидрографии (реками, прудами, озерами, болотами и т.п.). Это приводит к необходимости выполнения операций пересечения и вычитания площадных объектов.

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

В [М. de Berg, M. van Kreveld, M.Overmars, O.Schwarzkoft. Computational Geometry. Algorithms and Applications. Springer-Verlag Berlin Heidelberg, 1997. pp.33-39] излагается способ определения частей ломаной линии, лежащих внутри и лежащих вне многоугольной области, заданной как набор контуров в виде многоугольников на плоскости, включающий в себя внешний контур и контуры дыр, в котором формируют части ломаных линий, лежащие внутри или вне указанной области, путем анализа взаимного расположения указанной ломаной линии и границ указанной области, используя вычисление координат точек пересечения ломаной линии и контуров границы области и определение взаимного расположения отрезков ломаной линии и отрезков границ области методом заметания плоскости. Недостатком этого способа является его низкая надежность в ситуациях, когда некоторые вершины ломаной линии расположены очень близко к границам области. В этом случае при определении точек пересечения получаются плохо обусловленные системы уравнений, что приводит к очень большим погрешностям при определении точек пересечения, а также к ошибкам в определении взаимной ориентации контуров и, как следствие, к неправильным результатам при определении тех частей ломаной линии, которые лежат внутри или вне области.

Известно несколько способов выполнения логических (булевских) операций (пересечения, объединения, вычитания) над многоугольными областями. В [Иванов А.В. Алгоритм нахождения пересечения простых многоугольников // Моделирование и анализ информационных систем. - вып.3, Ярославль, 1996, с.15-27] и в [М. de Berg, М. van Kreveld, М.Overmars, O.Schwarzkoft. Computational Geometry. Algorithms and Applications. Springer-Verlag Berlin Heidelberg, 1997. pp.39-40] излагается способ выполнения булевских операций (пересечения, объединения, вычитания) над многоугольными областями, в котором выбирают положительное число ε>0, задающее точность вычисления результата, равным точности машинного представления координат вершин многоугольников, и определяют многоугольники, являющиеся границами указанных многоугольных областей результата, с точностью ε, путем вычисления координат точек пересечения границ первой и второй области и формирования границ областей результата методом заметания плоскости. Недостатком этого способа является его низкая надежность в ситуациях, когда некоторые вершины границ одной из областей расположены очень близко к границам второй области. В этом случае при определении точек пересечения получаются плохо обусловленные системы уравнений, что приводит к очень большим погрешностям при определении точек пересечения, а также ошибкам в определении взаимной ориентации контуров и, как следствие, к неправильным результатам при определении топологической структуры результата.

В [Fortune S, Van Wyk C.J. Static analysis yields efficient exact integer arithmetic for computational geometr // ACM Trans. Graph. - vol.15, N 3. - 1996, pp.223-248] этот способ был улучшен за счет использования сверхточной арифметики, когда вычисления проводятся с точностью, превышающей обычную машинную точность. В этом случае результаты всегда оказываются правильными, но здесь возникают три проблемы. Во-первых, в результате координаты вершин получающихся границ областей имеют вид чисел в формате с повышенной разрядностью и для получения окончательного результата их необходимо округлить до точности обычного машинного представления. Это необходимо произвести так, чтобы получающиеся границы областей и их дырок взаимно не пересекались, что является непростой задачей в случае, когда они подходят близко друг к другу. Во-вторых, в общем случае получающиеся области могут иметь очень тонкие длинные выступы, что недопустимо для целей применения этого способа в ГИС (ЗИС), поскольку там имеются ограничения на минимальные расстояния между разными линиями. В-третьих, использование сверхточной арифметики очень сильно увеличивает время выполнения операций, что особенно сильно сказывается на времени решения задач ГИС (ЗИС), когда реально приходится обрабатывать области с границами, имеющими до нескольких тысяч вершин.

В [Шебашев В.Е. К задаче определения взаимного положения двух плоских контуров // Тр. науч. конф. по итогам н.-и. работ Map. гос. техн. ун-та, Йошкар-Ола, 1999, с.23-25. Деп. в ВИНИТИ 21.06.99б N 1997 - В99] предложен способ определения пересечения многоугольных областей путем обхода контуров. Он обладает тем же недостатком: при пересечении границ двух многоугольников под очень острым углом возникающая неточность результата вычисления точки пересечения может приводить к неправильным результатам. Заложенная в основу способа фиксированная точность формирования результата (максимальная ошибка 0,5% от длины отрезка ломаной) в общем случае явно недостаточна для определения топологической структуры результата пересечения областей. Кроме того, этот способ не рассчитан на обработку областей с дырами.

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

Решение первой задачи достигается за счет формирования изображения частей ломаной линии, лежащих как внутри, так и вне многоугольной области, заданной как набор контуров в виде многоугольников на плоскости, включающий в себя внешний контур и контуры дыр, с заданной точностью ε, существенно большей результата умножения максимального значения всех длин сторон упомянутых многоугольных контуров на 2^-n, где n - разрядность мантиссы в представлении плавающих чисел в процессоре компьютера. При этом вводят в оперативную память компьютера данные упомянутой ломаной линии и упомянутой многоугольной области, представляющие собой упорядоченные последовательности координат вершин упомянутой ломаной линии и упомянутых контуров в порядке их обхода. Далее выполняют в процессоре компьютера обработку введенных данных, в ходе которой:

- находят пограничные части упомянутой ломаной линии, лежащие в ε-окрестности границы упомянутой многоугольной области, и оставшиеся части;

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

- классифицируют упомянутые оставшиеся части на внутренние и внешние в зависимости от того, является ли результат упомянутого подсчета, соответственно, нечетным или четным.

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

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

Важнейшим свойством предлагаемого способа является то, что для определения положения частей ломаной линии относительно границ области используются точки на ломаной линии, которые отстоят от границ области на расстояние, не меньшее фиксированного значения ε. Это обеспечивает достижение основного технического результата, состоящего в повышении надежности выполнения операций над ломаной линией и областью. Под надежностью здесь понимается вероятность правильно полученных результатов выполнения операций среди всех возможных пар из ломаной линии и области. Следует заметить, что ввиду конечной разрядности машинного представления координат вершин ломаной линии и координат вершин границ области число всех возможных вариантов исходных данных конечно, и тем самым определение вероятности корректно (в отличие от известного парадокса Бюффона здесь имеется естественное определение вероятностной меры, связанное с конечно-разрядным представлением исходных данных).

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

Возможно несколько вариантов задания частей ломаной линии. Например, часть ломаной линии может быть задана указанием начальной точки и длиной этой части. Часть ломаной линии может быть задана указанием координат начальной и конечной точки с указанием того, на каких звеньях ломаной линии эти точки находятся (это необходимо, поскольку ломаная линия в общем случае может иметь петли, т.е. одной и той же точке на плоскости может соответствовать несколько точек ломаной линии). Предпочтительным способом задания частей ломаной линии является способ, состоящий в том, что начальную и конечную точку части ломаной линии задают указанием номера прямолинейного отрезка ломаной линии и доли длины этого отрезка, соответствующей положению начальной или конечной точки части ломаной линии на этом прямолинейном отрезке ломаной линии. Таким образом, часть ломаной линии задают как пары ((m, a), (n, b)), где m и n - номера прямолинейных отрезков, на которых расположены начальная и конечная точки части ломаной линии, а значения 0≤а, b<1 определяют положение начала и конца части ломаной линии на соответствующем прямолинейном отрезке.

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

Способ получения укрупненных частей ломаной линии, лежащих как внутри, так и вне области, состоит в том, что после получения пограничных, внутренних и (или) внешних частей ломаной линии производят укрупнение частей ломаной линии, лежащих внутри (вне) области. Для этого сначала приписывают им тип t, равный -1, 0 или 1 в зависимости от того, лежит эта часть внутри области, в ε-окрестностях границ области или вне области, и заменяют пары ((m_j, a_j), (n_j, b_j)) (см. выше) тройками ((m_j, a_j), (n_j, b_j), t_j), где t_j - тип части ломаной линии ((m_j, a_j), (n_j, b_j)). Упомянутые части ломаной линии упорядочивают в соответствии с порядком на множестве точек на ломаной линии. После этого последовательно просматривают все части ломаной линии, и для каждой части ломаной линии ((m_j, a_j), (n_j, b_j), t_j), для которой t_j=0, рассматривают предыдущую (j-1)-ю и следующую (j+1)-ю части ломаной линии, где для замкнутой ломаной линии вычитание и прибавление 1 производят по модулю общего числа s частей ломаной линии, а для незамкнутой ломаной линии просматривают все части ломаной линии, кроме первой и последней. Если конец предыдущей части не совпадает с началом рассматриваемой части ломаной линии и начало следующей части ломаной линии не совпадает с концом рассматриваемой части ломаной линии, то рассматриваемую часть ломаной линии удаляют из последовательности {((m_j, a_j), (n_j, b_j))}, уменьшая номера всех последующих частей на 1 и уменьшая общее число частей на 1. Если же конец предыдущей части ломаной линии совпадает с началом рассматриваемой части ломаной линии и начало следующей части ломаной линии совпадает с концом рассматриваемой части ломаной линии, то тройку ((m_j-1, а_j-1), (n_j-1, b_j-1), t_j-1), ((m_j, a_j), (n_j, b_j), t_j), ((m_j+1, а_j+1), (n_j+1, b_j+1), t_j+1) заменяют одной частью ломаной линии ((m_j-1, a_j-1), (n_j+1, b_j+1), t_j-1), уменьшая номера всех последующих частей ломаной линии на 2 и уменьшая общее число частей ломаной линии на 2.

Такой способ формирования частей ломаной линии, лежащих внутри (вне) области, обеспечивает получение еще одного технического результата, состоящего в устранении дробления ломаной линии на слишком мелкие части в ситуации, когда ломаная линия проходит вблизи границы области, периодически заходя внутрь области и выходя из нее. Это соответствует известному картографическому правилу, состоящему в том, что при нарезке карты на листы в подобной ситуации допускается слегка деформировать линейный объект, чтобы обеспечить достаточно большую протяженность получаемых в результате обрезки объектов (обычно не менее 5-10 мм в масштабе карты).

Решение второй задачи достигается за счет формирования изображений границ областей, полученных в результате применения заданной логической операции к двум многоугольным областям, каждая из которых определена на плоскости в виде набора многоугольных контуров, имеющего внешнюю границу и, возможно, границы хотя бы одной дыры, где в результате выполнения указанных операций получаются наборы многоугольных областей, причем для формирования результата операции определяют многоугольники, являющиеся границами указанных многоугольных областей результата, с точностью ε, существенно большей результата умножения максимального значения всех длин сторон упомянутых многоугольных контуров на 2^-n, где n - разрядность мантиссы в представлении плавающих чисел в процессоре компьютера. При этом для каждой из двух областей находят те части замкнутых ломаных линий, являющиеся каждым из упомянутого набора многоугольных контуров, составляющих границу этой области, которые являются пограничными, внутренними или внешними по отношению к другой области в соответствии с упомянутой логической операцией, согласно вышеописанному способу получения укрупненных частей ломаной линии (п.6 формулы). Далее отбирают из всех найденных пограничных частей те, которые имеют направление обхода, совпадающее с направлением обхода другого многоугольного контура, или направление обхода, противоположное направлению обхода другого многоугольного контура, в соответствии с упомянутой заданной логической операцией. После этого находят части границ областей упомянутого результата путем объединения найденных на двух предыдущих шагах частей всех ломаных линий в контуры с добавлением при необходимости отрезков длины ε, соединяющих упомянутые части, принадлежащие разным исходным контурам. Наконец, выдают на устройство вывода компьютера изображения контуров границ областей упомянутого результата. При этом границы каждой из двух исходных областей могут иметь самопересечения и (или) взаимные пересечения, причем внутренности областей определяют как геометрические места точек, для которых какой-либо луч, выходящий из данной точки, имеет нечетное число пересечений с линями границ области.

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

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

Изобретение поясняется чертежами, где:

Фиг.1. Сравнение надежности определения взаимной ориентации контуров.

Фиг.2. Положение отрезка относительно ε-окрестности другого отрезка.

Фиг.3. Определение точки входа отрезка в ε-окрестность другого отрезка.

Фиг.4. Точный результат пересечения областей.

Фиг.5. Предпочтительный приближенный результат пересечения областей.

Фиг.6. Переход границы объединения областей с границы одной области на границу другой области.

Фиг.7. Переход границы объединения областей с границы одной области на другую часть границы той же области.

Фиг.8. Возникновение дополнительной дырки при объединении областей.

Фиг.9. Возникновение дополнительной области из дырок при пересечении областей.

Фиг.10. Случай пересечения ломаных линий с одинаковыми направлениями.

Фиг.11. Случай пересечения ломаных линий с разными направлениями.

Осуществление изобретения

1. Реализуемость способа выполнения операции над ломаной линией и областью

1.1. Описание способа в целом

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

Определение пограничных частей ломаной линии, лежащих в ε-окрестности границ области, и оставшихся частей ломаной линии может быть произведено несколькими способами в зависимости от наличия дополнительной информации о границах области. Например, из каких-либо дополнительных соображений могут быть известны контуры границ ε-окрестностей границ области, и тогда концы указанных частей ломаной линии могут быть вычислены как пересечения звеньев ломаной линии с этими известными контурами границ ε-окрестностей. Если такая информация неизвестна, то концы пограничных частей ломаной линии вычисляют без использования дополнительной информации при помощи способа, изложенного в п.1.2.

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

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

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

Способ определения частей ломаной линии, лежащих внутри (вне) области и не пересекающихся с ε-окрестностями границ второй области, по общему списку {(m_k, a_k), (n_k, b_k)}, 0≤k<M, частей ломаной линии (см. п.1.3), не пересекающихся с ε-окрестностями границ области, состоит в том, что в каждой из указанных частей ломаной линии, не пересекающихся с ε-окрестностями границ области, выбирают произвольную точку, вычисляют ее координаты и затем из полученной совокупности точек выбирают те точки, которые лежат внутри (вне) области. Соответствующие этим точкам части ломаной линии являются искомыми частями ломаной линии, лежащими внутри (вне) области и не пересекающимися с ε-окрестностями границ области.

Выбор точек в каждой из частей ломаной линии, не пересекающихся с ε-окрестностями границ области, производят, например, следующим образом. Пусть A₀A₁…A_n-1 - замкнутая или незамкнутая ломаная линия, содержащая n вершин, и {(m₀, c₀), (m₁, c₁)} - часть этой ломаной линии, не пересекающаяся с ε-окрестностями границ области (см. п.1.3). Если m₀<m₁, то в качестве искомой точки на ломаной линии берут пару (m₁, 0). Если m₀>m₁, то в качестве искомой точки на ломаной линии берут пару (m₀, 0). Если m₀=m₁ и c₀<c₁, то в качестве искомой точки на ломаной линии берут пару (m₀, (с₀+c₁)/2). Наконец, если m₀=m₁ и с₀>c₁, то в качестве искомой точки на ломаной линии берут пару (m₀+1, 0) (если m₀+1=n, то m₀+1 заменяют на 0). Допустимо использование и других способов выбора таких точек.

Координаты (х, у) произвольной точки на ломаной линии (m, а) определяют следующим образом. Если а=0, то (х, у) полагают равными координатам (х_m, у_m) точки А_m. В противном случае определяют номер m1=m+1 следующей точки (если m1=n, то полагают m1=0) и вычисляют координаты (х, у) по формулам

x=x_m+(x_m1-x_m)*а, у=у_m+(у_m1-у_m)*а.

Из полученных для всех М частей границ {(m_k, а_k), (n_k, b_k)} точек с координатами (x_k, у_k) отбирают те точки, которые лежат внутри (вне) области. Для этого проводят горизонтальный луч из точки (x_k, у_k) в направлении возрастания координаты х и подсчитывают число пересечений этого луча с отрезками, образующими границы области. Если число пересечений нечетно, то точка (x_k, у_k) лежит внутри области; если число пересечений четно, то точка (x_k, у_k) лежит вне области. Случай близости точки (x_k, у_k) к границе области исключается, поскольку точка (x_k, у_k) выбрана из частей ломаной линии, не пересекающихся с ε-окрестностями границ области.

Отобрав таким образом из общего списка точек (х_k, у_k), 0≤k<М, последовательность индексов k₀, …, k_s-1 точек, лежащих внутри (вне) области, получают искомую последовательность {(m_kj, a_kj), (n_kj, b_kj)}, 0≤j<s, частей ломаной линии, лежащих внутри (вне) области и не пересекающихся с ε-окрестностями границ области.

Возможно несколько вариантов учета пограничных частей ломаной линии, каждый из которых имеет преимущество в той или иной ситуации. Например, можно не включать такие части ломаной линии в результат операции. В случае пересечения ломаной линии с областью это соответствует пересечению ломаной линии с открытой областью, т.е. с областью без границы, а в случае вычитания области из ломаной линии - вычитанию замкнутой области, т.е. областью с границей. Напротив, можно включать такие части ломаной линии в результат операции. В случае пересечения ломаной линии с областью это соответствует пересечению ломаной линии с замкнутой областью, а в случае вычитания области из ломаной линии - вычитанию открытой области. Если пограничные части ломаной линии не включаются в результат операции, то никаких дополнительных действий не требуется. В противном случае может оказаться, что пограничная часть ломаной линии расположена между двумя частями ломаной линии, которые включены в результат. В этом случае производят объединение этих трех частей ломаной линии в одну часть, которая с точностью ε лежит внутри области или вне области. Тем самым производят укрупнение частей ломаной линии, входящих в результат выполнения операции. Способ укрупнения частей ломаной линии описывается в п.1.5.

Изложенный способ определения частей ломаной линии, лежащих внутри и (или) лежащих вне многоугольной области, обеспечивает достижение основного технического результата, состоящего в повышении надежности результата выполнения операции. Природа повышения надежности связана со следующим обстоятельством. В известном способе выполнения геометрических операций над ломаной линией и областью одним из важнейших моментов является определение взаимного расположения двух контуров в окрестности точки их пересечения. В случае большой погрешности определения точки пересечения получаемый результат будет сильно отличаться от правильного. Но даже при точно вычисленной точке пересечения возникает проблема в определении того, входит ломаная линия внутрь области или выходит из нее. Характерный пример приведен на фиг.1. Возможен случай, когда отрезок АВ ломаной линии расположен очень близко к отрезку CD границы области. Эта ситуация очень часто встречается в реальной практике, когда, например, контур …АВ… идет по границе некоторой области, полученной в результате пересечения некоторой области с областью …CD…, и из-за погрешностей вычислений, связанной с ограниченной разрядностью машинного представления чисел с плавающей точкой, точки А и В лежат не точно на отрезке CD. В известных способах вычисляют векторное произведение векторов АВ и CD и по знаку векторного произведения судят о взаимном расположении контуров. Но в случае, когда расстояние от точек А и В до отрезка CD очень мало и не превосходит, скажем, 2^-n от длины CD, где n - разрядность машинного представления мантиссы, результат вычисления знака векторного произведения из-за ошибок округления оказывается непредсказуемым. В отличие от этого, в предлагаемом способе вместо точек А и В, расстояния от которых до границы области не являются ограниченными снизу, используются точки A₁ и B₁, расположенные не ближе, чем фиксированное расстояние ε от границы области. Это обеспечивает более надежное определение взаимной ориентации контуров и тем самым повышает надежность результатов выполнения операций над ломаной линией и областью в целом.

Следует заметить, что указанный в предыдущем абзаце случай является очень часто встречающимся в реальном производстве картографической продукции. Типичной ситуацией является то, что контур …АВ… является линейным объектом, идущим вдоль контура площадного объекта, а контур …CD… - границей номенклатурного листа. При производстве картографической продукции сначала производят оцифровку контуров всех объектов данного района работ, а затем производят автоматическую нарезку всей получившейся карты на номенклатурные листы. В дальнейшем в ходе проведения контроля полученных листов часто возникает необходимость внесения исправлений в какой-либо лист карты, после чего еще раз производят обрезку по границе номенклатурного листа. В этом случае возникают ситуации взаимного расположения двух контуров, похожие на описанную в предыдущем абзаце, но когда ломаная линия лежит примерно по одну сторону от границы области (ломаная линия A₁ABB₂ на фиг.1). В результате ошибки в определении взаимной ориентации двух контуров вместо того, чтобы получить правильный результат обрезки ломаной линии A₁ABB₂, получают короткий отрезок, содержащий вершину В. Предлагаемый нами способ существенно уменьшает вероятность возникновения такого рода ошибок.

Заметим, что в реально встречающихся на практике задачах разумная величина ε существенно превосходит результат умножения максимального значения всех длин сторон упомянутых многоугольных контуров на 2^-n, где n - разрядность мантиссы в представлении плавающих чисел в процессоре компьютера. Например, в задачах картографии, связанных с автоматической нарезкой карты на листы, максимальная длина отрезков многоугольников заведомо не превосходит (в масштабе плана или карты) размера листа, что заведомо меньше 1 м. При этом разумная величина ε составляет порядка долей миллиметра. Таким образом, отношение ε к величине максимальной стороны многоугольного контура составляет величину порядка 10^-4, т.е. порядка 2^-13. В то же время значение n равно 32 или 64, что обеспечивает выполнение указанного условия. Аналогичные оценки могут быть сделаны и для других реально возникающих задач.

Второй технический результат, получающийся в результате выполнения предлагаемого способа, состоит в расширении возможностей выполнения логических операций над ломаной линией и областью, что связано с возможностью выполнения операции над ломаной линией и областью в случае, когда границы области могут иметь самопересечения и взаимные пересечения. Вышеизложенный способ определения того, лежит рассматриваемая часть ломаной линии внутри или вне области с границей без самопересечений, путем определения четности числа пересечений луча, выходящего из какой-либо точки рассматриваемой части, с границами области, является известным способом и описан, например, в [Препарата Ф, Шеймос М. Вычислительная геометрия: Введение. М, «Мир», 1989, с.59]. Мы используем обобщение этого способа на области, границы которых могут иметь самопересечения и взаимные пересечения. В этом случае под внутренностью области понимается совокупность точек плоскости, для которых любой луч, выходящий из данной точки, имеет нечетное число пересечений с границами области.

1.2. Предпочтительный способ определения пограничных частей ломаной линии

1.2.1. Общее описание

Предпочтительный способ определения пограничных частей ломаной линии состоит в выполнении трех этапов: сначала определяют список всех пар (I, II), где I - прямолинейный отрезок ломаной линии, II - прямолинейный отрезок ломаной границы области, причем I пересекает ε-окрестность отрезка II, затем для всех пар из полученного списка определяют пересечения отрезка I с ε-окрестностью отрезка II, затем исходя из всех полученных пересечений формируют пограничные части ломаной линии.

Возможность реализации всех указанных этапов обосновывается ниже в п.п.1.2.2-1.2.4 соответственно.

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

Способ определения всех пар (I, II), где I - прямолинейный отрезок ломаной линии, II - прямолинейный отрезок контура границы области, причем отрезок I пересекает ε-окрестность отрезка II, состоит в том, что сначала определяют все пары (I, II), где I - прямолинейный отрезок ломаной линии, II - прямолинейный отрезок ломаной границы области, причем отрезок I пересекает отрезок II, используя любой из известных способов определения пересекающихся отрезков, например, изложенный в [М. de Berg, М. van Kreveld, М.Overmars, О.Schwarzkoft. Computational Geometry. Algorithms and Applications. Springer-Verlag Berlin Heidelberg, 1997, pp.19-29], а затем к этим парам добавляют такие пары (I, II), для которых расстояние от одного из концов какого-либо отрезка до другого отрезка меньше ε. На практике удобно сначала найти все пары отрезков, для которых пересекаются ограничивающие их прямоугольники (увеличенные на ε/2 вдоль каждой из сторон) со сторонами, параллельными осям координат, и из полученных пар производить отбор нужных пар отрезков.

Правильность этого способа обосновывается с помощью следующих рассмотрений. Определение факта пересечения одного отрезка I с ε-окрестностью второго отрезка II зависит от взаимного расположения отрезков. Ниже излагается анализ всех возможных случаев. Все принципиально разные положения отрезка I относительно отрезка II будем обозначать арабскими цифрами 1, 2, …. Отрезок I будет рассматриваться как направленный, а его конец будет изображаться стрелкой. Возможно ровно три следующих случая (фиг.2):

1 - отрезки I и II пересекаются;

2 - расстояние от начала отрезка II до отрезка I меньше ε или расстояние от конца отрезка II до отрезка I меньше ε; или расстояние от начала отрезка I до отрезка II меньше ε или расстояние от конца отрезка I до отрезка II меньше ε;

3 - отрезок I не пересекает ε-окрестность отрезка II.

В самом деле, пусть отрезки I и II не пересекаются, но отрезок I пересекает ε-окрестность отрезка II. Если отрезок I пересекает полукруг с центром в точке А, являющийся частью ε-окрестности отрезка II (случаи 2.1-2.7), то расстояние от начала отрезка II до отрезка I меньше ε (см. фиг.2). Аналогично, если отрезок I пересекает полукруг с центром в точке В, являющийся частью ε-окрестности отрезка II, то расстояние от конца отрезка II до отрезка I меньше ε. Пусть, наконец, отрезок I пересекает ε-окрестность отрезка II, но не пересекает полукруги с центрами в точках А и В. Выберем систему координат так, чтобы отрезок II был горизонтальным, как это изображено на фиг.3. Тогда отрезок I пересекает прямоугольник CDEF, представляющий прямоугольную часть ε-окрестности отрезка II. Поскольку отрезок I по предположению не пересекает отрезок II, то он лежит либо целиком выше отрезка II, либо целиком ниже. Так как отрезок I не пересекает полукруги А и В, то либо начало, либо конец отрезка I попадают внутрь прямоугольника CDEF, и поэтому расстояние от начала отрезка I до отрезка II меньше ε или расстояние от конца отрезка I до отрезка II меньше ε.

Таким образом, все случаи, когда отрезок I пересекает ε-окрестность отрезка II, соответствуют случаям 1 и 2, откуда и вытекает правильность предложенного способа.

1.2.3. Определение пересечения отрезка I с ε-окрестностью отрезка II

Пересечение отрезка I с ε-окрестностью отрезка II характеризуется парой чисел (а, b), а, b≥0, а+b<1, где а - доля отрезка I, начиная с его начала, которая не входит в ε-окрестность отрезка II, b - доля отрезка I, начиная с его конца, которая не входит в ε-окрестность отрезка II.

Способы определения значений а и b аналогичны, поэтому ограничимся описанием способа определения значения а (см. фиг.3). Способ определения доли начала отрезка I, которая не входит в ε-окрестность отрезка II, состоит в следующем. Выбирают систему координат, в которой отрезок II проходил бы горизонтально по оси Ох, имея концы с х-координатами А, В (А<В), а начало и конец отрезка I имели бы координаты (х0, у0), (х1, у1), причем у0≥0. Определяют расстояние d от начала отрезка I до отрезка II, и если d≤ε, то полагают а=0. В противном случае, если у0≥ε, вычисляют а=(у0-ε)/(у0-у1). Заметим, что у1<ε, поскольку иначе отрезок I лежал бы целиком выше ε-окрестности отрезка II, так что 0≤а<1. Вычисляют координату х точки пересечения отрезка I с прямой CD, проходящей через верх прямоугольной части ε-окрестности отрезка II, по формуле х=х0+(х1-х0)*а. Если А≤х≤В, то вычисления а заканчивают, в противном случае, если х<А, вычисляют точки пересечения отрезка I с окружностью радиуса ε с центром в точке А, а если х>В, то вычисляют точки пересечения отрезка I с окружностью радиуса ε с центром в точке В. В любом случае из двух точек пересечения отрезка с окружностью берут ближайшую к началу отрезка I. Пусть она имеет координаты (х, у). Тогда по трем точкам (х0, у0), (х1, у1), (х, у) вычисляют значение доли а отрезка, на которую точка (х, у) отстоит от начала отрезка I.

1.2.4. Формирование частей ломаной линии, лежащих в ε-окрестности границ области

Способ формирования частей ломаной линии, лежащих в ε-окрестности границ области, зависит от того, является ломаная линия замкнутой или незамкнутой, и состоит в следующем.

Пусть A₀A₁…A_n-1 - замкнутая ломаная линия, содержащая n вершин, и пусть {(i_k, a_k), (i_k, b_k)}, 0≤k<N - совокупность всех частей ломаной линии, соответствующих пересечениям ее прямолинейных отрезков с ε-окрестностями границ области (см. п.1.3). Сначала упорядочивают все 2N точек на ломаной линии, соответствующие началам и концам указанных частей в соответствии с отношением порядка, введенным ниже в п.1.3. По полученной последовательности

(m₀, с₀)<(m₁, c₁)<…<(m_2N, c_2N)

формируют последовательность связных частей замкнутой ломаной линии

{(m₀, с₀), (m₁, c₁)}, …, {(m_2N-1, c_2N-1), (m_2N, c_2N)}, {(m_2N, с_2N), (m₀, с₀)},

из которой отбирают только те связные части, которые входят в какую-либо из исходных частей ломаной линии {(i_k, a_k), (i_k, b_k)}, 0≤k<N. Наконец, объединяют те из последовательно идущих отобранных связных частей, для которых конец предыдущей совпадает с началом следующей. Это дает совокупность всех частей ломаной линии, содержащихся в ε-окрестностях границ области.

Пусть теперь A₀A₁…A_n-1 - незамкнутая ломаная линия, содержащая n вершин, и пусть {(i_k, a_k), (i_k, b_k)}, 0≤k<N - совокупность всех частей ломаной линии, соответствующих пересечениям ее прямолинейных отрезков с ε-окрестностями границ области. Сначала упорядочивают все 2N точек на ломаной линии, соответствующие началам и концам указанных частей, в соответствии с отношением порядка, введенным ниже в п.1.3. По полученной последовательности

(m₀, с₀)<(m₁, c₁)<…<(m_2N, с_2N)

формируют последовательность связных частей замкнутой ломаной линии

{(m₀, c₀), (m₁, c₁)}, …, {(m_2N-1, c_2N-1), (m_2N, c_2N)},

Из этой последовательности отбирают только те связные части, которые входят в какую-либо из исходных частей ломаной линии {(i_k, a_k), (i_k, b_k)}, 0≤k<N. Наконец, объединяют те из последовательно идущих отобранных связных частей, для которых конец предыдущей совпадает с началом следующей. Это дает совокупность всех частей ломаной линии, содержащихся в ε-окрестностях границ области.

1.3. Задание частей ломаной линии

Введем понятие точки на ломаной линии и понятие сегмента ломаной линии. Пусть A₀A₁…A_n-1 - незамкнутая или замкнутая ломаная линия, содержащая n вершин, и пусть точка В лежит на этой ломаной линии, а именно, точка В принадлежит прямолинейному отрезку A_iA_i+1 (в случае замкнутой ломаной линии считается, что A_n=A₀). Предположим, что отношение длин отрезков A_iB и A_iA_i+1 равно а (0<а<1). Тогда точка В может быть задана парой (i, а), которая нами называется точкой на ломаной линии. Если точка В совпадает с какой-либо точкой А_i, то точка В задается парой (i, 0). На множестве точек на ломаной линии введем отношение порядка, считая, что (i, а)<(j, b) тогда и только тогда, когда i<j или i=j и а<b. Если бы мы имели дело с бесконечной точностью представления чисел, то задание точки на ломаной линии было бы эквивалентно заданию одного числа i+а.

Произвольная связная часть ломаной линии задается парой {(i, a), (j, b)} точек на ломаной линии, где (i, а) - начальная точка, (j, b) - конечная точка связной части ломаной линии. При этом считается, что i+а>j+b допустимо только в случае замкнутой ломаной линии, и в этом случае указанная часть ломаной линии содержит начальную точку А₀. В частности, полученным в п.1.2.3 пересечениям отрезков A_iA_i+1 с ε-окрестностями отрезка II, характеризующихся долями а, b, соответствует пара {(i, а), (i, 1-b)} точек на ломаной линии.

1.4. Получение оставшихся частей ломаной линии по набору пограничных частей

Способ получения оставшихся частей ломаной линии по набору пограничных частей {(m₀, с₀), (m₁, c₁)}, …, {(m_2N, с_2N), (m_2N+1, с_2N+1)} (см. п.1.1) зависит от того, является ломаная линия замкнутой или незамкнутой. В любом случае сначала упорядочивают заданные пограничные части по возрастанию их начальных точек, так что (m₀, с₀)<(m₂, с₂)<....<(m_2N, c_2N). Заметим, что поскольку пограничные части попарно не пересекаются, то из этого следует, что (m₀, с₀)<(m₁, c₁)<(m₂, с₂)<…<(m_2N, c_2N).

Если ломаная линия является замкнутой, то в качестве оставшихся частей ломаной линии берут последовательность частей {(m₁, c₁), (m₂, c₂)}, …, {(m_2N-1, с_2N-1), (m_2N, с_2N)}, {(m_2N+1, c_2N+1), (m₀, c₀)}.

Если ломаная линия является незамкнутой, то в качестве оставшихся частей ломаной линии берут последовательность частей {(0, 0), (m₀, с₀)}, {(m₁, c₁), (m₂, c₂)}, …, {(m_2N-1, c_2N-1), (m_2N, c_2N)}, {(m_2N+1, c_2N+1), (n-1, 0)}, где n - число вершин ломаной линии. При этом, если (m₀, с₀)=(0,0), то из этой последовательности удаляют первую часть {(0, 0), (m₀, с₀)}. Если (m_2N+1, c_2N+1)=(n-1, 0), то из этой последовательности удаляют последнюю часть {(m_2N+1, c_2N+1), (n-1,0)}.

1.5. Укрупнение частей ломаной линии

Способ укрупнения частей ломаной линии (см. п.1.1) состоит в следующем. Пусть {((m_j, a_j), (n_j, b_j))}, 0≤j<s, - совокупность всех частей ломаной линии, включающая в себя как пограничные части, так и части, которые не лежат в ε-окрестности границ области, но должны войти в результат (т.е. они лежат внутри или вне области в зависимости от типа операции). Каждой части ((m_j, a_j), (n_j, b_j)) ломаной линии приписывают тип t, равный -1, 0 или 1 в зависимости от того, лежит эта часть внутри области, в ε-окрестности границы области или вне области. Заменяют пары ((m_j, а_j), (n_j, b_j)) тройками ((m_j, a_j), (n_j, b_j)), t_j), где t_j - тип части ломаной линии ((m_j, a_j), (n_j, b_j)).

Сначала упорядочивают эти части в соответствии с порядком на множестве точек на ломаной линии, введенном в п.1.3. Для упрощения обозначений будем считать, что исходная последовательность {((m_j, a_j), (n_j, b_j), t_j)}, 0≤j<s, такова, что все точки на ломаной линии, соответствующие началам и концам частей ломаной линии, упорядочены по возрастанию.

Последовательно просматривают все части ломаной линии, и для каждой части ломаной линии ((m_j, a_j), (n_j, b_j), t_j), для которой t_j=0, рассматривают предыдущую (j-1)-ю и следующую (j+1)-ю части ломаной линии. При этом для замкнутой ломаной линии вычитание и прибавление 1 производят по модулю общего числа s частей ломаной линии, а для незамкнутой ломаной линии просматривают все части ломаной линии, кроме первой и последней. Если конец предыдущей части не совпадает с началом рассматриваемой части ломаной линии и начало следующей части не совпадает с концом рассматриваемой части, то рассматриваемую часть ломаной линии удаляют из последовательности {((m_j, a_j), (n_j, b_j))}, уменьшая номера всех последующих частей на 1 и уменьшая общее число частей на 1. Если конец предыдущей части совпадает с началом рассматриваемой части ломаной линии и начало следующей части совпадает с концом рассматриваемой части, то тройку ((m_j-1, a_j-1), (n_j-1, b_j-1), t_j-1), ((m_j, a_j), (n_j, b_j), t_j), ((m_j+1, a_j+1), (n_j+1, b_j+1), t_j+1) заменяют одной частью ломаной линии ((m_j-1, а_j-1), (n_j+1, b_j+1), t_j-1), уменьшая номера всех последующих частей на 2 и уменьшая общее число частей на 2.

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

Если для рассматриваемой части ломаной линии ((m_j, а_j), (n_j, b_j), t_j), для которой t_j=0, конец предыдущей части не совпадает с началом рассматриваемой части ломаной и начало следующей части не совпадает с концом рассматриваемой части, то это означает, что при движении вдоль ломаной линии ее часть, непосредственно предшествующая рассматриваемой части, лежит вне ε-окрестностях границ области, и внутри (вне) этой области так, что эта предшествующая часть не входит в результат операции, и то же верно для части границы, непосредственно следующей за рассматриваемой. Отсюда следует, что предшествующая и последующая части ломаной линии либо обе лежат внутри области, либо обе лежат вне области так, что они не входят в результат операции. Это означает, что если деформировать рассматриваемую часть ломаной линии на величину не более ε так, чтобы она стала проходить точно по границе ε-окрестности границ области, то рассматриваемая часть ломаной линии вместе с предыдущей и последующей частями границы станут лежать строго внутри (вне) области, и при формировании результата операции все три части ломаной не войдут в результат операции. Следовательно, рассматриваемая часть ломаной линии является лишней для формирования результата.

Если для рассматриваемой части ломаной линии ((m_j, а_j), (n_j, b_j), t_j), для которой t_j=0, конец предыдущей части совпадает с началом рассматриваемой части ломаной линии и начало следующей части совпадает с концом рассматриваемой части, то это означает, что при движении вдоль данной ломаной линии ее часть, непосредственно предшествующая рассматриваемой части, лежит вне ε-окрестности границ области, и внутри (вне) этой области так, что эта предшествующая часть входит в результат операции, и то же верно для части ломаной, непосредственно следующей за рассматриваемой. Отсюда следует, что предшествующая и последующая части ломаной либо обе лежат внутри области, либо обе лежат вне области так, что они входят в результат операции. Это означает, что если деформировать рассматриваемую часть ломаной линии на величину не более ε так, чтобы она стала проходить точно по границе ε-окрестности границы области, то рассматриваемая часть ломаной линии вместе с предыдущей и последующей частями ломаной линии станут лежать строго внутри (вне) другой области, и при формировании результата операции этот результат будет содержать часть ломаной линии, являющуюся объединением трех частей ломаной линии: рассматриваемой, предыдущей и последующей. Следовательно, можно объединить указанные три части ломаной линии, и это не испортит формирование результата.

2. Реализуемость способа выполнения операции над двумя областями

2.1. Описание способа в целом

Компьютерный способ формирования изображения границ одной или нескольких областей, полученных в результате применения заданной логической операции к двум многоугольным областям, определенным каждая на плоскости в виде набора многоугольных контуров, имеющего внешнюю границу и, возможно, границы хотя бы одной дыры, и для каждой из упомянутых многоугольных областей эти границы могут иметь самопересечения и (или) взаимные пересечения, с заданной точностью ε, состоит в том, что сначала вводят в оперативную память компьютера данные двух упомянутых многоугольных областей, представляющие собой упорядоченные последовательности координат вершин многоугольных контуров в порядке их обхода. Затем выполняют в процессоре компьютера обработку введенных данных. В ходе обработки данных в процессоре компьютера сначала находят те части замкнутых ломаных линий, являющихся каждым из упомянутых многоугольных контуров, которые являются пограничными, внутренними или внешними по отношению к другой области в соответствии с упомянутой логической операцией. Описание того, какие части выбирают в зависимости от выполняемой логической операции, приводится ниже в пп.2.2-2.4. Для получения таких частей используют действия, входящие в способ по п.6 формулы, обеспечивающие получение укрупненных частей границ. При этом в качестве ломаных линий берут замкнутые ломаные линии, составляющие границы каждой из двух многоугольных областей, а в качестве области берут другою область. Как указывалось выше в п.1.5, смысл таких укрупненных частей состоит в том, что для каждой укрупненной части можно так деформировать одну из исходных областей, что рассматриваемая укрупненная часть границы исходной области будет соответствовать части границы деформированной области, лежащей вне ε-окрестности границ другой области. Другими словами, укрупненные части границ одной области могут, вообще говоря, пересекать ε-окрестности границ другой области и даже сами границы другой области, но в случае пересечения они выходят за пределы второй области или входят внутрь второй области на глубину не более ε. Иными словами, укрупненные части границы одной области могут псевдокасаться границ другой области, где под псевдокасанием понимается пересечение границы другой области с уходом на глубину не более ε.

Далее из всех найденных пограничных частей отбирают те, которые имеют скорректированное направление обхода, совпадающее со скорректированным направлением обхода другого многоугольного контура, или скорректированное направление обхода, противоположное скорректированному направлению обхода другого многоугольного контура, в соответствии с упомянутой заданной логической операцией. Направление обхода контура задается последовательностью координат вершин многоугольного контура, введенной в память компьютера. В то же время для определения того, какие пограничные части контуров границ войдут в качестве частей границ областей, составляющих результат выполнения логической операции над двумя областями, важны не направления контуров границ, а скорректированные направления, определяемые ниже. Если бы контуры границ не имели самопересечений и взаимных пересечений, то всегда можно было бы изменить порядок обхода контура так, чтобы при обходе контура ограничиваемая им область была расположена слева от контура (обход внешней границы области против часовой стрелки и обход границ дыр по часовой стрелке). При наличии у контура самопересечений или при наличии взаимных пересечений контуров так сделать нельзя, и вместо обеспечения единого направления обхода контура, при котором ограничиваемая им область всегда остается по одну сторону от этого контура, приходится вводить локальное понятие скорректированного направления обхода. Точки самопересечения замкнутого контура границы области и точки пересечения этого контура с другими контурами границы области разбивают данный контур на части, для каждой из которых определяют скорректированное направление обхода следующим образом. Если при обходе данной части ломаной линии, являющейся контуром границы области, в соответствии с порядком вершин ломаной линии, ограничиваемая этим контуром область лежит слева от этой ломаной линии, то под скорректированным направлением понимают упомянутое направление обхода ломаной линии. В противном случае под скорректированным направлением понимают противоположное направление. Описание того, какие направления надо использовать (совпадающие или противоположные) в зависимости от логической операции, также приводится ниже в пп.2.2-2.4. Сам способ отбора пограничных частей с учетом направления обхода излагается ниже в п.2.5.

После того как будут определены части границ исходных областей, входящие в границы областей, являющихся результатом выполнения операции, производят формирования границ результата логической операции над областями из частей границ исходных областей и дополнительных коротких отрезков длины ε. Эти дополнительные короткие отрезки обеспечивают переходы контуров границ областей, составляющих результат выполнения операции, с отрезков границ одной исходной области на отрезки границ другой исходной области и тем самым стыкуют части границ исходных областей в связные контуры границ областей, образующих результат выполнения операции. Формирование контуров результата включает в себя определение порядка обхода отобранных частей границ исходных областей для получения обхода контуров границ результата операции и определение коротких отрезков длины ε, обеспечивающих стыковку частей границ в связные контуры. Эти два этапа излагаются ниже в п.2.6 и п.2.7.

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

2.2. Пересечение областей

На фиг.4 изображены две области I и II, первая из которых является шестиугольником неправильной формы, а вторая - треугольником. Область ABCDEF, являющаяся точным их пересечением, заштрихована. Заданная требуемая точность вычислений ε определяет соответствующие полосы (окрестности) вокруг границ областей I и II. Из этого чертежа видно, что область, являющаяся точным пересечением областей I и II, обладает двумя недостатками. Во-первых, она имеет длинный узкий выступ, заканчивающийся в точке В; во-вторых, в точке F пересечения сторон границ областей I и II угол между сторонами AF и FE границы пересечения близок к 180 градусам, что создает впечатление искривленности границы области ABCDEF. К тому же при вычислении координат точки F как точки пересечения отрезков границ исходных многоугольников возникает большая погрешность из-за плохой обусловленности системы линейных уравнений. Поскольку результат пересечения областей должен быть получен с точностью ε, гораздо более предпочтителен результат, изображенный на фиг.5.

Из сравнения фиг.4 и фиг.5 видно, что как точное пересечение областей, так и приближенное, имеют границы, содержащие часть LDK границы области I, лежащую вне ε-окрестности границы области II и внутри области II, а также часть MN границы области II, лежащую вне ε-окрестности границы области I и внутри области I. Все различие границ точного и приближенного пересечения областей сосредоточено внутри ε-окрестностей границ исходных областей. Таким образом, граница приближенного пересечения областей может быть составлена из:

- части границы области I, лежащей вне ε-окрестности границы области II и внутри области II;

- части границы области II, лежащей вне ε-окрестности границы области I и внутри области I;

- тех частей границ области I, которые лежат в ε-окрестности частей границы области II, имеющих те же скорректированные направления, что и рассматриваемые части границы области I;

- тех частей границ области II, которые лежат в ε-окрестности частей границы области I, имеющих те же скорректированные направления, что и рассматриваемые части границы области II;

- дополнительных коротких сторон, каждая из которых имеет длину ε.

2.3. Объединение областей

Рассмотрения, аналогичные приведенным в п.2.2, показывают, что граница приближенного объединения областей может быть составлена из:

- части границы области I, лежащей вне ε-окрестности границы области II и вне области II;

- части границы области II, лежащей вне ε-окрестности границы области I и вне области I;

- тех частей границ области I, которые лежат в ε-окрестности частей границы области II, имеющих скорректированные направления, противоположные скорректированным направлениям рассматриваемых частей границы области I;

- тех частей границ области II, которые лежат в ε-окрестности частей границы области I, имеющих скорректированные направления, противоположные скорректированным направлениям рассматриваемых частей границы области II;

- дополнительных коротких сторон, каждая из которых имеет длину ε.

2.4. Вычитание областей

Рассмотрения, аналогичные приведенным в п.2.2, показывают, что граница приближенного результата вычитания области II из области I может быть составлена из:

- части границы области I, лежащей вне ε-окрестности границы области II и вне области II;

- части границы области II, лежащей вне ε-окрестности границы области I и внутри области I;

- тех частей границ области I, которые лежат в ε-окрестности частей границы области II, имеющих скорректированные направления, противоположные скорректированным направлениям рассматриваемых частей границы области I;

- тех частей границ области II, которые лежат в ε-окрестности частей границы области I, имеющих скорректированные направления, противоположные скорректированным направлениям рассматриваемых частей границы области II;

- дополнительных коротких сторон, каждая из которых имеет длину ε.

2.5 Способ отбора пограничных частей с учетом скорректированных направлений

Способ формирования пограничных частей границ одной области, имеющих надлежащее скорректированное направление относительно границ другой области, состоит в следующем. Пусть A₀A₁…A_n-1 - замкнутая ломаная линия, содержащая n вершин и являющаяся одним из контуров границы первой области, и пусть {(i_k, а_k), (i_k, b_k)}, 0≤k<N - совокупность всех частей этой ломаной линии, соответствующих пересечениям ее прямолинейных отрезков с ε-окрестностями прямолинейных отрезков C_kD_k контуров границы второй области.

Сначала производят отбор тех частей ломаной линии {(i_k, a_k), (i_k, b_k)}, для которых прямолинейные отрезки A_kA_k+1 и C_kD_k контуров границ первой и второй области соответственно имеют надлежащие скорректированные направления (одинаковые или противоположные). При этом возможна такая ситуация, когда, например, отрезок C_kD_k контура границы второй области пересекается с некоторым отрезком той же границы второй области, так что образуется петля, или пересекается с другим контуром границы второй области, причем точка пересечения Е лежит в ε-окрестности отрезка A_kA_k+1. В этом случае в точке Е происходит изменение скорректированного направления отрезка C_kD_k контура границы второй области. В принципе, это достаточно редкая ситуация, и ее неучет мало скажется на вероятности правильного получения результата. Однако можно и учесть подобные ситуации, заменив прямолинейный отрезок C_kD_k на два отрезка C_kE и ED_k, а отрезок A_kA_k+1 - на два отрезка A_kF и FA_k+1, где F - проекция точки на отрезок A_kA_k+1, после чего произвести отбор пар отрезков с надлежащими взаимными скорректированными направлениями.

Чтобы не менять обозначений, мы обозначим число уже отобранных частей снова через N.

После этого упорядочивают все 2N точек на ломаной линии, соответствующие началам и концам указанных частей в соответствии с отношением порядка, введенным в п.1.3. По полученной последовательности

(m₀, с₀)<(m₁, c₁)<…<(m_2N, c_2N)

формируют последовательность связных частей замкнутой ломаной

{(m₀, с₀), (m₁, c₁)}, …, {(m_2N-1, с_2N-1), (m_2N, с_2N)}, {(m_2N, с_2N), (m₀, с₀)},

из которой оставляют только те связные части, которые входят в какую-либо из отобранных частей ломаной линии {(i_k, a_k), (i_k, b_k)}, 0≤k<N. Наконец, объединяют те из последовательно идущих оставленных связных частей, для которых конец предыдущей совпадает с началом следующей. Это дает совокупность всех частей границ одной области, лежащих в ε-окрестностях границ второй области и имеющих надлежащее скорректированное направление относительно границ другой области.

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

2.6.1. Общие положения

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

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

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

Если существуют укрупненные части границ первой и второй области, то собирают границы областей результата путем обхода укрупненных частей границ исходных областей (пп.2.6.2-2.6.4), получая последовательности частей границ двух исходных областей I и II, из которых состоят границы областей результата операции. В отличие от частей границ исходных областей, задаваемых тройками ((m, a), (n, b), t) (см. п.1.5), эти части границ задают четверками ((m, а), (n, b), t, с). Дополнительная компонента с принимает значения 1 или -1 в зависимости от того, проходится часть границы ((m, а), (n, b), t) исходной области в том же направлении, что и исходное направление обхода границы исходной области, или в противоположном направлении.

2.6.2. Объединение областей

В соответствии с терминологией п.1.5, все части границ исходных областей, из которых должны формироваться границы объединения областей, имеют тип 0 или 1, поскольку части границ одной области, лежащие внутри другой области, не входят в число границ, из которых формируются границы результата объединения областей.

Прежде всего формируют внешний контур результата. Легко видеть, что внешний контур объединения областей является подмножеством объединения внешних контуров исходных областей. Для формирования этого внешнего контура из всех укрупненных частей внешних границ исходных областей выбирают ту часть границы, для которой какая-либо ее вершина, начало или конец имеют минимальное значение координаты х. Это гарантирует то, что эта часть границы будет частью именно внешнего контура результата, а не частью контура какой-либо из его дырок. Если эта часть границы совпадает со всем контуром, то этот контур и будет искомым внешним контуром объединения областей. Пусть рассматриваемая часть границы не совпадает ни с каким контуром границ исходных областей. Если она имеет тип 0, то согласно рассмотрениям п.1.5 она следует за частью границы, имеющей тип 1, или непосредственно за ней следует часть границы, имеющая тип 1, и ясно, что эта соседняя часть границы типа 1 войдет во внешний контур объединения областей. В этом случае переходят от рассмотрения данной части границы, имеющей тип 0, к рассмотрению соседней с ней части границы, имеющей тип 1.

Итак, начиная формирование внешнего контура объединения областей, можно начать с некоторой части границы внешнего контура какой-либо из исходных областей, без ограничения общности считая, что рассматриваемая часть А имеет тип 1. Для определенности пусть эта часть принадлежит внешней границе области I. Части А приписывают направление обхода с=1. Непосредственно за ней идет часть контура I, лежащая в ε-окрестности границ другой области II, которая либо является одной из частей границы ((m, a), (n, b), t), имеющей тип t=0, либо не входит в число частей границ, отобранных на предыдущих шагах способа. На границе ε-окрестности объединения частей А и ((m, а), (n, b), t) (в первом случае) или на границе ε-окрестности части А (во втором случае) либо может лежать только одна из точек, являющихся началами или концами частей типа 1 внешнего контура области II, либо может лежать несколько таких точек, или не лежать ни одной такой точки. Простейшие примеры таких ситуаций приведены на фиг.6, 7.

В первом случае (фиг.6) из нескольких таких точек выбирают первую по направлению движения, имеющую координаты (х, у). Поскольку точка (х, у) является началом или концом части типа 1 внешнего контура области II, то от нее начинается или в ней заканчивается некоторая часть В границы области II типа 1. Тогда принимают решение о том, что граница объединения областей делает переход с части А границы области I на часть В границы области II. Если точка (х, у) является началом части В границы области II, то части В приписывают направление обхода с=1. Если точка (х, у) является концом части В границы области II, то части В приписывают направление обхода с=-1. Если точка (х, у) является и началом, и концом части В границы области II, т.е. граница области II имеет петлю, то направление обхода выбирают так, чтобы эта охватываемая этой петлей область находилась с той же стороны от петли, что и формируемая область относительно части границы А.

Во втором случае (фиг.7) часть В границы области II лежит целиком внутри ε-окрестности области I, а это возможно только в том случае, когда часть В в ε-окрестности точки (х, у) пересекается с некоторой частью С границы области I (см. фиг.7). В этом случае принимают решение о том, что граница объединения областей делает переход с части А границы области I на часть С границы той же области I. Если точка (х, у) является началом части С границы области I, то части С приписывают направление обхода с=1. Если точка (х, у) является концом части С границы области I, то части С приписывают направление обхода с=-1. Если точка (х, у) является и началом, и концом части С границы области I, т.е. граница области I имеет петлю, то направление обхода выбирают так, чтобы эта охватываемая этой петлей область находилась с той же стороны от петли, что и формируемая область относительно части границы А.

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

Затем формируют контуры дырок области, являющейся объединением исходных областей I и II. Для этого определяют те части типа 1 внешних контуров областей I и II, которые остались не использованными при формировании внешнего контура объединения областей (см. фиг.8), и при их наличии из них и из частей типа 1 дырок исходных областей формируют одну или несколько дырок объединения областей. Это производят путем процесса, аналогичного описанному процессу определения внешнего контура объединения.

2.6.3. Пересечение областей

В соответствии с терминологией п.1.5, все части границ исходных областей, из которых должны формироваться границы объединения областей, имеют тип 0 или -1, поскольку части границ одной области, лежащие вне другой области, не входят в число границ, из которых формируются границы результата объединения областей.

Пересечения двух областей в общем случае может состоять из нескольких областей, и их формирование производят последовательно. Для каждой очередной области, входящей в состав пересечения, прежде всего формируют внешний контур результата. Для формирования очередного внешнего контура из всех еще не использованных укрупненных частей границ исходных областей выбирают ту еще не использованную часть границы, для которой какая-либо ее вершина, начало или конец имеют минимальное значение координаты х. Это гарантирует то, что эта часть границы будет частью именно внешнего контура результата, а не частью контура какой-либо из его дырок. Если эта часть границы совпадает со всем контуром, то этот контур и будет искомым очередным внешним контуром пересечения областей. Пусть рассматриваемая часть границы не совпадает ни с каким контуром границ исходных областей. Если она имеет тип 0, то согласно рассмотрениям п.1.5 она следует за частью границы, имеющей тип -1, или непосредственно за ней следует часть границы, имеющая тип -1, и ясно, что эта соседняя часть границы типа -1 войдет во внешний контур пересечения областей. В этом случае переходят от рассмотрения данной части границы, имеющей тип 0, к рассмотрению соседней с ней части границы, имеющей тип -1.

Процесс формирования очередного внешнего контура пересечения аналогичен процессу формирования внешнего контура объединения.

Затем формируют контуры дырок очередной области, являющейся частью пересечения исходных областей I и II. Для этого определяют дырки областей I и II, которые остались еще не использованными при формировании пересечения и которые лежат внутри сформированного очередного внешнего контура пересечения, и при их наличии из их частей типа -1 формируют одну или несколько дырок пересечения областей. Это производят путем процесса, аналогичного описанному процессу определения внешнего контура объединения. Из оставшихся неиспользованными частей границ дырок типа -1 формируют границы областей, также входящих в состав пересечения областей и лежащих внутри дырок (см. фиг.9). На этой фигуре исходные области показаны заштрихованными под углом 45 и 135 градусов, а такая дополнительная область показана более мелкой штриховкой.

2.6.4. Вычитание областей

В соответствии с терминологией п.1.4, при вычитании области II из области I все части границ исходной области I, из которых должны формироваться границы объединения областей, имеют тип 0 или -1, поскольку части границ вычитаемой области, лежащие вне другой области, не входят в число границ, из которых формируются границы результата объединения областей. Аналогично, все части границ исходной области II, из которых должны формироваться границы объединения областей, имеют тип 0 или 1.

Результат вычитания области II из области I в общем случае может состоять из нескольких областей, и их формирование производят последовательно. Для каждой очередной области, входящей в состав результата вычитания, прежде всего формируют внешний контур результата. Для формирования очередного внешнего контура из всех еще не использованных укрупненных частей границ исходных областей выбирают ту еще не использованную часть границы, для которой какая-либо ее вершина, начало или конец имеют минимальное значение координаты х. Это гарантирует то, что эта часть границы будет частью именно внешнего контура результата, а не частью контура какой-либо из его дырок. Если эта часть границы совпадает со всем контуром, то этот контур и будет искомым очередным внешним контуром результата вычитания областей. Пусть рассматриваемая часть границы не совпадает ни с каким контуром границ исходных областей. Если она имеет тип 0, то согласно рассмотрениям п.1.5 она следует за частью границы, имеющей тип -1 или тип 1 (в зависимости от того, является она частью границы области I или области II), или непосредственно за ней следует часть границы, имеющая тип -1 (или 1), и ясно, что эта соседняя часть границы типа -1 (или 1) войдет во внешний контур пересечения областей. В этом случае переходят от рассмотрения данной части границы, имеющей тип 0, к рассмотрению соседней с ней части границы, имеющей тип -1 (или 1).

Процесс формирования очередного внешнего контура результата вычитания аналогичен процессу формирования внешнего контура объединения.

Затем формируют контуры дырок очередной области, являющейся частью результата вычитания области II из области I. Для этого определяют дырки областей I и все контура границы области II, которые остались еще не использованными при формировании пересечения и которые лежат внутри сформированного очередного внешнего контура пересечения, и при их наличии из их частей типа -1 (соответственно 1) формируют одну или несколько дырок результата вычитания областей. Это производят путем процесса, аналогичного описанному процессу определения внешнего контура объединения.

2.7. Определение координат вершин ломаных, составляющих границы результата

Исходными данными для получения координат вершин ломаных, составляющих границы результата выполнения логических операций над областями, является совокупность последовательностей {((m_j, a_j), (n_j, b_j), t_j, c_j)}, 0≤j<s, где каждая такая последовательность задает порядок прохождения частей границ исходных областей для формирования очередного контура границы области, входящей в результат операции. Эти части границ исходных областей в зависимости от их типов t_j являются либо частями границ одной области, лежащими в s-окрестностях границ другой области (при t_j=0), либо частями границ одной области, лежащими внутри или вне другой области (при t_j≠0).

Последовательность координат вершин ломаной линии, являющейся очередной границей области, входящей в результат выполнения геометрической операции, формируют путем последовательного прохождения по всем отрезкам последовательности {((m_j, a_j), (n_j, b_j), t_j, с_j)}, 0≤j<s, начиная с первого.

Для каждой части ((m_j, a_j), (n_j, b_j), t_j, с_j) границы одной из исходных областей формируют последовательность ее внутренних вершин следующим образом. Пусть эта часть границы является частью исходной замкнутой ломаной линии, имеющей N_j вершин. Если m_j+a_j<n_j+b_j, то в число вершин ломаной линии результата включают вершины исходной ломаной линии с номерами m_j+1, …n_j. В общем случае такая последовательность может оказаться и пустой, т.е. не содержащей ни одной вершины (при m_j=n_j). Если m_j+a_j>n_j+b_j, то в число вершин ломаной результата включают вершины исходной ломаной с номерами m_j+1, …, N_j-1, 0, …, n_j. Если с_j=1, то формирование последовательности ее вершин закончено. Если с_j=-1 и сформированная последовательность вершин содержит не менее двух вершин, то сформированную последовательность вершин A₁, …, А_р заменяют последовательностью вершин А_р, …, A₁, проходимой в обратном порядке.

Формирование координат вершин ломаной линии, составляющей очередную границу результата, завершают добавлением дополнительных вершин между соседними последовательностями вершин, соответствующими соседним элементам последовательности {((m_j, a_j), (n_j, b_j), t_j, с_j)}, 0≤j<s. Это осуществляют следующим образом.

Пусть ((m_j, a_j), (n_j, b_j), t_j, c_j) и ((m_j+1, a_j+1), (n_j+1, b_j+1), t_j+1, c_j+1) - две последовательные части исходных ломаных линий, входящих в границу результата выполнения логической операции. Если c_j=1 и c_j+1=1, то необходимо состыковать конец первой части с началом второй. Если c_j=1 и c_j+1=-1, то необходимо состыковать конец первой части с концом второй. Если с_j=-1 и с_j+1=1, то необходимо состыковать начало первой части с началом второй. Если с_j=-1 и c_j+1=-1, то необходимо состыковать начало первой части с концом второй. Во всех четырех случаях действуют аналогичным образом, и для определенности рассмотрим только первый случай.

Итак, пусть ((m_j, а_j), (n_j, b_j), t_j, c_j) и ((m_j+1, a_j+1), (n_j+1, b_j+1), t_j+1, c_j+1) - две последовательные части исходных ломаных линий, входящих в границу результата выполнения логической операции, причем с_j=c_j+1=1. Способ стыковки двух частей границы несколько отличается в зависимости от того, является текущая граница внешней границей области или границей дырки.

Рассмотрим сначала случай внешней границы, причем указанные две части ломаных линий принадлежат разным областям. Здесь возможны два принципиально разных случая, представленные соответственно на фиг.10-11. Используются следующие обозначения: А - точка входа первой части ломаной линии в ε-окрестность второй ломаной линии, В - точка выхода из ε-окрестности, С - точка входа следующей части второй ломаной линии в ε-окрестность первой ломаной линии, D - точка выхода следующей части второй ломаной линии из ε-окрестности первой ломаной линии. Фиг.10 соответствует случаю, когда ломаные линии пересекаются, причем часть АВ первой ломаной имеет одинаковое направление со второй ломаной; фиг.11 соответствует случаю, когда ломаные линии пересекаются, причем часть АВ первой ломаной линии имеет направление, противоположное направлению второй ломаной линии.

В случае фиг.10 проектируют точку А на ломаную линию CD, что дает точку А', и проектируют точку D на ломаную линию АВ, что дает точку D'. Это дает два возможных пути из точки А в точку D: AA'D и AD'D. Из этих двух путей выбирают наилучший по некоторому критерию, выбор которого может зависеть от конкретной задачи. Полученные в результате три точки вставляют в формируемую последовательность точек вершин ломаной линии результата.

В случае фиг.11 проектируют точку А на ломаную линию CD, что дает точку А', и проектируют точку D на ломаную линию АВ, что дает точку D', и в исходной последовательности вершин ломаной линии результата заменяют точку А на точку D' или заменяют точку В на точку А'. Из этих двух путей выбирают наилучший по некоторому критерию, выбор которого может зависеть от конкретной задачи.

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

Изобретение относится к способам генерации двумерных векторных изображений путем комбинирования фигур, точнее к компьютерным способам формирования векторных изображений путем выполнения логических операций над ломаными линиями и многоугольными областями. Изобретение обеспечивает повышение надежности формирования изображений по сравнению с известными способами без использования вычислений с неограниченной разрядностью мантиссы. Решение поставленной задачи при выполнении операций над ломаной линией и областью достигается за счет нахождения пограничных отрезков ломаной линии, лежащих в ε-окрестности границы области, определения оставшихся частей ломаной линии и выбора из них тех частей, которые лежат внутри или вне области. Этот способ формирования изображения частей ломаной линии, лежащих как внутри, так и вне многоугольной области, используется в способе формирования изображения границ одной или нескольких областей, полученных в результате применения заданной логической операции к двум многоугольным областям. 2 н. и 12 з.п. ф-лы, 11 ил.

1. Компьютерный способ формирования изображения частей ломаной линии, лежащих как внутри, так и вне многоугольной области, заданной на плоскости в виде набора многоугольных контуров, имеющего внешнюю границу и, возможно, границы хотя бы одной дыры, и все эти границы могут иметь самопересечения и (или) взаимные пересечения, причем изображения частей упомянутой ломаной линии формируют с заданной точностью ε, существенно большей результата умножения максимального значения всех длин сторон упомянутых многоугольных контуров и ломаной линии на 2^-n, где n - разрядность мантиссы в представлении плавающих чисел в процессоре компьютера, при анализе взаимного расположения частей этой ломаной линии и границ упомянутой многоугольной области, заключающийся в том, что:
- вводят в оперативную память компьютера данные упомянутой ломаной линии и упомянутой многоугольной области, представляющие собой упорядоченные последовательности координат вершин упомянутой ломаной линии и упомянутых многоугольных контуров в порядке их обхода;
- выполняют в процессоре компьютера обработку введенных данных, в ходе которой:
• находят пограничные части упомянутой ломаной линии, лежащие в ε-окрестности границы упомянутой многоугольной области, и оставшиеся части;
• подсчитывают, для каждой из упомянутых оставшихся частей, число пересечений луча, выходящего из любой точки данной оставшейся части, с границами упомянутой многоугольной области;
• классифицируют упомянутые оставшиеся части на внутренние и внешние в зависимости от того, является ли результат упомянутого подсчета, соответственно, нечетным или четным;
- выдают полученные в процессе упомянутой компьютерной обработки данные о внутренних и (или) внешних частях упомянутой ломаной линии на устройство вывода данных упомянутого компьютера.

2. Способ по п.1, отличающийся тем, что устройство вывода данных упомянутого компьютера является дисплеем.

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

4. Способ по п.1, отличающийся тем, что для определения частей ломаной линии, лежащих в ε-окрестности границ указанной области и вне ε-окрестности границ указанной области, находят пересечения всех прямолинейных отрезков ломаной линии с ε-окрестностями прямолинейных отрезков контуров границы указанной области, объединяют смежные пересечения в части ломаной линии и находят дополнение полученного множества частей ломаной линии до всей ломаной линии.

5. Способ по п.1, отличающийся тем, что каждая часть ломаной линии задается парой ((m_j, a_j), (n_j, b_j)) разных точек на ломаной линии, соответствующих началу и концу части ломаной линии, а каждая точка на ломаной линии является парой, первая компонента которой является номером звена ломаной линии, содержащего данную точку, а вторая компонента - долей расстояния от начала прямолинейного отрезка ломаной линии до данной точки в общей длине прямолинейного отрезка ломаной линии, причем для незамкнутой ломаной линии всегда выполняется условие m_j+a_j<n_j+b_j, а для замкнутой ломаной линии условие m_j+a_j>n_j+b_j означает, что данная часть ломаной линии содержит начало ломаной линии.

6. Способ по п.5, отличающийся тем, что после определения частей ломаной линии, лежащих в ε-окрестности границы указанной области, и частей ломаной линии, лежащих внутри (вне) области, производят укрупнение частей ломаной линии, для чего сначала приписывают им тип t, равный -1, 0 или 1 в зависимости от того, лежит эта часть внутри области, в ε-окрестностях границ области или вне области, заменяют пары ((m_j a_j), (n_j, b_j)) тройками ((m_j, a_j), (n_j, b_j), t_j)), где t_j - тип части ломаной линии ((m_j, a_j), (n_j, b_j)), упорядочивают эти части в соответствии с порядком на множестве точек на ломаной линии, последовательно просматривают все части ломаной линии, и для каждой части ломаной линии ((m_j, a_j), (n_j, b_j), t_j)), для которой t_j=0, рассматривают предыдущую (j-1)-ю и следующую (j+1)-ю части ломаной линии, где для замкнутой ломаной линии вычитание и прибавление 1 производят по модулю общего числа s частей ломаной линии, а для незамкнутой ломаной линии просматривают все части ломаной линии кроме первой и последней, причем если конец предыдущей части не совпадает с началом рассматриваемой части ломаной линии и начало следующей части ломаной линии не совпадает с концом рассматриваемой части ломаной линии, то рассматриваемую часть ломаной линии удаляют из последовательности {((m_j, a_j), (n_j, b_j))}, уменьшая номера всех последующих частей на 1 и уменьшая общее число частей на 1, а если конец предыдущей части ломаной линии совпадает с началом рассматриваемой части ломаной линии и начало следующей части ломаной линии совпадает с концом рассматриваемой части ломаной линии, то тройку ((m_j-1, a_j-1), (n_j-1, b_j-1), t_j-1)), ((m_j, a_j), (n_j, b_j), t_j)), ((m_j+1, a_j+1), (n_j+1, b_j+1), t_j+1)) заменяют одной частью ломаной линии ((m_j-1, a_j-1), (n_j+1, b_j+1), t_j-1), уменьшая номера всех последующих частей ломаной линии на 2 и уменьшая общее число частей ломаной линии на 2.

7. Способ по п.5, отличающийся тем, что для определения пограничных частей ломаной линии упорядочивают все точки на ломаной линии, соответствующие началам и концам пересечений прямоугольных отрезков ломаной линии с ε-окрестностями прямоугольных отрезков контуров границы области, в последовательность
(m₀, c₀)<(m₁, c₁)<…<(m_2N, с_2N),
где N - число указанных попарных пересечений, формируют последовательность частей ломаной линии: в случае замкнутой ломаной линии
{(m₀, c₀), (m₁, c₁)}, …, {(m_2N-1, с_2N-1), (m_2N, c_2N)}, {(m_2N, c_2N), (m₀, c₀)},
а в случае незамкнутой ломаной линии
{(m₀, с₀), (m₁, c₁)}, …, {(m_2N-1, c_2N-1), (m_2N, c_2N)},
после чего из сформированной последовательности отбирают только те связные части, которые являются частью какого-либо из упомянутых пересечений, и, наконец, объединяют те из последовательно идущих отобранных связных частей, для которых конец предыдущей совпадает с началом следующей.

8. Компьютерный способ формирования изображения границ одной или нескольких областей, полученных в результате применения заданной логической операции к двум многоугольным областям, определенным каждая на плоскости в виде набора многоугольных контуров, имеющего внешнюю границу и, возможно, границы хотя бы одной дыры, и для каждой из упомянутых многоугольных областей эти границы могут иметь самопересечения и (или) взаимные пересечения, причем изображение результата выполнения упомянутой логической операции формируют с заданной точностью ε, существенно большей результата умножения максимального значения всех длин сторон упомянутых многоугольных контуров на 2^-n, где n - разрядность мантиссы в представлении плавающих чисел в процессоре компьютера, при анализе взаимного расположения частей границ упомянутых многоугольных областей, заключающийся в том, что:
- для каждой из двух областей находят те части замкнутых ломаных линий, являющихся каждым из упомянутого набора многоугольных контуров, составляющих границу этой области, которые являются пограничными, внутренними ищи внешними по отношению к другой области, в соответствии с упомянутой логической операцией, согласно действиям способа по п.6;
- отбирают из всех найденных пограничных частей те, которые имеют скорректированное направление обхода, совпадающее со скорректированным направлением обхода другого многоугольного контура, или скорректированное направление обхода, противоположное скорректированному направлению обхода другого многоугольного контура, в соответствии с упомянутой заданной логической операцией, где под скорректированным направлением обхода понимают направление обхода в соответствии с порядком вершин ломаной линии, если ограничиваемая ею область лежит слева от этой ломаной линии, и противоположное направление в противном случае;
- находят замкнутые контура границ областей упомянутого результата путем объединения найденных на двух предыдущих шагах частей всех ломаных линий в контура с добавлением при необходимости отрезков длины ε, соединяющих упомянутые части, принадлежащие разным исходным контурам;
- выдают на устройство вывода компьютера изображения упомянутых контуров границ областей упомянутого результата.

9. Способ по п.8, в котором выбирают заданную логическую операцию из группы, состоящей из пересечения, объединения и вычитания.

10. Способ по п.8, отличающийся тем, что устройство вывода данных упомянутого компьютера является дисплеем.

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

12. Способ по п.8, отличающийся тем, что сначала определяют части границ одной области, лежащие в ε-окрестности границы другой исходной области, и части границ одной области, лежащие внутри (вне) другой области (в зависимости от типа операции), где каждая часть границы области является парой ((m_j, a_j), (n_j, b_j)) точек на ломаной линии, соответствующих началу и концу части границы, а каждая точка на ломаной линии является парой, первая компонента которой является номером прямолинейного отрезка ломаной линии, содержащего данную точку, а вторая компонента - долей расстояния от начала прямолинейного отрезка ломаной линии до данной точки в общей длине упомянутого прямоугольного отрезка ломаной линии, затем определяют порядок обхода полученных частей для формирования границ результата и, наконец, определяют точные значения координат вершин ломаных линий, представляющих результат выполнения операции путем использования координат вершин указанных частей ломаных линий и определения координат точек перехода с одной части на следующую.

13. Способ по п.8, отличающийся тем, что для определения частей границ одной области, лежащих в ε-окрестностях границ второй области с учетом взаимной ориентации, отбирают те взаимные пересечения прямолинейных отрезков ломаных линий, которые имеют заданные взаимные ориентации (одинаковые или противоположные), упорядочивают все точки на ломаной линии, соответствующие началам и концам отобранных пересечений, в последовательность
(m₀, c₀)<(m₁, c₁)<…<(m_2N, c_2N),
где N - число указанных отобранных пересечений, формируют последовательности связных частей замкнутой ломаной линии
{(m₀, с₀), (m₁, c₁)}, …, {(m_2N-1, c_2N-1), (m_2N, c_2N)}, {(m_2N, c_2N), m₀, c₀},
из которой отбирают только те связные части, которые входят в какую-либо из исходных частей ломаной линии, и, наконец, объединяют те из последовательно идущих отобранных связных частей, для которых конец предыдущей совпадает с началом следующей.

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