Область техники, к которой относится изобретение
[0001] Настоящее техническое решение относится к способам и системам симплификации кривой.
Уровень техники
[0002] Симплификация кривых включает в себя выборочное удаление вершин на протяжении кривой для удаления ненужной информации. Задачей алгоритмов симплификации кривых (также известных как алгоритмы симплификации линий) обычно является сохранение внешнего вида или формы кривой, хотя число ее точек и уменьшается, при этом сводя к минимуму погрешность в определении местоположения.
[0003] В компьютерных технологиях существует растущая потребность в способах симплификации кривых. Например, симплификация кривых (также известная как симплификация линий) является важной функцией в картографии и географических информационных системах (GIS), и широко используется в коммерческих пакетах программного обеспечения GIS. Множество мобильных устройств (например, смартфонов) имеют картографическое приложение, которое позволяет пользователю просматривать различные географические области для конкретных целей, например, чтобы проложить путь в конкретную область, оценить уровень загруженности конкретных дорог или найти расположение конкретных магазинов. Пользователь рассматривает различные области в картографическом приложении и приближает или удаляет изображение, чтобы видеть карту в разных масштабах. Такие функции требуют от систем картографической генерализации упрощения карт, чтобы отрисовать географические характеристики в высоком разрешении и с хорошим разрешением на выходе.
[0004] На цифровых картах одно- или двумерные объекты обычно представлены как ломаные линии (полилинии) или как многоугольники (полигоны). Ломаная линия - это соединенная последовательность сегментов в виде прямых линий. Многоугольник - частный случай ломаной линии, которая начинается и заканчивается в одной и той же точке. Таким образом, если объект в реальном мире искривлен, это передается последовательностью точек и сегментов в виде прямых линий, соединяющих эти точки.
Во внутреннем представлении карты одномерный объект, или одномерная граница двумерного объекта обычно представлены списком своих точек.
[0005] Часто при использовании данных цифровых карт производитель или пользователь данных обнаруживает, что данные слишком точны, а число точек гораздо больше, чем необходимо для конкретной цели. Например, это может произойти, когда данные, изначально собранные для использования при больших (приближенных) масштабах, используются при небольших (удаленных) масштабах. Если карта изображена с использованием более точных данных, присутствует гораздо больше точек, чем необходимо, что делает файл данных гораздо больше, а время обработки - гораздо дольше, чем необходимо. В такой ситуации преимуществом будет генерализовать ломаные линии на карте таким образом, что они станут не более точными, чем это необходимо для конкретной цели.
[0006] Алгоритмы симплификации линий являются важным компонентом таких систем генерализаций карт. Алгоритмы симплификации линий также используются в широком спектре областей, относящихся к графике, например, в видеоиграх (например, чтобы показать такой объект, как замок, пользователю), фоторедакторах, видеоредакторах, для уменьшения размера изображения, для загрузки на электронное устройство или с него, для хранения и так далее. Графы, насыщенные данными, часто встречаются в областях инженерии, включая стереографическое 3D и компьютерную мультипликацию, где перенасыщение данными может вызвать трудности при управлении в интерактивном режиме. Симплификация линий может также быть использована, например, при преобразовании исходных данных, чтобы уменьшить их объем для более компактного хранения, и для объединения разномасштабных баз данных.
[0007] Было разработано множество способов симплификации линий. Одним из наиболее широко используемых алгоритмов симплификации линий является алгоритм Дугласа-Пекера (также известный как алгоритм Рамера-Дугласа-Пекера, или алгоритм РДП (RDP)), (Douglas, D.Н. and Peucker, Т.K., Canadian Cartographer, vol. 10, pp. 112-22, 1973). Примеры других широко известных алгоритмов перечислены ниже: алгоритм Лэнга (Lang, Т., Geographical Magazine, vol. 42, pp. 50-51, 1969); Рейманна и Уиткема (Reumann, K. and Witkam, А.Р.М., Proc. Int. Computing Symp., pp. 467-472, North-Holland Publishing Company, Amsterdam, 1974); Висвалингема и Уайетта (Visvalingam, M. and Whyatt, J.D., The Cartographic Journal, vol. 30, pp. 46-51, 1993); Чжао и Заальфельда (алгоритм «подгонки рукавов» ("sleeve-fitting" algorithm; Zhao, Z. and Saalfeld, A., Autocarto 13, ACSM/ASPRS'97 Technical Papers, Seattle, Washington, vol. 5, pp. 214-223, 1997)); и Опхайма (Opheim, H., GeoProcessing, vol. 2, pp. 33-40). Однако у всех общеизвестных способов симплификации линий имеются значительные недостатки. Настоящие способы и системы для эффективной обработки и отрисовки симплифицированных линий неудовлетворительны.
[0008] Бальбоа и Лопез (Balboa, J.L.G. and Lopez, F.J.A., Pattern Recognition 42 (2009), pp. 2150-59) описывают автоматический способ деления линий на сегменты на основе распознавания изогнутого шаблона. Изогнутый шаблон измеряется с помощью полезной площади, как описано в алгоритме Висвалингема-Уайетта. Сегменты определяются с помощью применения алгоритма Дугласа-Пекера к форме профиля линии. Описанный способ деления на сегменты включает в себя три основных этапа: а) определение, с помощью алгоритма Висвалингема-Уайетта, полезной площади в каждой точке кривой; б) получение формы профиля кривой как суммы полезных площадей по всей линии; и в) выбор критических точек с помощью применения алгоритма Дугласа-Пекера к форме профиля линии. Автоматическое решение для деления на сегменты прилагается.
[0009] Парк и Ю (Park, W. and Yu, K., Pattern Recognition Letters 32 (2011), pp. 1267-73) описывают сегментацию и симплификацию линейного объекта на основе количественного анализа характеристик формы данного сегмента линии с использованием множества алгоритмов симплификации для определения того, какой из них дает наиболее высокую производительность для данного сегмента линии. Их способ включает в себя две главные части: 1) анализ описаний параметров сегментов линии, которые дают особенно высокую производительность для каждого проверенного алгоритма симплификации; и 2) сегментацию данных линии на однородные сегменты с использованием способов геометрического анализа, и симплификация сегментов с использованием алгоритма, определенного в процессе сегментации, т.е. алгоритма, который показал наиболее высокую производительность.
Раскрытие изобретения
[0010] Задачей предлагаемого технического решения является устранение по меньшей мере некоторых недостатков, присущих известному уровню техники.
[0011] Первым объектом настоящего технического решения является способ симплификации кривой. Способ выполняется на компьютерном устройстве, например, на сервере или на клиентском устройстве. Способ включает в себя этапы: получения инструкций на симплификацию кривой; выполнения первого алгоритма симплификации, причем первый алгоритм симплификации был предварительно определен, а его выполнение симплифицирует кривую, таким образом создавая первую симплифицированную кривую и параметры формы первой симплифицированной кривой; определения множества однородных сегментов первой симплифицированной кривой на основе параметров формы; и симплификации каждого однородного сегмента с использованием соответствующего второго алгоритма симплификации, причем соответствующий второй алгоритм симплификации выбран из множества предварительно определенных вторых алгоритмов симплификации, независимо для каждого однородного сегмента на основе параметров формы соответствующего однородного сегмента; таким образом выполняют создание итоговой симплифицированной кривой.
[0012] В некоторых вариантах осуществления настоящего технического решения первый алгоритм симплификации выбирается из алгоритмов: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, варианта RDP, алгоритма «подгонки рукавов» (sleeve-fitting (SF)), функции представления (turning function (TF)), алгоритма нумерации точек (N-ной точки), радиального расстояния, алгоритма перпендикулярного расстояния. Аналогично, в некоторых вариантах осуществления настоящего технического решения множество предварительно определенных вторых алгоритмов симплификации включает в себя один или несколько из следующих алгоритмов: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, вариант RDP, алгоритм «подгонки рукавов» (sleeve-fitting (SF)), функция представления (turning function (TF)), алгоритм нумерации точек (N-ной точка), радиальное расстояние, алгоритм перпендикулярного расстояния.
[0013] В некоторых вариантах осуществления настоящего технического решения способ дополнительно включает в себя следующие этапы: определение для каждого однородного сегмента симплифицированной кривой второго множества вторых однородных сегментов симплифицированного однородного сегмента на основе параметров формы симплифицированного однородного сегмента, причем эти параметры были созданы соответствующим вторым алгоритмом симплификации; и симплификацию каждого второго однородного сегмента с использованием соответствующего третьего алгоритма симплификации, который выбран из множества предварительно определенных третьих алгоритмов симплификации независимо для каждого второго однородного сегмента на основе параметров формы соответствующего второго однородного сегмента; таким образом выполняют создание второй итоговой симплифицированной кривой.
[0014] В некоторых вариантах осуществления настоящего технического решения множество предварительно определенных третьих алгоритмов симплификации включает в себя один или несколько из следующих алгоритмов: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, вариант RDP, алгоритм «подгонки рукавов» (sleeve-fitting (SF)), функция представления (turning function (TF)), алгоритм нумерации точек (N-ной точки), радиальное расстояние, алгоритм перпендикулярного расстояния.
[0015] Параметры формы различаются в зависимости от использованных алгоритмов симплификации. В некоторых вариантах осуществления настоящего технического решения параметры формы включают одно или несколько из: длина и угол наклона, изогнутость, расстояние высот, перепад высот, полезная площадь для точки, комплексность, монотонность, длина между точками, средняя длина сегмента и плотность точек. Множество однородных сегментов также различаются в зависимости от использованных алгоритмов симплификации и параметров формы. В некоторых вариантах осуществления настоящего технического решения однородные сегменты определяются с использованием одного или нескольких пунктов из списка: способ удаления точек, способ на основе измерений, способ критических точек, способ геометрического анализа, способ на основе частоты и способ на основе базы знаний.
[0016] В некоторых вариантах осуществления настоящего технического решения, когда компьютерное устройство является сервером, способ дополнительно включает в себя этап отправки на клиентское устройство инструкции на отображение итоговой симплифицированной кривой (или второй итоговой симплифицированной кривой) на экране клиентского устройства. Инструкция на отображение итоговой симплифицированной кривой на экране клиентского устройства может включать в себя, например, инструкцию на масштабирование визуального представления кривой.
[0017] В альтернативных вариантах осуществления настоящего технического решения, когда компьютерное устройство является клиентским устройством, способ дополнительно включает в себя этап отрисовки итоговой симплифицированной кривой на экране клиентского устройства. Отрисовка итоговой симплифицированной кривой на экране клиентского устройства может включать в себя, например, масштабирование визуального представления кривой.
[0018] В некоторых вариантах осуществления настоящего технического решения кривая, итоговая симплифицированная кривая и/или вторая итоговая симплифицированная кривая являются частью карты, фотографии, изображения, видео или видеоигры. Кривая, итоговая симплифицированная кривая и/или вторая итоговая симплифицированная кривая могут быть частью графического 2D-объекта или графического 3D-объекта. Кривые и симплифицированные кривые могут быть отрисованы браузерным движком отрисовки (рендеринга) или общим движком отрисовки (рендеринга).
[0019] В некоторых вариантах осуществления настоящего технического решения этапы способа (этапы определения однородных сегментов и их симплификация) повторяются до тех пор, пока не будут достигнуты один или несколько конечных пунктов, например, желаемый порог масштабирования, желаемое разрешение, использование выделенной памяти или выделенного времени. Технический результат заключается в повышении скорости симплификации кривой.
[0020] Другим объектом настоящего технического решения является сервер. Сервер включает в себя носитель информации; процессор, функционально соединенный с носителем информации и выполненный с возможностью сохранять объекты на носителе информации. Процессор реализован с дополнительной возможностью осуществлять: выполнение первого алгоритма симплификации, причем первый алгоритм симплификации был предварительно определен, а его выполнение симплифицирует кривую, таким образом создавая первую симплифицированную кривую и параметры формы первой симплифицированной кривой; определение множества однородных сегментов первой симплифицированной кривой на основе параметров формы; и симплификацию каждого однородного сегмента с использованием соответствующего второго алгоритма симплификации, причем соответствующий второй алгоритм симплификации выбран из множества предварительно определенных вторых алгоритмов симплификации, независимо для каждого однородного сегмента на основе параметров формы соответствующего однородного сегмента; таким образом выполняют создание итоговой симплифицированной кривой.
[0021] В некоторых вариантах осуществления настоящего технического решения сервер выполнен с дополнительной возможностью осуществлять: определение для каждого однородного сегмента симплифицированной кривой второго множества вторых однородных сегментов симплифицированного однородного сегмента на основе параметров формы симплифицированного однородного сегмента, причем эти параметры были созданы соответствующим вторым алгоритмом симплификации; и симплификацию каждого второго однородного сегмента с использованием соответствующего третьего алгоритма симплификации, который выбран из множества предварительно определенных третьих алгоритмов независимо для каждого второго однородного сегмента на основе параметров формы соответствующего второго однородного сегмента; таким образом выполняют создание второй итоговой симплифицированной кривой.
[0022] В некоторых вариантах осуществления сервера, когда компьютерное устройство является сервером, процессор выполнен с дополнительной возможностью осуществлять отправку на клиентское устройство инструкции на отображение итоговой симплифицированной кривой или второй итоговой симплифицированной кривой на экране клиентского устройства. В некоторых альтернативных вариантах осуществления сервера, когда компьютерное устройство является клиентским устройством, процессор выполнен с дополнительной возможностью осуществлять отрисовку итоговой симплифицированной кривой или второй итоговой симплифицированной кривой на экране клиентского устройства.
[0023] В контексте настоящего описания «сервер» подразумевает под собой компьютерную программу, работающую на соответствующем оборудовании, которая способна получать запросы (например, от клиентских устройств) по сети и выполнять эти запросы или инициировать выполнение этих запросов. Оборудование может представлять собой один физический компьютер или одну физическую компьютерную систему, но ни то, ни другое не является обязательным для настоящего технического решения. В контексте настоящего технического решения использование выражения «сервер» не означает, что каждая задача (например, полученные команды или запросы) или какая-либо конкретная задача будет получена, выполнена или инициирована к выполнению одним и тем же сервером (то есть одним и тем же программным обеспечением и/или аппаратным обеспечением); это означает, что любое количество элементов программного обеспечения или аппаратных устройств может быть вовлечено в прием/передачу, выполнение или инициирование выполнения любого запроса или последствия любого запроса, связанного с клиентским устройством, и все это программное и аппаратное обеспечение может быть одним сервером или несколькими серверами, оба варианта включены в выражение «по меньшей мере один сервер».
[0024] В контексте настоящего описания, если конкретно не указано иное, «клиентское устройство» подразумевает под собой электронное устройство, связанное с пользователем и включающее в себя любое аппаратное устройство, способное работать с программным обеспечением, подходящим к решению соответствующей задачи. Таким образом, примерами клиентских устройств (среди прочего) могут служить персональные компьютеры (настольные компьютеры, ноутбуки, нетбуки и т.п.) смартфоны, планшеты, а также сетевое оборудование, такое как маршрутизаторы, коммутаторы и шлюзы. Следует иметь в виду, что компьютерное устройство, ведущее себя как клиентское устройство в настоящем контексте, может вести себя как сервер по отношению к другим клиентским устройствам. Использование выражения «клиентское устройство» не исключает возможности использования множества клиентских устройств для получения/отправки, выполнения или инициирования выполнения любой задачи или запроса, или же последствий любой задачи или запроса, или же этапов любого вышеописанного способа.
[0025] В контексте настоящего описания, если конкретно не указано иное, «компьютерное устройство» подразумевает под собой любое электронное устройство, способное работать с программным обеспечением, подходящим к решению соответствующей задачи. Компьютерное устройство может являться сервером, клиентским устройством и так далее.
[0026] В контексте настоящего описания, если конкретно не указано иное, термин «база данных» подразумевает под собой любой структурированный набор данных, не зависящий от конкретной структуры, программного обеспечения по управлению базой данных, аппаратного обеспечения компьютера, на котором данные хранятся, используются или иным образом оказываются доступны для использования. База данных может находиться на том же оборудовании, выполняющем процесс, который сохраняет или использует информацию, хранящуюся в базе данных, или же она может находиться на отдельном оборудовании, например, выделенном сервере или множестве серверов.
[0027] В контексте настоящего описания, если конкретно не указано иное, «информация» включает в себя любую информацию любого типа, включая информацию, которую можно хранить в базе данных. Таким образом, информация включает в себя, среди прочего, аудиовизуальные произведения (фотографии, видео, звукозаписи, презентации и т.д.), данные (картографические данные, данные о местоположении, цифровые данные и т.д.), текст (мнения, комментарии, вопросы, сообщения и т.д.), документы, таблицы и т.д.
[0028] В контексте настоящего описания, если конкретно не указано иное, «компонент» подразумевает под собой программное обеспечение (соответствующее конкретному аппаратному контексту), которое является необходимым и достаточным для выполнения конкретной(ых) указанной(ых) функции(й).
[0029] В контексте настоящего описания если конкретно не указано иное, слово «координаты» подразумевает под собой расположение точек, и/или линий, или тому подобного в системах отсчета. Системы отсчета могут являться, например, числами, и/или любыми другими символами, которые используются для определения расположения точки, линиями (включая кривые), или плоскостями в пространстве данного измерения относительно системы линий (осей), или другими неподвижными системами отсчета.
[0030] В контексте настоящего описания, если конкретно не указано иное, термин «носитель информации» подразумевает под собой носитель абсолютно любого типа и характера, включая ОЗУ, ПЗУ, диски (компакт диски, DVD-диски, дискеты, жесткие диски и т.д.), USB флеш-накопители, твердотельные накопители, накопители на магнитной ленте и т.д.
[0031] В контексте настоящего описания, если конкретно не указано иное, выражение «двумерный объект» (2D-объект) подразумевает под собой плоскую фигуру, отображенную на экране компьютера, причем эта плоская фигура ограничена конечной последовательностью линий, замыкающихся в закрытый контур.
[0032] В контексте настоящего описания, если конкретно не указано иное, выражение «графический объект» подразумевает под собой любую графическую фигуру, которая может быть отображена на экране компьютера. Графические объекты могут быть линейными объектами, двумерными объектами и трехмерными объектами. Графические объекты могут иметь любую форму.
[0033] В контексте настоящего описания, если конкретно не указано иное, выражение «граница графического объекта» подразумевает под собой периметр или часть периметра графического объекта, причем слово «периметр» означает контур, ограничивающий графический объект. Граница графического объекта может включать в себя части границы, которые могут быть сохранены как линии, соединяющие две крайние точки соответствующей части периметра. Границы графических объектов могут быть прямыми или кривыми линиями, или же прямыми или кривыми поверхностями, в зависимости от графического объекта.
[0034] В контексте настоящего описания, если конкретно не указано иное, термин «кривая» подразумевает под собой линию, которая не является прямой, т.е. кривую линию. Выражение «симплификация кривой» и «симплификация линии» используется здесь взаимозаменяемо для обозначения симплификации кривой линии. Кривая может быть представлена ломаной линией, которая соединяет последовательность сегментов в виде прямых линий. Многоугольник - частный случай ломаной линии, которая начинается и заканчивается в одной и той же точке. В контексте настоящего описания, если конкретно не указано иное, выражение «многоугольный (полигональный) объект» подразумевает под собой двумерный объект, отображенный на экране компьютера, причем этот двумерный объект ограничен конечной последовательностью линий, замыкающихся в закрытый контур.
[0035] В контексте настоящего описания, если конкретно не указано иное, выражение «параметр формы» является характеристикой внешней или видимой формы кривой. Неограничивающие параметры формы включают в себя длину и угол наклона, изогнутость, расстояние высот, перепад высот, полезная площадь для точки (например, определенный по алгоритму Висвалингема-Уайятта), комплексность, монотонность, длину между точками, среднюю длину сегмента и плотность точек.
[0036] В контексте настоящего описания, если конкретно не указано иное, «симплификация» является способом, в котором происходит выборочное удаление вершин на протяжении кривой, чтобы избавиться от ненужных деталей, сохранив при этом основную форму кривой.
[0037] В контексте настоящего описания, если конкретно не указано иное, «генерализация» является способом, в котором информация выбирается и представляется на карте таким образом, что она соответствует масштабу или разрешению средств отображения информации карты, без обязательного сохранения всех сложных географических или других картографических деталей. Генерализация обычно требует сохранения четкости, с подходящим содержимым, при данном масштабе, для выбранной цели, связанной с картой, и предполагаемой аудитории.
[0038] В контексте настоящего описания, если конкретно не указано иное, «алгоритм симплификации» является алгоритмом для симплификации кривых, включая ломаные линии, многоугольники и тому подобное. Многие из этих алгоритмов являются известными. Неограничивающие примеры алгоритмов симплификации линий включают в себя алгоритмы Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, вариант RDP, алгоритм «подгонки рукавов» (sleeve-fitting (SF)), функцию представления (turning function (TF)), алгоритм нумерации точек (N-ной точки), радиальное расстояние, алгоритм перпендикулярного расстояния. Также известны и могут быть использованы в способах и системах, представленных здесь и другие способы симплификации линий и алгоритмы.
[0039] В контексте настоящего описания, если конкретно не указано иное, термин «сегмент» подразумевает под собой прямую часть линии кривой, которая соединяет точки кривой. «Однородный сегмент» является частью кривой, которая имеет одинаковые или, по меньшей мере, очень близкие параметры формы на своем протяжении. Таким образом, как описывается здесь, однородный сегмент может включать в себя множество сегментов кривой, в котором каждый из множества сегментов имеет одинаковые или, по меньшей мере, очень близкие параметры формы, или же параметры формы по всему множеству сегментов в целом одинаковы. В общем случае два сегмента считаются однородными, если у них один или несколько параметров формы одинаковы или по меньшей мере, очень близки. Как будет понятно специалистам в данной области техники параметры формы, используемые для определения однородности в настоящем техническом решении, будут отличаться в зависимости от алгоритма симплификации, используемого для определения и создания параметров формы для данной кривой.
[0040] В контексте настоящего описания, если конкретно не указано иное, слова «первый», «второй», «третий» и т.д. используются в виде прилагательных исключительно для того, чтобы отличать существительные, к которым они относятся, друг от друга, а не для целей описания какой-либо конкретной взаимосвязи между этими существительными.
Так, например, следует иметь в виду, что использование терминов «первый сервер» и «третий сервер» не подразумевает какого-либо порядка, отнесения к определенному типу, хронологии, иерархии или ранжирования (например) серверов/между серверами, равно как и их использование (само по себе) не предполагает, что некий «второй сервер» обязательно должен существовать в той или иной ситуации. В дальнейшем, как указано здесь в других контекстах, упоминание «первого» элемента и «второго» элемента не исключает возможности того, что это один и тот же фактический реальный элемент. Так, например, в некоторых случаях, «первый» сервер и «второй» сервер могут являться одним и тем же программным и/или аппаратным обеспечением, а в других случаях они могут являться разным программным и/или аппаратным обеспечением.
[0041] Каждый вариант осуществления настоящего технического решения преследует по меньшей мере одну из вышеупомянутых целей и/или объектов. Следует иметь в виду, что некоторые объекты настоящего технического решения, полученные в результате попыток достичь вышеупомянутой цели, могут удовлетворять и другим целям, отдельно не указанным здесь.
[0042] Дополнительные и/или альтернативные характеристики, аспекты и преимущества вариантов осуществления настоящего технического решения станут очевидными из последующего описания, прилагаемых чертежей и прилагаемой формулы изобретения.
Краткое описание чертежей
[0043] Для лучшего понимания настоящего технического решения, а также других его аспектов и характерных черт сделана ссылка на следующее описание, которое должно использоваться в сочетании с прилагаемыми чертежами, где:
[0044] На Фиг. 1 представлена принципиальная схема системы, выполненной в соответствии с неограничивающим вариантом осуществления настоящего технического решения.
[0045] На Фиг. 2 представлен неограничивающий пример кривой, перед симплификацией и после симплификации, причем первая симплифицированная кривая разделена на три однородных сегмента.
[0046] На Фиг. 3 представлена блок-схема способа, выполняемого в рамках системы, изображенной на Фиг. 1, в соответствии с вариантами осуществления настоящего технического решения, не ограничивающими его объем.
[0047] На Фиг. 4 представлена блок-схема способа, выполняемого в рамках системы, изображенной на Фиг. 1, в соответствии с вариантами осуществления настоящего технического решения, не ограничивающими его объем.
[0048] На Фиг. 5 представлен неограничивающий пример кривой, перед симплификацией и после симплификации, причем первая симплифицированная кривая разделена на пять однородных сегментов.
Осуществление изобретения
[0049] На Фиг. 1 представлена схема системы 100, выполненная в соответствии с вариантами осуществления настоящего технического решения, не ограничивающими его объем. Важно иметь в виду, что нижеследующее описание системы 100 представляет собой описание показательных вариантов осуществления настоящего технического решения. Таким образом, все последующее описание представлено только как описание показательного примера настоящего технического решения. Это описание не предназначено для определения объема или установления границ настоящего технического решения. Некоторые полезные примеры модификаций системы 100 также могут быть охвачены нижеследующим описанием. Целью этого является также исключительно помощь в понимании, а не определение объема и границ настоящего технического решения. Эти модификации не представляют собой исчерпывающий список, и специалистам в данной области техники будет понятно, что возможны и другие модификации. Кроме того, это не должно интерпретироваться так, что там, где не были изложены примеры модификаций, никакие модификации невозможны, и/или что то, что описано, является единственным вариантом осуществления этого элемента настоящего технического решения. Как будет понятно специалисту в данной области техники, это, скорее всего, не так. Кроме того, следует иметь в виду, что система 100 представляет собой в некоторых конкретных проявлениях достаточно простой вариант осуществления настоящего технического решения, и в подобных случаях представлен здесь с целью облегчения понимания. Как будет понятно специалисту в данной области техники, многие варианты осуществления настоящего технического решения будут обладать гораздо большей сложностью.
[0050] Система 100 включает в себя компьютерное устройство 102, являющееся сервером 102. Сервер 102 может представлять собой обычный компьютерный сервер. В примере варианта осуществления настоящего технического решения, сервер 102 может представлять собой сервер Dell™ PowerEdge™, на котором используется операционная система Microsoft™ Windows Server™. Излишне говорить, что сервер 102 может представлять собой любое другое подходящее аппаратное и/или прикладное программное, и/или системное программное обеспечение или их комбинацию. В представленном варианте осуществления настоящего технического решения, не ограничивающем его объем, сервер 102 является одиночным сервером. В других вариантах осуществления настоящего технического решения, не ограничивающих его объем, функциональность сервера 102 может быть разделена, и может выполняться с помощью нескольких серверов.
[0051] В некоторых вариантах осуществления настоящего технического решения сервер 102 может находиться под контролем и/или управлением поставщика картографических сервисов, такого, например, как Яндекс.Карты (Yandex Maps™). В альтернативных вариантах осуществления настоящего технического решения сервер 102 может получать доступ к картографическому сервису, предоставляемому сторонними поставщиками. В других вариантах осуществления настоящего технического решения сервер 102 может находиться под контролем и/или управлением или может получать доступ к поставщику таких сервисов, как сервисы компьютерных игр, сервисы графического дизайна и к другим сервисам, имеющим отношение к компьютерной графике. В других вариантах осуществления настоящего технического решения сервер 102 может находиться под контролем и/или управлением или может получать доступ к поставщику таких сервисов, как сервисы фоторедакторов, сервисы видеоредакторов, сервисы хранения изображений (например, облачные сервисы) и другие сервисы, имеющие отношение к управлению такими графическими объектами как фотографии, видео и так далее. В дополнительных вариантах осуществления настоящего технического решения сервер 102 может находиться под контролем и/или управлением или может получать доступ к поставщику таких сервисов, как сервисы управления базами данных и сервисы хранения данных.
[0052] Сервер 102 включает в себя носитель 104 информации, который может использоваться сервером 102. В общем случае носитель 104 информации может быть выполнен как носитель любого характера и вида, включая ОЗУ, ПЗУ, диски (компакт диски, DVD-диски, дискеты, жесткие диски и т.д.), USB флеш-накопители, твердотельные накопители, накопители на магнитной ленте и т.д. а также их комбинацию.
[0053] Варианты осуществления сервера 102 хорошо известны. Таким образом, достаточно отметить, что сервер 102 включает в себя, среди прочего, интерфейс 109 сетевой связи (например, модем, сетевую карту и тому подобное) для двусторонней связи по сети 110 передачи данных; и процессор 108, соединенный с интерфейсом 109 сетевой связи и носителем 104 информации, причем процессор 108 выполнен с возможностью выполнять различные процедуры, включая те, что описаны ниже. С этой целью процессор 108 может иметь доступ к машиночитаемым инструкциям, хранящимся на носителе 104 информации, выполнение которых инициирует процессор 108 реализовать различные описанные здесь процедуры.
[0054] В некоторых вариантах осуществления настоящего технического решения, не ограничивающих его объем, сеть 110 передачи данных может представлять собой Интернет. В других вариантах осуществления настоящего технического решения сеть 110 передачи данных может быть реализована иначе - в виде глобальной сети передачи данных, локальной сети передачи данных, частной сети передачи данных и т.п.
[0055] Носитель 104 информации выполнен с возможностью хранить данные, включая машиночитаемые инструкции и другие данные, включая данные графических объектов (например, картографические данные, данные видеоигр, изображений и т.д.). В некоторых вариантах осуществления настоящего технического решения носитель 104 информации может хранить по меньшей мере часть данных в базе данных 106. В других вариантах осуществления настоящего технического решения носитель 104 информации может хранить по меньшей мере часть данных в любом наборе данных, который отличается от базы данных.
[0056] Носитель 104 информации может хранить машиночитаемые инструкции, которые управляют обновлениями, заполнением и модификациям базы данных 106 и/или другими наборами данных. Более конкретно, машиночитаемые инструкции, хранящиеся на носителе 104 информации, могут позволить серверу 102 получить (например, обновить) информацию относительно графических объектов по сети 110 передачи данных и сохранить информацию относительно графических объектов, включая информацию относительно их симплифицированных кривых в базе данных 106 и/или других наборах данных.
[0057] Данные, сохраненные на носителе 104 информации (и, более конкретно, по меньшей мере частично, в некоторых вариантах осуществления настоящего технического решения, в базе данных 106) могут включать в себя, среди прочего, графические объекты любого типа. Неограничивающие примеры графических объектов включают в себя карты, видеоигры, изображения, фотографии и аудиовизуальные работы.
[0058] Машиночитаемые инструкции, сохраненные на носителе 104 информации, при исполнении могут инициировать получение процессором 108 инструкций на симплификацию кривой 208, 500. Инструкции на симплификацию кривой 208, 500 могут быть инструкциями пользователя 121, полученными сервером 102 от клиентского устройства 112, которое будет описано подробнее ниже. Инструкции на симплификацию кривой 208, 500 могут быть инструкциями пользовательского устройства 112, полученными сервером 102 от клиентского устройства 112. Например, в ответ на запрос пользователем 121 уменьшения изображения карты, клиентское устройство 112 может отправить на сервер 102 соответствующий запрос на симплификацию частей карты, которые включают в себя кривые линии, чтобы отобразить их в новом масштабе, без мелких деталей, принимая во внимание разрешение экрана 118 клиентского устройства 112. Альтернативно, клиентское устройство 112 может отправлять серверу 102 запрос на простое уменьшение изображения карты, а сервер 102 может интерпретировать такой запрос на простое уменьшение изображения карты как запрос (по меньшей мере частично) на симплификацию кривых линий на карте, например, как часть генерализации карты.
[0059] Машиночитаемые инструкции, сохраненные на носителе 104 информации, при выполнении могут дополнительно инициировать реализацию процессором 108 первого алгоритма симплификации (не изображен) для симплификации кривой 208, 500, таким образом создавая и первую симплифицированную кривую 200, 502, и параметры формы первой симплифицированной кривой 200, 502; причем первая симплифицированная кривая делится на однородные сегменты соответственно на основе параметров формы.
[0060] На Фиг. 2 представлен неограничивающий пример кривой 208, первой симплифицированной кривой 200 и итоговой симплифицированной кривой 210. Первая симплифицированная кривая 200 разделена на три однородных сегмента: первый однородный сегмент 202, второй однородный сегмент 204 и третий однородный сегмент 206. Первая симплифицированная кривая 200 была создана симплификацией кривой 208 и разделена на три однородных сегмента 202, 204, 206 с помощью первого алгоритма (не изображен) симплификации. Итоговая кривая 210 была создана симплификацией первой симплифицированной кривой 200 с использованием соответствующего второго алгоритма (не изображен) симплификации, выбранного для каждого однородного сегмента 202, 204, 206.
[0061] На Фиг. 5 представлен другой неограничивающий пример кривой 500, первой симплифицированной кривой 502 и итоговой симплифицированной кривой 514. Первая симплифицированная кривая 502 разделена на пять однородных сегментов: первый однородный сегмент 504, второй однородный сегмент 506, третий однородный сегмент 508, четвертый однородный сегмент 510 и пятый однородный сегмент 512. Первая симплифицированная кривая 502 была создана симплификацией кривой 500 и разделена на пять однородных сегментов 504, 506, 508, 510, 512 с помощью первого алгоритма (не изображен) симплификации. Итоговая кривая 514 была создана симплификацией первой симплифицированной кривой 502 с использованием соответствующего второго алгоритма (не изображен) симплификации, выбранного для каждого однородного сегмента 504, 506, 508, 510, 512.
[0062] В примерах, изображенных на Фиг. 2 и Фиг. 5 каждый однородный сегмент 202, 204, 206, 504, 506, 508, 510, 512 является ломаной линией, т.е. серией точек и сегментов в виде прямых линий, соединяющих эти точки. Следует учесть, что форма и размер первой симплифицированной кривой 200, 502 и кривых 208, 500 из которых они созданы, как объясняется ниже, никак конкретно не ограничены. Хотя первая симплифицированная кривая 200, 502 показана как разделенная на три однородных сегмента 202, 204, 206 и пять однородных сегментов 504, 506, 508, 510, 512, соответственно, в других вариантах осуществления настоящего технического решения первая симплифицированная кривая 200, 502 может быть разделена на любое другой число однородных сегментов, в зависимости от параметров формы. В некоторых (маловероятных) вариантах осуществления настоящего технического решения, если первая симплифицированная кривая 200, 502 является однородной по всей своей длине, тогда определяется только один однородный сегмент (а не множество однородных сегментов).
[0063] Первый алгоритм симплификации является предварительно определенным и никак конкретно не ограничен. Может быть использован любой подходящий алгоритм для симплификации кривых и создания параметров формы симплифицированных кривых. В некоторых неограничивающих вариантах осуществления настоящего технического решения первый алгоритм симплификации линий выбирается из алгоритмов Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, варианта RDP, алгоритма «подгонки рукавов» (sleeve-fitting (SF)), функции представления (turning function (TF)), алгоритма нумерации точек (N-ной точки), радиального расстояния, алгоритма перпендикулярного расстояния. Первый алгоритм симплификации может быть предварительно определен на основе нескольких критериев, например, типа графического объекта, включающего в себя кривую для симплификации, источника графического объекта, источника, из которого получена инструкция и так далее.
[0064] Машиночитаемые инструкции, сохраненные на носителе 104 информации, при выполнении могут дополнительно инициировать определение процессором 108 множества однородных сегментов 202, 204, 206 первой симплифицированной кривой 200 на основе параметров формы. Следует отметить, что, хотя настоящее техническое решение описывается здесь с учетом варианта осуществления настоящего технического решения, приведенного на Фиг. 2, Фигура 2 является только примером, и то же самое относится к варианту осуществления настоящего технического решения, показанному на Фигуре 5.
[0065] Однородные сегменты обычно (но не обязательно) включают в себя множество сегментов первой симплифицированной кривой 200, причем либо параметры формы во всем множестве сегментов (т.е. на протяжении однородного сегмента) одинаковы, или каждый из множества сегментов имеет одинаковые или по меньшей мере очень близкие параметры формы. Поскольку параметры формы создаются первым алгоритмом симплификации во время создания первой симплифицированной кривой 200, определение однородных сегментов 202, 204, 206 будет различаться в зависимости от того, какой первый алгоритм симплификации был использован. Кроме того, может быть определено любое число однородных сегментов 202, 204, 206 в зависимости от параметров формы. Однородные сегменты 202, 204, 206 в общем случае определяются первым алгоритмом симплификации во время процесса симплификации кривой 208 и создания параметров формы.
[0066] Машиночитаемые инструкции, сохраненные на носителе 104 информации, при выполнении могут дополнительно инициировать симплификацию процессором 108 каждого однородного сегмента 202, 204, 206 с использованием соответствующего второго алгоритма (не изображен) симплификации, таким образом создавая итоговую симплифицированную кривую 210. Второй алгоритм симплификации выбирается из множества предварительно определенных вторых алгоритмов симплификации, причем второй алгоритм симплификации выбирается независимо для каждого однородного сегмента 202, 204 и 206 на основе параметров формы соответствующего однородного сегмента 202, 204, 206. Другими словами, второй алгоритм симплификации для каждого однородного сегмента 202, 204, 206 может быть таким же или другим, в зависимости от параметров формы. Кроме того, первый и второй алгоритмы симплификации могут быть одинаковыми или неодинаковыми в зависимости от параметров формы однородных сегментов 202, 204, 206.
[0067] Как упоминалось выше, используемые параметры формы могут различаться в зависимости от использованного первого алгоритма симплификации для создания первой симплифицированной кривой 200. В некоторых вариантах осуществления настоящего технического решения параметры формы включают одно или несколько из: длина и угол наклона, изогнутость, расстояние высот, перепад высот, полезная площадь для точки, комплексность, монотонность, длина между точками и плотность точек.
[0068] Машиночитаемые инструкции, сохраненные на носителе 104 информации, при исполнении могут дополнительно инициировать дополнительную симплификацию процессором 108 итоговой симплифицированной кривой 210. Процессор 108 повторяет этапы определения множества однородных сегментов в рамках симплифицированных однородных сегментов на итоговой симплифицированной кривой 210 и симплифицирует снова определенные однородные сегменты (не изображены) с использованием третьего алгоритма симплификации. Третий алгоритм симплификации выбирается независимо для каждого из снова определенных однородных сегментов в рамках итоговой симплифицированной кривой 210. Третий алгоритм симплификации выбирается независимо от использованного ранее второго алгоритма симплификации. Таким образом создается вторая итоговая симплифицированная кривая (не изображена). Машиночитаемые инструкции, сохраненные на носителе 104 информации, могут инициировать повторение процессором 108 этих этапов итерационно, пока не будет получен желаемый конечный пункт (например, желаемый порог масштаба, желаемое разрешение, использование выделенной памяти, выделенного времени и так далее). Следует иметь в виду, что n-ная итоговая симплифицированная кривая будет создана на каждой n-ной итерации.
[0069] Машиночитаемые инструкции, сохраненные на носителе 104 информации, при выполнении могут дополнительно инициировать отправку процессором 108 на клиентское устройство 112 инструкции на отображение итоговой симплифицированной кривой 210 (или второй итоговой симплифицированной кривой, или n-ной итоговой симплифицированной кривой (не изображена), в зависимости от того, сколько итераций было завершено) на экране 118. Инструкция может быть отправлена по сети 110 передачи данных. В некоторых вариантах осуществления настоящего технического решения инструкция на отображение итоговой симплифицированной кривой 210 (или n-ной итоговой симплифицированной кривой) на экране 118 может включать в себя инструкцию на масштабирование визуального представления кривой 208, таким образом, чтобы итоговая симплифицированная кривая 210 выглядела больше или меньше.
[0070] В некоторых вариантах осуществления настоящего технического решения процессор 108 отправляет инструкции движку отрисовки (не изображен), на отображение итоговой симплифицированной кривой 210 (или n-ной итоговой симплифицированной кривой (не изображена)) на экране 118. Движок отрисовки - это программное обеспечение, которое отображает отформатированное содержимое на экране, сочетая информацию содержимого и форматирования для отрисовки в области содержимого в окне, которое отображается на экране. Движок отрисовки может быть браузерным движком отрисовки, т.е. он может быть встроен в веб-браузер или другое приложение, которое требует отображения графического содержимого. Альтернативно, движок отрисовки может быть общим движком отрисовки, т.е. частью операционной системы (не изображена) сервера 102 или клиентского устройства 112.
[0071] Система 100 также включает в себя компьютерное устройство 112, являющееся клиентским устройством 112. Клиентское устройство 112 обычно связано с пользователем 121. Следует отметить, что тот факт, что клиентское устройство 112 связано с пользователем 121, не подразумевает какого-либо конкретного режима работы, равно как и необходимости входа в систему, регистрации, или чего-либо подобного.
[0072] Варианты реализации клиентского устройства 112 конкретно не ограничены, но в качестве примера клиентского устройства 112 могут использоваться персональные компьютеры (настольные компьютеры, ноутбуки, нетбуки и т.п.) или беспроводные устройства передачи данных (смартфоны, планшеты и т.п.).
[0073] Клиентское устройство 112 включает в себя устройство 113 пользовательского ввода. Реализация устройства 113 пользовательского ввода не ограничена и будет зависеть от того, какое клиентское устройство 112 используется. Устройство 113 пользовательского ввода может включать в себя любой механизм предоставления пользовательского ввода процессору 116 клиентского устройства 112. Устройство 113 пользовательского ввода может являться клавиатурой и/или мышью и так далее. Устройство 113 ввода не ограничивается любым конкретным способом ввода, но может быть исполнено, например, как виртуальная кнопка на сенсорном экране или как физическая кнопка на корпусе электронного устройства.
[0074] Исключительно как пример и без введения ограничений, в тех вариантах осуществления настоящего технического решения, в которых клиентское устройство 112 реализовано как беспроводное устройство передачи данных (например, смартфон), устройство 113 пользовательского ввода может быть выполнено как устройство пользовательского ввода на основе интерференции света. Устройство 113 пользовательского ввода в одном примере является устройством восприятия движения пальца/объекта, которым пользователь осуществляет жест и/или на которое нажимает пальцем. Устройство 113 пользовательского ввода может идентифицировать/отслеживать жест и/или определять положение пальца пользователя на устройстве 113 пользовательского ввода. В примерах, в которых устройство 113 пользовательского ввода выполнено как устройство на основе интерференции света, например, сенсорный экран или мультисенсорный экран, устройство 113 пользовательского ввода может дополнительно выполнять функции устройства экрана 118.
[0075] Устройство 113 пользовательского ввода функционально подключено к процессору 116 и передает сигналы ввода (и сигналы вывода, когда оно функционирует и как экран 118) на основе различных форм пользовательского ввода для обработки и анализа процессором 116.
[0076] Клиентское устройство 112 дополнительно включает в себя используемый компьютером носитель 114 информации, также упоминаемый как локальная память 114. Локальная память 114 может включать в себя любой тип медиа, включая (но не ограничиваясь) ОЗУ, ПЗУ, диски (компакт диски, DVD-диски, дискеты, жесткие диски и т.д.), твердотельные накопители, накопители на магнитной ленте и т.д. В общем случае задачей локальной памяти 114 является хранение машиночитаемых команд, а также других данных.
[0077] Клиентское устройство 112 включает в себя экран 118. Экран 118 может быть жидкокристаллическим дисплеем (LCD), светодиодным дисплеем (LED), дисплеем на основе интерферометрической модуляции (IMOD) или дисплеем на основе любой другой подходящей технологии. Экран 118 в общем случае выполнен с возможностью отображать графический интерфейс пользователя (GUI), который предоставляет простой в использовании графический интерфейс между пользователем 121 клиентского устройства 112 и операционной системой или приложением(ями), установленными на клиентском устройстве 112. В общем случае графический интерфейс пользователя (GUI) представляет программы, файлы и операционные опции с помощью графических изображений. Экран 118 также в общем случае выполнен с возможностью отображать другую информацию, например, пользовательские данные и веб-ресурсы. Экран 118 может быть реализован как устройство на основе сенсорной модели, например, сенсорный экран. Сенсорный экран является экраном, который определяет наличие и местоположение касаний пользователя. Экран 118 может быть экраном мультисенсорной или дуальной сенсорной модели, которые могут определять наличие, местоположение и движение ввода прикосновениями. В примерах, в которых экран 118 выполнен как устройство на основе сенсорной модели, например, сенсорный экран, или мультисенсорный экран, экран 118 может выполнять функции устройства 113 пользовательского ввода.
[0078] Экран 118 функционально соединен с процессором 116 и получает от него сигналы. В примерах, в которых экран 118 выполнен как устройство на основе сенсорной модели, например, сенсорный экран, или мультисенсорный экран, экран 118 может также передавать сигналы ввода на основе различных форм пользовательского ввода для обработки и анализа процессором 116.
[0079] Клиентское устройство 112 также включает в себя вышеупомянутый процессор 116. Процессор 116 выполнен с возможностью реализовать различные операции в соответствии с машиночитаемым программным кодом. Процессор 116 функционально связан с устройством 113 пользовательского ввода, локальной памятью 114 и экраном 118. Процессор 116 выполнен с возможностью сохранять или иметь доступ к машиночитаемым командам, выполнение которых инициирует реализацию процессором 116 различных процедур. В качестве неограничивающих примеров, процессор 116, описанный здесь, может получить доступ к машиночитаемым инструкциям, которые при выполнении могут инициировать реализацию процессором 116: отображения информации на экране 118; получения от пользователя 121 клиентского устройства 112 с помощью устройства 113 пользовательского ввода выборки по меньшей мере некоторой отображенной информации; отправку клиентским устройством 112 на сервер 102 по сети 110 передачи данных выбранной пользователем информации; получения клиентским устройством 112 от сервера 102 веб-содержимого и других данных, включая карты, представления графических объектов (например, видео) и других данных для отображения на экране 118 клиентского устройства 112; отображения на экране 118 одного или нескольких графических объектов, включая графические объекты с симплифицированными кривыми.
[0080] Локальная память 114 выполнена с возможностью хранить данные, включая машиночитаемые инструкции и другие данные, включая данные графических объектов (например, картографические данные и т.д.). В некоторых вариантах осуществления настоящего технического решения локальная память 114 может хранить по меньшей мере часть данных в базе данных (не изображена). В других вариантах осуществления настоящего технического решения локальная память 114 может хранить по меньшей мере часть данных в любом наборе данных (не изображен), который отличается от базы данных.
[0081] Данные, сохраненные в локальной памяти 114 (и, более конкретно, по меньшей мере частично, в некоторых вариантах осуществления настоящего технического решения, в базе данных) могут включать в себя графические объекты любого типа.
[0082] Локальная память 114 может хранить машиночитаемые инструкции, которые управляют обновлениями, заполнением и модификациям базы данных (не изображена) и/или другими наборами данных (не изображены). Более конкретно, машиночитаемые инструкции, хранящиеся в локальной памяти 114, могут позволить клиентскому устройству 112 получить (или например, обновить) информацию относительно графических объектов по сети 110 передачи данных и сохранить информацию о графических объектах, включая информацию об их симплифицированных кривых в базе данных и/или других наборов данных.
[0083] Машиночитаемые инструкции, сохраненные в локальной памяти 114, при исполнении могут инициировать получение процессором 116 инструкций на симплификацию кривой (не изображена). Инструкции на симплификацию кривой могут быть получены при выполнении инструкций пользователя 121, полученных клиентским устройством 112, с помощью устройства 113 пользовательского ввода. Например, в ответ на запрос пользователя 121 уменьшить изображение карты, клиентское устройство 112 может отправить на сервер 102 соответствующий запрос на симплификацию кривой на карте.
[0084] В некоторых вариантах осуществления настоящего технического решения инструкция на симплификацию кривой может быть выполнена на сервере 102, и клиентское устройство 112 передает инструкции на сервер 102. Кроме того, машиночитаемые инструкции, сохраненные в локальной памяти 114, при исполнении могут инициировать получение процессором 116 от сервера 102, в результате обработки сервером 102, инструкции на отображение итоговой симплифицированной кривой на экране 118. Инструкции на отображение итоговой симплифицированной кривой на экране 118 могут быть получены от сервера 102 по сети 110 передачи данных. В некоторых вариантах осуществления настоящего технического решения инструкция на отображение итоговой симплифицированной кривой на экране 118 клиентского устройства 112 может включать в себя инструкцию на масштабирование визуального представления итоговой симплифицированной кривой.
[0085] В альтернативных вариантах осуществления настоящего технического решения инструкция на симплификацию кривой может быть выполнена локально на клиентском устройстве 112 без соединения с сервером 102.
[0086] Более конкретно, машиночитаемые инструкции, сохраненные в локальной памяти 114, при исполнении могут инициировать получение процессором 116 инструкций на симплификацию кривой. В некоторых вариантах осуществления настоящего технического решения инструкция на симплификацию кривой может быть инструкциями пользователя 121, введенными с помощью устройства 113 пользовательского ввода. Например, в ответ на запрос пользователя 121 уменьшить изображение карты, клиентское устройство 112 может получать инструкцию на симплификацию кривой на карте.
[0087] Машиночитаемые инструкции, сохраненные в локальной памяти 114, при выполнении могут дополнительно инициировать реализацию процессором 116 первого алгоритма симплификации (не изображен) для симплификации кривой 208, 500, таким образом создавая и первую симплифицированную кривую 200, 502, и параметры формы первой симплифицированной кривой 200, 502. Как описано выше, первый алгоритм симплификации предварительно определен.
[0088] Машиночитаемые инструкции, сохраненные в локальной памяти 114, при выполнении могут дополнительно инициировать определение процессором 116 множества однородных сегментов 202, 204, 206 первой симплифицированной кривой 200 (или однородных сегментов 504, 506, 508, 510, 512 первой симплифицированной кривой 502) на основе параметров формы, как было описано выше.
[0089] Машиночитаемые инструкции, сохраненные в локальной памяти 114, при выполнении могут дополнительно инициировать симплификацию процессором 116 каждого однородного сегмента 202, 204, 206 с использованием соответствующего второго алгоритма (не изображен) симплификации, таким образом создавая итоговую симплифицированную кривую 210. Как упоминалось выше, настоящее техническое решение описывается здесь с учетом Фиг. 2 исключительно с иллюстративными целями. Фиг. 2 не должна рассматриваться как ограничение, и описание с равным успехом применимо к другим вариантам осуществления настоящего технического решения, включая тот, что изображен на Фиг. 5.
[0090] Соответствующий второй алгоритм симплификации выбирается из множества предварительно определенных вторых алгоритмов симплификации, причем второй алгоритм симплификации выбирается независимо для каждого однородного сегмента 202, 204 и 206 на основе параметров формы соответствующего однородного сегмента 202, 204, 206. Другими словами, второй алгоритм симплификации для каждого однородного сегмента 202, 204, 206 может быть таким же или другим, в зависимости от параметров формы. Кроме того, первый и второй алгоритмы симплификации могут быть одинаковыми или неодинаковыми в зависимости от параметров формы.
[0091] Машиночитаемые инструкции, сохраненные в локальной памяти 114, при исполнении могут дополнительно инициировать дополнительную симплификацию процессором 116 итоговой симплифицированной кривой 210. Процессор 116 повторяет этапы определения множества однородных сегментов в рамках симплифицированных однородных сегментов на итоговой симплифицированной кривой 210 и симплифицирует снова определенные однородные сегменты (не изображены) с использованием третьего алгоритма симплификации. Третий алгоритм симплификации выбирается независимо для каждого из снова определенных однородных сегментов в рамках итоговой симплифицированной кривой 210. Этот третий алгоритм симплификации выбирается независимо от использованного ранее второго алгоритма симплификации. Таким образом создается вторая итоговая симплифицированная кривая (не изображена). Машиночитаемые инструкции, сохраненные в локальной памяти 114, могут инициировать повторение процессором 116 этих этапов итерационно, симплифицируя далее вторую итоговую симплифицированную кривую и создавая третью итоговую симплифицированную кривую (не изображена) и т.д., пока не будет получен желаемый конечный пункт (например, желаемый порог масштаба, желаемое разрешение, использование выделенной памяти, выделенного времени и так далее). N-ная итоговая симплифицированная кривая будет создана на каждой n-ной итерации.
[0092] Машиночитаемые инструкции, сохраненные в локальной памяти 114 информации, при выполнении могут дополнительно инициировать отрисовку процессором 116 итоговой симплифицированной кривой 210 (или второй итоговой симплифицированной кривой, или n-ной итоговой симплифицированной кривой и т.д., в зависимости от того, сколько итераций требовалось для достижения конечного пункта) на экране 118. В некоторых вариантах осуществления настоящего технического решения отрисовка итоговой симплифицированной кривой 210 (или n-ной итоговой симплифицированной кривой (не изображена)) на экране 118 является отрисовкой масштабированного визуального представления итоговой симплифицированной кривой 210. В некоторых вариантах осуществления настоящего технического решения инструкция на отображение итоговой симплифицированной кривой 210 (или n-ной итоговой симплифицированной кривой) на экране 118 может включать в себя инструкцию на масштабирование визуального представления кривой 208, таким образом, чтобы итоговая симплифицированная кривая 210 выглядела больше или меньше.
[0093] В некоторых вариантах осуществления настоящего технического решения процессор 116 отправляет инструкции движку отрисовки (не изображен), на отображение итоговой симплифицированной кривой 210 (или n-ной итоговой симплифицированной кривой) на экране 118. Движок отрисовки может быть браузерным движком отрисовки или общим движком отрисовки, т.е. частью операционной системы (не изображена) или клиентского устройства 112.
[0094] Следует отметить, что клиентское устройство 112 соединено с сетью 110 передачи данных через линию 124 передачи данных. В некоторых вариантах осуществления настоящего технического решения, не ограничивающих его объем, сеть 110 передачи данных может представлять собой Интернет. В других вариантах осуществления настоящего технического решения сеть 110 передачи данных может быть реализована иначе - в виде глобальной сети передачи данных, локальной сети передачи данных, частной сети передачи данных и т.п. Клиентское устройство 112 может устанавливать соединения по сети 110 передачи данных с другими устройствами, например, с серверами. Более конкретно, клиентское устройство 112 может устанавливать соединения и взаимодействовать с сервером 102.
[0095] Реализация линии 124 передачи данных не ограничена и будет зависеть от того, какое клиентское устройство 112 используется. В качестве примера, но не ограничения, в данных вариантах осуществления настоящего технического решения в случаях, когда клиентское устройство 112 представляет собой беспроводное устройство связи (например, смартфон), линия 124 передачи данных представляет собой беспроводную сеть передачи данных (например, среди прочего, линия передачи данных 3G, линия передачи данных 4G, беспроводной интернет Wireless Fidelity или коротко WiFi®, Bluetooth® и т.п.). В тех примерах, где клиентское устройство 112 представляет собой портативный компьютер, линия 124 передачи данных может быть как беспроводной (беспроводной интернет Wireless Fidelity или коротко WiFi®, Bluetooth® и т.п) так и проводной (соединение на основе сети Ethernet).
[0096] Важно иметь в виду, что варианты реализации клиентского устройства 112, линии 124 передачи данных и сети 110 передачи данных приведены исключительно для наглядности. Таким образом, специалисты в данной области техники смогут понять подробности других конкретных вариантов осуществления клиентского устройства 112, линии 124 передачи данных и сети 110 передачи данных. То есть, представленные здесь примеры не ограничивают объем настоящего технического решения.
[0097] На Фиг. 3 представлен компьютерный способ 300 симплификации кривой, способ выполняется на компьютерном устройстве 102, 112 системы 100 с Фиг. 1.
[0098] Этап 302 - получение инструкции на симплификацию кривой
[0099] Способ 300 начинается на этапе 302, на котором компьютерное устройство, в этом варианте осуществления настоящего технического решения являющееся сервером 102, получает инструкцию на симплификацию кривой 208, 500.
[00100] Следует иметь в виду, что, хотя способ 300 описан здесь с учетом варианта осуществления настоящего технического решения, в котором компьютерное устройство является сервером 102, это описание представлено здесь исключительно для примера, и способ 300 может быть выполнен с соответствующими изменениями в других вариантах осуществления настоящего технического решения, в которых компьютерное устройство является клиентским устройством 112.
[00101] Кривая 208, 500 в общем случае определяется множеством координат вершин. Кривая 208, 500 может быть частью графического объекта (не изображен) любой формы, например (без введения ограничений), карты, фотографии, изображения, видео, видеоигры, многоугольного объекта и так далее. Кривая 208, 500 может быть частью двумерного (2D) или трехмерного (3D) графического объекта. Графический объект может быть отрисован в веб-браузере (например, в области содержимого окна), в клиенте электронной почты, в электронной книге или в другом приложении, отображающем графическое содержимое (например, в картографическом приложении). Альтернативно, графический объект может быть отрисован общим движком отрисовки операционной системы компьютерного устройства (например, сервера 102 или клиентского устройства 112).
[00102] В некоторых вариантах осуществления настоящего технического решения кривая 208, 500 является частью пограничной линии или границы (например, граница страны, граница моря, граница земельного владения), нарисованной на карте (не изображена).
[00103] Существует множество ситуаций, в которой может быть получена инструкция на симплификацию кривой 208, 500. Например, симплификация кривых является ключевым этапом генерализации карт; линии - наиболее распространенный элемент в картографии. Инструкция на симплификацию кривой 208, 500 может, следовательно, быть получена как часть инструкции на масштабирование части карты. В других вариантах осуществления настоящего технического решения инструкция на симплификацию кривой 208, 500 может быть получена как часть инструкции на отображение объекта (например, замка, лодки, дракона и т.д.) в видеоигре или в иллюстрации. В других вариантах осуществления настоящего технического решения инструкция на симплификацию кривой 208, 500 может быть получена как часть инструкции на уменьшение размера изображения для загрузки на электронное устройство или с электронного устройства или для сохранения, или для уменьшения плотности данных графических объектов компьютерной мультипликации. В других вариантах осуществления настоящего технического решения инструкция на симплификацию кривой 208, 500 может быть получена как часть инструкции на редактуру изображения или видео, или для 3D-редактирования. В других вариантах осуществления настоящего технического решения инструкция на симплификацию кривой 208, 500 может быть получена как часть инструкции на преобразование исходных данных, чтобы уменьшить объем данных, или для более компактного хранения данных, или для слияния разномасштабных баз данных. Возможно множество других вариантов осуществления настоящего технического решения. Следует понимать, что контекст, в котором происходит получение инструкций на симплификацию кривой 208, 500 никак конкретно не ограничен.
[00104] Кроме того, графические объекты могут иметь различные источники. Например, графические объекты могут быть сканированными изображениями, изображениями, загруженными с удаленного сервера и так далее. В некоторых вариантах осуществления настоящего технического решения данные отрисовки, представляющие графический объект и/или кривую 208, 500, сохраняются на носителе 104 информации, например, в базе данных 106. В альтернативных вариантах осуществления настоящего технического решения данные отрисовки, представляющие графический объект и/или кривую 208, 500 получены (например, загружены) сервером 102 с клиентского устройства 112 по сети 110 передачи данных. В других вариантах осуществления настоящего технического решения данные отрисовки, представляющие графический объект и/или кривую 208, 500 извлечены (например, загружены) с внешнего источника по сети 110 передачи данных.
[00105] В таком варианте осуществления настоящего технического решения сервер 102 запрашивает кривую 208, 500 с внешнего источника (не изображен), который может являться, например, поставщиком картографических данных. В других вариантах осуществления настоящего технического решения источником кривой 208, 500 может являться любой подходящий источник, например, любое устройство, которое оптически сканирует изображения и преобразует их в цифровые изображения. Кроме того, сервер 102 может преобразовать графический объект из растрового формата изображения в векторный формат изображения и наоборот.
[00106] Затем способ 300 переходит к этапу 304.
[00107] Этап 304 - выполнение первого алгоритма симплификации, который предварительно определен, выполнение симплификации кривой и, таким образом, создание первой симплифицированной кривой и параметров формы первой симплифицированной кривой
[00108] Далее, на этапе 304 сервер 102 выполняет первый алгоритм симплификации (не изображен).
[00109] Первый алгоритм симплификации предварительно определен. Следует иметь в виду, что первый алгоритм симплификации никак конкретно не ограничен. Может быть использован любой подходящий алгоритм для симплификации кривых и создания параметров формы симплифицированных кривых. В некоторых неограничивающих вариантах осуществления настоящего технического решения первый алгоритм симплификации линий выбирается из алгоритмов Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, варианта RDP, алгоритма «подгонки рукавов» (sleeve-fitting (SF)), функции представления (turning function (TF)), алгоритма нумерации точек (N-ной точки), радиального расстояния, алгоритма перпендикулярного расстояния. Известны и другие алгоритмы симплификации; они также могут быть использованы как первый алгоритм симплификации. Первый алгоритм симплификации может быть предварительно выбран на основе нескольких критериев, например, типа графического объекта, включающего в себя кривую для симплификации, источника графического объекта, источника, из которого получена инструкция, пригодности конкретного алгоритма для конкретного типа кривой/параметров формы и так далее. Например, алгоритм RDP часто хорошо подходит для работы с кривыми на картах, и может быть выбран для приложения, включающего в себя генерализацию карт. В примерах, показанных на Фиг. 2 и Фиг. 5, алгоритм RDP выбирается как первый алгоритм симплификации, однако, следует понимать, что эти примеры показаны исключительно с иллюстративными целями и не должны рассматриваться как ограничивающие.
[00110] На этапе 304 первый алгоритм симплификации симплифицирует кривую 208, 500, таким образом создавая первую симплифицированную кривую 200, 502, и в то же время создавая параметры формы первой симплифицированной кривой 200, 502. В вариантах осуществления настоящего технического решения, показанных на Фиг. 2 и Фиг. 5, первым алгоритмом симплификации является алгоритм RDP, который выполняется для создания первой симплифицированной кривой 200, 502, а также параметров ее формы. Как будет понятно специалисту в данной области техники создание параметров формы первой симплифицированной кривой 200, 502 является частью способа симплификации, осуществляемого первым алгоритмом симплификации.
[00111] В алгоритме RDP конкретно указано расстояние максимального отклонения dmax (например, 5 км). Первая и последняя точки линии помечаются как «сохранить». Определяется прямой сегмент линии от первой точки P1 до последней точки Pn исходной линии, и происходит проверка точек исходной линии на то, не превосходят ли они максимальное расстояние dmax от сегмента линии. Если какие-то из них превосходят, точка Pi, самая удаленная от сегмента линии, помечается как «сохранить», и такая же операция проводится с частями линии от начала P1 до самой удаленной точки Pi и от самой удаленной точки Pi до конечной точки Pn. Этот процесс проверки, отметки и подразделения применяется рекурсивно, пока исходная линия не делится на части таким образом, что сегменты линии с начала и до конца каждой части находятся не дальше, чем расстояние максимального отклонения dmax, из любой промежуточной точки.
[00112] Другие алгоритмы используют другие способы и могут создавать другие параметры формы. Конкретные созданные параметры формы будут зависеть от того, какой алгоритм симплификации используется как первый алгоритм симплификации. Неограничивающие примеры параметров формы включают в себя длину и угол наклона, изогнутость, расстояние высот, перепад высот, полезную площадь для точки (например, определенную по алгоритму Висвалингема-Уайятта), комплексность, монотонность, длину между точками, среднюю длину сегмента, плотность точек и сочетание перечисленного.
[00113] Затем способ 300 переходит к этапу 306.
[00114] Этап 306 - определение множества однородных сегментов первой симплифицированной кривой на основе параметров формы
[00115] Далее, на этапе 306 определяется множество однородных сегментов 202, 204, 206 первой симплифицированной кривой 200 (или же, если брать в расчет Фиг. 5, однородных сегментов 504, 506, 508, 510, 512 первой симплифицированной кривой 502). Однородные сегменты 202, 204, 206, 504, 506, 508, 510, 512 определяются на основе параметров формы первой симплифицированной кривой 200, 502, причем параметры формы созданы во время симплификации кривой 200, 502, как описано выше. В вариантах осуществления настоящего технического решения, показанных на Фиг. 2 и Фиг. 5, однородные сегменты 202, 204, 206, 504, 506, 508, 510, 512 были определены анализом характеристик вершин (например, расстояние высот, перепад высот, монотонность) первой симплифицированной кривой 200, 502. На основе таких характеристик первая симплифицированная кривая 200 подразделяется на три однородных сегмента 202, 204, 206, причем каждый однородный сегмент 202, 204, 206 представляет часть первой симплифицированной кривой 200, в которой поведение вершин одинаково или очень близко. В примере на Фиг. 2 первый однородный сегмент 202 является сегментом, в котором длина каждого сегмента соответствует высоте линии (в соответствии с параметрами формы, созданными первым алгоритмом симплификации, который в этом примере является алгоритмом RDP). Второй однородный сегмент 204 является другим сегментом первой симплифицированной кривой 200 с плотно расположенными сегментами почти одинаковой высоты. Третий однородный сегмент 206 является немонотонным сегментом первой симплифицированной кривой 200. Аналогично, в примере, показанном на Фиг. 5, было определено пять однородный сегментов 504, 506, 508, 510, 512 на основе характеристик формы.
[00116] Как показано на Фиг. 2 и Фиг. 5, однородные сегменты 202, 204, 206, 504, 506, 508, 510, 512 могут включать в себя множество сегментов первой симплифицированной кривой 200, 502, причем каждый из множества сегментов имеет одинаковые или по меньшей мере крайне близкие параметры формы. Два сегмента в общем случае считаются одинаковыми, если у них один или несколько параметров формы одинаковы или по меньшей мере, очень близки. Как будет понятно специалистам в данной области техники параметры формы, используемые для определения однородности, будут отличаться в зависимости от алгоритма симплификации, используемого для создания параметров формы для данной кривой. Соответственно, множество определенных однородных сегментов также будет различаться в зависимости от использованного алгоритма симплификации.
[00117] В некоторых вариантах осуществления настоящего технического решения множество однородных сегментов определяется первым алгоритмом симплификации, после создания параметров формы первой симплифицированной кривой 200, 502. В альтернативных неограничивающих вариантах осуществления настоящего технического решения множество однородных сегментов определяется другим алгоритмом, например, алгоритмом симплификации, отличающимся от первого алгоритма симплификации, на основе параметров формы первой симплифицированной кривой 200, 502, которые были созданы первым алгоритмом симплификации. Способ, по которому определяется множество однородных сегментов, никак конкретно не ограничен. Известно и может быть использовано на этапе 306 множество таких способов. Например, множество однородных сегментов может быть определено с использованием (без введения ограничений) одного или нескольких: способа удаления точек, способа на основе измерений, способа критических точек, способа геометрического анализа, способа на основе частоты и способа на основе базы знаний (для обзора этих способов см., например, Lopez, F.J.A. and Balboa, J.L.G., Pattern Recognition, vol. 41, pp. 1593-1609, 2008, содержание этой работы включено здесь в полном объеме посредством ссылки).
[00118] Следует отметить, что в некоторых (маловероятных) случаях, если первая симплифицированная кривая 200, 502 является однородной по всей своей длине, тогда определяется только один однородный сегмент (а не множество однородных сегментов). В этом случае способ, тем не менее, переходит к этапу 308, как будто множество однородных точек все же было определено.
[00119] Затем способ 300 переходит к этапу 308.
[00120] Этап 308 - симплификация каждого однородного сегмента с использованием соответствующего второго алгоритма симплификации, который был выбран из множества предварительно определенных вторых алгоритмов симплификации, независимо для каждого однородного сегмента на основе параметров формы соответствующего однородного сегмента; такая симплификация создает итоговую симплифицированную кривую.
[00121] Далее, на этапе 308 сервер 102 переходит ко второму этапу симплификации, на котором каждый симплифицированный однородный сегмент 202, 204, 206, 504, 506, 508, 510, 512 в первой симплифицированной кривой 200, 502 снова симплифицируется с использованием второго алгоритма симплификации (не изображен). Второй алгоритм симплификации выбирается независимо для каждого однородного сегмента 202, 204, 206, 504, 506, 508, 510, 512 на основе параметров формы соответствующего однородного сегмента 202, 204, 206, 504, 506, 508, 510, 512. Как будет понятно специалистам в данной области техники различные алгоритмы симплификации лучше всего подходят для симплификации различных типов кривых, в зависимости от параметров формы конкретной кривой и способа, используемого конкретным алгоритмом для симплификации линий. Вторые алгоритмы симплификации предварительно определены в соответствии с критериями для выбора алгоритма симплификации, подходящего для конкретных параметров формы сегмента линии. Такие критерии для выбора алгоритма симплификации, подходящего для конкретных параметров формы сегмента линии, известны в данной области техники (см., например, Park, W. and Yu, K., Pattern Recognition Letters 32 (2011), pp. 1267-73, содержание этой работы включено здесь в полном объеме посредством ссылки). На этапе 308 второй алгоритм симплификации выбирается из множества предварительно определенных вторых алгоритмов симплификации на основе параметров формы каждого соответствующего однородного сегмента 202, 204, 206, 504, 506, 508, 510, 512, который должен быть симплифицирован. В каждом случае выбирается второй алгоритм симплификации, лучше всего подходящий для конкретных параметров формы конкретного однородного сегмента.
[00122] Множество предварительно определенных вторых алгоритмов симплификации никак конкретно не ограничено. В некоторых неограничивающих вариантах осуществления настоящего технического решения множество предварительно определенных вторых алгоритмов симплификации включает в себя один или несколько из следующих алгоритмов: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, вариант RDP, алгоритм «подгонки рукавов» (sleeve-fitting (SF)), функция представления (turning function (TF)), алгоритм нумерации точек (N-ной точки), радиальное расстояние, алгоритм перпендикулярного расстояния. Известны и другие алгоритмы; они также могут быть использованы.
[00123] Второй алгоритм симплификации может быть, а может и не быть таким же, что и первый алгоритм симплификации, в зависимости от параметров формы соответствующего однородного сегмента 202, 204, 206, 504, 506, 508, 510, 512.
[00124] Например, в иллюстрации, приведенной на Фиг. 2, первый однородный сегмент 202 лучше всего подходит для симплификации с помощью алгоритма RDP. Соответственно, в этом примере первый однородный сегмент 202 симплифицируется на этапе 308 с помощью алгоритма RDP. Напротив, второй однородный сегмент 204 лучше всего подходит для алгоритма Рейманна-Уиткема. Соответственно, в этом примере второй однородный сегмент 204 симплифицируется на этапе 308 с помощью алгоритма Рейманна-Уиткема. Третий однородный сегмент 206 лучше всего подходит для симплификации с помощью алгоритма Опхайма, и соответственно, в этом примере, третий однородный сегмент 206 симплифицируется на этапе 308 с помощью алгоритма Опхайма. Следует иметь в виду, что возможно множество других вариантов этого способа, в зависимости от параметров формы однородных сегментов и характеристик доступных алгоритмов симплификации.
[00125] Аналогично, в иллюстрации, приведенной на Фиг. 5, однородные сегменты 504 и 512 лучше всего подходит для симплификации с помощью алгоритма RDP. Соответственно, в этом примере однородные сегменты 504 и 512 симплифицируются на этапе 308 с помощью алгоритма RDP. Напротив, однородные сегменты 506 и 510 лучше всего подходят для симплификации с помощью алгоритма Висвалингема-Уайятта. Соответственно, в этом примере однородные сегменты 506 и 510 симплифицируются на этапе 308 с помощью алгоритма Висвалингема-Уайятта. Оставшийся однородный сегмент 508 лучше всего подходит для симплификации с помощью алгоритма Опхайма, и соответственно, в этом примере, однородный сегмент 508 симплифицируется на этапе 308 с помощью алгоритма Опхайма. Следует иметь в виду, что возможно множество других вариантов этого способа, в зависимости от параметров формы однородных сегментов и характеристик доступных алгоритмов симплификации.
[00126] В некоторых вариантах осуществления настоящего технического решения, когда компьютерное устройство является сервером 102 (как в варианте осуществления настоящего технического решения, изображенном здесь), способ 300 может дополнительно включать в себя этап (не изображен) отправки на клиентское устройство 112 инструкции на отображение итоговой симплифицированной кривой 210, 514 на экране 118 клиентского устройства 112. В некоторых вариантах осуществления настоящего технического решения инструкция на отображение итоговой симплифицированной кривой 210, 514 на экране 118 клиентского устройства 112 включает в себя инструкцию на масштабирование визуального представления кривой 208, 500. Например, инструкция отобразить итоговую симплифицированную кривую 210, 514 на экране 118 клиентского устройства 112 может быть частью инструкции на масштабирование части карты. В таком случае инструкции, полученные на этапе 302, могут также быть частью инструкции на масштабирование части карты. В альтернативном варианте осуществления настоящего технического решения инструкция на отображение итоговой симплифицированной кривой 210, 514 на клиентском устройстве 112 может быть частью инструкции на отображение фотографии, причем файл, включающий в себя фотографию, был уменьшен в размере, чтобы уменьшить пространство памяти, занимаемое фотографией. В таком случае инструкции, полученные на этапе 302, могут также быть частью инструкции на уменьшение размера файла с фотографией.
[00127] В альтернативных вариантах осуществления настоящего технического решения, когда компьютерное устройство является клиентским устройством 112, способ 300 может дополнительно включать в себя этап (не изображен) отрисовки итоговой симплифицированной кривой 210, 514 на экране 118 клиентского устройства 112. В некоторых вариантах осуществления настоящего технического решения отрисовка итоговой симплифицированной кривой 210, 514 на экране 118 клиентского устройства 112 включает в себя масштабирование визуального представления кривой 208, 500. В некоторых вариантах осуществления настоящего технического решения итоговая симплифицированная кривая 210, 514 отрисована на экране 118 с помощью движка отрисовки (не изображен), например, браузерного движка отрисовки или общего движка отрисовки, который является частью операционной системы (не изображена) сервера 102 или клиентского устройства 112.
[00128] В некоторых вариантах осуществления настоящего технического решения способ 300 завершается после этапа 308. Например, если желаемый конечный пункт был достигнут, то способ 300 завершается после этапа 308. Желаемый конечный пункт может являться (не вводя ограничений) одним или несколькими пунктами из: желаемый порог масштабирования, желаемое разрешение, использование выделенной памяти, использование выделенного времени. Например, когда получена инструкция на масштабирование части карты, а кривая 208, 500 является пограничной линией на части карты, то, если был достигнут желаемый порог масштабирования после этапа 308, способ 300 завершается. В некоторых вариантах осуществления настоящего технического решения способ 300 завершается в этом случае после отрисовки итоговой симплифицированной кривой 210, 514 (как части масштабированной области карты) на экране 118 клиентского устройства 112.
[00129] Однако в альтернативных вариантах осуществления настоящего технического решения желаемый конечный пункт может не быть достигнут после этапа 308. В этом случае требуется дальнейшая симплификация итоговой симплифицированной кривой 210, 514, и способ 300 продолжается на этапах 402, 404 способа 400, на котором каждый симплифицированный однородный сегмент (не изображен) в составе итоговой симплифицированной кривой 210, 514 подвергается дальнейшей симплификации.
[00130] На Фиг. 4 представлен компьютерный способ 400, который выполняется на компьютерном устройстве 102, 112 системы 100 с Фиг. 1. Способ 400 является опциональным расширением способа 300, в котором практически повторяются этапы 306 и 308 для каждого симплифицированного однородного сегмента итоговой симплифицированной кривой 210, 514.
[00131] Способ 400 начинается на этапе 402.
[00132] Этап 402 - для каждого симплифицированного однородного сегмента итоговой симплифицированной кривой определение второго множества вторых однородных сегментов симплифицированного однородного сегмента на основе параметров формы симплифицированного однородного сегмента, причем параметры формы симплифицированного однородного сегмента были созданы соответствующим вторым алгоритмом симплификации
[00133] На этапе 402 определяется второе множество вторых однородных сегментов для каждого симплифицированного однородного сегмента итоговой симплифицированной кривой 210, 514 на основе соответствующих параметров его формы. Следует понимать, что, как было описано выше относительно первого алгоритма симплификации и этапа 304, на этапе 308 второй алгоритм симплификации симплифицировал каждый однородный сегмент 202, 204, 206, 504, 506, 508, 510, 512 и, в то же время, создал параметры формы симплифицированных однородных сегментов (не изображены). Как будет понятно специалисту в данной области техники, создание параметров формы симплифицированных однородных сегментов является частью способа симплификации, осуществляемого вторым алгоритмом симплификации на этапе 308 во время создания итоговой симплифицированной кривой 210, 514. В некоторых вариантах осуществления настоящего технического решения определение второго множества вторых однородных сегментов (не изображены) также является частью способа симплификации, осуществленного вторым алгоритмом симплификации на этапе 308 во время создания итоговой симплифицированной кривой 210, 514.
[00134] На этапе 402, как на этапе 306, описанном выше, определяется второе множество вторых однородных сегментов каждого симплифицированного однородного сегмента на основе параметров формы. Соответствующее описание, сделанное для этапа 306, применимо для этапа 402 и не будет здесь приводиться, чтобы избежать повторения.
[00135] Способ 400 далее переходит к выполнению этапа 404.
[00136] Этап 404 - симплификация каждого второго однородного сегмента с использованием соответствующего третьего алгоритма симплификации, который был выбран из множества предварительно определенных третьих алгоритмов симплификации, независимо для каждого второго однородного сегмента на основе параметров формы соответствующего второго однородного сегмента; такая симплификация создает вторую итоговую симплифицированную кривую
[00137] На этапе 404 каждый второй однородный сегмент итоговой симплифицированной кривой 210, 514 симплифицирован с использованием соответствующего третьего алгоритма (не изображен) симплификации, выбранном независимо для каждого второго однородного сегмента (не изображен) на основе соответствующих параметров его формы. Соответствующее описание этапа 308 и второго алгоритма симплификации, приведенное выше, применимо к этапу 404, и не будет здесь приводиться, чтобы избежать повторения.
[00138] Способ 400 может повторяться по мере необходимости или желания, пока не будет достигнут желаемый конечный пункт. Например, если желаемый конечный пункт достигнут, способ 400 завершается после этапа 404, на котором произошло создание второй итоговой кривой (не изображена). Например, когда получена инструкция на масштабирование части карты, а кривая 208, 500 является пограничной линией на части карты, то, если был достигнут желаемый порог масштабирования после этапа 404, способ 400 завершается. В некоторых вариантах осуществления настоящего технического решения способ 400 завершается в этом случае после отрисовки второй итоговой симплифицированной кривой (как части масштабированной области карты) (не изображена) на экране 118 клиентского устройства 112.
[00139] Однако, если желаемый конечный пункт не был достигнут, способ 400 может повторяться, пока не будет достигнут желаемый конечный пункт. В таких вариантах осуществления настоящего технического решения способ, следовательно, является рекурсивным, с постоянно повторяемым определением и симплификацией однородных сегментов n-ной итоговой симплифицированной кривой до достижения желаемого конечного пункта. На каждой итерации алгоритм симплификации независимо выбирается для каждого соответствующего однородного сегмента на основе параметров его формы. Следует понимать, что на каждой итерации алгоритм симплификации также выбирается независимо от алгоритма симплификации, используемого на предыдущих итерациях. Таким образом, алгоритм симплификации, используемый на каждой последующей итерации, может быть таким же алгоритмом симплификации, используемым на предыдущих итерациях для сегмента, а может и не быть таким же; в любом случае алгоритм симплификации выбирается на основе параметров формы сегмента, с использованием предварительно определенных критериев, как было описано выше.
[00140] Кроме того, в каждом случае, когда желаемый конечный пункт был достигнут, способ может также включать в себя этап отображения n-ной итоговой симплифицированной кривой на экране 118 клиентского устройства 112.
[00141] Некоторые из описанных выше этапов, а также передача-получение сигнала хорошо известны в данной области техники и поэтому для упрощения были опущены в конкретных частях данного описания. Сигналы могут быть переданы/получены с помощью оптических средств (например, оптоволоконного соединения), электронных средств (например, проводного или беспроводного соединения) и механических средств (например, на основе давления, температуры или другого подходящего параметра).
[00142] Некоторые технические эффекты неограничивающих вариантов осуществления настоящего технического решения могут включать предоставление пользователю быстроисполнимого, эффективного и/или рекурсивного способа симплификации кривой. В некоторых вариантах осуществления настоящего технического решения, настоящее техническое решение позволяет выбирать лучше всего подходящий алгоритм симплификации сегмента линии после выполнения выбранного по умолчанию алгоритма симплификации. Сегменты, определенные первым алгоритмом симплификации анализируются для определения того, какой из предварительно определенного множества вторых алгоритмов симплификации лучше всего подходит для конкретного сегмента, после чего происходит симплификация этого сегмента с помощью выбранного второго алгоритма симплификации. В некоторых вариантах осуществления настоящего технического решения способ является рекурсивным, и на каждой итерации для симплификации сегмента может быть использован другой алгоритм симплификации, в зависимости от параметров его формы и того, какой алгоритм лучше всего подходит для этих параметров формы. В некоторых вариантах осуществления настоящего технического решения не требуется дополнительная сегментация или аналитические этапы, которые предваряют симплификацию.
[00143] Модификации и улучшения вышеописанных вариантов осуществления настоящего технического решения будут ясны специалистам в данной области техники. Предшествующее описание представлено только в качестве примера и не несет никаких ограничений. Таким образом, объем настоящего технического решения ограничен только объемом прилагаемой формулы изобретения.
[00144] Таким образом, с некоторой точки зрения, варианты осуществления настоящего технического решения можно изложить следующим образом, структурированно, пронумерованными пунктами:
[00145] ПУНКТ 1. Способ симплификации кривой (208, 500), выполняемый на компьютерном устройстве (102, 112) и включающий в себя этапы:
[00146] а) получения инструкций на симплификацию кривой (208, 500);
[00147] б) выполнения первого алгоритма симплификации, который был предварительно определен, причем выполнение первого алгоритма симплификации симплифицирует кривую (208, 500) и, таким образом, создает первую симплифицированную кривую (200, 502) и параметры формы первой симплифицированной кривой (200, 502);
[00148] в) определения множества однородных сегментов (202, 204, 206, 504, 506, 508, 510, 512) первой симплифицированной кривой (200, 502) на основе параметров формы; и
[00149] г) симплификации каждого однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512) с использованием соответствующего второго алгоритма симплификации, который был выбран из множества предварительно определенных вторых алгоритмов симплификации, независимо для каждого однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512) на основе параметров формы соответствующего однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512); такая симплификация создает итоговую симплифицированную кривую.
[00150] ПУНКТ 2. Способ по п. 1, в котором первый алгоритм симплификации выбирается из алгоритмов Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, варианта RDP, алгоритма «подгонки рукавов» (sleeve-fitting (SF)), функции представления (turning function (TF)), алгоритма нумерации точек (N-ной точки), радиального расстояния, алгоритма перпендикулярного расстояния.
[00151] ПУНКТ 3. Способ по п. 1 или 2, в котором множество предварительно определенных вторых алгоритмов симплификации включает в себя один или несколько из следующих алгоритмов: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, вариант RDP, алгоритм «подгонки рукавов» (sleeve-fitting (SF)), функция представления (turning function (TF)), алгоритм нумерации точек (N-ной точки), радиальное расстояние, алгоритм перпендикулярного расстояния.
[00152] ПУНКТ 4. Способ по любому из пп. 1-3, дополнительно включающий в себя:
[00153] д) определение для каждого однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512) итоговой симплифицированной кривой второго множества вторых однородных сегментов симплифицированного однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512) на основе параметров формы симплифицированного однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512), причем эти параметры были созданы соответствующим вторым алгоритмом симплификации на этапе г); и
[00154] е) симплификация каждого второго однородного сегмента с использованием соответствующего третьего алгоритма симплификации, который выбран из множества предварительно определенных третьих алгоритмов симплификации независимо для каждого второго однородного сегмента на основе параметров формы соответствующего второго однородного сегмента; таким образом происходит создание второй итоговой симплифицированной кривой.
[00155] ПУНКТ 5. Способ по п. 4, в котором множество предварительно определенных третьих алгоритмов симплификации включает в себя один или несколько из следующих алгоритмов: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, вариант RDP, алгоритм «подгонки рукавов» (sleeve-fitting (SF)), функция представления (turning function (TF)), алгоритм нумерации точек (N-ной точки), радиальное расстояние, алгоритм перпендикулярного расстояния.
[00156] ПУНКТ 6. Способ по любому из пп. 1-5, в котором параметры формы включают в себя одно или несколько из: длина и угол наклона, изогнутость, расстояние высот, перепад высот, полезная площадь для точки, комплексность, монотонность, длина между точками и плотность точек.
[00157] ПУНКТ 7. Способ по любому из пп. 1-6, в котором множество однородных сегментов (202, 204, 206, 504, 506, 508, 510, 512) определяется с использованием одного или нескольких: способа удаления точек, способа на основе измерений, способа критических точек, способа геометрического анализа, способа на основе частоты и способа на основе базы знаний.
[00158] ПУНКТ 8. Способ по любому из пп. 1-7, в котором, когда компьютерное устройство является сервером (102), способ дополнительно включает в себя этап отправки на клиентское устройство (112) инструкции на отображение итоговой симплифицированной кривой (210, 514) или второй итоговой симплифицированной кривой на экране (118) клиентского устройства (112).
[00159] ПУНКТ 9. Способ по п. 8, в котором инструкция на отображение итоговой симплифицированной кривой (210, 514) или второй итоговой симплифицированной кривой на экране (118) клиентского устройства (112) включает в себя инструкцию на масштабирование визуального представления кривой (208, 500).
[00160] ПУНКТ 10. Способ по любому из пп. 1-7, в котором компьютерное устройство является клиентским устройством (112), способ дополнительно включает в себя этап отрисовки итоговой симплифицированной кривой (210, 514) или второй итоговой симплифицированной кривой на экране (118) клиентского устройства (112).
[00161] ПУНКТ 11. Способ по п. 10, в котором отображение итоговой симплифицированной кривой (210, 514) или второй итоговой симплифицированной кривой на экране (118) клиентского устройства (112) включает в себя масштабирование визуального представления кривой (208, 500).
[00162] ПУНКТ 12. Способ по любому из пунктов пп. 1-11, в котором кривая (208, 500), итоговая симплифицированная кривая (210, 514), и/или вторая итоговая симплифицированная кривая являются частью карты, фотографии, изображения, видео, или видеоигры.
[00163] ПУНКТ 13. Способ по п. 12, в котором кривая (208, 500), итоговая симплифицированная кривая (210, 514), и/или вторая итоговая симплифицированная кривая являются частью 2D графического объекта или 3D графического объекта.
[00164] ПУНКТ 14. Способ по п. 12, в котором кривая (208, 500), итоговая симплифицированная кривая (210, 514), и/или вторая итоговая симплифицированная кривая отрисовываются браузерным движком отрисовки или общим движком отрисовки.
[00165] ПУНКТ 15. Способ по любому из пп. 4-14, в котором этапы д) и е) повторяются, пока не будут достигнуты один или несколько конечных пунктов: желаемый порог масштабирования, желаемое разрешение, использование выделенной памяти или выделенного времени.
[00166] ПУНКТ 16. Сервер (102), включающий в себя:
[00167] носитель (104) информации;
[00168] процессор (108), функционально соединенный с носителем (104) информации, причем процессор (108) выполнен с возможностью сохранять объекты на носителе (104) информации; процессор (108) также выполнен с возможностью осуществлять:
[00169] а) получение инструкции на симплификацию кривой (208, 500);
[00170] б) выполнение первого алгоритма симплификации, который был предварительно определен, причем выполнение первого алгоритма симплификации симплифицирует кривую (208, 500) и, таким образом, создает первую симплифицированную кривую (200, 502) и параметры формы первой симплифицированной кривой (200, 502);
[00171] в) определение множества однородных сегментов (202, 204, 206, 504, 506, 508, 510, 512) первой симплифицированной кривой (200, 502) на основе параметров формы; и
[00172] г) симплификацию каждого однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512) с использованием соответствующего второго алгоритма симплификации, причем соответствующий второй алгоритм симплификации выбран из множества предварительно определенных вторых алгоритмов симплификации, независимо для каждого однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512) на основе параметров формы соответствующего однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512); таким образом происходит создание итоговой симплифицированной кривой (210, 514).
[00173] ПУНКТ 17. Сервер (102) по п. 16, в котором первый алгоритм симплификации выбирается из алгоритмов Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, варианта RDP, алгоритма «подгонки рукавов» (sleeve-fitting (SF)), функции представления (turning function (TF)), алгоритма нумерации точек (N-ной точки), радиального расстояния, алгоритма перпендикулярного расстояния.
[00174] ПУНКТ 18. Сервер (102) по п. 16 или 17, в котором множество предварительно определенных вторых алгоритмов симплификации включает в себя один или несколько из следующих алгоритмов: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, вариант RDP, алгоритм «подгонки рукавов» (sleeve-fitting (SF)), функция представления (turning function (TF)), алгоритм нумерации точек (N-ной точки), радиальное расстояние, алгоритм перпендикулярного расстояния.
[00175] ПУНКТ 19. Сервер (102) по любому из пп. 16-18, в котором процессор (108) дополнительно выполнен с возможностью осуществлять:
[00176] д) определение для каждого однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512) итоговой симплифицированной кривой (210, 514) второго множества вторых однородных сегментов симплифицированного однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512) на основе параметров формы симплифицированного однородного сегмента (202, 204, 206, 504, 506, 508, 510, 512), причем эти параметры были созданы соответствующим вторым алгоритмом симплификации на этапе г); и
[00177] е) симплификацию каждого второго однородного сегмента с использованием соответствующего третьего алгоритма симплификации, который выбран из множества предварительно определенных третьих алгоритмов симплификации независимо для каждого второго однородного сегмента на основе параметров формы соответствующего второго однородного сегмента; таким образом создание второй итоговой симплифицированной кривой.
[00178] ПУНКТ 20. Сервер (102) по п. 19, в котором множество предварительно определенных третьих алгоритмов симплификации включает в себя один или несколько из следующих алгоритмов: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, вариант RDP, алгоритм «подгонки рукавов» (sleeve-fitting (SF)), функция представления (turning function (TF)), алгоритм нумерации точек (N-ной точки), радиальное расстояние, алгоритм перпендикулярного расстояния.
[00179] ПУНКТ 21. Сервер (102) по любому из пп. 16-20, в котором параметры формы включают в себя одно или несколько из: длина и угол наклона, изогнутость, расстояние высот, перепад высот, полезная площадь для точки, комплексность, монотонность, длина между точками и плотность точек.
[00180] ПУНКТ 22. Сервер (102) по любому из пп. 16-21, в котором множество однородных сегментов (202, 204, 206, 504, 506, 508, 510, 512) определяется с использованием одного или нескольких: способа удаления точек, способа на основе измерений, способа критических точек, способа геометрического анализа, способа на основе частоты и способа на основе базы знаний.
[00181] ПУНКТ 23. Сервер (102) по любому из пп. 16-22, в котором компьютерное устройство является сервером (102), процессор (106) выполнен с дополнительной возможностью отправлять на клиентское устройство (112) инструкцию на отображение итоговой симплифицированной кривой (210, 514) или второй итоговой симплифицированной кривой на экране (118) клиентского устройства (112).
[00182] ПУНКТ 24. Сервер (102) по п. 23, в котором инструкция на отображение итоговой симплифицированной кривой (210, 514) или второй итоговой симплифицированной кривой на экране (118) клиентского устройства (112) включает в себя инструкцию на масштабирование визуального представления кривой (208, 500).
[00183] ПУНКТ 25. Сервер (102) по любому из пп. 16-22, в котором компьютерное устройство является клиентским устройством (112), процессор (116) выполнен с дополнительной возможностью отображать итоговую симплифицированную кривую (210, 514) или вторую итоговую симплифицированную кривую на экране (118) клиентского устройства (112).
[00184] ПУНКТ 26. Сервер (102) по п. 25, в котором отображение итоговой симплифицированной кривой (210, 514) или второй итоговой симплифицированной кривой на экране (118) клиентского устройства (112) включает в себя масштабирование визуального представления кривой (208, 500).
[00185] ПУНКТ 27. Сервер (102) по любому из пунктов пп. 1-26, в котором кривая (208, 500), итоговая симплифицированная кривая (210, 514), и/или вторая итоговая симплифицированная кривая являются частью карты, фотографии, изображения, видео, или видеоигры.
[00186] ПУНКТ 28. Сервер (102) по п. 27, в котором кривая (208, 500), итоговая симплифицированная кривая (210, 514), и/или вторая итоговая симплифицированная кривая являются частью 2D графического объекта или 3D графического объекта.
[00187] ПУНКТ 29. Сервер (102) по п. 27, в котором кривая (208, 500), итоговая симплифицированная кривая (210, 514), и/или вторая итоговая симплифицированная кривая отрисовываются браузерным движком отрисовки или общим движком отрисовки.
[00188] ПУНКТ 30. Сервер (102) по любому из пп. 19-29, в котором процессор (106, 116) выполнен с дополнительной возможностью повторять этапы д) и е), пока не будут достигнуты один или несколько конечных пунктов: желаемый порог масштабирования, желаемое разрешение, использование доступной памяти или выделенного времени.
Изобретение относится к способам и системам симплификации кривой. Технический результат заключается в повышении скорости симплификации кривой. В способе симплификации кривой после получения инструкции на симплификацию кривой выполняется первый, предварительно определенный, алгоритм симплификации для создания первой симплифицированной кривой и параметров формы первой симплифицированной кривой. Определяется множество однородных сегментов первой симплифицированной кривой на основе параметров формы. Каждый однородный сегмент симплифицируется с использованием соответствующего второго алгоритма симплификации для создания итоговой симплифицированной кривой. Второй алгоритм симплификации выбирается из множества предварительно определенных вторых алгоритмов симплификации независимо для каждого однородного сегмента на основе параметров формы соответствующего однородного сегмента. 2 н. и 26 з.п. ф-лы, 5 ил.
1. Способ симплификации кривой, выполняемый на компьютерном устройстве и включающий в себя этапы:
получения инструкций на симплификацию кривой;
выполнения первого алгоритма симплификации, который был предварительно определен, причем выполнение первого алгоритма симплификации симплифицирует кривую и таким образом создает первую симплифицированную кривую и параметры формы первой симплифицированной кривой;
определения множества однородных сегментов первой симплифицированной кривой на основе параметров формы; и
симплификации каждого однородного сегмента с использованием соответствующего второго алгоритма симплификации, который был выбран из множества предварительно определенных вторых алгоритмов симплификации, независимо для каждого однородного сегмента на основе параметров формы соответствующего однородного сегмента; такая симплификация создает итоговую симплифицированную кривую.
2. Способ по п. 1, в котором первый алгоритм симплификации выбирают из алгоритмов Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, варианта RDP, алгоритма «подгонки рукавов» (SF), функции представления (TF), алгоритма нумерации точек (N-ной точки), радиального расстояния, алгоритма перпендикулярного расстояния.
3. Способ по любому из пп. 1-2, в котором множество предварительно определенных вторых алгоритмов симплификации включает в себя один или несколько из следующих алгоритмов: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, вариант RDP, алгоритм «подгонки рукавов» (SF), функция представления (TF), алгоритм нумерации точек (N-ной точки), радиальное расстояние, алгоритм перпендикулярного расстояния.
4. Способ по п. 1, в котором дополнительно выполняют этапы:
определения для каждого симплифицированного однородного сегмента итоговой симплифицированной кривой второго множества вторых однородных сегментов симплифицированного однородного сегмента на основе параметров формы симплифицированного однородного сегмента, причем эти параметры были созданы соответствующим вторым алгоритмом симплификации на этапе симплификации каждого однородного сегмента с использованием соответствующего второго алгоритма симплификации; и
симплификации каждого второго однородного сегмента с использованием соответствующего третьего алгоритма симплификации, который выбран из множества предварительно определенных третьих алгоритмов симплификации независимо для каждого второго однородного сегмента на основе параметров формы соответствующего второго однородного сегмента; таким образом выполняют создание второй итоговой симплифицированной кривой.
5. Способ по п. 4, в котором множество предварительно определенных третьих алгоритмов симплификации включает в себя один или несколько из следующих алгоритмов: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, вариант RDP, алгоритм «подгонки рукавов» (SF), функция представления (TF), алгоритм нумерации точек (N-ной точки), радиальное расстояние, алгоритм перпендикулярного расстояния.
6. Способ по п. 4, в котором этап определения для каждого симплифицированного однородного сегмента итоговой симплифицированной кривой и этап симплификации каждого второго однородного сегмента с использованием соответствующего третьего алгоритма симплификации повторяют, пока не будут достигнуты один или несколько конечных пунктов: желаемый порог масштабирования, желаемое разрешение, использование выделенной памяти или выделенного времени.
7. Способ по п. 1, в котором параметры формы включают в себя одно или несколько из: длина и угол наклона, изогнутость, расстояние высот, перепад высот, полезная площадь для точки, комплексность, монотонность, длина между точками и плотность точек.
8. Способ по п. 1, в котором множество однородных сегментов определяют с использованием одного или нескольких пунктов из списка: способа удаления точек, способа на основе измерений, способа критических точек, способа геометрического анализа, способа на основе частоты и способа на основе базы знаний.
9. Способ по п. 1, в котором компьютерное устройство является сервером, и в котором дополнительно выполняют этап отправки на клиентское устройство инструкции на отображение итоговой симплифицированной кривой на экране клиентского устройства.
10. Способ по п. 9, в котором инструкция на отображение итоговой симплифицированной кривой на экране клиентского устройства включает в себя инструкцию на масштабирование визуального представления кривой.
11. Способ по п. 1, в котором компьютерное устройство является клиентским устройством и в котором дополнительно выполняют этап отрисовки итоговой симплифицированной кривой на экране клиентского устройства.
12. Способ по п. 11, в котором отрисовка итоговой симплифицированной кривой на экране клиентского устройства включает в себя масштабирование визуального представления кривой.
13. Способ по п. 1, в котором кривая является частью: карты, или фотографии, или изображения, или видео, или видеоигры.
14. Способ по п. 13, в котором кривая является частью 2D графического объекта или 3D графического объекта.
15. Способ по п. 13, в котором кривую и/или итоговую симплифицированную кривую отрисовывают браузерным движком отрисовки или графическим движком отрисовки.
16. Сервер для симплификации кривой, включающий в себя:
носитель информации;
процессор, функционально соединенный с носителем информации, причем процессор выполнен с возможностью сохранять объекты на носителе информации; процессор также выполнен с возможностью осуществлять:
получение инструкции на симплификацию кривой;
выполнение первого алгоритма симплификации, который был предварительно определен, причем выполнение первого алгоритма симплификации симплифицирует кривую и таким образом создает первую симплифицированную кривую и параметры формы первой симплифицированной кривой;
определение множества однородных сегментов первой симплифицированной кривой на основе параметров формы; и
симплификацию каждого однородного сегмента с использованием соответствующего второго алгоритма симплификации, который был выбран из множества предварительно определенных вторых алгоритмов симплификации, независимо для каждого однородного сегмента на основе параметров формы соответствующего однородного сегмента; такая симплификация создает итоговую симплифицированную кривую.
17. Сервер по п. 16, в котором процессор дополнительно выполнен с возможностью осуществлять алгоритмы: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, варианта RDP, «подгонки рукавов» (SF), функции представления (TF), нумерации точек (N-ной точки), радиального расстояния, перпендикулярного расстояния.
18. Сервер по п. 16, в котором процессор дополнительно выполнен с возможностью осуществлять:
определение для каждого симплифицированного однородного сегмента итоговой симплифицированной кривой второго множества вторых однородных сегментов симплифицированного однородного сегмента на основе параметров формы симплифицированного однородного сегмента, причем эти параметры были созданы соответствующим вторым алгоритмом симплификации; и
симплификацию каждого второго однородного сегмента с использованием соответствующего третьего алгоритма симплификации, который выбран из множества предварительно определенных третьих алгоритмов симплификации независимо для каждого второго однородного сегмента на основе параметров формы соответствующего второго однородного сегмента; и таким образом создание второй итоговой симплифицированной кривой.
19. Сервер по п. 16, в котором параметры формы включают в себя одно или несколько из: длины и угла наклона, изогнутости, расстояния высот, перепада высот, полезной площади для точки, комплексности, монотонности, длины между точками и плотности точек.
20. Сервер по п. 16, в котором процессор выполнен с дополнительной возможностью осуществлять определение множества однородных сегментов с использованием одного или нескольких пунктов из списка: способ удаления точек, способ на основе измерений, способ критических точек, способ геометрического анализа, способ на основе частоты и способ на основе базы знаний.
21. Сервер по п. 16, в котором компьютерное устройство является сервером и процессор выполнен с дополнительной возможностью отправлять на клиентское устройство инструкцию на отображение итоговой симплифицированной кривой на экране клиентского устройства.
22. Сервер по п. 23, в котором инструкция на отображение итоговой симплифицированной кривой на экране клиентского устройства включает в себя инструкцию на масштабирование визуального представления кривой.
23. Сервер по п. 16, в котором компьютерное устройство является клиентским устройством и процессор выполнен с дополнительной возможностью отрисовывать итоговую симплифицированную кривую на экране клиентского устройства.
24. Сервер по п. 18, в котором процессор дополнительно выполнен с возможностью осуществлять алгоритмы: Рамера-Дугласа-Пекера (RDP), Висвалингема-Уайетта, Чжао-Заальфельда, Лэнга, Рейманна-Уиткема, Опхайма, Рангайяна, варианта RDP, «подгонки рукавов» (SF), функции представления (TF), нумерации точек (N-ной точки), радиального расстояния, перпендикулярного расстояния.
25. Сервер по п. 16, в котором процессор выполнен с дополнительной возможностью получать инструкции для кривой или итоговой симплифицированной кривой, где кривая или итоговая симплифицированная кривая являются частью карты, фотографии, изображения, видео или видеоигры.
26. Сервер по п. 25, в котором процессор выполнен с дополнительной возможностью получать инструкции для кривой или итоговой симплифицированной кривой, где кривая или итоговая симплифицированная кривая являются частью графического объекта 2D или графического объекта 3D.
27. Сервер по п. 25, в котором процессор выполнен с дополнительной возможностью получать инструкции для кривой или итоговой симплифицированной кривой, где кривая или итоговая симплифицированная кривая отрисовываются браузерным движком отрисовки или общим движком отрисовки.
28. Сервер по п. 18, в котором процессор выполнен с дополнительной возможностью повторять этап определения для каждого симплифицированного однородного сегмента итоговой симплифицированной кривой и этап симплификации каждого второго однородного сегмента с использованием соответствующего третьего алгоритма симплификации, пока не будут достигнуты один или несколько конечных пунктов: желаемый порог масштабирования, желаемое разрешение, использование доступной памяти или выделенного времени.
Способ и приспособление для нагревания хлебопекарных камер | 1923 |
|
SU2003A1 |
Пломбировальные щипцы | 1923 |
|
SU2006A1 |
Колосоуборка | 1923 |
|
SU2009A1 |
US 5731820 A, 24.03.1998 | |||
Способ обработки целлюлозных материалов, с целью тонкого измельчения или переведения в коллоидальный раствор | 1923 |
|
SU2005A1 |
СПОСОБ ПРЕОБРАЗОВАНИЯ РАСТРОВОГО ИЗОБРАЖЕНИЯ В МЕТАФАЙЛ | 2011 |
|
RU2469400C1 |
Авторы
Даты
2018-02-01—Публикация
2015-09-02—Подача