СПОСОБ (ВАРИАНТЫ) И МАШИНОЧИТАЕМЫЙ НОСИТЕЛЬ (ВАРИАНТЫ) ДЛЯ ОПРЕДЕЛЕНИЯ ПРИНАДЛЕЖНОСТИ ТОЧКИ КРИВОЙ В МНОГОМЕРНОМ ПРОСТРАНСТВЕ Российский патент 2017 года по МПК G06N7/00 G01S5/00 G06T7/60 

Область техники, к которой относится изобретение

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

Уровень техники

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

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

Таким образом, здесь требуется усовершенствование способов определения принадлежности точки кривой в многомерном пространстве.

Раскрытие изобретения

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

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

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

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

генерацию второй кривой, являющейся аппроксимацией первой кривой;

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

сохранение на постоянном компьютерно-читаемом носителе (машиночитаемом носителе информации) координат областей;

анализ координат областей и координат точки и индикацию принадлежности точки первой кривой или индикацию отсутствия принадлежности точки первой кривой.

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

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

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

В некоторых вариантах осуществления технологии способ дополнительно включает в себя:

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

анализ координат области и координат точки; и

на основе анализа предоставление пользователю электронного устройства индикации о том, что точка принадлежит или не принадлежит первой кривой.

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

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

получение координат точки, определяющих ее положение в многомерном пространстве;

анализ координат области и координат точки; и

на основе анализа предоставление пользователю электронного устройства индикации о принадлежности точки или непринадлежности первой кривой.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фигура 1 является диаграммой компьютерной системы подходящей для реализации представленной технологии и/или совместного использования с вариантами осуществления представленной технологии;

Фигуры 2-4 являются снимками экрана приложения построения графиков, иллюстрирующими осуществления представленной технологии;

Фигура 5 является диаграммой сетевой вычислительной среды подходящей для использования вариантов осуществления представленной технологии;

Фигуры 6-8 являются снимками экрана картографического приложения, иллюстрирующими осуществления представленной технологии;

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

Фигуры 14-20 являются диаграммами, иллюстрирующими процесс определения областей охватывающих соответствующие части кривой (формирующие периферию полигонов) при итерационном генерировании второй кривой аппроксимации кривой в соответствии с другим вариантом осуществления представленной технологии; и

Фигуры 21 и 22 являются блок-схемами, иллюстрирующими соответствующие этапы двух вариантов осуществления способа представленной технологии.

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

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

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

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

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

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

Функции различных элементов, показанных на фигурах, включающие в себя любые функциональные блоки, обозначенные как "процессор", могут быть реализованы с помощью специализированного аппаратного обеспечения или же аппаратного обеспечения, способного выполнить программы соответствующего программного обеспечения. Когда идет выполнение процессором, функции могут выполняться одним специализированным процессором, одним общим процессором или множеством индивидуальных процессоров, причем некоторые из них могут являться общими. Более того, явное использование термина "процессор" или "контроллер" не должно толковаться исключительно как аппаратное обеспечение, способное выполнить программу, но также может содержать, без ограничений, цифровой сигнальный процессор (DSP), сетевой процессор, интегральную схему специального назначения (ASIC), программируемую пользователем вентильную матрицу (FPGA), постоянное запоминающее устройство (ПЗУ) для хранения программного обеспечения, оперативное запоминающее устройство (ОЗУ) и энергонезависимое запоминающее устройство. Также может быть включено другое аппаратное обеспечение, обычное и/или специальное.

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

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

На фигуре 1, где показана компьютерная система 100, подходящая для использования в некоторых вариантах реализации представленной технологии, которая содержит различные аппаратные средства, содержащие один или более одно или многоядерных процессоров, коллективно представленных процессором 110, твердотельным диском 120, оперативным запоминающим устройством 130, интерфейсом дисплея 140 и входным/выходным интерфейсом 150.

Связь между различными компонентами компьютерной системы 100 может осуществляться одной или более внутренней и/или внешней шиной 160 (например, шина PCI, универсальная последовательная шина (USB), шина IEEE 1394 "Firewire", шина SCSI, шина Serial-ATA и т.д.), к которой электрически подключены различные элементы аппаратного обеспечения. Интерфейс дисплея 140 может быть подключен к монитору 142 (например, по кабелю HDMI 144) видимому пользователю 170, а интерфейс входа/выхода 150 может быть подключен к клавиатуре 151 (например, по кабелю USB 153) и мыши 152 (например, по кабелю USB 154), причем и клавиатура 151, и мышь 152 управляются пользователем 170.

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

