применение эффектов к объединенной текстовой дорожке

Формула изобретения

1. Реализуемый компьютером способ применения эффектов к образцу текста внутри документа посредством использования формы образца текста, содержащий:

прием образца текста, причем образец текста включает в себя два или более символов;

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

определение того, перекрываются ли два смежных символа в образце текста;

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

генерацию формы из объединенной текстовой дорожки и применение эффекта к форме.

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

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

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

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

6. Способ по п.5, в котором использование логических операций включает в себя прием геометрии, которая ассоциирована с образцом текста;

разбиение геометрии на звенья;

вычисление соединений;

отбрасывание избыточных звеньев и

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

7. Способ по п.1, в котором применение эффекта включает в себя применение эффекта линии к образцу текста.

8. Способ по п.1, в котором применение эффекта включает в себя применение эффекта выдавливания и скашивания.

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

приема образца текста, к которому должен применяться первый эффект;

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

определение того, перекрываются ли два смежных символа в образце текста;

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

генерации единой формы из объединенной текстовой дорожки и применения первого эффекта к единой форме.

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

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

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

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

14. Машиночитаемый носитель по п.9, в котором применение эффекта включает в себя применение эффекта линии к образцу текста.

15. Машиночитаемый носитель по п.9, в котором применение эффекта включает в себя применение эффекта выдавливания и скашивания.

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

процессор и машиночитаемый носитель;

операционную среду, сохраненную на машиночитаемом носителе и исполняющуюся на процессоре;

дисплей;

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

процессор эффектов, который конфигурирован для:

приема образца текста, причем текст включает в себя два или более символов;

создания объединенной текстовой дорожки для образца текста путем дополнительного конфигурирования процессора эффектов для:

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

аппроксимирует одну или более криволинейных форм многоугольниками;

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

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

отбрасывания избыточных звеньев;

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

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

генерации и формы из объединенной текстовой дорожки;

применение эффекта к форме и отображение формы на дисплее.

17. Устройство по п.16, в котором генерация формы из объединенной текстовой дорожки включает в себя сохранение текстовых свойств, которые ассоциированы с образцом текста.

18. Устройство по п.17, дополнительно содержащее создание контура из объединенной текстовой дорожки.

19. Устройство по п.16, в котором создание объединенной текстовой дорожки для образца текста включает в себя использование логических операций.

20. Устройство по п.17, в котором применение эффекта включает в себя применение эффекта, выбранного из эффекта линии; масштабирования; затенения; выдавливания и скашивания.

Описание изобретения к патенту

Предшествующий уровень техники

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

Сущность изобретения

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

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

Краткое описание чертежей

Фиг. 1 иллюстрирует приведенное для примера вычислительное устройство;

Фиг. 2 показывает систему эффектов;

Фиг. 3 иллюстрирует приведенное для примера окно приложения, показывающее различные эффекты, примененные к образцу текста;

Фиг. 4 показывает процесс для применения эффектов к форме, которая сгенерирована из объединенной текстовой дорожки;

Фиг. 5 иллюстрирует процесс для создания объединенной текстовой дорожки с использованием логических операций; и

Фиг. 6 показывает, как соединяются звенья, чтобы сформировать контур.

Детальное описание

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

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

Со ссылкой на фиг. 1 ниже описана иллюстративная компьютерная архитектура для компьютера 100, используемая в различных вариантах осуществления. Компьютерная архитектура, показанная на фиг. 1, может быть сконфигурирована как настольный или мобильный компьютер и включает в себя центральный обрабатывающий блок 5 (центральный процессор, CPU), системную память 7, включающую в себя оперативную память (ОЗУ, RAM) 9 и постоянную память (ПЗУ, ROM) 11, и системную шину 12, которая соединяет память с центральным процессором 5. Базовая система ввода/вывода, содержащая базовые стандартные программы, которые помогают переносить информацию между элементами в пределах компьютера, например, при запуске, сохранена в ROM 11. Компьютер 100 дополнительно включает в себя массовую память (ЗУ большой емкости) 14 для хранения операционной системы 16, прикладных программ и других программных модулей, которые описаны ниже более подробно.

