Способ (варианты) и машиночитаемый носитель (варианты) для определения принадлежности точки кривой в многомерном пространстве

Способ (варианты) и машиночитаемый носитель (варианты) для определения принадлежности точки кривой в многомерном пространстве

Иллюстрации

Показать все

Реферат

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

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

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

Во множестве компьютерных приложений первые данные могут быть представлены кривой проходящей два или более измерений многомерного пространства, вторые данные могут быть представлены точкой в том же многомерном пространстве, и может быть полезным определять расположение точки, представляющей вторые данные, лежащей около кривой, представляющей первые данные. Например, первые данные могут представлять дорогу через местность географического региона, а вторые данные могут представлять приблизительную позицию транспортного средства в географическом регионе, возможно, полученную от спутника глобальной системы позиционирования (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, поскольку граничное расстояние, по крайн