На Фигуре 2 показан снимок экрана приложения построения графиков 200, выполняемого на процессоре 110 компьютерной системы 100 фигуры 1, как, возможно, отображается на дисплее 142 по интерфейсу дисплея 140. Приложения построения графиков 200 демонстрирует линию изменения цен 202, иллюстрирующую изменения цен на акции Yandex N.V., продаваемые под тикером YNDX" на фондовой бирже NASDAQ, с начала 2012 до начала 2014. Изображение снимка экрана 200 также содержит курсор 204, который может передвигаться по экрану 142 пользователем 170 с помощью мыши 152 и интерфейса входа/выхода 150. Используя мышь 152, пользователь 170 кликает на точке клика 206 приложения построения графиков 200, точка 206 расположена близко, но не на самой линии цен акций 202.

Фигуры 3 и 4 показывают потенциальные снимки экрана приложения построения графиков 200, как оно может выглядеть на дисплее 142 компьютерной системы 100 после того, как пользователь 170 кликнет мышью 152 на точке клика 206 фигуры 2, в зависимости от того, определило ли приложением построения графиков 200, что точка клика 206 находится или нет на линии цен акций 202. Точнее, Фигура 3 иллюстрирует снимок экрана с приложением построения графиков 200, определившем, что точка клика 206 расположена на линии цен акций 202. Снимок экрана содержит дополнительно информацию 208, связанную с частью линии цен акций 202, наиболее близкую к точке клика 206. Таким образом, отображая дополнительную информацию 208 на дисплее 142, приложение построения графиков 200 предоставляет пользователю 170 индикацию о том, что оно определило, что точка клика 206 принадлежит линии цен акций 202.

Альтернативно фигура 4 иллюстрирует снимок экрана приложения построения графиков 200 так, как оно может выглядеть на дисплее 142 после того, как приложение построения графиков 200 определило, что точка клика 206 не принадлежит линии цен акций 202, приложение построения графиков 200, таким образом, определило клик пользователя 170 мышью 152 в точке клика 206 так, как индикацию того, что желаемо вхождение в режим ввода текста, и поэтому текст 210 покрывает приложение построения графиков 200 в точке клика 206. Фигура 4 показывает текст 210, введенный пользователем 170, например, набором на клавиатуре 151, с курсором 204, предоставляющего индикацию пользователю 170 расположения (конец текста 210), где новые знаки, набранные на клавиатуре 151, будут появляться. Таким образом, изменяя вид курсора 204 из стрелочного вида (как на фигуре 2) в вид текстового курсора (как на фигуре 4), приложение построения графиков 200 предоставляет пользователю 170 индикацию о том, что оно определило, что точка клика 206 не находится на линии изменения цен 202.

Обращаясь к Фигуре 5, на которой показано сетевое компьютерное оборудование 300, подходящее для использования в нескольких вариантах осуществления представленной технологии, сетевое компьютерное оборудование 300 содержит смартфон 310 (например, Apple iPhone или Samsung Galaxy S4) с сенсорным экраном 312 для отображения информации для пользователя 170 и получения сенсорных команд от пользователя 170 картографическим сервером 320, связанным со смартфоном 310 по коммуникационной сети 301 (например, Интернет), и спутник GPS 330, передающий GPS сигнал 332 на смартфон 310.

На ряду с сенсорным экраном 312 смартфон 310 также содержит внутренние компоненты аппаратуры, содержащие один или более одно- или многоядерных процессоров, коллективно относящиеся здесь к процессору 110 и оперативное запоминающее устройство 130, каждое из которых аналогичны подобно пронумерованным компонентам оборудования компьютерной системы 100, проиллюстрированной на фигуре 1, так же как сетевой интерфейс (не показан) для связи с картографическим сервером 320 по коммуникационной сети 301 и приемником GPS (не показано) для получения сигнала GPS 332 от спутника GPS 330.

Фигура 6 показывает картографическое приложение 400, работающее на процессоре 110 смартфона 310 на фигуре 5, как, возможно, отображаемое на сенсорном экране 312. Картографическое приложение 400 отображает карту 401, содержащую маршрут 410 от первой позиции 412 до второй позиции 414. Например, программные инструкции картографического приложения 400 при исполнении процессором 110 смартфона 310 могут вызывать получение процессором 110 запроса от пользователя 170 по сенсорному экрану 312, на определение маршрута 410 от первой позиции 412 до второй позиции 414. В результате процессор 110 может управлять сетевым интерфейсом смартфона 310 для получения подходящей картографической информации от картографического сервера 320 по коммуникационной сети 301 фигуры 5.

