СПОСОБ И УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ОБЛАСТЕЙ ИНТЕРЕСА НА ОСНОВЕ ДАННЫХ ГЕОПОЗИЦИОНИРОВАНИЯ
METHOD AND APPARATUS FOR DETERMINING AREAS OF INTEREST BASED ON DATA OF LOCATION

Область техники, к которой относится изобретение
Эта заявка относится к области интернет-технологий и, в частности, к способу и устройству для определения области интереса на основе данных геопозиционирования.
Уровень техники
В наши дни приложения на основе данных геопозиционирования, особенно карты, основанные на данных геопозиционирования, становятся все более популярными.
На практике пользователи могут ожидать нахождение областей интереса на картах. Например, пользователи рассчитывают ходить за покупками, находить развлечение или питаться в областях интереса; и, соответственно, продавцы также рассчитывают открывать магазины в областях интереса. Поэтому согласно этим потребностям пользователей области интереса, как правило, помечаются на картах.
В существующих технологиях области интереса обычно определяются человеком. Однако, эффективность определения областей интереса человеком является относительно низкой, а затраты также являются относительно большими вследствие использования ручного труда.
Сущность изобретения
Эта заявка обеспечивает способ и устройство для определения области интереса на основе данных геопозиционирования, чтобы решать существующую проблему относительно низкой эффективности и относительно больших затрат для определения области интереса.
Согласно варианту осуществления этой заявки, обеспечен способ для определения области интереса на основе данных геопозиционирования, причем способ включает в себя:
нанесение координатной сетки для области на карте, которая должна быть обработана;
для каждого блока в области с нанесенной координатной сеткой подсчет значения блока в течение предварительно заданного интервала, причем значение блока является количеством пользователей, которые сообщают данные геопозиционирования в соответствующем блоке;
выбор значений блоков больше предварительно заданного порогового значения из подсчитанных значений блоков;
определение опорных точек согласно блокам, соответствующим выбранным значениям блоков;
вычисление, согласно опорным точкам и на основе предварительно заданного алгоритма, кривой, охватывающей все опорные точки; и
определение области на кривой в качестве области интереса.
Необязательно, нанесение координатой сетки на область на карте, которая должна быть обработана, в частности, включает в себя:
разделение области на карте, которая должна быть обработана, по меньшей мере, на один блок согласно предварительно заданной длине стороны.
Необязательно, опорная точка является центральной точкой блока.
Необязательно, способ дополнительно включает в себя:
получение типов точек информации (POI) в области на кривой;
получение количеств POI одинаковых типов; и
определение типа точек информации POI наибольшего количества как типа интереса для области интереса.
Необязательно, способ дополнительно включает в себя:
получение точек информации POI в области на карте, после того как опорные точки определяются в блоках, соответствующих выбранным значениям блоков, при этом
вычисление, согласно опорным точкам и на основе предварительно заданного алгоритма, кривой, охватывающей все опорные точки, в частности, содержит:
вычисление, согласно точкам информации POI и опорным точкам и на основе предварительно заданного алгоритма, кривой, охватывающей все опорные точки и точки информации POI.
Необязательно, предварительно заданный алгоритм является алгоритмом выпуклой оболочки; и
кривая является кривой выпуклой оболочки.
Необязательно, алгоритм выпуклой оболочки включает в себя алгоритм Грэхема, алгоритм Джарвиса, метод центра, метод уровня или алгоритм быстрой оболочки.
Согласно варианту осуществления этой заявки предоставляется устройство для определения области интереса на основе данных геопозиционирования, причем устройство включает в себя:
блок обработки для нанесения координатной сетки на область на карте, которая должна быть обработана;
блок подсчета для подсчета значения блока в течение предварительно заданного интервала для каждого блока в области с нанесенной координатной сеткой, значение блока является количеством пользователей, которые сообщают данные геопозиционирования в соответствующем блоке;
блок выбора для выбора значений блоков больше предварительно заданного порогового значения из подсчитанных значений блоков;
первый блок определения для определения опорных точек согласно блокам, соответствующим выбранным значениям блоков;
блок вычисления для вычисления, согласно опорным точкам и на основе предварительно заданного алгоритма, кривой, охватывающей все опорные точки; и
второй блок определения для определения области на кривой в качестве области интереса.
Необязательно, блок обработки предназначен, в частности, для:
разделения области на карте, которая должна быть обработана, по меньшей мере, на один блок согласно предварительно заданной длине стороны.
Необязательно, опорная точка является центральной точкой блока.
Необязательно, устройство дополнительно включает в себя:
субблок получения для получения типов точек информации (POI) в области на кривой;
субблок подсчета для получения количеств POI одинаковых типов; и
субблок определения для определения типа точек информации POI наибольшего количества в качестве типа интереса для области интереса.
Необязательно, устройство дополнительно включает в себя:
субблок получения для получения точек информации POI в области на карте, после того как опорные точки определяются в блоках, соответствующих выбранным значениям блоков, при этом
соответственно, блок вычисления предназначен, в частности, для:
вычисления, согласно точкам информации POI и опорным точкам и на основе предварительно заданного алгоритма, кривой, охватывающей все опорные точки и точки информации POI.
Необязательно, предварительно заданный алгоритм является алгоритмом выпуклой оболочки; и
кривая является кривой выпуклой оболочки.
Необязательно, алгоритм выпуклой оболочки включает в себя алгоритм Грэхема, алгоритм Джарвиса, метод центра, метод уровня или алгоритм быстрой оболочки.
В вариантах осуществления этой заявки на область на карте, которая должна быть обработана, наносится координатная сетка; для каждого блока в области с нанесенной координатной сеткой, значение координатной сетки блока подсчитывается в течение предварительно заданного интервала, причем значение координатной сетки является количеством пользователей, которые сообщают данные геопозиционирования в соответствующем блоке; значения блоков больше предварительно заданного порогового значения выбираются из подсчитанных значений блоков; опорные точки определяются согласно блокам, соответствующим выбранным значениям блоков; кривая, охватывающая все опорные точки, вычисляется согласно опорным точкам и на основе предварительно заданного алгоритма; и область на кривой определяется как область интереса. Таким образом, сервер может автоматически определять области интереса на карте с помощью данных геопозиционирования, фактически сообщенных пользователями, чтобы устранять низкую эффективность и высокие затраты, вызванные ручным разграничением областей интереса, тем самым улучшая эффективность и снижая затраты для определения областей интереса.
Краткое описание чертежей
Фиг. 1 - это блок-схема последовательности операций способа определения области интереса на основе данных геопозиционирования согласно варианту осуществления этой заявки;
Фиг. 2 - это схематичный чертеж области на карте согласно варианту осуществления этой заявки;
Фиг. 3 - это схематичный чертеж, полученный после того, как на область на карте наносится координатная сетка согласно этой заявке;
Фиг. 4 - это схематичный чертеж области на карте, помеченной значениями блоков согласно этой заявке;
Фиг. 5 - это схематичный чертеж выбранных значений блоков согласно этой заявке;
Фиг. 6 - это схематичный чертеж системы координат, установленной согласно этой заявке;
Фиг. 7 - это схематичный чертеж области интереса, определенной согласно опорным точкам согласно этой заявке;
Фиг. 8 - это схематичный чертеж области на карте, показанной на фиг. 2, помеченной точками информации POI;
Фиг. 9 - это схематичный чертеж области интереса, определенной согласно точкам информации POI и опорным точкам согласно этой заявке;
Фиг. 10 - это аппаратная структурная схема оборудования, которое включает в себя устройство для определения области интереса на основе данных геопозиционирования согласно этой заявке; и
Фиг. 11 - это схематичный модульный чертеж устройства для определения области интереса на основе данных геопозиционирования согласно варианту осуществления этой заявки.
Подробное описание изобретения
Примерные варианты осуществления описаны подробно в данном документе, и примеры примерных вариантов осуществления показаны на сопровождающих чертежах. Когда последующие описания соотносятся с сопровождающими чертежами, пока не указано иное, одинаковые номера на различных сопровождающих чертежах представляют одинаковые или аналогичные элементы. Реализации, описанные в последующих примерных вариантах осуществления, не представляют все реализации, согласующиеся с этой заявкой. Напротив, реализации являются просто примерами устройств и способов, которые описываются подробно в прилагаемой формуле изобретения, и которые согласуются с некоторыми аспектами этой заявки.
Термины, используемые в этой заявке, существуют только с целью описания конкретных вариантов осуществления и не предназначены, чтобы ограничивать эту заявку. Формы единственного числа ("a" и "the"), используемые в этой заявке и прилагаемой формуле изобретения, предназначены, чтобы включать в себя также множественные формы, пока контекст явно не указывает иное. Следует дополнительно понимать, что термин "и/или", используемый в этой спецификации, ссылается на и включает в себя любые или все возможные сочетания одного или более ассоциированных перечисленных элементов.
Следует понимать, что, хотя термины, такие как "первый", "второй" и "третий", могут использоваться в этой заявке, чтобы описывать различную информацию, информация не должна быть ограничена этими терминами. Эти термины используются, только чтобы отличать информацию одинакового типа. Например, без отступления от рамок настоящего изобретения, первая информация может также называться второй информацией, и аналогично, вторая информация может называться первой информацией. В зависимости от контекста, слово "если", используемое в данном документе, может быть интерпретировано как "в то время как" или "когда" или "в ответ на определение".
В существующих технологиях области интереса на картах, как правило, получаются посредством ручного разделения. Поскольку ручное разделение обычно легко подвергается влиянию субъективного нанесения на карту, границы полученных, в конечном счете, областей интереса имеют относительно большие погрешности. Например, места, которые не являются областями интереса, могут быть легко помещены в области интереса, или места, которые принадлежат областям интереса, могут не быть помещены в области интереса.
Чтобы решать вышеописанную проблему, фиг. 1 показывает блок-схему последовательности операций способа для определения области интереса на основе данных геопозиционирования согласно варианту осуществления этой заявки. Этот вариант осуществления описывается с позиции сервера, и способ включает в себя следующие этапы.
Этап 110: нанесение координатной сетки на область на карте, которая должна быть обработана.
В этом варианте осуществления область на карте, которая должна быть обработана, может быть выбрана вручную, например, обведена кругом на карте штатным сотрудником.
Область на карте, которая должна быть обработана, может также быть определена сервером согласно списку регионов. Список регионов может быть предварительно задан, и различные регионы включаются в список. Например, регион A, регион B и регион C включаются в список регионов, причем области интереса в регионе A были определены; и сервер может определять, согласно списку, что регион B является областью, которая должна быть обработана. После того как области интереса региона B также были определены, сервер может определять регион C в качестве области, которая должна быть обработана.
Нанесение координатной сетки для области может включать в себя: разделение, посредством сервера, области на карте, которая должна быть обработана, по меньшей мере, на один блок согласно предварительно заданной длине стороны.
Предварительно заданная длина стороны может быть эмпирическим значением, предварительно заданным вручную.
Например, фиг. 2 является схематичным чертежом области на карте согласно этому изобретению. Область на карте имеет длину 1300 метров (м) и ширину 1050 метров (м). Предполагается, что предварительно заданная длина стороны равна 200 м, т.е., область на карте делится на несколько блоков на основе длины стороны, равной 200 м. Фиг. 3 - это схематичный чертеж, полученный после того, как на область карты накладывается координатная сетка. Как показано на фиг. 3, длина стороны каждого блока в области равна 200 м, и, посредством наложения координатной сетки, область на карте может быть разделена на блоки одинакового размера. Как показано на фиг. 3, фрагменты на границах области на карте, имеющие более короткие стороны по сравнению с предварительно заданной длиной стороны, могут не иметь координатной сетки. Альтернативно, фрагменты, имеющие стороны, более короткие по сравнению с предварительно заданной длиной стороны, могут также иметь координатную сетку. Это не ограничивается в данном документе.
В другом варианте осуществления нанесение координатной сетки для области на карте может дополнительно включать в себя: разделение, посредством сервера, области на карте, которая должна быть обработана, на предварительно заданное количество блоков. Предварительно заданное количество может быть эмпирическим значением, предварительно заданным вручную. Например, область на карте делится на 100 блоков.
Этап 120: для каждого блока в области подсчет значения блока в течение предварительно заданного интервала, значение блока является количеством пользователей, которые сообщают данные геопозиционирования в соответствующем блоке.
В этом варианте осуществления, сообщенные данные геопозиционирования могут быть выгружены посредством мобильного терминала пользователя через приложение, установленное в мобильном терминале.
Например, в сценарии мобильной оплаты, мобильный терминал пользователя может выполнять процесс оплаты совместно с взаимодействующей стороной в том же месте. Взаимодействующая сторона может быть пользователем, имеющим другой мобильный терминал, или может быть фиксированным терминальным устройством. Процесс может затрагивать третью сторону, предоставляющую службу оплаты, помимо двух или более взаимодействующих сторон. Сторонний поставщик услуг может предоставлять услугу безопасного взаимодействия, в то же время предоставляя этот тип сторонних услуг оплаты.
Сторонний поставщик услуги оплаты может создавать свой собственный веб-сайт или предоставлять сервер, выделенный для обработки платежа, например, платежную платформу. Таким образом, две или более стороны платежа могут выполнять платеж с помощью службы, предоставленной на платежной платформе. Например, платежной платформой может быть eBay или Alibaba. Мобильный терминал и/или фиксированный терминал может осуществлять доступ, через Интернет, к платежной платформе, предоставленной сторонним поставщиком услуг оплаты, и выполнять конкретный процесс оплаты с помощью платежной платформы. Кроме того, для удобства и безопасности, мобильный терминал и/или фиксированный терминал может быть установлен со специализированным клиентом (например, приложением). Например, приложение, предоставляемое сторонним поставщиком услуг оплаты, может быть установлено для эффективного выполнения оплаты.
Данные геопозиционирования являются местоположением мобильного терминала, на котором установлен клиент. Например, данные геопозиционирования могут включать в себя информацию о координатах геопозиционирования мобильного терминала, записанную посредством устройства позиционирования мобильного терминала. Обычное устройство позиционирования может использовать спутниковую навигационную систему глобального позиционирования (GPS) США, европейскую спутниковую навигационную систему "Galileo", российскую глобальную навигационную спутниковую систему (ГЛОНАСС) или китайскую спутниковую навигационную систему "BeiDou" или их сочетание. Этот тип информации о координатах для позиционирования также называется мобильным позиционированием. Кроме того, как правило, сообщенные данные геопозиционирования дополнительно несут сообщенную отметку времени. Отметка времени может быть временем, в которое устройство позиционирования определяет данные геопозиционирования; или время, в которое клиент на мобильном терминале сообщает данные геопозиционирования.
Данные геопозиционирования могут быть получены посредством преобразования сетевым устройством на основе признаков сигналов мобильного терминала, на котором клиент находится. Например, сетевой оператор может использовать сигналы мобильного терминала, чтобы вычислять данные геопозиционирования мобильного терминала на основе позиций базовых станций согласно принципу охвата базовых станций. В последнем вычислении местоположения, как правило, мобильный терминал измеряет вспомогательные сигналы нисходящей линии связи различных базовых станций, чтобы получать время прибытия (TOA) вспомогательного сигнала нисходящей линии связи каждой базовой станции или временную разницу прибытия (TDOA) между вспомогательными сигналами нисходящей линии связи различных базовых станций, и, как правило, использует результаты измерений и координаты базовых станций, чтобы вычислять местоположение мобильного терминала согласно алгоритму триангуляции. На практике, три или более базовых станций могут использоваться. Существует множество алгоритмов в существующих технологиях, которые являются относительно сложными. В целом, чем больше базовых станций измеряется, тем более высокую точность имеет измерение. Таким образом, характеристика позиционирования значительно улучшается.
Кроме того, данные геопозиционирования могут быть дополнительно получены посредством объединения способа устройства позиционирования на мобильном терминале и способа позиционирования на основе базовых станций. Таким образом, полученные данные геопозиционирования могут быть более точными.
Как правило, выгруженные данные геопозицонирования представляются долготами и широтами местоположений. Согласно долготе и широте местоположения каждого терминала может быть определено, в каком блоке в области на карте находится местоположение терминала, указанное посредством выгруженных данных геопозиционирования. Кроме того, значение блока для каждого блока в предварительно заданном интервале может быть определено согласно отметкам времени в данных геопозиционирования.
Предварительно заданный интервал может быть эмпирическим значением, предварительно заданным вручную, таким как, один день. Т.е., значение блока для каждого блока в течение одного дня может быть определено, т.е., количество пользователей, которые сообщают информацию о местоположении в каждом квадрате координатной сетки, подсчитываются.
Посредством подсчета количества пользователей популярность области, соответствующей каждому блоку, в течение предварительно заданного интервала может быть фактически отражена. Большее значение блока указывает, что больше пользователей находится в блоке, и область, соответствующая блоку, имеет тенденцию быть областью интереса; напротив, меньшее значение блока указывает, что меньшее количество пользователей находятся в блоке, и область, соответствующая блоку, вероятно не является областью интереса.
Этап 130: выбор значений блоков больше предварительно заданного порогового значения из подсчитанных значений блоков.
В этом варианте осуществления предварительно заданное пороговое значение может быть эмпирическим значением, предварительно заданным вручную.
В вышеупомянутом примере на фиг. 3, после того как количество пользователей, которые сообщают данные геопозиционирования в каждом блоке, подсчитывается, значение блока для каждого блока может быть получено. Фиг. 4 является схематичным чертежом области на карте, помеченной значениями блоков. На фиг. 4, для ясности, карта на фиг. 3 опускается, и остаются только блоки.
Предположим, что предварительно заданное пороговое значение равно 200, блок, соответствующий значению блока больше 200, выбирается. Фиг. 5 является схематичным чертежом выбранного значения блока. Как показано на фиг. 5, блоки, соответствующие значениям блоков более 200, помечаются порядковыми номерами от p0 до p9, соответственно.
Этап 140: определение опорных точек в блоках, соответствующих выбранным значениям блоков.
В этом варианте осуществления опорная точка может быть центральной точкой блока, имеющего выбранное значение блока.
В другом варианте осуществления опорная точка может быть любой из других точек в блоке, например, вершиной блока, точкой на 1/2 или 1/3 пути от вершины до центральной точки. Это не ограничивается в этой заявке.
Следует отметить, что опорная точка может также быть определена следующим образом. Что касается значений блоков для двух соседних блоков, когда одно больше предварительно заданного порогового значения, а другое меньше предварительно заданного порогового значения, опорная точка может быть определена на основе соотношения двух значений блоков.
Например, когда одно значение блока равно 100, а другое значение блока равно 300, опорная точка может быть задана на 1/3 пути от блока со значением 300 до блока со значением 100.
Этап 150: вычисление, согласно опорным точкам и на основе предварительно заданного алгоритма, кривой, охватывающей некоторые или все опорные точки.
В этом варианте осуществления предварительно заданный алгоритм может быть использован для вычисления кривой, охватывающей все опорные точки. В целом, множество X {X1, X2, …, Xn} точек может быть помечено на двухмерной плоскости, и после того как самые внешние точки соединяются, кривая, охватывающая все точки во множестве X точек, может быть сформирована.
В варианте осуществления предварительно заданный алгоритм может быть алгоритмом выпуклой оболочки, а кривая может быть кривой выпуклой оболочки.
В этом варианте осуществления алгоритм выпуклой оболочки используется в векторном пространстве действительных чисел, и, для заданного множества X {X1, X2, …, Xn} точек, пересечение S всех выпуклых множеств, включающих в себя множество X точек, называется выпуклой оболочкой множества X точек. Выпуклая оболочка множества X точек может быть сформирована посредством линейной комбинации всех точек (X1, …, Xn) в X.
Просто, во множестве точек на двухмерной плоскости, выпуклая оболочка является выпуклым многоугольником, сформированным посредством соединения самых внешних точек, и выпуклый многоугольник может включать в себя все точки во множестве точек.
Алгоритм выпуклой оболочки включает в себя алгоритм Грэхема, алгоритм Джарвиса, метод центра, метод уровня или алгоритм быстрой оболочки.
Алгоритм Грэхема используется в качестве примера ниже для описания. На основе блоков с выбранными значениями блоков, показанных на фиг. 5, система координат устанавливается, как показано на фиг. 6.
На практике, координаты каждой точки во множестве точек {p0, p1, p2, p3, p4, p5, p6, p7, p8, p9} формируются посредством долгот и широт, причем долготы находятся по оси X, а широты находятся по оси Y. В этом варианте осуществления, для легкости описания, координаты приводятся как целые числа. На фиг. 6 предполагается, что координатами для p0 являются (1, -2); координатами для p1 являются (1, 2); координатами для p2 являются (1, -2); координатами для p3 являются (1, 2); координатами для p4 являются (1, -2); координатами для p5 являются (1, 2); координатами для p6 являются (1, -2); координатами для p7 являются (1, 2); координатами для p8 являются (1, -2); и координатами для p9 являются (1, -2).
Процесс работы алгоритма выпуклой оболочки описывается подробно следующим образом.
A1: выбор точки из всех точек в качестве базовой точки.
В частности, выбор базовой точки может быть выполнен каким-либо одним из следующих способов.
Первый: точка с минимальной координатой Y во всех точках может быть выбрана в качестве базовой точки. Если существуют две или более точек с минимальной координатой Y, выбирается точка с минимальной координатой X.
Второй: точка с минимальной координатой X во всех точках может быть выбрана в качестве базовой точки. Если существуют две или более точек с минимальной координатой X, выбирается точка с минимальной координатой Y.
Третий: точка с максимальной координатой Y во всех точках может быть выбрана в качестве базовой точки. Если существуют две или более точек с максимальной координатой Y, выбирается точка с максимальной координатой X.
Четвертый: точка с максимальной координатой X во всех точках может быть выбрана в качестве базовой точки. Если существуют две или более точек с максимальной координатой X, выбирается точка с максимальной координатой Y.
В этом варианте осуществления используется второй способ, т.е., выбирается точка с минимальной координатой X. Поскольку p0 и p9 обе имеют минимальную координату X, тогда выбирается точка с минимальной координатой Y, т.е., p0 выбирается в качестве базовой точки.
A2: сортировка других точек согласно косинусным значениям прилежащих углов между осью X и векторами, сформированными другими точками и базовой точкой.
В этом варианте осуществления, для любого треугольника, квадрат любой стороны равен сумме квадратов других двух сторон минус удвоенное произведение двух сторон и косинуса прилежащего угла двух сторон.
Предположим, что три стороны треугольника равны a, b и c, и три угла треугольника равны A, B и C, косинусные значения углов могут быть вычислены с помощью следующих формул:
формула 1
формула 2
формула 3
где диапазон косинусных значений равен [-1, 1]. В декартовой системе координат косинусные значения являются положительными в первом и четвертом квадрантах, отрицательными во втором и третьем квадрантах и равны 0 на оси X или оси Y.
После того как косинусные значения прилежащих углов векторов, сформированных всеми другими точками и базовой точкой, получаются посредством вычисления согласно вышеприведенным формулам, косинусные значения сортируются в убывающем порядке, и порядок точек, соответствующих косинусным значениям, может быть, например, p0, p1, p2, p4, p3, p5, p6, p7, p8, p9.
A3: сканирование точек согласно отсортированному порядку и оставление точек с векторным произведением больше 0, чтобы получать кривую выпуклой оболочки.
В этом варианте осуществления векторное произведение является бинарной операцией векторов в векторном пространстве и может быть вычислено следующим образом:
формула 4
где sinθ является синусным значением вектора AB и вектора BC, и результат векторного произведения может быть положительным значением, отрицательным значением или 0.
Когда векторное произведение вектора AB и вектора BC больше 0, это указывает, что вектор AB находится в направлении по часовой стрелке для вектора BC; и точка B оставляется.
Когда векторное произведение вектора AB и вектора BC меньше 0, это указывает, что вектор AB находится в направлении против часовой стрелки для вектора BC; и точка B удаляется, а точки A и C соединяются, чтобы формировать вектор AC.
Когда векторное произведение вектора AB и вектора BC равно 0, это указывает, что вектор AB является коллинеарным с вектором BC; и точка B удаляется, а точки A и C соединяются, чтобы формировать вектор AC.
Этапы (1-14) сканирования включают в себя следующее, как показано на фиг. 6.
1: Сначала, соединение p0 и p1, чтобы формировать вектор p0p1.
2: Соединение p1 и p2, чтобы формировать вектор p1p2.
Поскольку векторное произведение вектора p0p1 и вектора p1p2 равно 0, p1 удаляется, и p0 и p2 соединяются, чтобы формировать вектор p0p2.
3: Соединение p2 и p4, чтобы формировать вектор p2p4.
Поскольку векторное произведение вектора p0p2 и вектора p2p4 больше 0, p2 остается.
4: Соединение p4 и p3, чтобы формировать вектор p4p3.
Поскольку векторное произведение вектора p2p4 и вектора p4p3 больше 0, p4 остается.
5: Соединение p3 и p5, чтобы формировать вектор p3p5.
Поскольку векторное произведение вектора p4p3 и вектора p3p5 меньше 0, p3 удаляется.
6: Соединение p4 и p5, чтобы формировать вектор p4p5.
Поскольку векторное произведение вектора p2p4 и вектора p4p5 больше 0, p4 продолжает оставаться.
7: Соединение p5 и p6, чтобы формировать вектор p5p6.
Поскольку векторное произведение вектора p4p5 и вектора p5p6 меньше 0, p5 удаляется.
8: Соединение p4 и p6, чтобы формировать вектор p4p6.
Поскольку векторное произведение вектора p2p4 и вектора p4p6 больше 0, p4 продолжает оставаться.
9: Соединение p6 и p7, чтобы формировать вектор p6p7.
Поскольку векторное произведение вектора p4p6 и вектора p6p7 больше 0, p6 остается.
10: Соединение p7 и p8, чтобы формировать вектор p7p8.
Поскольку векторное произведение вектора p6p7 и вектора p7p8 меньше 0, p7 удаляется.
11: Соединение p6 и p8, чтобы формировать вектор p6p8.
Поскольку векторное произведение вектора p4p6 и вектора p6p8 больше 0, p6 продолжает оставаться.
12: Соединение p8 и p9, чтобы формировать вектор p8p9.
Поскольку векторное произведение вектора p6p8 и вектора p8p9 меньше 0, p8 удаляется.
13: Соединение p6 и p9, чтобы формировать вектор p6p9.
Поскольку векторное произведение вектора p4p6 и вектора p6p9 больше 0, p6 продолжает оставаться.
14: Соединение p9 и p0, чтобы формировать вектор p9p0.
Поскольку векторное произведение вектора p6p9 и вектора p9p0 больше 0, p9 остается.
Соответственно, оставшиеся точки включают в себя p0, p2, p4, p6 и p9, и кривая, сформированная вектором p0p2, вектором p2p4, вектором p4p6, вектором p6p9 и вектором p9p0, является кривой выпуклой оболочки.
Этап 160: определение области в кривой в качестве области интереса.
Фиг. 7 - это схематичный чертеж области интереса, определенной согласно опорным точкам согласно этой заявке. Кривая (например, граница области интереса) на фиг. 7 охватывает все точки во множестве (p0-p9).
Согласно вариантам осуществления изобретения, сначала, сервер наносит координатную сетку на область на карте, которая должна быть обработана, подсчитывает значение блока для каждого блока, выбирает значения блоков больше предварительно заданного порогового значения из подсчитанных значений блоков, определяет опорные точки в блоках, соответствующих выбранным значениям блоков, вычисляет кривую, охватывающую все опорные точки, на основе предварительно заданного алгоритма и определяет область на кривой в качестве области интереса. Таким образом, сервер может автоматически определять области интереса на карте с помощью данных геопозиционирования, фактически сообщенных пользователями, чтобы устранять низкую эффективность и высокие затраты, вызванные ручным разграничением областей интереса, тем самым, улучшая эффективность и снижая затраты для определения областей интереса.
На практике, различные области интереса имеют различные типы. Например, пространство с заведениями питания имеет, как правило, тип общественного питания, жилой район имеет, как правило, тип сообщества, и т.д. В вышеупомянутых вариантах осуществления область интереса, полученная с помощью сообщенных данных геопозиционирования, не имеет типа.
Чтобы решать вышеупомянутую проблему, в конкретном варианте осуществления этого изобретения после этапа 160 способ может дополнительно включать в себя:
получение типов точек информации (POI) на кривой;
подсчет количеств POI одинаковых типов; и
определение типа точек информации POI наибольшего количества как типа интереса для области интереса.
В этом варианте осуществления точка информации (POI) является точкой информации, предоставленной посредством карты. POI может ссылаться на место, такое как крупный торгово-развлекательный комплекс, супермаркет, школа или жилой район.
Как правило, POI может иметь тип для отличия от других POI других функций, такой как тип общественного питания, тип сообщества, тип школьного городка, тип больницы, тип совершения покупок и т.д.
Следует отметить, что POI может быть точкой информации, предоставленной посредством карты, где находится область, которая должна быть обработана, или посредством других карт.
Согласно этому варианту осуществления, сервер может подсчитывать число точек информации POI одинаковых типов в области интереса и определять тип для точек информации POI наибольшего числа в качестве типа интереса для области интереса. Таким образом, тип интереса может быть помечен в полученной области интереса, так что пользователи могут быстро узнавать тип области интереса, тем самым, улучшая пользовательское восприятие.
На практике данные геопозиционирования, сообщенные пользователями, могут иметь ошибки. Например, устройство позиционирования мобильного терминала имеет отклонение в позиционировании, вызывающее отклонение в сообщенных данных позиционирования. В другом примере, когда мобильный терминал отключает устройство позиционирования, мобильный терминал все еще является способным выгружать данные геопозиционирования, но выгруженные данные геопозиционирования указывают геопозиционирование точки доступа (такой как WiFi), соединенной с мобильным терминалом, или базовой станции. Таким образом, данные геопозиционирования также имеют отклонение.
Чтобы решать вышеупомянутую проблему, в конкретном варианте осуществления этого изобретения способ может дополнительно включать в себя:
получение точек информации POI в области на карте, после того как опорные точки определяются в блоках, соответствующих выбранным значениям блоков (вышеупомянутый этап S140).
Соответственно, этап 150, в частности, включает в себя:
вычисление, согласно точкам информации POI и опорным точкам и на основе предварительно заданного алгоритма, кривой, охватывающей все опорные точки и точки информации POI.
В этом варианте осуществления POI являются точками информации, предоставленными посредством карты. POI могут ссылаться на места, такие как крупный торгово-развлекательный комплекс, супермаркет, школа, жилой район и т.д. POI могут представлять некоторые интересы пользователей, и данные геопозиционирования для точек информации POI являются, как правило, точными.
Следует отметить, что POI могут быть точками информации, предоставленными посредством карты, где находится область, которая должна быть обработана, или посредством других карт.
В этом варианте осуществления сервер вычисляет, согласно опорным точкам и полученным POI и на основе предварительно заданного алгоритма, кривую, охватывающую все опорные точки и точки информации POI. Процесс вычисления предварительно заданного алгоритма показан в вышеприведенных вариантах осуществления и не будет повторяться в данном документе.
Фиг. 8 - это схематичный чертеж области на карте, показанной на фиг. 2, помеченной точками информации POI.
Соответственно, фиг. 9 является схематичным чертежом области интереса, определенной согласно точкам информации POI и опорным точкам. По сравнению с областью интереса, показанной на фиг. 7, дополнительные популярные места добавляются в область интереса, показанную на фиг. 9, так что область интереса является более точной.
Согласно этому варианту осуществления, точки информации POI могут быть использованы, чтобы модифицировать данные геопозиционирования, сообщенные пользователями, так что окончательно полученная область интереса является более точной.
Согласно вышеупомянутым вариантам осуществления способа для определения области интереса на основе данных геопозиционирования, эта заявка дополнительно предоставляет варианты осуществления устройства для определения области интереса на основе данных геопозиционирования.
Варианты осуществления устройства для определения области интереса на основе данных геопозиционирования в этой заявке могут быть соответственно применены к серверному устройству. Варианты осуществления устройства могут быть реализованы с помощью программного обеспечения или аппаратных средств или способом сочетания программного обеспечения и аппаратных средств. Беря программную реализацию в качестве примера, устройство в логическом аспекте формируется посредством процессора оборудования, в котором устройство находится, считывающего соответствующие компьютерные программные инструкции в энергонезависимом запоминающем устройстве в память для работы. На уровне аппаратных средств, фиг. 10 иллюстрирует аппаратную структурную схему оборудования, которое включает в себя устройство для определения области интереса на основе данных геопозиционирования согласно этой заявке. В дополнение к процессору, сетевому интерфейсу, памяти и энергонезависимому запоминающему устройству, показанным на фиг. 10, оборудование, включающее в себя устройство, может, в целом, дополнительно включать в себя другие аппаратные средства согласно функциям определения области интереса на основе данных геопозиционирования, и это не будет конкретизироваться.
Фиг. 11 - это схематичный модульный чертеж устройства для определения области интереса на основе данных геопозиционирования согласно варианту осуществления этой заявки. Этот вариант осуществления описывается со стороны сервера, и устройство включает в себя: блок обработки 610, блок 620 подсчета, блок 630 выбора, первый блок 640 определения, блок 650 вычисления и второй блок 660 определения.
Блок обработки 610 сконфигурирован, чтобы наносить координатную сетку на область карты, которая должна быть обработана.
Блок 620 подсчета сконфигурирован, чтобы подсчитывать значение блока для каждого блока в течение предварительно заданного интервала, значение блока является количеством пользователей, которые сообщают данные геопозиционирования в соответствующем блоке.
Блок 630 выбора сконфигурирован, чтобы выбирать значения блока больше предварительно заданного порогового значения из значений блоков, определенных для блоков.
Первый блок 640 определения сконфигурирован, чтобы определять опорные точки в блоках, соответствующих выбранным значениям блоков.
Блок 650 вычисления сконфигурирован, чтобы вычислять, согласно опорным точкам и на основе предварительно заданного алгоритма, кривую, охватывающую все опорные точки.
Второй блок 660 определения сконфигурирован, чтобы определять область на кривой в качестве области интереса.
В необязательной реализации:
блок обработки 610 дополнительно сконфигурирован, чтобы делить область на карте, которая должна быть обработана, по меньшей мере, в один блок согласно предварительно заданной длине стороны.
В необязательной реализации:
опорная точка является центральной точкой блока, имеющей выбранное значение.
В необязательной реализации:
Устройство дополнительно включает в себя:
субблок получения для получения типов точек информации POI на кривой;
субблок подсчета для подсчета количеств точек информации POI одинаковых типов; и
субблок определения для определения типа точек информации POI наибольшего количества в качестве типа интереса для области интереса.
В необязательной реализации:
устройство дополнительно включает в себя:
субблок получения для получения точек информации POI в области на карте, после того как опорные точки определяются в блоках, соответствующих выбранным значениям блоков.
Соответственно, блок 650 вычисления сконфигурирован, чтобы
вычислять, согласно точкам информации POI и опорным точкам и на основе предварительно заданного алгоритма, кривую, охватывающую все опорные точки и точки информации POI.
В необязательной реализации:
алгоритм выпуклой оболочки включает в себя алгоритм Грэхема, алгоритм Джарвиса, метод центра, метод уровня или алгоритм быстрой оболочки.
Согласно вариантам осуществления этой заявки, сначала, сервер делит область на карте, которая должна быть обработана, подсчитывает значение блока для каждого блока, выбирает значения блоков больше предварительно заданного порогового значения из подсчитанных значений блоков, определяет опорные точки в блоках, соответствующих выбранным значениям блоков, вычисляет кривую, охватывающую все опорные точки, на основе предварительно заданного алгоритма и определяет область на кривой в качестве области интереса. Таким образом, сервер может автоматически определять области интереса в области на карте с помощью данных геопозиционирования, фактически сообщенных пользователями, чтобы устранять низкую эффективность и высокие затраты, вызванные ручным разграничением областей интереса, тем самым, улучшая эффективность и снижая затраты для определения областей интереса.
Ссылка на процессы реализации соответствующих этапов в вышеупомянутом способе может быть сделана для подробностей процесса реализации функций и действий блоков в устройстве. Подробности не описываются в данном документе снова.
Поскольку варианты осуществления устройства, в основном, соответствуют вариантам осуществления способа, для связанных частей, ссылка может быть сделана на описания в варианте осуществления способа. Вышеупомянутые описанные варианты осуществления устройства являются просто примерами. Блоки, описанные как отдельные части, могут или не могут быть физически раздельными, а части, отображенные как блоки, могут или не могут быть физическими блоками, могут быть расположены в одной позиции или могут быть распределены по множеству сетевых блоков. Некоторые или все модули могут быть выбраны согласно фактическим потребностям для достижения целей решений этой заявки. Специалист в области техники может понять и реализовать варианты осуществления без творческих усилий.
После рассмотрения спецификации и применения на практике настоящего изобретения, специалист в области техники может легко понять другие реализации этой заявки. Эта заявка предназначается, чтобы охватывать любые разновидности, использования или адаптивные изменения этой заявки. Эти разновидности, использования или адаптивные изменения следуют общим принципам этой заявки и включают в себя обычное общее знание или обычное техническое средство в области техники, которые не раскрываются в этой заявке. Спецификация и варианты осуществления рассматриваются как просто примерные, и рамки и смысл этой заявки указываются в последующей формуле изобретения.
Следует понимать, что эта заявка не ограничивается точными структурами, описанными выше и показанными на сопровождающих чертежах, и различные модификации и изменения могут быть выполнены без отступления от рамок этой заявки. Рамки этой заявки описываются посредством прилагаемой формулы изобретения.