Автоматическое обнаружение регулярных фигур из элементов
Изобретение относится к области обработки данных. Технический результат – обеспечение распознавания фигур среди элементов геометрической модели. Способ распознавания фигур содержит этапы, на которых: принимают набор 2D точек посредством системы обработки данных; идентифицируют соседние точки для каждой из множества точек в наборе посредством системы обработки данных; обнаруживают по меньшей мере одну фигуру среди точек в наборе посредством системы обработки данных, причем указанная фигура представляет собой одно из: линейной фигуры, прямоугольной фигуры, непрямоугольной фигуры или круговой фигуры; и сохраняют данные фигуры, соответствующие обнаруженной фигуре. 3 н. и 17 з.п. ф-лы, 20 ил.
Область техники, к которой относится изобретение
[0001] Настоящее изобретение относится в общем к системам компьютеризированного проектирования, визуализации и производства, системам управления жизненным циклом продуктов (“PLM”) и к подобным системам, которые управляют данными в отношении продуктов и других предметов (вместе называемых системами «управления данными о продуктах» или системами PDM).
Уровень техники
[0002] Системы компьютеризированного проектирования («системы CAD») позволяют пользователям проектировать и визуализировать объекты-модели. Желательно создание улучшенных систем.
Раскрытие изобретения
[0003] Различные описанные варианты выполнения включают в себя способы распознавания фигур и соответствующие системы и машиночитаемые носители. Способ включает в себя этап, на котором принимают набор двумерных (2D) точек. Способ включает в себя этап, на котором идентифицируют соседние точки для каждой из множества точек в наборе и обнаруживают по меньшей мере одну указанную фигуру среди точек в наборе. Указанная фигура может быть одним из линейной фигуры, идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки на 2D плоскости и на одной линии с ней, прямоугольной фигуры, идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки в ортогональных направлениях, непрямоугольной фигуры, идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки и на линии с ней в двух направлениях на 2D плоскости, или круговой фигуры, идентифицируемой посредством множества точек в наборе на регулярных расстояниях друг от друга, каждая из которых лежит вдоль дуги окружности с общим центром. Способ включает в себя этап, на котором сохраняют данные фигуры, соответствующие обнаруженной указанной фигуре.
[0004] Приведенное выше было весьма широкой характеристикой признаков и технических преимуществ настоящего изобретения для того, чтобы специалисты в данной области техники могли лучше понять нижеследующее подробное описание. Дополнительные признаки и преимущества изобретения будут описаны ниже и образуют предмет формулы изобретения. Специалистам в данной области техники будет понятно, что они могут с легкостью использовать замысел и конкретный описанный вариант выполнения в качестве основы для модификации или разработки других структур для решения тех же задач настоящего изобретения. Также специалистам в данной области техники будет понятно, что такие эквивалентные конструкции не выходят за рамки сущности и объема изобретения в его наиболее широком виде.
[0005] Перед обращением к нижеприведенному подробному описанию может быть полезным представление определений некоторых слов или словосочетаний, используемых на протяжении данного патентного документа: понятия «включать в себя» и «содержать», а также их производные, означают включение без ограничения; понятие «или» является включающим, означающим и/или; словосочетания «ассоциированный с» и «ассоциированный с упомянутым», а также их производные, могут означать «включать в себя», «быть включенным в», «быть взаимосвязанным с», «содержать», «содержаться в», «связывать» или «связываться с», «соединять» или «соединяться с», «быть выполненным с возможностью осуществления связи с», «взаимодействовать с», «перемежать», «накладывать», «быть близким», «быть связанным» или «быть связанным с», «иметь», «иметь свойство», или тому подобное; и понятие «контроллер» означает любое устройство, систему или их часть, которая управляет по меньшей мере одной операцией, если такое устройство реализовано в виде аппаратного обеспечения, микропрограммного обеспечения, программного обеспечения или некоторого сочетания по меньшей мере двух из них. Следует отметить, что функциональность, связанная с каким-либо конкретным контроллером, может быть централизованной или распределенной, как локально, так и удаленно. Определения некоторых слов и словосочетаний приведены на протяжении данного патентного документа, и специалистам в данной области техники будет понятно, что такие определения во многих, если не во всех случаях применимы к предшествующим, а также будущим применениям определенных таким образом слов и словосочетаний. Притом, что некоторые понятия могут включать в себя широкое разнообразие вариантов выполнения, приложенная формула изобретения может в явном виде ограничивать эти понятия конкретными вариантами выполнения.
Краткое описание чертежей
[0006] Для более полного понимания настоящего изобретения и его преимуществ обратимся теперь к нижеследующему описанию, рассматриваемому вместе с сопровождающими чертежами, на которых аналогичные позиции обозначают аналогичные объекты, и на которых:
[0007] Фиг. 1 иллюстрирует блок-схему системы обработки данных, в которой может быть реализован вариант выполнения.
[0008] Фиг 2 иллюстрирует блок-схему процесса в соответствии с описанными вариантами выполнения.
[0009] Фиг. 3A иллюстрирует модель, которая включает в себя множество 3D элементов двух различных основных типов элементов в соответствии с описанными вариантами выполнения.
[0010] Фиг. 3B иллюстрирует проекцию заданных точек элементов на плоскости в соответствии с описанными вариантами выполнения.
[0011] Фиг. 4 иллюстрирует пример набора 2D точек, соответствующих геометрической модели, который может быть обработан в соответствии с описанными вариантами выполнения.
[0012] Фиг. 5A-5D иллюстрируют примеры указателей фигуры в соответствии с описанным вариантом выполнения.
[0013] Фиг. 6 иллюстрирует одну методику вычисления центра для кругового указателя в соответствии с описанными вариантами выполнения.
[0014] Фиг. 7A-7J иллюстрируют пример результатов и преимуществ итеративного процесса, описанного в настоящем документе.
Осуществление изобретения
[0015] Фиг. 1-7J, описанные ниже, и различные варианты выполнения, используемые для описания принципов настоящего изобретения в данном патентном документе носят лишь иллюстративный характер и не должны быть каким-либо образом истолкованы как ограничивающие объем изобретения. Специалистам в данной области техники будет понятно, что принципы настоящего изобретения могут быть реализованы в любом устройстве, конфигурированном надлежащим образом. Многочисленные новые идеи настоящей заявки будут описаны с обращением к примерным неограничивающим вариантам выполнения.
[0016] CAD и другие системы могут поддерживать сетки или фигуры из элементов, которые в настоящем документе будут обобщенно называться «фигурами». Эти фигуры в контексте настоящего документа относятся к структурированной организации элементов геометрической модели по отношению друг к другу. Эти элементы могут быть любыми элементами геометрической модели, поддерживаемой в PDM или другой системе. Различные системы включают в себя способы создания элементов и их явной маркировки и таким образом их функционирования в качестве части системы.
[0017] Однако многие модели могут содержать неявные фигуры, которые не имеют явной маркировки, и которые поэтому не могут надлежащим образом функционировать в системе. Они могут возникать различными путями, включая, но не ограничиваясь, данные, импортируемые из другой системы, элементы в моделях, сформированных в более ранних версиях системы, модели, созданные посредством нетрадиционных, опосредованных или неявных способов, и другое.
[0018] Описанные варианты выполнения включают в себя системы и способы автоматического распознавания прямоугольных, круговых и линейных фигур среди элементов геометрических моделей.
[0019] Фиг. 1 иллюстрирует блок-схему системы обработки данных, в которой может быть реализован вариант выполнения, например в виде системы CAD, в частности конфигурированной посредством программного обеспечения или другим способом для выполнения процессов, описанных в настоящем документе, и в частности в качестве одной из множества взаимосвязанных и осуществляющих связь систем, описанных в настоящем документе. Система обработки данных включает в себя процессор 102, соединенный с кэшем/мостом 104 второго уровня, который, в свою очередь, соединен с локальной системной шиной 106. Локальная системная шина 106 может быть, например, шиной архитектуры взаимосвязи периферийных компонентов (PCI). Также с локальной системной шиной в показанном примере соединены основная память 108 и графический адаптер 110. Графический адаптер 110 может быть соединен с дисплеем 111.
[0020] Другие периферийные устройства, такие как адаптер 112 локальной сети (LAN)/глобальной сети/беспроводной сети (например, Wi-Fi), также могут быть соединены с локальной системной шиной 106. Интерфейс 114 шины расширения соединяет локальную системную шину 106 с шиной 116 ввода/вывода (I/O). Шина 116 I/O соединена с адаптером 118 клавиатуры/мыши, контроллером 120 дисков и адаптером 122 I/O. Контроллер 120 дисков может быть соединен с запоминающим устройством 126, которое может представлять собой любой используемый компьютером или машиночитаемый носитель, включая, но не ограничиваясь, энергонезависимые, жестко запрограммированные носители, такие как постоянные запоминающие устройства (ROM) или стираемые, электрически программируемые не перезаписываемые носители (EEPROM), накопители на магнитной ленте и записываемые пользователем носители, такие как гибкие диски, накопители на жестких дисках и не перезаписываемые носители на компакт-дисках (CD-ROM) или универсальных цифровых дисках (DVD), и другие известные оптические, электрические или магнитные запоминающие устройства.
[0021] Также в показанном примере с шиной 116 I/O соединен аудиоадаптер 124, с которым могут быть соединены громкоговорители (не показаны) для проигрывания звуков. Адаптер 118 клавиатуры/мыши обеспечивает соединение с координатным устройством (не показано), таким как мышь, шаровой манипулятор, тензометрический джойстик, сенсорная панель и т.п.
[0022] Специалисты в данной области техники поймут, что аппаратное обеспечение, изображенное на фиг. 1, может быть различным в конкретных реализациях. Например, в дополнение к изображенному аппаратному обеспечению или вместо него также могут быть использованы другие периферийные устройства, такие как оптический дисковод и тому подобное. Изображенный пример приведен только в целях пояснения и не подразумевается, что он содержит архитектурные ограничения по отношению к настоящему изобретению.
[0023] Система обработки данных в соответствии с вариантом выполнения настоящего изобретения включает в себя операционную систему, использующую графический пользовательский интерфейс. Операционная система позволяет одновременно представлять на графическом пользовательском интерфейсе множество окон отображения, причем каждое окно отображения обеспечивает интерфейс для другого приложения или для другого экземпляра того же приложения. Пользователь может манипулировать курсором на графическом пользовательском интерфейсе посредством координатного устройства. Положение курсора может изменяться и/или может формироваться событие, такое как нажатие кнопки мыши, для вызова желаемого ответа.
[0024] Может применяться одна из различных доступных на рынке операционных систем, такая как версия Microsoft WindowsTM, которая является продукцией корпорации Microsoft, расположенной в Редмонде, штат Вашингтон, если она будет слегка модифицирована. Операционная система модифицирована или создана в соответствии с настоящим изобретением, как описано.
[0025] Адаптер 112 LAN/WAN/беспроводной сети может быть соединен с сетью 130 (не являющейся частью системы 100 обработки данных), которая может быть любой общественной или частной сетью системы обработки данных или сочетанием сетей, как известно специалистам в данной области техники, включая сеть Интернет. Система 100 обработки данных может осуществлять связь по сети 130 с системой 140 серверов, которая также не является частью системы 100 обработки данных, но может быть реализована, например, в виде отдельной системы 100 обработки данных.
[0026] Описанные варианты выполнения могут анализировать геометрическую модель, включающую в себя множество элементов, и автоматически распознавать фигуры среди элементов. Фиг. 2 иллюстрирует блок-схему процесса в соответствии с описанными вариантами выполнения, который может выполняться, например, одной или более системами CAD (в общем называемыми ниже «системой»); другие чертежи используются в нижеприведенном описании для иллюстрации аспектов или примеров такого процесса.
[0027] Система принимает набор двумерных (2D) точек, представляющих по меньшей мере участок геометрической модели (205). Прием в контексте настоящего документа может включать в себя загрузку с запоминающего устройства, прием от другого устройства или процесса, прием через взаимодействие с пользователем, предварительную обработку других данных для обеспечения принимаемых данных или прочее.
[0028] Процесс в соответствии с описанными вариантами выполнения может принимать в качестве входных данных простой набор 2D точек. Исходные входные данные из модели могут, в качестве альтернативы, представлять собой либо 2D, либо трехмерные (3D) элементы, и в качестве части позиции 205 система может получить соответствующую опорную точку для каждого из элементов, как более подробно описано ниже с обращением к фиг. 3A и 3B.
[0029] Фиг. 3A иллюстрирует модель 300, которая включает в себя множество 3D элементов двух различных основных типов (форм) элементов. Для каждого из типов элементов система может назначить соответствующую точку на типе элемента и вектор ориентации для элемента. Например, элемент 302 представляет собой определенный тип элемента с определенной формой; система назначает точку 304 в том же местоположении на каждой из этих форм, и назначает вектор 306 ориентации с началом в точке 304, который указывает ориентацию каждой формы. Исходное назначение точки и вектора на первом из любого определенного типа элемента может быть произвольным, а остальные назначения для одинаковых типов элементов выполняются по отношению к первому элементу того типа.
[0030] Для элементов, точки которых уже не находятся в 2D пространстве, система может преобразовать точки в 2D пространство путем проецирования на общую плоскость. Фиг. 3B иллюстрирует проецирование назначенных точек элементов 320 на плоскость 322. Спроецированные точки 324 соответствуют местоположению точек на каждом из элементов 320.
[0031] Элементы в модели, вероятно, будут иметь множество различных типов, форм, размеров, ориентаций, а в 3D – различную высоту по отношению к плоскости. Любые, некоторые или все из этих переменных, а также другие, могут быть использованы для предварительного разделения входных данных.
[0032] Например, если элементы различных типов не должны рассматриваться для включения в фигуру, они могут быть отделены и могут быть переданы к отдельным и определенным вызовам процесса обнаружения. То есть если должны быть идентифицированы только фигуры среди общих типов элементов, то процесс обнаружения, описанный в настоящем документе, может быть отдельно выполнен последовательно или параллельно для каждого из различных типов элементов. Например, в контексте фиг. 3A процесс может быть выполнен один раз для всех элементов того же типа, что и элемент 302, и может быть выполнен второй раз для всех элементов того же типа, что и элемент 308.
[0033] В качестве другого примера, если интересуют только элементы с определенной ориентацией, то они могут быть сгруппированы, и каждая группа по ориентации (или только интересующая группа по ориентации) может быть отдельно пропущена через процесс обнаружения. Например, в контексте фиг. 3A процесс может быть выполнен только для элементов с той же вертикальной ориентацией, что и элемент 308, но не для элементов с другой ориентацией, таких как элемент 310.
[0034] Когда элементы группируются, включаются или исключаются, как описано в настоящем документе, соответствующие проецируемые 2D точки могут быть сгруппированы, включены или исключены соответственно для процесса обнаружения.
[0035] Вышеприведенные примеры служат лишь в качестве иллюстраций. Любые элементы, которые могут быть обработаны в набор 2D точек любым способом, могут быть обработаны посредством методик, описанных в настоящем документе, и любые такие процессы подразумеваются включенными как часть приема набора 2D точек.
[0036] При этом система может обнаруживать прямоугольные, линейные, круговые и другие фигуры среди точек.
[0037] Фиг. 4 иллюстрирует пример набора 2D точек 400, соответствующего геометрической модели (2D, либо 3D посредством методики проецирования, такой как описано выше), который может быть обработан в соответствии с описанными вариантами выполнения после его приема. Система может обнаруживать фигуры среди 2D точек.
[0038] Возвращаясь к Фиг. 2, система идентифицирует ближайшие «соседние» точки для каждой точки в наборе (210). Понятие «соседняя» в контексте настоящего документа относится к одной или более точкам, ближайшим к одной или более точкам, составляющим набор точек. Количество ближайших соседних точек, идентифицированных для каждой точки, может зависеть от выбранных «указателей», как описано ниже, или может включать в себя любое количество соседних точек. Указатели, такие как указатели фигур, распознаваемые системой, включают в себя, не ограничиваясь, указатели прямоугольных фигур, указатели линейных фигур, указатели круговых фигур и указатели непрямоугольных фигур; предусмотрены и указатели других фигур. Процесс 210 идентификации могут включать в себя определение расстояния и направления (вместе – вектор) от каждой точки к ее соседним точкам.
[0039] Затем система обнаруживает указанные фигуры среди набора точек (215). Для каждой точки в наборе система определяет, указывает ли она и ее ближайшие соседние точки на какие-либо фигуры. Следует отметить, что одна точка может указывать на множество типов фигур. Система может принимать пользовательский выбор указателей фигур, которые следует применить, таким образом, что идентифицируются только определенные типы фигур, или может применять любые или все указатели фигур.
[0040] Указатели фигур указывают на фигуру среди точек. Каждая точка проверяется по отношению к ее ближайшим соседним точкам, чтобы определить, указывает ли она на фигуру. Если она указывает на фигуру, то информация об этой фигуре (например, тип, интервал, направление) может быть сохранена вместе с идентификатором точки, которая впервые указала на него (исходная точка), как описано ниже.
[0041] Фиг. 5A-5D иллюстрируют примеры указателей фигур в соответствии с описанным вариантом выполнения. Эти указатели не являются ограничивающими, и могут быть использованы другие указатели на фигуры среди точек.
[0042] Фиг. 5A иллюстрирует пример указателя прямоугольной фигуры. В данном примере точка P является обрабатываемой точкой. Обнаруживаются векторы A и B из P к ее ближайшим соседним точкам. Векторы A и B ортогональны (90°) друг другу и образуют пример указателя прямоугольной фигуры. Прямоугольная фигура идентифицируется посредством множества точек в наборе на регулярных расстояниях от определенной точки P в ортогональных направлениях. Следует отметить, что «регулярные расстояния» в контексте настоящего документа могут включать в себя расстояния, кратные регулярному расстоянию, без точки в каждом интервале. Например, подразумевается, что это включает в себя случай, когда первая соседняя точка находится на расстоянии X, а следующая точка на фигуре в том же направлении находится на расстоянии 4X, даже если в наборе нет точек на расстояниях 2X или 3X.
[0043] Фиг. 5B иллюстрирует пример указателя линейной фигуры. В данном примере точка P является обрабатываемой точкой. Обнаруживаются векторы A и B из P к ее ближайшим соседним точкам. Векторы A и B являются линейными (180°, на одной линии) по отношению друг к другу и имеют равную величину, и образуют пример указателя линейной фигуры. Поэтому линейная фигура может быть идентифицирован посредством множества точек в наборе на регулярных расстояниях от определенной точки P и на одной линии с ней на 2D плоскости.
[0044] Фиг. 5C иллюстрирует пример указателя круговой фигуры. В этом примере точка P является обрабатываемой точкой. Обнаруживаются векторы A и B из P к ее ближайшим соседним точкам. Векторы A и B имеют одинаковую величину; то есть соседние точки для P находятся на равном расстоянии от P. Система может вычислять центр C, радиус r и угол Θ между следующими друг за другом элементами фигуры по отношению к центру указанной фигуры из точек A, B и P. Таким образом, круговая фигура может быть идентифицирована посредством множества точек в наборе на регулярных расстояниях друг от друга, каждая из которых лежит вдоль дуги окружности с общим центром C (хотя окружность и ее центр не являются частью точек или модели).
[0045] Фиг. 5D иллюстрирует пример указателя «непрямоугольной» фигуры. Непрямоугольные фигуры являются естественным расширением прямоугольных фигур, в которых угол между направлениями отличается от 90°, так что векторы не являются ортогональными друг другу. Непрямоугольная фигура может быть идентифицирована посредством множества точек в наборе на регулярных расстояниях от определенной точки и на линии с ней в двух направлениях на 2D плоскости. В этом примере точка P является обрабатываемой точкой. Обнаруживаются векторы A и B из P к ее ближайшим соседним точкам. Векторы A и B не являются ортогональными друг другу и образуют пример указателя непрямоугольной фигуры. Непрямоугольная фигура может быть идентифицирована посредством множества точек в наборе на регулярных расстояниях от определенной точки и на линии с ней в двух направлениях на 2D плоскости.
[0046] Фиг. 6 иллюстрирует одну методику для вычисления центра C для кругового указателя, определенной точки P, вектора A из точки P к соседней точке P2 и вектора B из точки P к соседней точке P1. Система может определять линию PL1 в качестве секущей вектора B в срединной точке m1, ортогональной вектору B. Система может определять линию PL2 в качестве секущей вектора A в срединной точке m2, ортогональной вектору A. Центр C круговой фигуры является пересечением PL1 и PL2.
[0047] Существуют два вида круговых фигур, указываемых различными вариантами выполнения – незамкнутые круговые фигуры и замкнутые круговые фигуры. Оба этих вида указываются одним и тем же указателем, однако важно, что угол Θ для замкнутых фигур должен иметь значение, которое делит 360° (т.е. 360°=N*угол Θ, где N – натуральное число). То есть угол между двумя точками в «замкнутой» круговой фигуре нацело делится на 360° таким образом, что набор точек в замкнутой круговой фигуре разделен равными расстояниями по предполагаемой окружности, если есть достаточно точек для завершения окружности. Для «незамкнутой» кругового фигуры такое требование отсутствует, угол Θ не делится нацело на 360°, и хотя фактические точки в наборе разделены равными расстояниями по предполагаемой окружности, если бы имелось достаточное количество точек для завершения окружности, то по меньшей мере две их них не были бы разделены равными расстояниями.
[0048] Возвращаясь к процессу, проиллюстрированному на Фиг. 2, в качестве части обнаружения указанных фигур на этапе 215 для каждого типа фигуры, указанного определенной точкой (если таковые имеются), система может проверить, была ли уже указана эта фигура, путем сравнения указанных фигур. Если фигура не была уже указана, система может сохранить вновь обнаруженную фигуру, например путем добавления в список указанных фигур следующих данных и сравнения данных для определения, что фигура уже указана:
- Для прямоугольных фигур система может сохранить расстояние по x и y и направления x и y. Первая точка, которая указала на эту фигуру, может быть использована в качестве исходной точки (которая сохраняется в качестве исходной для первой точки). Прямоугольные фигуры указывают на ту же фигуру как на предыдущую фигуру, когда их соответствующие фигуры накладываются друг на друга, так что расстояние по x и y является равным, направления x и y, соответственно, параллельны (и ортогональны друг другу), и исходная точка каждого из них лежит на фигуре для другого из них.
- Для линейных фигур система может сохранить расстояние, направление и исходную точку. Первая точка, которая указала на эту фигуру, может быть использована в качестве исходной точки (которая сохраняется в качестве исходной для первой точки). Линейные фигуры указывают на ту же фигуру как на предыдущую фигуру, когда их соответствующие фигуры накладываются друг на друга, так что расстояние между точками является равным, направления векторов параллельны, и исходная точка каждого из них лежит на фигуре другого из них.
- Для круговых фигур система может сохранить центр, угловое расстояние, направление и исходную точку. Первая точка, которая указала на эту фигуру, может быть использована в качестве исходной точки (которая сохраняется в качестве исходной для первой точки). Круговые фигуры указывают на ту же фигуру как на предыдущую фигуру, когда их соответствующие фигуры накладываются друг на друга таким образом, что угловые расстояния Θ равны, центры C равны, радиусы r (расстояние от центра до исходной точки) равны, и исходная точка для каждой точки лежит на фигуре другой точки. Круговая фигура не требует полного «набора» точек для завершения окружности.
[0049] Если текущая указанная фигура является той же, что и ранее обнаруженная указанная фигура, система может увеличить подсчет для этой указанной фигуры.
[0050] Система может объединять обнаруженные линейные фигуры в прямоугольные фигуры (220). Процесс обнаружения фигур иногда может формировать то, что могло бы в идеальном случае представлять собой прямоугольные фигуры, в виде отдельных линейных фигур. В таких случаях система может корректировать это и объединять такие случаи в прямоугольные фигуры.
[0051] Система может выбирать основную фигуру (225). Из всех указанных фигур на данном этапе система может выбирать основную фигуру. Эта основная фигура может быть выбрана из указанных фигур различными способами для выполнения конкретных требований. Например, один критерий для выбора основной фигуры может быть то, что фигура содержит наибольшее количество точек. Во многих случаях при выборе основной фигуры игнорируются любые фигуры с тремя или менее точками.
[0052] Система может сохранять данные фигур, включающие в себя ассоциированные точки (230). Это может включать в себя маркировку, отметку или другую ассоциацию с фигурами, включая любую основную фигуру, всех точек из набора, которые соответствуют основной фигуре, и с любыми 2D или 3D элементами, которые были использованы для формирования набора точек, и сохранение этих данных фигуры. Это может включать в себя удаление всех точек, которые соответствуют основной фигуре, или из всех обнаруженных фигур, из набора точек. В различных вариантах выполнения могут быть удалены все точки, которые соответствуют обнаруженным фигурам, или могут быть удалены только точки, которые соответствуют основной фигуре. Все точки, которые соответствуют фигурам в любом из этих случаев могут быть удалены из набора точек, обрабатываемого в данный момент, таким образом, что могут быть обнаружены дополнительные фигуры, которые не включают в себя точки, уже ассоциированные с основной фигурой или другими обнаруженными фигурами.
[0053] Система может повторять процесс до 210, теперь обрабатывая только оставшиеся точки в наборе, для обнаружения других фигур. То есть как только точки в первой основной фигуре или во всех обнаруженных фигурах удалены из набора, система может повторять процесс с использованием только оставшихся точек, начиная с обнаружения ближайших соседних точек для каждой оставшейся точки.
[0054] Фиг. 7A-7J иллюстрируют пример результатов и некоторые преимущества итеративного процесса, описанного в настоящем документе; существуют и другие преимущества. Фиг. 7A иллюстрирует пример входного набора точек для первой итерации процесса, описанного в настоящем документе.
[0055] Фиг. 7B иллюстрирует пример прямоугольной фигуры, идентифицированной при первой итерации процесса, описанного в настоящем документе, такой как проиллюстрированная позицией 702.
[0056] После того, как эти фигуры идентифицированы при первой итерации, все точки на этих фигурах удаляются из исходного набора точек, и оставшиеся точки обрабатываются при второй итерации.
[0057] Фиг. 7C иллюстрирует пример оставшегося набора точек после того, как прямоугольная фигура, идентифицированная при первой итерации (как проиллюстрировано на фиг. 7B) удалена из входного набора точек после первой итерации. Эти оставшиеся точки 704 вводятся во вторую итерацию. Следует отметить, что в целях иллюстрации элементы или точки для фигуры действительно удаляются из иллюстрируемой модели; однако в типичном варианте реализации эти элементы или точки лишь удаляются из рассмотрения как часть данных, и не включаются в набор точек, переходящий в следующую итерацию процесса.
[0058] Фиг. 7D иллюстрирует пример прямоугольной фигуры, идентифицированной при второй итерации процесса, описанного в настоящем документе, как проиллюстрировано позицией 706. Следует отметить, что эта фигура могла не быть идентифицирована при первой итерации, поскольку удаленные теперь точки скрывали фигуру при их обработке в качестве соседних точек.
[0059] Фиг. 7E иллюстрирует пример оставшегося набора точек после того, как прямоугольная фигура, идентифицированная при второй итерации (как проиллюстрировано на фиг. 7D) также удалена из обрабатываемого набора точек. Эти оставшиеся точки вводятся в третью итерацию.
[0060] Фиг. 7F иллюстрирует пример круговой фигуры, идентифицированной при третьей итерации процесса, описанного в настоящем документе, как проиллюстрировано позицией 708. Следует отметить, что эта фигура могла не быть идентифицирована при первой итерации, поскольку удаленные теперь точки скрывали фигуру при их обработке в качестве соседних точек.
[0061] Фиг. 7G иллюстрирует пример оставшегося набора точек после того, как круговая фигура, идентифицированная при третьей итерации (как проиллюстрировано на фиг. 7F) также удалена из обрабатываемого набора точек. Эти оставшиеся точки вводятся в четвертую итерацию.
[0062] Фиг. 7H иллюстрирует пример линейной фигуры, идентифицированной при четвертой итерации процесса, описанного в настоящем документе, как проиллюстрировано позицией 710. Следует отметить, что эта фигура могла не быть идентифицирована при первой итерации, поскольку удаленные теперь точки скрывали фигуру при их обработке в качестве соседних точек.
[0063] Фиг. 7I иллюстрирует пример оставшегося набора точек после того, как линейная фигура, идентифицированная при четвертой итерации (как проиллюстрировано на фиг. 7H) также удалена из обрабатываемого набора точек. Эти оставшиеся точки вводятся в пятую итерацию.
[0064] Фиг. 7J иллюстрирует пример круговой фигуры, идентифицированной при пятой итерации процесса, описанного в настоящем документе, как проиллюстрировано позицией 712. Следует отметить, что эта фигура могла не быть идентифицирована при первой итерации, поскольку удаленные теперь точки скрывали фигуру при их обработке в качестве соседних точек.
[0065] Другие варианты выполнения включают в себя вариации конкретных методик, описанных выше. Например, «линейная» фигура может в качестве альтернативы быть представлена в виде прямоугольной фигуры с подсчетом Y, равным одному, и разделением по y, равным нулю. В некоторых вариантах выполнения все точки могут быть сохранены в древовидной структуре, что значительно ускоряет обнаружение ближайших соседних точек.
[0066] В некоторых вариантах выполнения для предотвращения обнаружения всех возможных линейных фигур в прямоугольных фигурах система может сначала обнаружить прямоугольные и круговые фигуры, удалить их из входного набора точек, и затем выполнить поиск линейной фигуры в оставшихся данных в последующей итерации.
[0067] Конечно, специалисты в данной области техники поймут, что, если это не указано конкретно или не требуется последовательностью операций, определенные этапы в процессе, описанном выше, могут быть пропущены, выполнены одновременно или последовательно, или выполнены в другом порядке.
[0068] Специалисты в данной области техники поймут, что для простоты и ясности в настоящем документе не показана или не описана полная структура и работа всех систем обработки данных, подходящих для использования с настоящим изобретением. Вместо этого, показана и описана только та часть системы обработки данных, которая является уникальной для настоящего изобретения или необходимой для понимания настоящего изобретения. Остальная часть конструкции и работы системы 100 обработки данных может соответствовать любым из различных существующих вариантов реализации и технологий, известных в данной области техники.
[0069] Важно отметить, что при том, что описание включает в себя описание в контексте полностью функциональной системы, специалисты в данной области техники поймут, что по меньшей мере части механизма настоящего изобретения выполнены с возможностью распространения в виде инструкций, содержащихся на используемом устройством, используемом компьютером или машиночитаемом носителе в любой из различных форм, и что настоящее изобретение в равной степени применимо вне зависимости от конкретного вида носителя инструкций или сигнала, используемого для фактического выполнения распространения. Примеры используемых устройством/машиночитаемых или используемых компьютером/машиночитаемых носителей включают в себя: носители энергонезависимого, жестко запрограммированного типа, такие как постоянные запоминающие устройства (ROM) или стираемые, электрически программируемые не перезаписываемые носители (EEPROM), и носители записываемого пользователем типа, такие как гибкие диски, накопители на жестких дисках и не перезаписываемые носители на компакт-дисках (CD-ROM) или универсальных цифровых дисках (DVD).
[0070] При том, что был подробно описан примерный вариант выполнения настоящего изобретения, специалистам в данной области техники будет понятно, что могут быть выполнены различные изменения, замены, вариации и усовершенствования, раскрытые в настоящем документе, без выхода за рамки сущности и объема изобретения в его наиболее широком виде.
[0071] Ничто из описания настоящей заявки не должно быть истолковано как подразумевающее, что какой-либо конкретный элемент, этап или функция является существенным элементом, который должен быть включен в объем формулы: объем запатентованного объекта изобретения определяется только патентоспособной формулой изобретения. Кроме того, ни к одному из этих пунктов формулы не должен относиться шестой абзац §112 ст. 35 USC, если за точным словосочетанием «средство для» не следует причастие.
1. Способ распознавания фигур, причем способ выполняется системой (100) обработки данных и содержит этапы, на которых:
принимают (205) набор двумерных точек (400) посредством системы обработки данных – «двумерный» далее обозначено «2D»;
идентифицируют (210) соседние точки для каждой из множества точек в наборе посредством системы обработки данных;
обнаруживают (215) по меньшей мере одну указанную фигуру среди точек в наборе посредством системы обработки данных, причем указанная фигура представляет собой одно из:
линейной фигуры (710), идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки (P) и на линии с ней на 2D плоскости,
прямоугольной фигуры (702), идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки (P) в ортогональных направлениях,
непрямоугольной фигуры, идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки (P) и на линии с ней в двух направлениях на 2D плоскости, или
круговой фигуры (708, 712), идентифицируемой посредством множества точек в наборе на регулярных расстояниях друг от друга, каждая из которых лежит вдоль дуги окружности с общим центром (C); и
сохраняют (230) данные фигуры, соответствующие обнаруженной указанной фигуре.
2. Способ по п. 1, в котором система обработки данных также преобразует 2D или трехмерные элементы (320) в набор 2D точек.
3. Способ по п. 1 или 2, в котором система обработки данных объединяет (220) множество линейных фигур в прямоугольную фигуру.
4. Способ по п. 1 или 2, в котором точки, соответствующие обнаруженной указанной фигуре, удаляются из набора 2D точек, и система обработки данных повторяет идентификацию, обнаружение и сохранение.
5. Способ по п. 1 или 2, в котором система обработки данных принимает пользовательский выбор указанной фигуры, который подлежит обнаружению.
6. Способ по п. 1 или 2, в котором система обработки данных определяет расстояние и направление между каждой точкой в наборе и каждой соседней точкой к упомянутой точке в наборе.
7. Способ по п. 1 или 2, в котором система обработки данных обнаруживает множество указанных фигур и выбирает (225) основную фигуру из множества обнаруженных указанных фигур.
8. Система (100) обработки данных, содержащая:
процессор (102); и
доступную память (108), причем система обработки данных, в частности, выполнена с возможностью:
приема (205) набора двумерных точек (400) - «двумерный» далее обозначено «2D»;
идентификации (210) соседних точек для каждой из множества точек (400) в наборе;
обнаружения (215) по меньшей мере одной указанной фигуры среди точек в наборе, причем указанная фигура представляет собой одно из:
линейной фигуры (710), идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки (P) и на линии с ней на 2D плоскости,
прямоугольной фигуры (702), идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки (P) в ортогональных направлениях,
непрямоугольной фигуры, идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки (P) и на линии с ней в двух направлениях на 2D плоскости, или
круговой фигуры (708, 712), идентифицируемой посредством множества точек в наборе на регулярных расстояниях друг от друга, каждая из которых лежит вдоль дуги окружности с общим центром (C); и
сохранения (230) данных фигуры, соответствующих обнаруженной указанной фигуре.
9. Система обработки данных по п. 8, причем система обработки данных также преобразует 2D или трехмерные элементы (320) в набор 2D точек.
10. Система обработки данных по п. 8 или 9, причем система обработки данных объединяет (220) множество линейных фигур в прямоугольную фигуру.
11. Система обработки данных по п. 8 или 9, в которой точки, соответствующие обнаруженной указанной фигуре, удаляются из набора 2D точек, и система обработки данных повторяет идентификацию, обнаружение и сохранение.
12. Система обработки данных по п. 8 или 9, причем система обработки данных принимает пользовательский выбор указанной фигуры, которая подлежит обнаружению.
13. Система обработки данных по п. 8 или 9, причем система обработки данных определяет расстояние и направление между каждой точкой в наборе и каждой соседней точкой к упомянутой точке в наборе.
14. Система обработки данных по п. 8 или 9, причем система обработки данных обнаруживает множество указанных фигур и выбирает (225) основную фигуру из множества обнаруженных указанных фигур.
15. Постоянный машиночитаемый носитель (126), закодированный исполняемыми инструкциями, которые при исполнении побуждают одну или более систем (100) обработки данных:
принимать (205) набор двумерных точек (400) - «двумерный» далее обозначено «2D»;
идентифицировать (210) соседние точки для каждой из множества точек (400) в наборе;
обнаруживать (215) по меньшей мере одну указанную фигуру среди точек в наборе, причем указанная фигура представляет собой одно из:
линейной фигуры (710), идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки (P) и на линии с ней на 2D плоскости,
прямоугольной фигуры (702), идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки (P) в ортогональных направлениях,
непрямоугольной фигуры, идентифицируемой посредством множества точек в наборе на регулярных расстояниях от определенной точки (P) и на линии с ней в двух направлениях на 2D плоскости, или
круговой фигуры (708, 712), идентифицируемой посредством множества точек в наборе на регулярных расстояниях друг от друга, каждая из которых лежит вдоль дуги окружности с общим центром (C); и
сохранять (230) данные фигуры, соответствующие обнаруженной указанной фигуре.
16. Машиночитаемый носитель по п. 15, причем система обработки данных также преобразует 2D или трехмерные элементы (320) в набор 2D точек.
17. Машиночитаемый носитель по п. 15 или 16, причем система обработки данных объединяет (220) множество линейных фигур в прямоугольную фигуру.
18. Машиночитаемый носитель по п. 15 или 16, причем точки, соответствующие обнаруженной указанной фигуре, удаляются из набора 2D точек, и система обработки данных повторяет идентификацию, обнаружение и сохранение.
19. Машиночитаемый носитель по п. 15 или 16, причем система обработки данных принимает пользовательский выбор указанной фигуры, которая подлежит обнаружению.
20. Машиночитаемый носитель по п. 15 или 16, причем система обработки данных определяет расстояние и направление между каждой точкой в наборе и каждой соседней точкой к упомянутой точке в наборе.