Как показано на фигурах 7 и 8, программные инструкции картографического приложения 400 могут дополнительно вызывать с помощью процессора 110 направление приемнику GPS смартфона 310 получения GPS позиции 416 смартфона 310, декодируя GPS сигнал 332, полученный от спутника GPS 330 Фигуры 5. Например, пользователь 170 может путешествовать вдоль маршрута 410 из первой позиции 412 ко второй позиции 414, неся смартфон 310. Каждая из фигур 7 и 8 представляет потенциальный снимок экрана картографического приложения 400, как оно может выглядеть на сенсорном экране 312 смартфона 310, в зависимости от того, получило ли картографическое приложение 400 GPS позицию 416 смартфона 310 или нет около маршрута 410.

Точнее, фигура 7 иллюстрирует, как карта 401 может выглядеть на сенсорном экране 312, если картографическое приложение 400 определило, что точка, представляющая GPS позицию 416, расположена около кривой, представляющей маршрут 410 в многомерном пространстве карты 401. Как показано на фигуре 7, хотя GPS позиция 416 не строго располагается «на» маршруте 410, картографическое приложение 400 может пренебречь таким незначительным отклонением от маршрута 410 и тем не менее показать GPS позицию 416, расположенную около маршрута 410. Например, картографическое приложение 400 может отображать на карте 401 полученную позицию 418 смартфона 310, являющуюся ближайшей точкой к GPS позиции 416 на маршруте 410, такое отображение скорее дополняет или заменяет GPS позицию 416. Таким же образом, картографическое приложение 400 может предоставлять индикацию пользователю 170 о том, что GPS позиция 416 располагается на маршруте 410.

Такая толерантность к отклонению GPS позиции 416 от маршрута 410 имеет смысл в обычных обстоятельствах. Например, конструктор картографического приложения 400 может считать информацию GPS позиционирования неточной в силу ряда причин (таких как переотражение от зданий или облаков), приводящее к сомнениям относительно того, насколько GPS позиция 416 представляет позицию смартфона 310 (и пользователя 170 по совместительству). В то время как слепая вера в точность GPS позиции 416 может предполагать то, что пользователь 170 отклонился от маршрута 410, хотя пользователь 170 может быть на маршруте 410. Разрешением некоторой величины погрешности картографическое приложение 400 может избежать такого ложного заключения. Конечно, подходящая степень толерантности должна быть выбрана с осторожностью для того, чтобы не столкнуться с обратной проблемой, при которой пользователь 170 фактически отклонится от маршрута 410.

Фигура 8 иллюстрирует, как карта 401 может отображаться на сенсорном экране 312 смартфона 310, если картографическое приложение 400 определило, что GPS позиция 416 на самом деле не принадлежит маршруту 410. В таком случае картографическое приложение 400 может считать смартфон 310 расположенным в полученной позиции 418 на дороге, которая не является частью маршрута 410, как наиближайшей дорогой, расположенной к GPS позиции 416 на карте 401. В таких условиях картографическое приложение 400 может решить, что пользователь 170 отклонился от маршрута 410 на такую величину, что необходимо получить новый маршрут 411 из позиции 412 ко второй позиции 414, новый маршрут 411 проходит через полученную позицию 418. Таким образом, картографическое приложение 400 может связываться с картографическим сервером 320 фигуры 5 по коммуникационной сети 301 для получения нового маршрута 411. Картографическое приложение 400 может затем отобразить маршрут 411 как часть карты 401, возможно, вместе с индикацией одного (или обоих, как на Фигуре 8) GPS позиции 416 и полученной позиции 418.

Описав, ссылаясь на фигуры 1-8, некоторые неограничивающие примеры проблемы определения принадлежности точки кривой в многомерном пространстве, будет описано основное решение этой проблемы, ссылаясь на фигуры 9-20. Точнее, в фигурах 9-13 кривая 500 связывает две точки 501 и 502, характеризуется определением участков, каждый из которых охватывает соответствующую часть кривой 500 как часть процесса генерации второй кривой аппроксимации кривой 500 в соответствии с вариантом осуществления хорошо известного алгоритма Рамера - Дугласа - Пекера (РДП). Затем, в фигурах 14-20, кривая, формирующая край многоугольника, будет характеризоваться определением областей, которые охватывают соответствующие части кривой как часть процесса генерации аппроксимации кривой в соответствии с другим вариантом осуществления РДП алгоритма.