ЗУ 14 большой емкости связано с центральным процессором 5 через контролер ЗУ большой емкости (не показан), связанный с шиной 12. ЗУ 14 большой емкости и ассоциированные с ним машиночитаемые носители обеспечивают энергонезависимую память для компьютера 100. Хотя описание машиночитаемых носителей, упоминаемых здесь, относится к ЗУ большой емкости, такому как жесткий диск или дисковод CD-ROM, машиночитаемые носители могут быть любыми доступными носителями, к которым может получить доступ компьютер 100.

В качестве примера, но не ограничения, машиночитаемые носители могут включать в себя компьютерные носители данных и коммуникационные среды. Компьютерные носители данных включают в себя энергозависимые и энергонезависимые, сменные и несменные носители, реализованные любым способом или по любой технологии для хранения информации, такой как считываемые компьютером инструкции, структуры данных, программные модули или другие данные. Компьютерные носители данных включают в себя, без ограничения указанным, RAM (ОЗУ), ROM (ПЗУ), стираемое программируемое ПЗУ (EPROM), электронно-стираемое программируемое ПЗУ (EEPROM), флэш-память или другую технологию твердотельного ЗУ, ПЗУ на компакт-диске (CD-ROM), цифровые универсальные диски (DVD) или другое оптическое ЗУ, магнитные кассеты, магнитную ленту, ЗУ на магнитном диске или другие магнитные ЗУ, или какой-либо другой носитель, который может использоваться, чтобы хранить желательную информацию, к которой может получить доступ компьютер 100.

Согласно различным воплощениям компьютер 100 может работать в сетевой среде, использующей логические соединения с удаленными компьютерами через сеть 18, такую как Интернет. Компьютер 100 может соединяться с сетью 18 через блок 20 сетевого интерфейса, связанный с шиной 12. Сетевое соединение может быть беспроводным и/или проводным. Блок 20 сетевого интерфейса может также быть использован для соединения с сетями других типов и удаленными компьютерными системами. Компьютер 100 может также включать в себя контроллер 22 ввода/вывода для приема и обработки ввода из ряда других устройств, включая клавиатуру, мышь или электронное перо (не показано на фиг. 1). Аналогичным образом, контроллер 22 ввода/вывода может обеспечить вывод на экран 28 дисплея, принтер или устройство вывода другого типа.

Как упомянуто кратко выше, многие программные модули и файлы данных могут быть сохранены в ЗУ 14 большой емкости и RAM 9 компьютера 100, включая операционную систему 16, подходящую для управления операцией сетевого персонального компьютера, такую как операционная система WINDOWS XP от MICROSOFT CORPORATION, Редмонд, шт. Вашингтон. ЗУ 14 большой емкости и RAM 9 может также хранить один или более программных модулей. В частности, ЗУ 14 большой емкости и RAM 9 может хранить одну или более прикладных программ 10. Прикладная(ые) программа(ы) 10 действует(ют) для применения эффектов к тексту. Согласно одному воплощению прикладная(ые) программа(ы) 10 включает(ют) в себя набор прикладных программ WINDOWS OFFICE от MICROSOFT CORPORATION. Например, прикладная программа 10 может представлять собой MICROSOFT WORD, POWERPOINT, EXCEL, ACCESS, PUBLISHER, OUTLOOK и т.п. Другие прикладные программы, которые реализуют текстовые эффекты, могут также быть использованы. Например, могут быть использованы программы электронной почты, программы настольной издательской системы, программы презентации и любой другой тип программы, которая позволяет применять эффекты к тексту.