Фигура 9 иллюстрирует для описания кривую 500 в двух измерениях, кривая 500 соединяет первую точку 501 («А») и вторую точку 502 («В»). Кривая 500 может считаться представляющей, в общей форме, кривую, используемую в более конкретном приложении, неограничивающими примерами которой являются кривая цен акций 202 приложения построения графиков 200, показанного на фигурах 2-4, так же как и маршруты 410 и 411 на картографическом приложении 400, показанном на фигурах 6-8.

Фигура 10 иллюстрирует вторую кривую, содержащую отдельный линейный сегмент 510, соединяющий точки 501 и 502 и являющийся первой аппроксимацией кривой 500. Наиболее удаленная точка 503 («С») линейного сегмента 510 на кривой 500 определяет граничное расстояние области 520, охватывающей кривую 500. Область 520 состоит из всех точек, удаленных не далее чем точка 503 (наиболее удаленная точка от сегмента линии 510, лежащего на кривой 510 между точками 501 и 502) от сегмента линии 503.

Из-за того что многомерное пространство двумерно, область 520 является двумерной (площадь). Поскольку эта версия второй кривой имеет только один сегмент линии 510, он охватывается набором областей, имеющим только один член: область 520. В этом случае РДП алгоритм может продолжить аппроксимацию кривой 500, поскольку граничное расстояние области 520 может быть больше чем пороговая величина, возможно, определенная как число точек или физическое расстояние на экране 142.

Фигура 11 показывает эволюцию второй кривой, связанной с той, что показана на фигуре 10, в соответствии с реализацией РДП алгоритма. Отдельный сегмент линии 510 фигуры 10 был заменен двумя сегментами линии 511 и 512, сегмент линии 511 связывает точки 501 («А») и 503 («С»), которые были определены как наиболее удаленные точки от сегмента линии 510, и сегмент линии 512 связывает точки 503 («С») и 502 («В»).

Наиболее удаленная точка 504 («D») от сегмента линии 511 на кривой 500 между точками 501 («А») и 503 («С») определяет граничное расстояние области 521, которая охватывает часть кривой 500, включая ту часть кривой 500, которая располагается между точками 501 («А») и 503 («С»). Наиболее удаленная точка 505 («Е») от сегмента линии 512 на кривой 500 между точками 503 («С») и 502 («В») определяет граничное расстояние области 522, которая охватывает часть кривой 500, включающую ту часть кривой 500, которая расположена между точками 503 («С») и 502 («В»).

Поскольку эта версия второй кривой имеет два сегмента линии 511 и 512, она охватывается набором областей, имеющим два члена: область 521 и область 522. В этом случае РДП алгоритм может продолжить аппроксимацию кривой 500, поскольку граничное расстояние, по крайней мере, одной из областей (521, 522) в наборе областей может быть большим чем пороговое значение.

Фигура 12 показывает дополнительную эволюцию второй кривой, связанной с той, что показана на фигуре 11, в соответствии с реализацией РДП алгоритма. Вторая кривая аппроксимация кривой 500 теперь состоит из трех линейных сегментов 511, 513 и 514. Линейный сегмент 512 фигуры 11 был заменен двумя линейными сегментами 513 и 514, линейный сегмент 513 связывает точки 503 («С») и 505 («Е»), которые были определены как наиболее удаленные точки от линейного сегмента 512, и линейный сегмент 514 связывает точки 505 («Е») и 502 («В»).

Линейный сегмент 511 остается частью второй кривой, поскольку в соответствии с этим вариантом осуществления РДП алгоритма граничное расстояние от линейного сегмента 511 до точки 504 («D») значительно меньше для остановки дальнейшей аппроксимации части кривой 500, расположенной между 501 («А») и 503 («С»). Наиболее удаленная точка 506 («F») от линейного сегмента 513 на кривой 500 между точками 503 («С») и точкой 505 («Е») определяет граничное расстояние области 523, которая охватывает область кривой 500, включающую ту часть кривой 500, которая расположена между точками 503 («С») и 505 («Е»).

Наиболее удаленная точка 507 («G») из линейного сегмента 514 на кривой 500 между точками 505 («Е») и 502 («В») определяет граничное расстояние области 524, которая охватывает часть кривой 500, включая ту часть кривой 500, которая лежит между точкой 505 («Е») и 502 («В»). Поскольку эта версия второй кривой имеет три линейных сегмента 511, 512 и 513, то она охватывается набором областей, имеющим три члена: область 521, область 523 и область 524. В этом случае РДП алгоритм может продолжить аппроксимацию кривой 500, поскольку граничное расстояние, по крайней мере, одной из областей (521, 523, 524) в наборе областей может быть большим чем пороговое значение.

Фигура 13 показывает дополнительную эволюцию второй кривой, связанной с той, что показана на фигуре 12, в соответствии с реализацией РДП алгоритма. Вторая кривая аппроксимация кривой 500 теперь состоит из четырех линейных сегментов 511, 513, 515 и 516. Линейный сегмент 514 фигуры 12 был заменен двумя линейными сегментами 515 и 516, линейный сегмент 515 связывает точки 505 («Е») и 507 («G»), которые были определены как наиболее удаленные точки от линейного сегмента 514, и линейный сегмент 516 связывает точки 507 («G») и 502 («В»).

Линейные сегменты 511 и 513 остаются частью второй кривой, поскольку в соответствии с этим вариантом осуществления РДП алгоритма граничные расстояния от областей 521 и 523 соответственно значительно меньшие для остановки дальнейшей аппроксимации частей кривой 500, расположенных между точками 501 («А») и 503 («С») и между точками 503 («С») и 505 («Е»). Наиболее удаленная точка 508 («Н») от линейного сегмента 515 на кривой 500 между точками 505 («Е») и точкой 507 («G») определяет граничное расстояние области 525, которая охватывает часть кривой 500, включающую ту часть кривой 500, которая расположена между точками 505 («Е») и 507 («G»).

Наиболее удаленная точка 509 («I») из линейного сегмента 516 на кривой 500 между точками 507 («G») и 502 («В») определяет граничное расстояние области 526, которая охватывает часть кривой 500, включая ту часть кривой 500, которая лежит между точками 507 («G») и 502 («В»). Поскольку эта версия второй кривой имеет четыре линейных сегмента 511, 513, 515 и 516, она охватывается набором областей, имеющим четыре члена: область 521, область 523, область 525 и область 526. В этом случае РДП алгоритм может прекратить аппроксимацию кривой 500, поскольку граничные расстояния областей 521, 523, 525 и 526 могут в конечном итоге все являются меньшими чем пороговое значение.

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

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

Например, как представлено на фигуре 15, область, состоящая из компонентных областей 620 и 630, охватывает линейный сегмент 610 второй кривой. Наиболее удаленная точка 601C от первой стороны линейного сегмента 610 кривой 600 между точками 601A и 601B определяет первое граничное расстояние компонентной области 620 и наиболее удаленная точка 601D от второй стороны линейного сегмента 610 на кривой 600 между точками 601B и 601A определяет граничное расстояние компонентной области 630.

Таким образом, в варианте осуществления представленной технологии, показанном на фигуре 15 (так же как и фигурах 16-20), каждая область определяется двумя граничными расстояниями, одно в противоположном направлении от соответствующей стороны линейного сегмента второй кривой. Для специалиста в данной области будет понятно, что этот тип областей (площадь в двумерном случае) является просто одной вариацией из представленных выше на фигурах 9-13, в которых каждая область была определена одним граничным расстоянием к наиболее удаленной точке от соответствующего линейного сегмента второй кривой. Другие типы областей могут также использоваться в различных вариациях представленной технологии.

Фигура 16 показывает эволюцию второй кривой, связанной с той, что показана на фигуре 15, в соответствии с реализацией РДП алгоритма. Отдельный линейный сегмент 610 фигуры 11 заменяется четырьмя линейными сегментами 611-614, линейный сегмент 611 соединяет точки 601A и 601C, которая была определена как наиболее удаленная точка от первой стороны линейного сегмента 610, линейный сегмент 612 соединяет точки 601C и 601B, линейный сегмент 613 соединяет точки 601A и 601D, которая была определена как наиболее удаленная точка от второй стороны линейного сегмента 610, и линейный сегмент 614 соединяет точки 601D и 601B.

На фигуре 15 каждый из линейных сегментов 611-614 сгенерированной второй кривой охватывается соответствующей областью, определяемой как область, состоящая из двух компонентных областей, каждая из компонентных областей была определена, в свою очередь, соответствующим граничным расстоянием наиболее удаленной точки на соответствующем участке кривой 600 от одной стороны соответствующего линейного сегмента (одного из 611-614), аппроксимируя эту часть кривой 600.