Прикладная программа 10 может использовать менеджер 26 эффектов. Хотя менеджер 26 эффектов показан отдельно от прикладной программы 10, он может быть включен в прикладную программу 10 или находиться в некотором другом местоположении. Например, менеджер 26 эффектов может быть включен в графический конвейер (см. элемент 220 на фиг. 2), операционную систему 16 и т.п. Как будет описано более подробно ниже, менеджер 26 эффектов применяет эффекты к форме, которая сгенерирована из объединенной текстовой дорожки. Объединенная текстовая дорожка удаляет любое наложение и избыточность символов в пределах образца текста. В общем случае символы, которые содержатся в пределах образца текста, могут накладываться из-за настроек шрифта. Настройками шрифта, которые в типовом случае влияют на степень наложения в образце текста, являются гарнитура шрифта, размер шрифта, используемые эффекты, кернинг (регулирование расстояния между определенными парами символов) и используемый интервал между символами. Форма, которая генерируется из объединенной текстовой дорожки, удаляет это наложение и сохраняет информацию текстовой дорожки, ассоциированную с текстовой дорожкой, так чтобы дополнительные эффекты могли быть применены к форме. Например, деформирование, масштабирование и эффекты линии могут быть применены к форме. Трехмерная (3-D) модель текстовой дорожки может также быть создана из формы, которая имеет различные эффекты, применимые к ней, такие как экструзия (способ построения трехмерной модели путем "выдавливания" двумерного компонента в определенном направлении), создание скоса (эффект объемности, создаваемый графическими средствами на границах экранных клавиш, ярлыков и т. п.) и т.п. Операция менеджера 26 эффектов будет описана более подробно ниже.

Фиг. 2 показывает систему 200 эффектов. Как проиллюстрировано, система 200 эффектов включает в себя прикладную программу 10, менеджер 26 эффектов, модуль 210 объединения, операционную систему 16, графический конвейер 220 и дисплей 28. Как описано кратко выше, менеджер 26 эффектов создает форму из объединенной текстовой дорожки и применяет эффекты к форме. Объединенная текстовая дорожка создается из каждой текстовой дорожки, которая ассоциирована с образцом текста (например, текстом 202) для приложения 10. Как проиллюстрировано в системе 200, прикладная программа 10 конфигурирована для посылки образцов текста (например, образца 202 текста) менеджеру 26 эффектов. В проиллюстрированном примере прикладная программа 10 послала образец текста "Letter" (письмо) менеджеру 26 эффектов 26. Однако любой образец текста может быть послан менеджеру эффектов. Образец текста может быть одним или более символами. Например, образец текста может быть несколькими символами, словом, предложением и т.п. Менеджер 26 эффектов может быть конфигурирован, чтобы принимать все или часть образцов текста из приложения 10. Например, менеджер 26 эффектов может быть конфигурирован, чтобы принимать только образцы текстов, к которым должны быть применены текстовые эффекты. Например, если образец 202 текста должен быть визуализирован без эффектов, то образец текста может быть послан непосредственно в графический конвейер 220, как проиллюстрировано стрелкой 212. В принципе, каждая буква в пределах образца текста составлена из текстовой дорожки, которая грубо описывает ее контур. Например, текстовая дорожка для верхнего регистра "L" в шрифте Arial, показанная в образце 202 текста, состоит из шести точек, которые описывают контур буквы.

Модуль 210 слияния (объединения) конфигурирован для создания объединенной текстовой дорожки для образца текста под управлением процессора 26 эффектов. Объединенная текстовая дорожка - это единая дорожка, из которой может генерироваться форма таким образом, чтобы могли быть применены эффекты. Хотя модуль 210 объединения проиллюстрирован внутри менеджера 26 эффектов, он может находиться во многих различных местоположениях в пределах системы 200. Например, модуль 210 объединения может находиться в приложении 10, операционной системе 16 и графическом конвейере 220. Альтернативно, модуль 210 объединения может располагаться независимо от других модулей в пределах системы. Модуль 210 объединения конфигурирован для приема каждой текстовой дорожки для каждой буквы в тексте (например, образце 202 текста) и затем вычисления объединенной текстовой дорожки для всего образца текста. Согласно одному воплощению модуль 210 объединения использует булевы (логические) операции для вычисления объединенной текстовой дорожки. Альтернативно, модуль 210 объединения может конфигурироваться для создания объединенной текстовой дорожки только для символов в образце текста, к которому должны быть применены эффекты. Каждая текстовая дорожка включает в себя набор точек, которые составляют границу для каждого символа. Вообще, модуль 210 объединения вычисляет объединенную текстовую дорожку, которая представляет границу (контур) для всего образца текста. В настоящем примере граница для образца 202 текста включает в себя шесть символов, составляющих "Letter". Граница для всего образца текста определяет объединение символов, определенных их границами, идентифицированными текстовыми дорожками. Модуль 210 объединения удаляет избыточные части объединенных символов в пределах образца текста. Процессор 26 эффектов может тогда создать форму из единой объединенной текстовой дорожки, к которой могут быть применены эффекты. Форма, которая сгенерирована, представляет полную объединенную форму. Так как модуль 210 объединения устраняет наложение между формами в пределах образца текста, безызбыточная 3-D модель может быть создана из текстовой дорожки.