Таким образом, линейный сегмент 612 охватывается областью, состоящей из области 622, определенной первым граничным расстоянием от линейного сегмента 612 к наиболее удаленной точке 601H от первой стороны линейного сегмента 612, и областью 632, определенной вторым граничным расстоянием от линейного сегмента 612 к наиболее удаленной точке 6011 от второй стороны линейного сегмента 612; линейный сегмент 613 охватывается областью, состоящей из области 623, определяемой первым граничным расстоянием от линейного сегмента 613 к наиболее удаленной точке 601F от первой стороны линейного сегмента 613, и областью 633, определяемой вторым граничным расстоянием от линейного сегмента 613 к наиболее удаленной точке 601G от второй стороны линейного сегмента 613; и линейный сегмент 614 охватывается областью, состоящей из области 624, определяемой первым граничным расстоянием от линейного сегмента 614 к наиболее удаленной точке 601J от первой стороны линейного сегмента 614, и области 634, определяемой вторым граничным расстоянием от линейного сегмента 614 к наиболее удаленной точке 6011 от второй стороны линейного сегмента 614.

Область, охватывающая линейный сегмент 611, представляет особый случай, в котором граничное расстояние от первой стороны линейного сегмента 611 является нулевым, поскольку нет ни одной части кривой 600, расположенной между точками 601A и 601C, лежащими по эту сторону линейного сегмента 611. Поэтому область, охватывающая линейный сегмент 611, является областью, состоящей из первой компонентной области 621, определенной первым граничным расстоянием от линейного сегмента 611 к наиболее удаленной точке 601E от первой стороны линейного сегмента 611, и нулевая область соответствует нулевому граничному расстоянию второй стороны линейного сегмента 611.

В соответствии с настоящим примерным вариантом осуществления РДП алгоритма генерация второй кривой аппроксимации кривой 600 может остановиться сразу после одной итерации, поскольку может быть определено, что ни одна из областей в наборе областей, показанных на фигуре 16, не имеет граничное расстояние, большее чем пороговое значение. Конечная версия второй кривой может, тем не менее, состоять из линейных сегментов 611-614, как показано на фигуре 16.

Возвращаясь к фигуре 17, кривая 600 изображается снова так, как на фигуре 15, со второй кривой, являющейся первой аппроксимацией кривой 600, состоящей из всего одного сегмента 610, соединяющего точки 601A и 601B, линейный сегмент 610 охватывается областью, состоящей из компонентных областей 620 и 630, каждая из которых определяется соответствующим граничным расстоянием к соответствующим наиболее удаленным точкам 601C, 601D от соответствующей стороны линейного сегмента 611. В дополнение, точка 641 изображена вблизи к кривой 600.

Точка 641 представляет основной случай точки, которая может или не может быть определена как лежащая около кривой 600 (принадлежащая этой кривой). В более конкретных приложениях, таких как приложение построения графиков 200 (фигура 2) или картографическое приложение 400 (фигура 6), точка 641 может быть точкой 206 клика, близкой к линии 202 цен акций, или позиции 416 GPS, близкой к маршруту 410.

В соответствии с вариантами осуществления представленной технологии первое определение расположения точки 641 около кривой 600 может быть сделано в результате анализа координат области, охватывающей линейный сегмент 610 (то есть области, состоящей из компонентных областей 620 и 630), для определения, не расположена ли в них точка 641. Как показано на фигуре 17, точка 641 действительно лежит в компонентной области 620.

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

Например, если области были определены с помощью РДП алгоритма, как описано выше в соответствии с фигурами 13-16, может считаться, что пороговое значение, на основе которого РДП алгоритм был остановлен, является достаточно малым для индикации того, что любая точка, лежащая внутри областей из набора областей, охватывающих конечную версию второй кривой (например, области, показанные на фигуре 16), могут считаться принадлежащими кривой 600. В других вариантах осуществления граничное расстояние области, в которых располагается точка 641, могут быть точно проверены по отношению к пороговому значению.

Если граничное расстояние не больше чем пороговое значение, можно сделать вывод, что точка 641 принадлежит кривой 600. Однако если граничное расстояние больше чем пороговое значение, то могут быть выполнены дальнейшие расчеты для определения расположения точки 641 в другой области, охватывающей большую часть аппроксимации кривой 600, так же как областей 621, 622, 632, 623, 633, 624 и/или 634 фигуры 18. Как показано на фигуре 18, точка 641 фактически располагается в области 622, охватывающей линейный сегмент 612. Если граничное расстояние области 622 не больше чем пороговое значение, можно сделать вывод, что точка 641 действительно принадлежит кривой 600.