Например, в представленном примере процессор 26 эффектов обработал образец текста "Letter", используя модуль 210 объединения; применил эффекты к сгенерированной форме, представляющей "Letter", и затем предоставил графический конвейер с отображенной версией (230) "Letter", которая показана на дисплее 28.

На фиг. 3 показано приведенное для примера окно 300 приложения, показывающее различные эффекты, примененные к образцу текста. Как проиллюстрировано, фиг. 3 включает в себя окно 310 приложения, элементы 320 окна, область 330 дисплея и образцы 325, 334 и 336 текста.

Образец 325 текста иллюстрирует наложение, которое создается, когда эффекты применяются к образцу текста, без генерации формы из объединенной текстовой дорожки. Как можно заметить, каждая буква в пределах слова "Letter "накладывается на другую букву.

Образец 334 текста иллюстрирует слово "Letter", созданное с использованием формы, которая сгенерирована из объединенной текстовой дорожки и к которой применены следующие эффекты: линия, заполнение (градиент) и теневой эффект, примененный к тексту.

Образец 336 текста иллюстрирует 3-D модель со скосом и выдавливанием, созданную с использованием объединенной текстовой дорожки для слова "Letter". Выдавливание создается дублированием формы, которая была сгенерирована из объединенной текстовой дорожки, на отличающейся глубине и соединением двух форм. Скос создается путем уточнения выдавленной 3-D модели формы с применением профиля к краям 3-D модели.

Со ссылками на фиг. 4 и 5 ниже описан иллюстративный процесс для применения эффектов к форме, которая генерируется из объединенной текстовой дорожки.

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

На фиг. 4 показан процесс для применения эффектов к форме, которая генерируется из объединенной текстовой дорожки.

После операции запуска процесс переходит к операции 410, где принимается образец текста. Как правило, образец текста включает в себя символы, которые составляют слово и/или предложение. Однако больше или меньше символов может быть включено в образец текста.

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

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

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

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

После операции начала процесс переходит к операции 510, где принимается геометрия, ассоциированная с каждым символом в пределах образца текста. Полученная геометрия в общем случае состоит из 2D областей, представленных в терминах их границ. Каждая граница является совокупностью замкнутых фигур, которые могут быть представлены тремя классами точек. Эти классы точек включают в себя точки внутри границы, точки вне границы и точки на границе. В принципе, для конкретной точки то, где она содержится, может быть определено путем проведения бесконечного луча из точки, подсчета его пересечений с границей и затем применения некоторого правила.

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

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

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