Обратимся сейчас к фигуре 19, кривая 600 снова показана, как на фигуре 15, но с добавлением второй точки 642, которая может или не может быть определенна как принадлежащая кривой 600. Как выше указано, первое определение расположения точки 642 около кривой 600 может быть сделано в результате анализа координат области, охватывающей линейный сегмент 610 (то есть области, состоящей из компонентных областей 620 и 630) для определения, не расположена ли в них точка 642 (компонентная зона 620, конкретнее).

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

Фигура 20 показывает более детализированную аппроксимацию кривой 600. Точка 642 не располагается внутри любой из областей 621, 622, 632, 623, 633, 624 или 634, которые составляют набор областей, охватывающих проиллюстрированную версию второй кривой. В некоторых вариантах осуществления представленной технологии факт того, что точка 642 находится вне всех областей набора областей, связанных с версией второй кривой, может быть достаточным для вывода о том, что точка 642 не принадлежит кривой 600.

Это может быть случаем, например, если наименьшее расстояние любой из областей является большим чем пороговое значение, что может быть в случае, например, если области были определены при генерации второй кривой в соответствии с РДП алгоритмом (как показано выше в соответствии с фигурами 14-16), в которых граничное расстояние областей было сравнено с пороговым значением при определении, когда надо прекратить расчет. В других вариантах осуществления граничное расстояние каждой из областей набора областей может быть сравнено с пороговым значением, и, если граничное расстояние каждой из областей больше чем пороговое значение, то это может быть определено как то, что точка 642 располагается слишком далеко от линейного сегмента 614 и, по совместительству, слишком далеко от кривой 600, чтобы считаться принадлежащей кривой 600.

На фигуре 21 представлена блок-схема, соответствующая показанному примеру способа осуществления настоящей технологии. Таким образом, фигура 21 иллюстрирует компьютерно-выполняемый способ 700 для определения принадлежности точки первой кривой в многомерном пространстве, способ выполняется процессором электронного устройства. Способ 700 может быть выполнен, например, в контексте компьютерной системы 100 фигуры 1 или в составе смартфона 310 фигуры 5 процессором 110, выполняющим программные инструкции, загруженные в ОЗУ 130 из твердотельного диска 120.

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

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

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

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

На этапе 730 координаты области, по крайней мере, одной из областей, сохраняются в постоянном машиночитаемом носителе (примеры которого содержат ОЗУ 130 и твердотельный диск 120 компьютерной системы 100). Анализ координат области и координат точки, определяющих положение точки в многомерном пространстве, может затем выполнятся для предоставления пользователю индикации о том, что точка принадлежит первой кривой, или индикации о том, что точка не принадлежит первой кривой.

Этот анализ может выполняться тем же процессором 110 того же электронного устройства (например, компьютерной системы 100 или смартфона 310), что определял области, охватывающие соответствующие участки первой кривой, или может выполняться разными процессорами разных электронных устройств, получивших координаты областей от процессора 110 электронного устройства, например по коммуникационной сети (например, коммуникационной сети 301).

Так, в некоторых случаях способ 700 может дополнительно содержать этапы 740, 750 и 760. На этапе 740 получают координаты точки, определяющие ее положение в многомерном пространстве. В соответствии с неограничивающими примерами приложения построения графиков 200 и картографического приложения 400 получение координат точки может относиться к получению координат точки клика 206 мыши 152 на приложении построения графиков 200 или получения координат GPS позиции 416. На этапе 750 проводится выполнение анализа координат области и координат точки.

Например, анализ может содержать оценивание принадлежности точка внутри или вне одной или более областей. На этапе 760 на основе анализа пользователю электронного устройства предоставляется индикация о том, что точка расположена на первой кривой. Например, в соответствии с приложением построения графиков 200 всплывающее окно с дополнительной информацией 208 может служить в качестве индикации для пользователя 170 приложения построения графиков, кликнувшего на точку клика 206, что точка клика 206 была определена как не лежащая на линии цены акций 202. Как дополнительный пример в соответствии с картографическим приложением 400, индикацией того, что GPS позиция 416 не принадлежит маршруту 410, может предоставить пользователю 170 демонстрацию нового маршрута 411 на карте 401.

В других случаях, как описано выше, анализ может не выполняться как часть способа 700, но как независимый компьютерно-исполняемый способ 800 для определения принадлежности точки первой кривой в многомерном пространстве, как показано на фигуре 22. Например, способ 800 может быть выполнен в составе другой компьютерной системы 100, имеющей координаты области, сохраненные на постоянном машиночитаемом носителе, таком как твердотельный диск 120 или ОЗУ 130.

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