Согласно одному воплощению поддерживаются два рабочих списка ссылок звеньев, включая список активных звеньев и список звеньев-кандидатов. Список активных звеньев содержит звенья, которые имеют края на текущей высоте обработки, отсортированные по горизонтали слева направо. Список звеньев-кандидатов содержит активные звенья, отсортированные по высоте их вершин-кандидатов. Согласно одному воплощению координаты вершин округлены до сетки целых чисел. В дополнение к их приближенным координатам, новые вершины, которые сформированы пересечениями краев, хранят информацию пересекающихся сегментов, которые сформировали их. Вместо сравнения приближенных чисел запросы на таких вершинах сравнивают выражения, которые определяют числа, которые должны сравниваться. Интервальная арифметика используется для вычисления интервала, который гарантированно будет содержать числовой результат каждого вычисления. Сравнение результатов вычисления может тогда быть сделано однозначно, если сравниваемые интервалы являются несвязными, что имеет место большую часть времени. Когда сравниваемые интервалы действительно накладываются, то процессы пересортировываются до вычисления, выполняемого пакетом точной арифметики, для получения определенного ответа. Цикл 530 сканирования содержит три различных операции, включая: разбиение звеньев в пересечениях 540; вычисление соединений 550 и выдача замкнутых фигур 560. Эти операции могут происходить повторно во время операции сканирования.

Операция 540 разбивает звено в его пересечениях. Первая (самая высокая) вершина в звене является его головной частью, а последняя (самая низкая) вершина - его концом. Когда обрабатывается любая другая вершина, то край ниже этой вершины исследуется на наличие пересечений с ее левыми и правыми соседями в активном списке. Когда пересечение найдено, звенья разбиваются. Новые разделенные звенья (ниже пересечения) вводятся в главный список звеньев. Может использоваться версия алгоритма Bentley-Ottman для идентификации пересечений между данным набором линейных сегментов. Звено в главном списке звеньев активизируется путем вставки его в рабочие списки (активный список и список кандидата), и его курсор затем помещается в его головную часть. После того как его конец обработан, активное звено удаляется из рабочих списков. Если звено разбивается (в пересечении), оно удаляется из списка кандидатов и повторно вводится согласно высоте вершины пересечения, которая является теперь вершиной кандидата (и концом) звена.

Когда вершина выбрана для обработки из списка кандидатов, звено удаляется из того списка, курсор перемещается к кандидату и затем обрабатывается. Если есть вершина ниже его, то она становится кандидатом, и звено вводится в список кандидатов согласно высоте той вершины-кандидата. Если нет никакой вершины- кандидата, то там устанавливается соединение и звено деактивируется после того, как соединение обработано. Операция 540 может иметь место в любой вершине, когда она обрабатывается.

Соединения вычисляются в операции 550. Когда новое звено активизируется или когда конец существующего звена обработан, соединение устанавливается и заполняется всеми звеньями, головные части или концы которых совпадают с ним. Первые называются звеньями головной части, а последние - звеньями конца. При запуске активизацией нового звена местоположение соединения среди активных звеньев устанавливается путем исследования его положения относительно их активных краев. Соседние звенья собираются и добавляются к соединению как концевые звенья, если их концы совпадают с соединением. Дополнительные звенья добавляются к соединению из главного списка как головные звенья, если их головные части совпадают с соединением. Головные звенья сортируются слева направо по их направлению в соединении. Любая пара звеньев, у которых первые края коллинеарны, разбивается в конце более короткого края. Крайние левые и крайние правые головные звенья соединения тестируются и разбиваются, если они пересекаются с их соседями. Если соединение не имеет никаких головных звеньев, тогда его левые и правые соседи (которые станут соседями друг друга после того, как соединение исчезает), тестируются и разбиваются, если они пересекаются. Все новые головные звенья затем классифицируются (как левое, правое или избыточное) с использованием объекта классификатора. В настоящее время есть два типа классификаторов. Один предназначен для классификации единственной формы, основываясь на правиле ее заполнения, а другой, кроме того, классифицирует границу двух форм, основываясь на взаимном содержании краев друг друга, и маркирует избыточные звенья, основываясь на типе логической операции.

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

На фиг. 6 показано, каким образом звенья соединяются для формирования контура.

Начинаясь с последовательности звеньев, имеющих пару головных звеньев (610), концевое звено соединяется с головным звеном (620). Два концевых звена соединяются, и их последовательность звеньев конкатенируется, если они отличны (630). В результате получается замкнутый контур, если они принадлежат последовательности звеньев (640).

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

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