На этапе 820, как на этапе 740, описанном выше, получают координаты точки, определяющие ее положение в многомерном пространстве.

На этапе 830, как на этапе 750, проводится выполнение анализа координат области и координат точки.

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

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

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

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

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

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

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

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

генерацию второй кривой, являющейся аппроксимацией первой кривой;

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

сохранение на постоянном компьютерно-читаемом носителе координат областей;

анализ координат областей и координат точки и индикацию принадлежности точки первой кривой или индикацию отсутствия принадлежности точки первой кривой.

2. Способ по п. 1, в котором определение областей многомерного пространства включает:

определение первого набора областей при генерации первой версии второй кривой, являющейся первой полигональной кривой; и

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

3. Способ по п. 2, в котором:

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

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

4. Способ по п. 2, в котором генерирование второй кривой включает выполнение алгоритма Рамера - Дугласа - Пекера.

5. Способ по п. 1, в котором получают координаты точки, определяющие ее положение в многомерном пространстве;

выполняют анализ координат области и координат точки; и

на основе анализа предоставляют пользователю электронного устройства индикацию принадлежности или отсутствия принадлежности точки первой кривой.

6. Способ по п. 5, в котором предоставление индикации отсутствия принадлежности точки первой кривой основано на анализе координат точки и координат области и осуществляется после:

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

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

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

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

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

выполнение анализа координат областей и координат точки; и

на основе анализа предоставление пользователю электронного устройства индикации принадлежности или индикации отсутствия принадлежности точки первой кривой.

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

9. Способ по п. 7, в котором предоставление индикации отсутствия принадлежности точки первой кривой основано на анализе координат точки и координат области и осуществляется после:

определения принадлежности точки области из первого набора областей, связанного с первой версией второй кривой, являющейся первой полигональной кривой; и

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

10. Способ по п. 7, в котором предоставление индикации принадлежности точки первой кривой основано на анализе координат точки и координат области и осуществляется после:

определения принадлежности точки области; и

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

11. Способ по п. 7, в котором предоставление индикации отсутствия принадлежности точки первой кривой основано на анализе координат точки и координат области и осуществляется после:

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

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

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

13. Способ по п. 12, в котором многомерное пространство имеет только два измерения, а каждая из областей является областью многомерного пространства.

14. Способ по п. 7, в котором многомерное пространство имеет только два измерения, а каждая область является соответствующей областью многомерного пространства состоящего из:

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

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

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

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

генерирования второй кривой, являющейся аппроксимацией первой кривой;

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

сохранения на постоянном машиночитаемом носителе координат областей;

анализа координат областей и координат точки и индикации принадлежности точки первой кривой или индикации отсутствия принадлежности точки первой кривой.

16. Носитель по п. 15, в котором определение областей многомерного пространства включает:

определение первого набора областей при генерации первой версии второй кривой, являющейся первой полигональной кривой; и

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

17. Носитель по п. 16, в котором:

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

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

18. Носитель по п. 16, в котором генерирование второй кривой включает выполнение алгоритма Рамера - Дугласа - Пекера.

19. Носитель по п. 15, в котором программные инструкции дополнительно выполняются процессором для:

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

выполнения анализа координат области и координат точки; и

на основе анализа предоставления пользователю электронного устройства индикации принадлежности или отсутствия принадлежности точки первой кривой.

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

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

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

выполнения анализа координат областей и координат точки; и

на основе анализа предоставление пользователю электронного устройства индикации принадлежности или индикации отсутствия принадлежности точки первой кривой.

21. Носитель по п. 20, в котором предоставление индикации основано на анализе координат точки и координат областей, при этом предоставление индикации отсутствия принадлежности точка первой кривой при определении отсутствия расположения точки ни в одной из областей.

22. Носитель по п. 20, в котором предоставление индикации отсутствия принадлежности точки первой кривой основано на анализе координат точки и координат области и осуществляется после:

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

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

23. Носитель по п. 20, в котором предоставление индикации принадлежности точки первой кривой основано на анализе координат точки и координат области и осуществляется после:

определения принадлежности точки области, являющейся одной из областей; и

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

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

25. Носитель по п. 24, в котором многомерное пространство имеет только два измерения, а каждая из областей является соответствующей областью многомерного пространства.

26. Носитель по п. 20, в котором многомерное пространство имеет только два измерения, а каждая область является соответствующей областью многомерного пространства, состоящего из:

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

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