[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

WO2020114272A1 - 商户查找方法、装置、电子设备和存储介质 - Google Patents

商户查找方法、装置、电子设备和存储介质 Download PDF

Info

Publication number
WO2020114272A1
WO2020114272A1 PCT/CN2019/120839 CN2019120839W WO2020114272A1 WO 2020114272 A1 WO2020114272 A1 WO 2020114272A1 CN 2019120839 W CN2019120839 W CN 2019120839W WO 2020114272 A1 WO2020114272 A1 WO 2020114272A1
Authority
WO
WIPO (PCT)
Prior art keywords
circumscribed rectangle
rectangle
circumscribed
geographic location
index tree
Prior art date
Application number
PCT/CN2019/120839
Other languages
English (en)
French (fr)
Inventor
王大松
Original Assignee
拉扎斯网络科技（上海）有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 拉扎斯网络科技（上海）有限公司 filed Critical 拉扎斯网络科技（上海）有限公司
Publication of WO2020114272A1 publication Critical patent/WO2020114272A1/zh

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/95—Retrieval from the web
    • G06F16/953—Querying, e.g. by the use of web search engines
    • G06F16/9537—Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Definitions

  • This application relates to the technical field of e-commerce, and in particular to a merchant search method, device, electronic equipment, and storage medium.
  • LBS location services
  • the related technology is to use the spatial query function of the relational database management system (PostgreSQL).
  • PostgreSQL relational database management system
  • This solution uses a method of comparing all the merchant distribution areas one by one when searching for merchants, which is suitable for merchants. In the case of a small number of distribution areas, when the number of merchant distribution areas is tens of thousands, this solution is obviously unacceptable; the related technology is to use the search engine Lucene spatial query to divide the distribution area into several grids and use Indexing and querying the relationship between the grid and the user's location has a certain improvement in performance, but this solution increases the amount of spatial data. When the spatial data reaches the level of one million or ten million, the index is too large, which will cause There is an error in the query results.
  • the purpose of some embodiments of the present application is to provide a merchant search method, device, electronic equipment and storage medium.
  • the spatial location search scheme based on the index tree and the idea of external rectangular filtering are used to aggregate merchants close to each other when the user searches. When you are a merchant, you can quickly find a merchant that meets the search criteria.
  • the embodiments of the present application provide a merchant search method, which includes: acquiring a user's geographic location, and using a pre-established index tree to find a first circumscribed rectangle covering the geographic location, where the first circumscribed rectangle is The smallest circumscribed rectangle covering the distribution area of the merchant; the target distribution area covered by the distribution area corresponding to the first circumscribed rectangle is determined; the merchant corresponding to the target distribution area is regarded as the distributable merchant corresponding to the geographical position; wherein, the leaf node of the index tree Corresponding to the first circumscribed rectangle, the non-leaf nodes of the index tree correspond to the second circumscribed rectangle, and the second circumscribed rectangle is the smallest circumscribed rectangle determined according to at least two merchant distribution areas.
  • An embodiment of the present application also provides a merchant search device, including: a search module for acquiring a user's geographic location, and using a pre-established index tree to find a first circumscribed rectangle covering the geographic location, where the first circumscribed rectangle is The smallest circumscribed rectangle covering the distribution area of the merchant; the target distribution area determination module for determining the target distribution area covered by the distribution area corresponding to the first circumscribed rectangle; the merchantable distribution determination module for the merchant corresponding to the target distribution area As a distributable merchant corresponding to the geographic location; where the leaf nodes of the index tree correspond to the first circumscribed rectangle, and the non-leaf nodes of the index tree correspond to the second circumscribed rectangle, the second circumscribed rectangle is determined according to at least two merchant distribution areas in the business circle The smallest circumscribed rectangle.
  • An embodiment of the present application further provides an electronic device, including: at least one processor; and a memory communicatively connected to the at least one processor; wherein the memory stores instructions executable by the at least one processor, and the instructions are at least one
  • the processor executes to realize: acquiring the user's geographic location, and using a pre-established index tree to find the first circumscribed rectangle covering the geographic location, where the first circumscribed rectangle is the smallest circumscribed rectangle covering the merchant's distribution area; The target distribution area covered by the distribution area corresponding to the circumscribed rectangle; the merchant corresponding to the target distribution area is regarded as the deliverable merchant corresponding to the geographic location; where the leaf nodes of the index tree correspond to the first circumscribed rectangle, and the non-leaf nodes of the index tree correspond to the second The circumscribed rectangle, the second circumscribed rectangle is the smallest circumscribed rectangle determined according to at least two merchant distribution areas.
  • the embodiments of the present application also provide a non-volatile storage medium for storing a computer-readable program, and the computer-readable program is used for the computer to execute the merchant search method as described above.
  • each non-leaf node of the index tree includes a first number of leaf nodes, and the first number is less than the threshold of the number of nodes.
  • each non-leaf node of the index tree includes a second number of leaf nodes and a third number of non-leaf nodes; the sum of the second number and the third number is less than the node number threshold.
  • the dynamically changing public rectangle is determined by the two third circumscribed rectangles; if the two third circumscribed rectangles are mutually included, the common rectangle is equal to the larger of the two third circumscribed rectangles; if the two The third circumscribed rectangles are partially overlapping or separated from each other.
  • the common rectangle is equal to the smallest circumscribed rectangle that covers the two third circumscribed rectangles; where the two third circumscribed rectangles include a first circumscribed rectangle and a common rectangle, or include two The first circumscribed rectangle; the second circumscribed rectangle at each level of the index tree is the common rectangle at the corresponding level of the index tree when the creation is completed.
  • creating the index tree further includes: selecting a first circumscribed rectangle that is closest to the common rectangle at the highest level of the index tree under construction from several first circumscribed rectangles to be inserted; according to the closest first circumscribed rectangle The position relationship with the unsaturated common rectangle in the index tree under construction determines the level of insertion of the closest circumscribed rectangle; wherein the index tree under construction corresponds to any state before the index tree is created;
  • the unsaturated common rectangle is the common rectangle whose number of child nodes is less than the threshold of the number of nodes.
  • the determining the level of insertion of the closest first circumscribed rectangle according to the positional relationship between the closest first circumscribed rectangle and the unsaturated common rectangle in the index tree under construction includes: if there are several The positional relationship between the unsaturated common rectangle and the closest circumscribed rectangle includes the closest circumscribed rectangle, and then the insertion level is determined as the smallest common rectangle among the plurality of unsaturated common rectangles The next layer; if the position relationship between the closest first circumscribed rectangle and the common rectangle at the highest level of the index tree under construction is partially overlapping or separated from each other, then the insertion level is determined to be the highest of the index tree under construction Floor.
  • each first circumscribed rectangle covering the geographic location is determined.
  • determining the second circumscribed rectangle of each level covering the geographic location in order from the root node in the index tree it also includes: determining the business district to which the user belongs and the index tree corresponding to the business district according to the geographic location.
  • using the pre-established index tree to find the first circumscribed rectangle covering the geographic location includes: determining whether the geographic location is within the latitude and longitude extreme range of the first circumscribed rectangle; if so, determining that the first circumscribed rectangle covers the geographic location, otherwise, It is determined that the first circumscribed rectangle does not cover the geographic location.
  • determining the target delivery area whose geographic location is covered by the delivery area corresponding to the first circumscribed rectangle includes: using a parallel computing method, and at the same time determining whether the geographic location is covered by the geographic location The delivery area corresponding to each first circumscribed rectangle of the position is covered, and if so, it is determined that the delivery area corresponding to the first circumscribed rectangle is the target delivery area.
  • the merchant corresponding to the target delivery area is regarded as the deliverable merchant corresponding to the geographic location, it also includes: sending the deliverable merchant to the user's terminal device, and displaying the information of the deliverable merchant by the terminal device.
  • the geographic location and distribution area are represented by latitude and longitude information.
  • the first circumscribed rectangle is determined according to the following steps: determine the latitude and longitude extreme value in the merchant distribution area, the latitude and longitude extreme value includes maximum longitude, minimum longitude, maximum latitude and minimum latitude; determine the first circumscribed rectangle according to the latitude and longitude extreme value.
  • FIG. 1 is a flowchart of a merchant search method according to the first embodiment of the present application
  • FIG. 2 is a flowchart of determining a first circumscribed rectangle of a delivery area according to the first embodiment of the present application
  • FIG. 3 is a schematic diagram of determining a second circumscribed rectangle of a non-leaf node according to the second embodiment of the present application.
  • FIG. 4 is a schematic diagram of an R-tree index tree according to the second embodiment of the present application.
  • FIG. 5 is a schematic diagram of a merchant search device according to a third embodiment of the present application.
  • FIG. 6 is a schematic diagram of an electronic device according to a fourth embodiment of the present application.
  • the first embodiment of the present application relates to a merchant search method.
  • This embodiment can be applied to a terminal side, such as a terminal device such as a mobile phone, a tablet computer, or a server on a network side.
  • the business circle contains several merchants, and each merchant has a fixed service delivery area, that is, the merchant only provides order and delivery services for users who are located within their own delivery area.
  • users place an order through the network, they will first search the list of merchants corresponding to the distribution area to which their location belongs, and then select the merchant to place the order.
  • FIG. 1 is a flowchart of a method for searching a merchant according to the first embodiment of the present application. The method includes the following steps.
  • the index tree is specifically an R-tree index tree, that is, a Rectangle-tree (rectangular index tree), which is a tree-like data structure used for spatial data storage.
  • the core idea is to aggregate nodes with similar distances in the tree.
  • the upper layer of the structure represents it as the smallest circumscribed rectangle of these nodes, and this smallest circumscribed rectangle becomes a node of the upper layer.
  • the R-tree index tree can ensure that the search of a spatial data only needs to access a small number of nodes by indexing the spatial data.
  • the first circumscribed rectangle is the smallest circumscribed rectangle covering the distribution area of a merchant.
  • a leaf node of the R-tree index tree corresponds to a first circumscribed rectangle
  • a non-leaf node of the R-tree index tree corresponds to a second circumscribed rectangle.
  • Rectangle, the second circumscribed rectangle is the smallest circumscribed rectangle determined according to the distribution area of at least two merchants in the business circle.
  • the distribution area of the merchant corresponds to a certain geographical range.
  • the shape of the distribution area may be a regular rectangle or an irregular shape.
  • the geographic location information of the user's geographic location and the merchant's distribution area is latitude and longitude.
  • the first circumscribed rectangle is determined according to the extreme values of the latitude and longitude of the distribution area.
  • the extreme values of the latitude and longitude include maximum longitude, minimum longitude, and maximum latitude. And minimum latitude. It includes the following steps.
  • S1011 Extract the latitude and longitude information on the boundary of the delivery area.
  • the latitude and longitude information includes the latitude and longitude values of all points on the boundary of the distribution area.
  • S1012. Extract longitude and latitude extreme values from the longitude and latitude information, that is, maximum longitude, minimum longitude, maximum latitude, and minimum latitude.
  • the maximum longitude and the minimum longitude are found; among all the extracted latitude values on the boundary of the distribution area, the maximum latitude and the minimum latitude are found.
  • the maximum longitude and minimum longitude are, for example, W max and W min , respectively, and the maximum latitude and minimum latitude are, for example, N max and N min, respectively .
  • S1013. Determine the first coordinates of the first circumscribed rectangle according to the maximum longitude and the maximum latitude, and determine the second coordinates of the first circumscribed rectangle according to the minimum longitude and the minimum latitude.
  • the first coordinate of the first circumscribed rectangle determined according to the maximum longitude W max and the maximum latitude N max is C1 (W max , N max )
  • the first coordinate of the first circumscribed rectangle determined according to the minimum longitude W min and the minimum latitude is The second coordinate is C2 (W min , N min ).
  • the first corresponding to the delivery area is determined Circumscribed rectangle.
  • an R-tree index tree is established in units of business circles, that is, an R-tree index tree corresponding to business circles is established for the number of merchants included in each business circle and the distribution area of each merchant.
  • the sub-nodes of the non-leaf nodes of the pre-established R-tree index tree include a first number of leaf nodes, and the first number is less than the node number threshold.
  • the next-level child nodes of the non-leaf nodes of the R-tree index tree include a second number of leaf nodes and a third number of non-leaf nodes, and the sum of the second number and the third number is less than the node number threshold.
  • the size of the threshold of the number of nodes is determined according to the number of merchants and the threshold of tree depth.
  • the threshold of the number of nodes can be set to a large value so that the tree depth of the R-tree index tree does not exceed the tree depth threshold.
  • the node number threshold can be set to a smaller value to make the tree depth larger and speed up the search.
  • the first node threshold may be set to 6.
  • the R-tree index tree in this embodiment is established in a bottom-up order, and each layer of the finally established R-tree index tree has at most one non-leaf node.
  • a dynamically changing rectangle is defined as a public rectangle.
  • the position of the public rectangle in the R-tree index tree is the same as the position of the second circumscribed rectangle, that is, it is located on a non-leaf node.
  • the common rectangle on the non-leaf nodes of the R-tree index tree in the final state is determined as the second circumscribed rectangle of the R-tree index tree.
  • the dynamically changing common rectangle is determined by two third circumscribed rectangles.
  • the two third circumscribed rectangles include a first circumscribed rectangle and a common rectangle, or include two first circumscribed rectangles; the two third circumscribed rectangles determine the common In the case of rectangles, specifically, if the two third circumscribed rectangles are mutually contained, the common rectangle is equal to the larger of the two third circumscribed rectangles; if the two third circumscribed rectangles are partially overlapping or separated from each other, the common rectangle is equal to covering The smallest circumscribed rectangle of the two third circumscribed rectangles.
  • the finally established R-tree index tree has a total of N layers, and the numbers are 0, 1, 2, ..., N-1 in order from the lowest layer.
  • the currently-built part is an n-R-tree index tree, and several first circumscribed rectangles remain to be inserted into the index tree.
  • the nth layer of the nR-tree index tree contains one non-leaf node, that is, a common rectangle, and the nth layer of the nR-tree index tree contains several leaf nodes, that is, the first circumscribed rectangle, nR-tree
  • the other n-2 layers of the index tree include one non-leaf node and several leaf nodes, that is, one common rectangle and several first circumscribed rectangles.
  • the first circumscribed rectangle that is closest to the common rectangle of the nth layer of the nR-tree index tree, and you need to insert it into the nR-tree index tree you need to determine The level of the nearest first circumscribed rectangle insertion.
  • the common rectangle including the nearest first circumscribed rectangle changes, that is, the number of covered first circumscribed rectangles increases by one.
  • the insertion level of the nearest first circumscribed rectangle is the multiple
  • the next layer of the smallest common rectangle among the common rectangles that is, insert the nearest first circumscribed rectangle into the child nodes of the smallest common rectangle among the multiple common rectangles.
  • the minimum common common rectangle changes, that is, the number of covered first circumscribed rectangles increases by one.
  • the nearest first circumscribed rectangle is determined
  • the insertion level of the rectangle is the nth layer of the nR-tree index tree, that is, the nearest first circumscribed rectangle is inserted into the leaf node of the nth layer of the nR-tree index tree, and the nearest first circumscribed rectangle and nR -The common rectangle of the nth layer of the tree index tree determines the common rectangle of the n+1 layer.
  • the common rectangle of the n+1 layer is the smallest of the common rectangle covering the nearest first circumscribed rectangle and the nth layer of the nR-tree index tree. Bounding rectangle.
  • the n-R-tree index tree becomes an n+1-R-tree index tree, that is, the R-tree index tree is built up to the n+1th layer.
  • the nth common rectangle is defined as the nth common rectangle.
  • the steps for creating an R-tree index tree starting from level 0 include, for example, the following steps.
  • the two closest circumscribed rectangles as the leaf nodes of the 0th layer of the R-tree index tree, and determine the first common rectangle covering the two closest circumscribed rectangles.
  • the rectangle serves as a non-leaf node at the first level of the R-tree index tree and serves as the parent node of the two first circumscribed rectangles; where, if the two first circumscribed rectangles are mutually contained, the first common rectangle is equal to the two first circumscribed The larger of the rectangles; if the two first circumscribed rectangles are partially overlapping or separated from each other, the first common rectangle is equal to the smallest circumscribed rectangle covering the two first circumscribed rectangles.
  • the larger one is the first common rectangle
  • a leaf node is added at level 0 of the R-tree index tree
  • the first common rectangle is added to the coverage of the first common rectangle at level 1 of the R-tree index tree.
  • the rectangle is the first circumscribed rectangle closest to the first common rectangle.
  • the larger one is the nearest first circumscribed rectangle then it is determined that the second common rectangle at the second level of the R-tree index tree is equal to the nearest first circumscribed rectangle, that is, becomes the first common rectangle and the The parent node of the nearest first circumscribed rectangle; a leaf node is added to the first layer of the R-tree index tree, that is, the first circumscribed rectangle closest to the first common rectangle.
  • the second common rectangle at the second level of the R-tree index tree is equal to covering the first common rectangle and the first closest circumscribed rectangle
  • a leaf node is added to the first layer of the R-tree index tree, that is, the first circumscribed rectangle closest to the first common rectangle.
  • the R-tree index tree is established. It is worth noting that, during the establishment of the R-tree index tree, when the number of child nodes of a certain layer has reached the threshold of the number of nodes, the first outer circumscribed rectangle no longer added to this layer is added as a new leaf node. That is, at this time, even if the common rectangle of the layer contains the closest first circumscribed rectangle, the first circumscribed rectangle is not added to the leaf node of the common rectangle, but the first circumscribed rectangle is added to the common rectangle Leaf nodes on the same level. At the same time, the common rectangle of the upper layer is determined, and the common rectangle of the upper layer is equal to the common rectangle of the next layer, but the coverage range is increased by the nearest first circumscribed rectangle.
  • the closest distance mentioned in this embodiment is specifically used to describe the distance between the center points of two first circumscribed rectangles, or the distance between the common rectangle and the center point of the first circumscribed rectangle, and the closest first circumscribed distance
  • the rectangle indicates that the distance to the center point of the first circumscribed rectangle is the shortest.
  • the R-tree index tree For example, to obtain the geographic location of the user, use the R-tree index tree to find the first circumscribed rectangle covering the geographic location of the user, as follows.
  • each first circumscribed rectangle covering the geographic location of the user is determined.
  • the first circumscribed rectangle is added to the list of deliverable first circumscribed rectangles; if there is a non-leaf node's second circumscribed rectangle covering the user's
  • For the geographic location continue to search for the next child node of the non-leaf node to determine whether the user's geographic location is covered by the first circumscribed rectangle of the leaf node in the child node or the second circumscribed rectangle of the non-leaf node in the child node. Until all the first circumscribed rectangles covering the geographic location of the user are found, a list of the first circumscribed rectangles that can be delivered is obtained.
  • the above judgment whether the user's geographic location is covered by the first circumscribed rectangle of the leaf node can be done by comparing the user's geographic location with the latitude and longitude extreme value of the first circumscribed rectangle, if the user's geographic location is located at the latitude and longitude extreme of the first circumscribed rectangle In the value interval, it means that the first circumscribed rectangle covers the user position. For example, comparing whether the longitude of the user's geographic location is between the minimum longitude and the maximum longitude of the first circumscribed rectangle, and whether the latitude is between the minimum latitude and the maximum latitude of the first circumscribed rectangle.
  • the merchant's first circumscribed rectangle contains the user's location and does not mean that the geographic area covered by the merchant's distribution area also includes the user position. Therefore, the latitude and longitude information of the user's position is compared with the coverage of the distribution area corresponding to the first circumscribed rectangle covering the user's position, and it is determined whether the user's position is within the coverage of the distribution area corresponding to the first circumscribed rectangle to determine the coverage user The target distribution area of the location.
  • the latitude and longitude information of the user's location is within the coverage area of the distribution area corresponding to the first circumscribed rectangle, it means that the merchant corresponding to the first circumscribed rectangle can provide distribution services for the user, and determine that the distribution area corresponding to the first circumscribed rectangle is the target Delivery Area.
  • the latitude and longitude information of the user's location is not within the coverage area of the distribution area corresponding to the first circumscribed rectangle, it means that the merchant corresponding to the first circumscribed rectangle cannot provide distribution services for the user.
  • serial calculation can be used to sequentially determine the multiple distribution areas, or Use parallel computing to judge multiple distribution areas simultaneously.
  • the serial calculation method refers to the distribution area of multiple merchants, and calculates and judges whether the distribution area of each merchant covers the user's position one by one
  • the parallel calculation method refers to the distribution area of multiple merchants, and simultaneously calculates and Determine whether the distribution area of each merchant covers the user's location.
  • the merchant corresponding to the target distribution area is regarded as a deliverable merchant corresponding to the geographic location of the user.
  • the distribution area corresponding to the target distribution area covers the geographic location of the user, that is, the merchant corresponding to the target distribution area can provide the distribution service for the user, and the merchant is determined as the user's distributable merchant, that is, the Distributable merchants in the user's geographic location.
  • the distributable merchant is sent to the user's terminal device, and the terminal device displays the information of the distributable merchant.
  • the terminal device displays the information of the distributable merchant.
  • the display content may include the merchant's ID, the merchant's name, the distance from the merchant to the user, the delivery fee, and the starting price.
  • the merchant, the distribution area of the merchant, and the first circumscribed rectangle of the distribution area are connected through the characteristic parameters of the merchant, and the characteristic parameter of the merchant is, for example, the ID of the merchant.
  • the embodiment of the present application adopts the idea of spatial location search scheme based on index tree and filtering of circumscribed rectangles, aggregating merchants that are close to each other, and represented on the non-leaf nodes of the index tree structure as the first circumscribed rectangle of these merchants.
  • Common circumscribed rectangle When the user searches for a merchant, the amount of calculation is greatly reduced, and the merchant that meets the search conditions can be quickly found.
  • the first circumscribed rectangle is determined according to the maximum latitude and longitude and the minimum latitude and longitude on the boundary of the distribution area, and the minimum circumscribed rectangle including the merchant's distribution area can be obtained, reducing the calculation amount in the search process.
  • the second embodiment of the present application relates to a merchant search method based on spatial location.
  • This embodiment can be applied to a terminal side, such as a terminal device such as a mobile phone or a tablet computer, or a server on a network side.
  • the merchant search method provided by the second embodiment of the present application includes the following steps.
  • the sub-nodes of the non-leaf nodes of the pre-established R-tree index tree include a first number of leaf nodes, and the first number is less than the threshold of the number of nodes.
  • the next-level child nodes of the non-leaf nodes of the R-tree index tree include a second number of leaf nodes and a third number of non-leaf nodes, and the sum of the second number and the third number is less than the node number threshold.
  • the size of the threshold of the number of nodes is determined according to the number of merchants and the threshold of tree depth.
  • the threshold of the number of nodes can be set to a large value so that the tree depth of the R-tree index tree does not exceed the tree depth threshold.
  • the node number threshold can be set to a smaller value to make the tree depth larger and speed up the search.
  • the first node threshold may be set to 6.
  • the threshold of the R-tree index tree is set to 2.
  • FIG. 3 the schematic diagram of determining the second circumscribed rectangle of the non-leaf node according to the second embodiment of the present application is shown in FIG. 3.
  • FIG. 4 The schematic diagram of the R-tree index tree according to the second embodiment of the present application is shown in FIG. 4.
  • Figure 3 and Figure 4 when building an R-tree index tree, you can start from any first circumscribed rectangle, for example, from the first circumscribed rectangle of a merchant located at the edge of the business circle, or from the center of the business circle.
  • the first circumscribed rectangle adjacent to the serial number indicates that the geographic location is also adjacent. For example, starting from D1, first compare the latitude and longitude ranges of D1 and the first closest circumscribed rectangle D2, and find that D1 and D2 are partially overlapping, then determine that the first common circumscribed rectangle of the parent node of the upper layer is D12, D12
  • the coverage area of contains two first circumscribed rectangles D1 and D2.
  • the coverage of D123 includes three first circumscribed rectangles D1, D2, D3.
  • the same method continues to insert the remaining first circumscribed rectangles D5 by comparing the latitude and longitude ranges of the public circumscribed rectangle of the parent node and the next closest circumscribed rectangle to complete the establishment of the R tree.
  • the user's geographic location is obtained, and the first circumscribed rectangle covering the user's geographic location is found in the R-tree index tree to obtain a list of first circumscribed rectangles that can be distributed.
  • the top-down search sequence is adopted, that is, the search starts from the root node circumscribed rectangle, which specifically includes the following steps.
  • the second circumscribed rectangle corresponding to the root node contains the user's position, continue to search whether the circumscribed rectangles of all the child nodes of the second layer contain the user's position.
  • user B or user E in FIG. 3 uses the R-tree index tree shown in FIG. 4 to search within the coverage range of the second circumscribed rectangles D1 to 5.
  • the circumscribed rectangles of all child nodes include several second circumscribed rectangles, or the circumscribed rectangles of all child nodes include several second circumscribed rectangles and First circumscribed rectangle.
  • the circumscribed rectangle corresponding to the leaf node contains the user's location, it means that the merchant corresponding to the leaf node can provide distribution services for the user's location and record the first circumscribed rectangle; for example, the E user in Figure 3, after searching, finds the first circumscribed rectangle Within the coverage of D5.
  • the second circumscribed rectangle does not include the user's location, it means that the merchant corresponding to the second circumscribed rectangle does not provide distribution services for the user's location.
  • the second circumscribed rectangle contains the user's location, it means that the merchant corresponding to the second circumscribed rectangle can provide distribution service for the user's location, then continue to find whether the circumscribed rectangle corresponding to all the child nodes of the third layer of the second circumscribed rectangle contains the user's location For example, the user B in FIG. 3, after searching, within the coverage of the second circumscribed rectangles D1 to 4, continue searching to the next layer.
  • the child nodes of the second circumscribed rectangle containing the user's location are searched according to the method of step (2) above until all the first circumscribed rectangles containing the user's location are found.
  • the B user in FIG. 3 after a top-down search in the R-tree index tree, finally finds two first circumscribed rectangles covering the location of the B user: D1 and D2.
  • step S202 Determine a target distribution area covered by the distribution area corresponding to the first circumscribed rectangle of the geographic location of the user.
  • the details are as in step S102 in the first specific embodiment.
  • the merchant corresponding to the target distribution area is regarded as a deliverable merchant corresponding to the geographic location of the user.
  • the distribution area corresponding to the target distribution area covers the geographic location of the user, that is, the merchant corresponding to the target distribution area can provide the distribution service for the user, and the merchant is determined as the user's distributable merchant, that is, the Distributable merchants in the user's geographic location.
  • the embodiment of the present application adopts the idea of spatial location search scheme based on index tree and filtering of circumscribed rectangles, aggregating merchants that are close to each other, and represented on the non-leaf nodes of the index tree structure as the first circumscribed rectangle of these merchants.
  • Common circumscribed rectangle When the user searches for a merchant, the public circumscribed rectangle can quickly find multiple clustered merchants that meet the conditions, greatly reducing the amount of calculation.
  • the closest merchants are aggregated, which is more in line with the user search scenario.
  • users can effectively filter out merchants that do not meet the conditions when searching for merchants, and can quickly find multiple merchants that match the user's location.
  • FIG. 5 is a schematic diagram of a merchant search device according to a third embodiment of the present application.
  • the merchant search device 500 includes the following modules.
  • the search module 501 is used to obtain the user's geographic location, and use the pre-established index tree to find the first circumscribed rectangle covering the geographic location, where the first circumscribed rectangle is the smallest circumscribed rectangle covering the merchant's distribution area; the user's geographic location and distribution The area is used for latitude and longitude information.
  • the target delivery area determination module 502 is used to determine a target delivery area whose geographic location is covered by the delivery area corresponding to the first circumscribed rectangle.
  • the deliverable merchant determination module 503 is used to make the merchant corresponding to the target delivery area as the deliverable merchant corresponding to the geographic location; wherein, the leaf nodes of the index tree correspond to the first circumscribed rectangle, and the non-leaf nodes of the index tree correspond to the second circumscribed rectangle,
  • the second circumscribed rectangle is the smallest circumscribed rectangle determined according to at least two merchant distribution areas in the business circle.
  • the child nodes of each non-leaf node of the index tree include a first number of leaf nodes, and the first number is less than the threshold of the number of nodes.
  • the child nodes of each non-leaf node of the index tree include a second number of leaf nodes and a third number of non-leaf nodes; the sum of the second number and the third number is less than the node number threshold.
  • the search module 501 determines the second circumscribed rectangles covering each level of the geographic location in order from the root node in the index tree; from the leaf nodes contained in the second circumscribed rectangle at the last level covering the geographic location, the coverage geography is determined
  • Each first circumscribed rectangle of the location includes: judging whether the geographic location is within the latitude and longitude extreme range of the first circumscribed rectangle, if it is, it is determined that the first circumscribed rectangle covers the geographic location, otherwise, it is determined that the first circumscribed rectangle does not cover the geographic location .
  • determining the target distribution area whose geographic location is covered by the distribution area corresponding to the first circumscribed rectangle includes: using a parallel computing method, while determining whether the geographic location is covered by the geographic location The delivery area corresponding to each first circumscribed rectangle of the position is covered. If so, the delivery area corresponding to the first circumscribed rectangle is determined to be the target delivery area.
  • the search module 501 determines the business circle to which the user belongs and the index tree corresponding to the business circle according to the geographic location of the user before determining the second circumscribed rectangles at each level covering the geographic location from the root node in the index tree.
  • the merchant search device 500 further includes an index tree creation module 504, which is used to create an index tree according to the distribution area of the merchant in the commercial circle.
  • the index tree creation module 504 includes a first circumscribed rectangle determination module 5041, a common rectangle determination module 5042, and an insertion level determination module 5043.
  • the first circumscribed rectangle determining module 5041 is used to determine the first circumscribed rectangle according to the distribution area of the merchant in the business circle, specifically: determining the extreme values of latitude and longitude in the distribution area of the merchant, the extreme values of latitude and longitude include maximum longitude, minimum longitude, and maximum Latitude and minimum latitude; the first circumscribed rectangle is determined according to the extreme value of latitude and longitude.
  • the common rectangle determining module 5042 is used to determine the dynamically changing common rectangle according to the two third circumscribed rectangles, specifically: if the two third circumscribed rectangles are mutually included, the common rectangle is equal to the two third circumscribed rectangles If the two third circumscribed rectangles are partially overlapping or separated from each other, the common rectangle is equal to the smallest circumscribed rectangle covering the two third circumscribed rectangles.
  • the two third circumscribed rectangles include a first circumscribed rectangle and a common rectangle, or include two first circumscribed rectangles; the second circumscribed rectangle at each level of the index tree is the common rectangle.
  • the insertion level determination module 5043 is used to select the first circumscribed rectangle closest to the common rectangle at the highest level of the index tree under construction from several first circumscribed rectangles to be inserted, according to the closest first circumscribed rectangle The positional relationship with the unsaturated common rectangle in the index tree under construction determines the insertion level of the closest circumscribed rectangle.
  • the insertion level is determined to be below the smallest common rectangle among the several unsaturated public rectangles One layer; if the position relationship between the closest first circumscribed rectangle and the common rectangle of the highest layer of the index tree under construction is partially overlapping or separated from each other, then the insertion level is determined to be the highest layer of the index tree under construction.
  • the index tree under construction corresponds to any state before the index tree is created; the unsaturated public rectangle is a public rectangle whose number of child nodes is less than the threshold of the number of nodes.
  • FIG. 6 is a schematic diagram of an electronic device according to a fourth embodiment of the present application.
  • the electronic device includes: at least one processor 601; Memory 602; and, respectively, a communication component 603 that is communicatively connected to the processor 601 and the memory 602, and the communication component 603 receives and sends data under the control of the processor 601; wherein, the memory 602 stores at least one processor 601
  • the executed instruction is executed by at least one processor 601 to achieve: obtain the user's geographic location, and use a pre-established index tree to find the first circumscribed rectangle covering the geographic location, where the first circumscribed rectangle is the smallest covering the merchant's distribution area Circumscribed rectangle; determine the target distribution area whose geographic location is covered by the distribution area corresponding to the first circumscribed rectangle; consider the merchant corresponding to the target distribution area as the distributable merchant corresponding to the geographical position; where the leaf nodes of the index tree correspond to the first circumscribed rectangle, The non-leaf nodes of the index
  • the electronic device includes: one or more processors 601 and a memory 602.
  • a processor 601 is used as an example.
  • the processor 601 and the memory 602 may be connected through a bus or in other ways. In FIG. 6, the connection through a bus is used as an example.
  • the memory 602 is a non-volatile computer-readable storage medium, and can be used to store non-volatile software programs, non-volatile computer executable programs, and modules.
  • the processor 601 executes various functional applications and data processing of the device by running non-volatile software programs, instructions, and modules stored in the memory 602, that is, implementing the above merchant search method.
  • the memory 602 may include a storage program area and a storage data area, where the storage program area may store an operating system and application programs required by at least one function; the storage data area may store a merchant's ID, longitude and latitude information of the merchant's distribution area, and the like.
  • the memory 602 may include a high-speed random access memory, and may also include a non-volatile memory, such as at least one magnetic disk storage device, a flash memory device, or other non-volatile solid-state storage devices.
  • the memory 602 may optionally include memories set remotely with respect to the processor 601, and these remote memories may be connected to an external device through a network. Examples of the above network include but are not limited to the Internet, intranet, local area network, mobile communication network, and combinations thereof.
  • One or more modules are stored in the memory 602, and when executed by one or more processors 601, execute the merchant search method in any of the above method embodiments.
  • the fifth embodiment of the present application relates to a non-volatile storage medium for storing a computer-readable program, and the computer-readable program is used for a computer to execute some or all of the above method embodiments.
  • a program which is stored in a storage medium and includes several instructions to make a device ( It may be a single chip microcomputer, a chip, etc.) or a processor to execute all or part of the steps of the methods of the embodiments of the present application.
  • the aforementioned storage media include: U disk, mobile hard disk, read-only memory (ROM, Read-Only Memory), random access memory (RAM, Random Access Memory), magnetic disk or optical disk and other media that can store program code .

Landscapes

  • Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Navigation (AREA)

Abstract

一种商户查找方法、装置、电子设备及非易失性存储介质，所述方法包括：获取用户的地理位置，利用预先建立的索引树查找覆盖地理位置的第一外接矩形（101），其中，第一外接矩形为覆盖商户配送区域的最小外接矩形；确定地理位置被第一外接矩形对应的配送区域覆盖的目标配送区域（102）；将目标配送区域对应的商户作为地理位置对应的可配送商户（103）；其中，索引树的叶子节点对应第一外接矩形，索引树的非叶子节点对应第二外接矩形，第二外接矩形为根据至少两个商户配送区域确定的最小外接矩形。

Description

商户查找方法、装置、电子设备和存储介质
交叉引用
本申请引用于2018年12月08日递交的名称为“商户查找方法、装置、电子设备和存储介质”的第201811498585.9号中国专利申请，其通过引用被全部并入本申请。
技术领域
本申请涉及电商技术领域，尤其涉及一种商户查找方法、装置、电子设备和存储介质。
背景技术
随着互联网的发展，网上购物越来越普遍，在餐饮、酒店等行业，用户通过网络便可实现快速下单。例如外卖行业，用户下单过程中，先定位到自己的位置，然后根据点餐需求选择商户进行下单。这个过程包含了基于位置服务(LBS)的空间位置搜索的过程，即根据用户定位的位置搜索到附近可以为用户提供配送服务的商家列表。
目前有关LBS空间搜索的实现方案，相关技术一是利用关系型数据库管理系统(PostgreSQL)的空间查询功能，这种方案在搜索商家时，采用的是对所有商户配送区域逐一比较的方式，适合商户配送区域数量较少的情况，当面对商户配送区域数量上万的情况，显然这种方案不能接受；相关技术二是利用搜索引擎Lucene空间查询，将配送区域划分为若干个网格之后，利用网格与用户位置的关系进行索引及查询，其在性能上有一定提升，但是此方案因为增加了空间数据量，当空间数据达到百万、千万级别的情况下，索引太大，会导致查询结果存在误差。
发明内容
本申请部分实施例的目的在于提供一种商户查找方法、装置、电子设备和存储介质，采用基于索引树的空间位置搜索方案及外接矩形过滤的思想，将距离相近的商户进行聚合，当用户查找商户时，可快速找到符合搜索条件的商户。
为解决上述技术问题，本申请的实施例提供了一种商户查找方法，包括：获取用户的地理位置，利用预先建立的索引树查找覆盖地理位置的第一外接矩形，其中，第一外接矩形为覆盖商户配送区域的最小外接矩形；确定地理位置被第一外接矩形对应的配送区域覆盖的目标配送区域；将目标配送区域对应的商户作为地理位置对应的可配送商户；其中，索引树的叶子节点对应第一外接矩形，索引树的非叶子节点对应第二外接矩形，第二外接矩形为根据至少两个商户配送区域确定的最小外接矩形。
本申请的实施例还提供了一种商户查找装置，包括：查找模块，用于获取用户的地理位置，利用预先建立的索引树查找覆盖地理位置的第一外接矩形，其中，第一外接矩形为覆盖商户配送区域的最小外接矩形；目标配送区域确定模块，用于确定地理位置被第一外接矩形对应的配送区域覆盖的目标配送区域；可配送商户确定模块，用于将目标配送区域对应的商户作为地理位置对应的可配送商户；其中，索引树的叶子节点对应第一外接矩形，索引树的非叶子节点对应第二外接矩形，第二外接矩形为根据商圈内至少两个商户配送区域确定的最小外接矩形。
本申请的实施例还提供了一种电子设备，包括：至少一个处理器；以及与至少一个处理器通信连接的存储器；其中，存储器存储有可被至少一个处理器执行的指令，指令被至少一个处理器执行以实现：获取用户的地理位置，利用预先建立的索引树查找覆盖地理位置的第一外接矩形，其中，第一外接矩形为覆盖商户配送区域的最小外接矩形；确定地理位置被第一外接矩形对应的配送区域覆盖的目标配送区域；将目标配送区域对应的商户作为地理位置对应的可配送商户；其中，索引树的叶子节点对应第一外接矩形，索引树的非叶子节点对应第二外接矩形，第二外接矩形为根据至少两个商户配送区域确定的最小外接矩形。
本申请的实施例还提供了一种非易失性存储介质，用于存储计算机可 读程序，计算机可读程序用于供计算机执行如上的商户查找方法。
另外，索引树的每个非叶子节点的子节点中包括第一数量的叶子节点，第一数量小于节点数阈值。
另外，索引树的每个非叶子节点的子节点中包括第二数量的叶子节点和第三数量的非叶子节点；第二数量和第三数量的和小于节点数阈值。
另外，创建索引树时，包括由两个第三外接矩形确定动态变化的公共矩形；若两个第三外接矩形为相互包含，公共矩形等于两个第三外接矩形中的较大者；若两个第三外接矩形为部分重叠或相互分离，公共矩形等于覆盖两个第三外接矩形的最小外接矩形；其中，两个第三外接矩形包括一个第一外接矩形和一个公共矩形，或者包括两个第一外接矩形；所述索引树每一层级的所述第二外接矩形为创建完成时的索引树对应层级的所述公共矩形。
另外，创建所述索引树还包括：从若干个待插入的第一外接矩形中选择与在建索引树最高层的公共矩形距离最近的第一外接矩形；根据所述距离最近的第一外接矩形与所述在建索引树中未饱和公共矩形的位置关系确定所述距离最近的第一外接矩形插入的层级；其中，所述在建索引树对应所述索引树创建完成之前的任一状态；所述未饱和公共矩形为子节点数小于所述节点数阈值的所述公共矩形。
另外，所述根据所述距离最近的第一外接矩形与所述在建索引树中未饱和公共矩形的位置关系确定所述距离最近的第一外接矩形插入的层级，包括：若存在若干个所述未饱和公共矩形与所述距离最近的第一外接矩形的位置关系为包含所述距离最近的第一外接矩形，则确定所述插入层级为若干个所述未饱和公共矩形中的最小公共矩形的下一层；若距离最近的第一外接矩形与所述在建索引树最高层的公共矩形的位置关系为部分重叠或相互分离，则确定所述插入层级为所述在建索引树的最高层。
另外，获取用户的地理位置，利用预先建立的索引树查找覆盖地理位置的第一外接矩形，包括：在索引树中从根节点开始依次确定覆盖地理位置的每级第二外接矩形；从覆盖地理位置的最末级第二外接矩形包含的叶子节点中，确定覆盖地理位置的每个第一外接矩形。
另外，在索引树中从根节点开始依次确定覆盖地理位置的每级第二外接矩形之前，还包括：根据地理位置确定用户所属的商圈及商圈对应的索引树。
另外，利用预先建立的索引树查找覆盖地理位置的第一外接矩形，包括：判断地理位置是否位于第一外接矩形的经纬度极值区间内，若是，则确定第一外接矩形覆盖地理位置，否则，确定第一外接矩形未覆盖地理位置。
另外，当覆盖地理位置的第一外接矩形为至少两个时，确定地理位置被第一外接矩形对应的配送区域覆盖的目标配送区域，包括：采用并行计算方式，同时判断地理位置是否被覆盖地理位置的每个第一外接矩形对应的配送区域覆盖，若是，则确定所述第一外接矩形对应的配送区域为目标配送区域。
另外，在将目标配送区域对应的商户作为地理位置对应的可配送商户之后，还包括：发送可配送商户到用户的终端设备，由终端设备显示可配送商户的信息。
另外，地理位置和配送区域用经纬度信息表示。
另外，第一外接矩形根据如下步骤确定：确定商户配送区域内的经纬度极值，经纬度极值包括最大经度、最小经度、最大纬度和最小纬度；根据经纬度极值确定第一外接矩形。
附图说明
图1是根据本申请第一实施例提供的商户查找方法流程图；
图2是根据本申请第一实施例中的确定配送区域的第一外接矩形的流程图；
图3是根据本申请第二实施例中的确定非叶子节点的第二外接矩形的示意图；
图4是根据本申请第二实施例中的R-tree索引树的示意图；
图5是根据本申请第三实施例提供的商户查找装置示意图；
图6是根据本申请第四实施例提供的电子设备示意图。
具体实施方式
为使本申请实施例的目的、技术方案和优点更加清楚，下面将结合附图对本申请的各实施例进行详细的阐述。然而，本领域的普通技术人员可以理解，在本申请各实施例中，为了使读者更好地理解本申请而提出了许多技术细 节。但是，即使没有这些技术细节和基于以下各实施例的种种变化和修改，也可以实现本申请所要求保护的技术方案。
本申请的第一实施例涉及一种商户查找方法，本实施例可以应用在终端侧，如应用在手机，平板电脑等终端设备中，也可以应用在网络侧的服务器中。
餐饮领域中，商圈内包含若干个商户，每个商户有固定服务的配送区域，即商户只为位于自己配送区域范围内的用户提供下单及配送服务。用户通过网络下单时，会先搜索到自己所在位置所属配送区域对应的商户列表，然后选择商户进行下单。
图1是根据本申请第一实施例提供的商户查找方法流程图，该方法包括以下步骤。
S101、获取用户的地理位置，利用预先建立的索引树查找覆盖用户地理位置的第一外接矩形。
本实施例中，索引树具体为R-tree索引树，即Rectangle-tree(矩形索引树)，是用于做空间数据存储的树状数据结构，其核心思想是聚合距离相近的节点并在树结构的上一层将其表示为这些节点的最小外接矩形，这个最小外接矩形就成为上一层的一个节点。R-tree索引树通过对空间数据建立索引，能够保证对一个空间数据的搜索只需要访问很小一部分的节点。
具体地，第一外接矩形为覆盖一个商户的配送区域的最小外接矩形，R-tree索引树的一个叶子节点对应一个第一外接矩形，R-tree索引树的一个非叶子节点对应一个第二外接矩形，第二外接矩形为根据商圈内至少两个商户的配送区域确定的最小外接矩形。
商户的配送区域对应一定的地理范围，配送区域的形状可能是规则的矩形，也可能是不规则形状。例如，用户的地理位置和商户的配送区域的地理位置信息为经纬度。根据本申请第一实施例中的确定配送区域的第一外接矩形的流程如图2所示，根据配送区域的经纬度极值确定第一外接矩形，经纬度极值包括最大经度、最小经度、最大纬度和最小纬度。具体包括以下步骤。
S1011、提取配送区域边界上的经纬度信息。经纬度信息包括配送区域边界上所有点的经度值和纬度值。
S1012、从经纬度信息中提取经纬度极值，即最大经度、最小经度、 最大纬度和最小纬度。
具体地，在提取到的配送区域边界上的所有经度值中，找到最大经度和最小经度；在提取到的配送区域边界上的所有纬度值中，找到最大纬度和最小纬度。最大经度和最小经度例如分别为W max和W min，最大纬度和最小纬度例如分别为N max和N min。
S1013、根据最大经度和最大纬度确定第一外接矩形的第一坐标，根据最小经度和最小纬度确定第一外接矩形的第二坐标。
具体地例如，根据最大经度W max和最大纬度N max确定的第一外接矩形的第一坐标为C1(W max，N max)，根据最小经度W min和最小纬度确定的第一外接矩形的第二坐标为C2(W min，N min)。
S1014、根据第一坐标和第二坐标确定第一外接矩形。
具体地，以第一坐标C1(W max，N max)和第二坐标C2(W min，N min)之间的连线作为第一外接矩形的对角线，确定出配送区域对应的第一外接矩形。
本实施例中，以商圈为单位建立R-tree索引树，即针对每一个商圈中包含的商户数量及每个商户的配送区域，建立起对应该商圈的R-tree索引树。
例如，预先建立的R-tree索引树的非叶子节点的下一层子节点包括第一数量的叶子节点，第一数量小于节点数阈值。或者，R-tree索引树的非叶子节点的下一层子节点包括第二数量的叶子节点和第三数量的非叶子节点，第二数量和第三数量的和小于节点数阈值。节点数阈值的大小具体根据商户的数量和树深度阈值来决定。当商户数量较多时，节点数阈值可设置较大的值，以使R-tree索引树的树深度不超过树深度阈值。当商户数量较少时，在R-tree索引树的树深度不超过树深度阈值的情况下，节点数阈值可设置较小的值，以使树深度较大，加快查找的速度。具体地，例如当商户数量为2000时，第一节点阈值可设置为6。其中，根节点上的第二外接矩形所表示的地理范围覆盖了商圈内所有商户的第一外接矩形。子节点上的第二外接矩形所表示的地理范围覆盖了若干个商户的第一外接矩形。
更为具体地，本实施例中的R-tree索引树采用自下而上的顺序建立，最终建立的R-tree索引树的每一层最多有一个非叶子节点。在创建R-tree索引树的过程中，定义一个动态变化的矩形为公共矩形，公共矩形在R-tree索引树中的位置同于第二外接矩形的位置，即位于非叶子节点上。当R-tree索引树 建立完成后，最终状态的R-tree索引树的非叶子节点上的公共矩形则确定为R-tree索引树的第二外接矩形。
上述动态变化的公共矩形由两个第三外接矩形确定，两个第三外接矩形包括一个第一外接矩形和一个公共矩形，或者包括两个第一外接矩形；由两个第三外接矩形确定公共矩形时，具体为，若两个第三外接矩形为相互包含，公共矩形等于两个第三外接矩形中的较大者；若两个第三外接矩形为部分重叠或相互分离，公共矩形等于覆盖两个第三外接矩形的最小外接矩形。
在一个实施例中，例如最终建立的R-tree索引树共有N层，从最底层起编号依次为0、1、2、…、N-1。在创建R-tree索引树的过程中，当完成到第n层时，例如当前已建成部分为n-R-tree索引树，剩余若干个第一外接矩形待插入到索引树中。当前状态下，n-R-tree索引树的第n层包含1个非叶子节点，即1个公共矩形，n-R-tree索引树的第0层包含若干个叶子节点，即第一外接矩形，n-R-tree索引树的其他n-2层包含1个非叶子节点和若干个叶子节点，即包含1个公共矩形和若干个第一外接矩形。例如，从若干个待插入的第一外接矩形中选择一个与n-R-tree索引树第n层的公共矩形距离最近的第一外接矩形，需要将其插入到该n-R-tree索引树，则需要确定该最近的第一外接矩形插入的层级。具体为，从n-R-tree索引树的第n层的公共矩形开始，从上往下遍历每一层级的公共矩形，判断该最近的第一外接矩形与每一层级的公共矩形的位置关系，并根据位置关系确定该最近的第一外接矩形插入的层级，包括：若存在包含该最近的第一外接矩形的公共矩形，且该公共矩形包含的子节点数小于节点数阈值时，则确定该最近的第一外接矩形的插入层级为包含该最近的第一外接矩形的公共矩形的下一层，即将该最近的第一外接矩形插入到包含该最近的第一外接矩形的公共矩形的子节点中。此时，包含该最近的第一外接矩形的公共矩形发生变化，即覆盖的第一外接矩形的数量增加一个。
例如，若存在多个包含该最近的第一外接矩形的公共矩形，且该多个公共矩形包含的子节点数小于节点数阈值时，则确定该最近的第一外接矩形的插入层级为该多个公共矩形中的最小公共矩形的下一层，即将该最近的第一外接矩形插入到该多个公共矩形中的最小公共矩形的子节点中。此时，该最小公共公共矩形发生变化，即覆盖的第一外接矩形的数量增加一个。
若不存在包含该最近的第一外接矩形的公共矩形，即此时该最近的第 一外接矩形与第n层的公共矩形的位置关系为部分重叠或相互分离，则确定该最近的第一外接矩形的插入层级为n-R-tree索引树的第n层，即将该最近的第一外接矩形插入到该n-R-tree索引树第n层的叶子节点中，并且由该最近的第一外接矩形与n-R-tree索引树第n层的公共矩形确定n+1层的公共矩形，n+1层的公共矩形即为覆盖该最近的第一外接矩形与n-R-tree索引树第n层的公共矩形的最小外接矩形。此时n-R-tree索引树变成n+1-R-tree索引树，即R-tree索引树建到第n+1层。
在一个具体实施例中，第n层的公共矩形定义为第n公共矩形。从第0层开始创建R-tree索引树的步骤例如包括以下步骤。
(1)、选择距离最相近的两个第一外接矩形作为R-tree索引树第0层的叶子节点，确定覆盖距离最相近的两个第一外接矩形的第一公共矩形，以第一公共矩形作为R-tree索引树第1层的非叶子节点，并作为两个第一外接矩形的父节点；其中，若两个第一外接矩形为相互包含，第一公共矩形等于两个第一外接矩形中的较大者；若两个第一外接矩形为部分重叠或相互分离，第一公共矩形等于覆盖两个第一外接矩形的最小外接矩形。
(2)、选择与第一公共矩形距离最相近的第一外接矩形，确定覆盖第一公共矩形和距离最相近的第一外接矩形的公共矩形；若第一公共矩形与距离最近的第一外接矩形为相互包含，公共矩形等于第一公共矩形和距离最相近的第一外接矩形中的较大者。
在一个例子中，较大者为第一公共矩形，则R-tree索引树的第0层增加一个叶子节点，R-tree索引树第1层的第一公共矩形的覆盖范围增加一个第一外接矩形，即与第一公共矩形最近的第一外接矩形。
在一个例子中，较大者为该最近的第一外接矩形，则确定R-tree索引树的第2层的第二公共矩形等于该最近的第一外接矩形，即成为第一公共矩形和该最近的第一外接矩形的父节点；R-tree索引树的第1层增加一个叶子节点，即与第一公共矩形最近的第一外接矩形。
若第一公共矩形与距离最近的第一外接矩形为部分重叠或相互分离，则确定R-tree索引树的第2层的第二公共矩形等于覆盖第一公共矩形和距离最近的第一外接矩形的最小外接矩形，R-tree索引树的第1层增加一个叶子节点，即与第一公共矩形最近的第一外接矩形。
按照上述方法，直到所有的第一外接矩形都使用完，R-tree索引树建立完成。值得说明的是，R-tree索引树建立过程中，当某一层的子节点数目已达到节点数阈值时，该层不再增加距离最近的第一外接矩形作为新增叶子节点。即此时，即使该层的公共矩形包含距离最近的第一外接矩形，也不将该第一外接矩形增加为该公共矩形的叶子节点，而是将该第一外接矩形增加为与该公共矩形同层的叶子节点。同时确定上一层的公共矩形，并且上一层的公共矩形等于下一层的公共矩形，但覆盖范围增加了该最近的第一外接矩形。
本实施例中提及的距离最相近具体用于描述两个第一外接矩形的中心点距离的远近，或公共矩形与第一外接矩形的中心点的距离的远近，距离最相近的第一外接矩形表示到该第一外接矩形的中心点的距离最近。
例如，获取用户的地理位置，利用R-tree索引树中查找覆盖用户地理位置的第一外接矩形，具体如下。
通过对用户进行实时定位，获取用户的地理位置，例如经纬度信息，在R-tree索引树中从根节点开始依次确定覆盖用户的地理位置的每级第二外接矩形；从覆盖用户的地理位置的最末级第二外接矩形包含的叶子节点中，确定覆盖用户的地理位置的每个第一外接矩形。
更为具体地，若有叶子节点的第一外接矩形覆盖用户的地理位置，则将该第一外接矩形加入可配送第一外接矩形列表中；若有非叶子节点的第二外接矩形覆盖用户的地理位置，则继续查找该非叶子节点的下一层子节点，判断用户的地理位置是否被子节点中的叶子节点的第一外接矩形覆盖或者被子节点中的非叶子节点的第二外接矩形覆盖。直到找到所有覆盖用户地理位置的第一外接矩形，得到可配送第一外接矩形列表。
具体地，上述判断用户的地理位置是否被叶子节点的第一外接矩形覆盖，可以通过比较用户的地理位置与第一外接矩形的经纬度极值，若用户的地理位置位于第一外接矩形的经纬度极值区间内，则说明该第一外接矩形覆盖该用户位置。例如，比较用户地理位置的经度是否在第一外接矩形的最小经度到最大经度之间，且纬度是否在第一外接矩形的最小纬度到最大纬度之间。
S102、确定用户的地理位置被第一外接矩形对应的配送区域覆盖的目标配送区域。
根据步骤S101中查找到的包含用户位置的第一外接矩形，进而可以 得到对应的商户。因为商户的第一外接矩形覆盖的地理范围并不同于商户的配送区域覆盖的地理范围，因此该商户的第一外接矩形包含用户位置，并不代表该商户的配送区域覆盖的地理范围也包含用户位置。因此，将用户位置的经纬度信息与覆盖用户位置的第一外接矩形对应的配送区域的覆盖范围进行比较，判断用户位置是否在该第一外接矩形对应的配送区域的覆盖范围内，从而确定覆盖用户位置的目标配送区域。
若用户位置的经纬度信息在该第一外接矩形对应的配送区域的覆盖范围内，说明该第一外接矩形对应的商户可为该用户提供配送服务，确定该第一外接矩形对应的配送区域为目标配送区域。
若用户位置的经纬度信息不在该第一外接矩形对应的配送区域的覆盖范围内，说明该第一外接矩形对应的商户不能为该用户提供配送服务。
例如，当覆盖用户位置的第一外接矩形数量有多个时，本步骤中判断该多个商户的配送区域是否覆盖用户位置时，可采用串行计算方式对多个配送区域依次进行判断，或者采用并行计算方式对多个配送区域同时进行判断。其中，串行计算方式是指对该多个商户的配送区域，逐个依次计算并判断每个商户的配送区域是否覆盖用户位置；并行计算方式是指对该多个商户的配送区域，同时计算并判断每个商户的配送区域是否覆盖用户位置。
S103、将目标配送区域对应的商户作为用户地理位置对应的可配送商户。
本实施例中，目标配送区域对应的配送区域覆盖用户的地理位置，也就是说目标配送区域对应的商户能够为该用户提供配送服务，将该商户确定为该用户的可配送商户，也即该用户地理位置的可配送商户。
本实施例中，当确定了用户的可配送商户之后，发送可配送商户到用户的终端设备，由终端设备显示可配送商户的信息。例如发送可配送商户到用户的手机上，并在手机屏幕上显示可配送商户的信息，显示内容可包括商户的ID、商户名称、商户到用户的距离、配送费、起送价等。
本实施例中，商户、商户的配送区域、配送区域的第一外接矩形通过商户的特征参数建立联系，商户的特征参数例如为商户的ID。
本申请实施例采用了基于索引树的空间位置搜索方案及外接矩形过滤的思想，将距离相近的商户进行聚合，在索引树结构的非叶子节点上表示为 这些商户的第一外接矩形共同组成的公共外接矩形。当用户查找商户时，大大降低了运算量，可快速找到符合搜索条件的商户。另外根据配送区域边界上的最大经纬度和最小经纬度确定第一外接矩形，可以得到包含商户配送区域在内的最小外接矩形，减少查找过程中的计算量。
本申请的第二实施例涉及一种基于空间位置的商户查找方法，本实施例可以应用在终端侧，如应用在手机，平板电脑等终端设备中，也可以应用在网络侧的服务器中。
本申请第二实施例提供的商户查找方法包括以下步骤。
S201、获取用户的地理位置，利用预先建立的索引树查找覆盖用户的地理位置的第一外接矩形。
预先建立的R-tree索引树的非叶子节点的下一层子节点包括第一数量的叶子节点，第一数量小于节点数阈值。或者，R-tree索引树的非叶子节点的下一层子节点包括第二数量的叶子节点和第三数量的非叶子节点，第二数量和第三数量的和小于节点数阈值。节点数阈值的大小具体根据商户的数量和树深度阈值来决定。当商户数量较多时，节点数阈值可设置较大的值，以使R-tree索引树的树深度不超过树深度阈值。当商户数量较少时，在R-tree索引树的树深度不超过树深度阈值的情况下，节点数阈值可设置较小的值，以使树深度较大，加快查找的速度。具体地，例如当商户数量为2000时，第一节点阈值可设置为6。在一个具体例子中，设置R-tree索引树的节点数阈值为2。
具体地，根据本申请第二实施例中的确定非叶子节点的第二外接矩形的示意图如图3所示。根据本申请第二实施例中的R-tree索引树的示意图如图4所示。结合图3和图4，建立R-tree索引树时，可以从任一个第一外接矩形开始，例如可以从位于商圈最边缘的商户的第一外接矩形开始，也可以从位于商圈最中心的商户的第一外接矩形开始，将其与距离最相近的另一个第一外接矩形的经纬度范围进行比较，确定其上一层的父节点的公共外接矩形，再将该公共外接矩形与下一个距离最相近的第一外接矩形的经纬度范围进行比较，确定更上一层的父节点的虚拟节点外接矩形，同样的方法将每一个第一外接矩形插入R-tree索引树中，完成R-tree索引树的建立。
例如，假设商圈内商户总数量为5，对所有商户对应的第一外接矩形 进行编号排序后为D1、D2、D3、D4、D5。序号相邻的第一外接矩形，表示地理位置也是相邻的。例如从D1开始，首先比较D1与距离最相近的第一外接矩形D2的经纬度范围，得到D1与D2为部分重叠，则确定得到其上一层的父节点的第一公共外接矩形为D12，D12的覆盖范围包含了两个第一外接矩形D1和D2。其次，比较第一公共外接矩形D12与下一个距离最相近的第一外接矩形D3的经纬度范围，得到D12与D3为相互独立，则确定得到其上一层的父节点的第二公共外接矩形为D123，D123的覆盖范围包含了三个第一外接矩形D1、D2、D3。再次，比较第二公共外接矩形D123与下一个距离最相近的第一外接矩形D4的经纬度范围，得到D123包含D4，则确定得到其上一层的父节点的第三公共外接矩形与D123的大小和位置相同，用D1～4表示，D1～4的覆盖范围包含了四个第一外接矩形D1、D2、D3、D4。同样的方法继续通过比较每一次得到的父节点的公共外接矩形与下一个距离最相近的第一外接矩形的经纬度范围的方法依次插入剩余的第一外接矩形D5，完成R树的建立。
例如，获取用户的地理位置，利用R-tree索引树中查找到覆盖用户地理位置的第一外接矩形，得到可配送第一外接矩形列表。
例如，在R-tree索引树中查找覆盖用户位置的第一外接矩形时，采用自上而下的查找顺序，即从根节点外接矩形开始查找，具体包括以下步骤。
(1)、查找根节点对应的第二外接矩形是否包含用户位置：若根节点对应的第二外接矩形不包含用户位置，说明商圈内所有的商户都不为该用户位置提供配送服务，结束查找；例如图3中的A用户，利用图5所示的R-tree索引树查找，不在第二外接矩形D1～5的覆盖范围内。
若根节点对应的第二外接矩形包含用户位置，则继续查找第二层的所有子节点的外接矩形是否包含用户位置。例如图3中的B用户或E用户，利用图4所示的R-tree索引树查找，在第二外接矩形D1～5的覆盖范围内。
(2)、依次查找第二层的所有子节点对应的外接矩形是否包含用户位置，所有子节点外接矩形包括若干个第二外接矩形，或者所有子节点外接矩形包括若干个第二外接矩形和若干个第一外接矩形。依次查找每一个子节点对应的外接矩形是否包含用户位置：若叶子节点对应的第一外接矩形不包含用户位置，说明该叶子节点对应的商户不为该用户位置提供配送服务；例如图3中的B用户，经查找，不在第一外接矩形D5的覆盖范围内。
若叶子节点对应的外接矩形包含用户位置，说明该叶子节点对应的商户可以为该用户位置提供配送服务，记录该第一外接矩形；例如图3中的E用户，经查找，在第一外接矩形D5的覆盖范围内。
若第二外接矩形不包含用户位置，说明该第二外接矩形对应的商户不为该用户位置提供配送服务。
若第二外接矩形包含用户位置，说明该第二外接矩形对应的商户可以为该用户位置提供配送服务，则继续查找该第二外接矩形的第三层所有子节点对应的外接矩形是否包含用户位置；例如图3中的B用户，经查找，在第二外接矩形D1～4的覆盖范围内，则继续向下一层查找。
对于每一级中包含用户位置的第二外接矩形的子节点均按照如上步骤(2)的方法进行查找，直到查找到所有包含用户位置的第一外接矩形。
例如图3中的B用户，经过在R-tree索引树中自上而下的查找，最终查找到覆盖B用户位置的第一外接矩形有两个：D1和D2。
S202、确定用户的地理位置被第一外接矩形对应的配送区域覆盖的目标配送区域。具体如第一具体实施例中步骤S102。
S203、将目标配送区域对应的商户作为用户地理位置对应的可配送商户。
本实施例中，目标配送区域对应的配送区域覆盖用户的地理位置，也就是说目标配送区域对应的商户能够为该用户提供配送服务，将该商户确定为该用户的可配送商户，也即该用户地理位置的可配送商户。
本申请实施例采用了基于索引树的空间位置搜索方案及外接矩形过滤的思想，将距离相近的商户进行聚合，在索引树结构的非叶子节点上表示为这些商户的第一外接矩形共同组成的公共外接矩形。当用户查找商户时，通过该公共外接矩形快速找到聚类的多个满足条件的商户，大大降低了运算量。另外根据位置关系，将距离最相近的商户进行聚合，更加符合用户搜索的场景。并通过在索引树中进行自上而下的查找，使用户在查找商户时，有效滤除掉不符合条件的商户，能够快速找到与用户位置相匹配的多个商户。
本申请的第三实施例涉及一种商户查找装置，图5是根据本申请第三实施例提供的商户查找装置示意图，该商户查找装置500包括以下模块。
查找模块501，用于获取用户的地理位置，利用预先建立的索引树查 找覆盖地理位置的第一外接矩形，其中，第一外接矩形为覆盖商户配送区域的最小外接矩形；用户的地理位置和配送区域用于经纬度信息表示。
目标配送区域确定模块502，用于确定地理位置被第一外接矩形对应的配送区域覆盖的目标配送区域。
可配送商户确定模块503，用于将目标配送区域对应的商户作为地理位置对应的可配送商户；其中，索引树的叶子节点对应第一外接矩形，索引树的非叶子节点对应第二外接矩形，第二外接矩形为根据商圈内至少两个商户配送区域确定的最小外接矩形。
具体地，索引树的每个非叶子节点的子节点中包括第一数量的叶子节点，第一数量小于节点数阈值。或者索引树的每个非叶子节点的子节点中包括第二数量的叶子节点和第三数量的非叶子节点；第二数量和第三数量的和小于节点数阈值。
更为具体地，查找模块501在索引树中从根节点开始依次确定覆盖地理位置的每级第二外接矩形；从覆盖地理位置的最末级第二外接矩形包含的叶子节点中，确定覆盖地理位置的每个第一外接矩形，包括：判断地理位置是否位于第一外接矩形的经纬度极值区间内，若是，则确定第一外接矩形覆盖地理位置，否则，确定第一外接矩形未覆盖地理位置。
例如，当覆盖地理位置的第一外接矩形为至少两个时，确定地理位置被第一外接矩形对应的配送区域覆盖的目标配送区域，包括：采用并行计算方式，同时判断地理位置是否被覆盖地理位置的每个第一外接矩形对应的配送区域覆盖，若是，则确定第一外接矩形对应的配送区域为目标配送区域。
例如，查找模块501在索引树中从根节点开始依次确定覆盖地理位置的每级第二外接矩形之前，根据用户的地理位置确定用户所属的商圈及商圈对应的索引树。
本申请实施例中，该商户查找装置500还包括索引树创建模块504，用于根据商圈内商户的配送区域创建索引树。具体地，索引树创建模块504包括第一外接矩形确定模块5041、公共矩形确定模块5042和插入层级确定模块5043。
具体地，第一外接矩形确定模块5041用于根据商圈内商户的配送区域确定第一外接矩形，具体为：确定商户配送区域内的经纬度极值，经纬度极 值包括最大经度、最小经度、最大纬度和最小纬度；根据经纬度极值确定第一外接矩形。
更为具体地，公共矩形确定模块5042用于根据两个第三外接矩形确定动态变化的公共矩形，具体为：若两个第三外接矩形为相互包含，公共矩形等于两个第三外接矩形中的较大者；若两个第三外接矩形为部分重叠或相互分离，公共矩形等于覆盖两个第三外接矩形的最小外接矩形。其中，两个第三外接矩形包括一个第一外接矩形和一个公共矩形，或者包括两个第一外接矩形；索引树每一层级的第二外接矩形为创建完成时的索引树每一层级的公共矩形。
更为具体地，插入层级确定模块5043用于从若干个待插入的第一外接矩形中选择与在建索引树最高层的公共矩形距离最近的第一外接矩形，根据距离最近的第一外接矩形与在建索引树中未饱和公共矩形的位置关系确定距离最近的第一外接矩形的插入层级。具体为，若存在若干个未饱和公共矩形与距离最近的第一外接矩形的位置关系为包含距离最近的第一外接矩形，则确定插入层级为若干个未饱和公共矩形中的最小公共矩形的下一层；若距离最近的第一外接矩形与在建索引树最高层的公共矩形的位置关系为部分重叠或相互分离，则确定插入层级为在建索引树的最高层。其中，在建索引树对应索引树创建完成之前的任一状态；未饱和公共矩形为子节点数小于节点数阈值的公共矩形。
本申请第四实施例涉及一种电子设备，图6是根据本申请第四实施例提供的电子设备示意图，该电子设备包括：至少一个处理器601；以及，与至少一个处理器601通信连接的存储器602；以及，分别与处理器601和存储器602均为通信连接的通信组件603，通信组件603在处理器601的控制下接收和发送数据；其中，存储器602存储有可被至少一个处理器601执行的指令，指令被至少一个处理器601执行以实现：获取用户的地理位置，利用预先建立的索引树查找覆盖地理位置的第一外接矩形，其中，第一外接矩形为覆盖商户配送区域的最小外接矩形；确定地理位置被第一外接矩形对应的配送区域覆盖的目标配送区域；将目标配送区域对应的商户作为地理位置对应的可配送商户；其中，索引树的叶子节点对应第一外接矩形，索引树的非叶子节点对应第二外接矩形，第二外接矩形为根据至少两个商户配送区域确定的最小外接矩形。
该电子设备包括：一个或多个处理器601以及存储器602，图6中以一个处理器601为例。处理器601、存储器602可以通过总线或者其他方式连接， 图6中以通过总线连接为例。存储器602作为一种非易失性计算机可读存储介质，可用于存储非易失性软件程序、非易失性计算机可执行程序以及模块。处理器601通过运行存储在存储器602中的非易失性软件程序、指令以及模块，从而执行设备的各种功能应用以及数据处理，即实现上述商户查找方法。
存储器602可以包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需要的应用程序；存储数据区可存储商户的ID、商户的配送区域的经纬度信息等。此外，存储器602可以包括高速随机存取存储器，还可以包括非易失性存储器，例如至少一个磁盘存储器件、闪存器件、或其他非易失性固态存储器件。在一些实施例中，存储器602可选包括相对于处理器601远程设置的存储器，这些远程存储器可以通过网络连接至外接设备。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。
一个或者多个模块存储在存储器602中，当被一个或者多个处理器601执行时，执行上述任意方法实施例中的商户查找方法。
上述产品可执行本申请实施例所提供的方法，具备执行方法相应的功能模块和有益效果，未在本实施例中详尽描述的技术细节，可参见本申请实施例所提供的方法。
本申请的第五实施例涉及一种非易失性存储介质，用于存储计算机可读程序，计算机可读程序用于供计算机执行上述部分或全部的方法实施例。
即，本领域技术人员可以理解，实现上述实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，该程序存储在一个存储介质中，包括若干指令用以使得一个设备(可以是单片机，芯片等)或处理器(processor)执行本申请各个实施例方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。
本领域的普通技术人员可以理解，上述各实施例是实现本申请的具体实施例，而在实际应用中，可以在形式上和细节上对其作各种改变，而不偏离本申请的精神和范围。

Claims (28)

  1. 一种商户查找方法，包括：
    获取用户的地理位置，利用预先建立的索引树查找覆盖所述地理位置的第一外接矩形，其中，所述第一外接矩形为覆盖商户配送区域的最小外接矩形；
    确定所述地理位置被所述第一外接矩形对应的配送区域覆盖的目标配送区域；
    将所述目标配送区域对应的商户作为所述地理位置对应的可配送商户；
    其中，所述索引树的叶子节点对应第一外接矩形，所述索引树的非叶子节点对应第二外接矩形，所述第二外接矩形为根据至少两个所述商户配送区域确定的最小外接矩形。
  2. 根据权利要求1所述的方法，其中，所述索引树的每个非叶子节点的子节点中包括第一数量的叶子节点，所述第一数量小于节点数阈值。
  3. 根据权利要求1所述的方法，其中，所述索引树的每个非叶子节点的子节点中包括第二数量的叶子节点和第三数量的非叶子节点；所述第二数量和第三数量的和小于节点数阈值。
  4. 根据权利要求1至3中任一项所述的方法，其中，创建所述索引树包括：由两个第三外接矩形确定动态变化的公共矩形；
    若所述两个第三外接矩形为相互包含，所述公共矩形等于所述两个第三外接矩形中的较大者；
    若所述两个第三外接矩形为部分重叠或相互分离，所述公共矩形等于覆盖所述两个第三外接矩形的最小外接矩形；
    其中，所述两个第三外接矩形包括一个所述第一外接矩形和一个公共矩形，或者包括两个所述第一外接矩形；
    所述索引树每一层级的所述第二外接矩形为创建完成时的索引树对应层级的所述公共矩形。
  5. 根据权利要求4所述的方法，其中，创建所述索引树还包括：
    从若干个待插入的第一外接矩形中选择与在建索引树最高层的公共矩形距离最近的第一外接矩形；
    根据所述距离最近的第一外接矩形与所述在建索引树中未饱和公共矩形的位置关系确定所述距离最近的第一外接矩形插入的层级；
    其中，所述在建索引树对应所述索引树创建完成之前的任一状态；所述未饱和公共矩形为子节点数小于所述节点数阈值的所述公共矩形。
  6. 根据权利要求5所述的方法，其中，所述根据所述距离最近的第一外接矩形与所述在建索引树中未饱和公共矩形的位置关系确定所述距离最近的第一外接矩形插入的层级，包括：
    若存在若干个所述未饱和公共矩形与所述距离最近的第一外接矩形的位置关系为包含所述距离最近的第一外接矩形，则确定所述插入层级为若干个所述未饱和公共矩形中的最小公共矩形的下一层；
    若所述距离最近的第一外接矩形与所述在建索引树最高层的公共矩形的位置关系为部分重叠或相互分离，则确定所述插入层级为所述在建索引树的最高层。
  7. 根据权利要求1所述的方法，其中，所述获取用户的地理位置，利用预先建立的索引树查找覆盖所述地理位置的第一外接矩形，包括：
    在所述索引树中从根节点开始依次确定覆盖所述地理位置的每级第二外接矩形；
    从覆盖所述地理位置的最末级第二外接矩形包含的叶子节点中，确定覆盖所述地理位置的每个第一外接矩形。
  8. 根据权利要求7所述的方法，其中，所述在所述索引树中从根节点开始依次确定覆盖所述地理位置的每级第二外接矩形之前，还包括：
    根据所述地理位置确定所述用户所属的商圈及所述商圈对应的所述索引树。
  9. 根据权利要求1所述的方法，其中，所述利用预先建立的索引树查找覆盖所述地理位置的第一外接矩形，包括：
    判断所述地理位置是否位于所述第一外接矩形的经纬度极值区间内，若是，则确定所述第一外接矩形覆盖所述地理位置，否则，确定所述第一外接矩形未覆盖所述地理位置。
  10. 根据权利要求9所述的方法，其中，当覆盖所述地理位置的第一外接矩形为至少两个时，所述确定所述地理位置被所述第一外接矩形对应的配送区域覆盖的目标配送区域，包括：
    采用并行计算方式，同时判断所述地理位置是否被覆盖所述地理位置的每个所述第一外接矩形对应的配送区域覆盖，若是，则确定所述第一外接矩形对 应的配送区域为目标配送区域。
  11. 根据权利要求1所述的方法，其中，在所述将所述目标配送区域对应的商户作为所述地理位置对应的可配送商户之后，还包括：
    发送所述可配送商户到所述用户的终端设备，由所述终端设备显示所述可配送商户的信息。
  12. 根据权利要求1所述的方法，其中，所述地理位置和所述配送区域用经纬度信息表示。
  13. 根据权利要求12所述的方法，其中，所述第一外接矩形根据如下步骤确定：
    确定所述商户配送区域内的经纬度极值，所述经纬度极值包括最大经度、最小经度、最大纬度和最小纬度；
    根据所述经纬度极值确定所述第一外接矩形。
  14. 一种商户查找装置，包括：
    查找模块，用于获取用户的地理位置，利用预先建立的索引树查找覆盖所述地理位置的第一外接矩形，其中，所述第一外接矩形为覆盖商户配送区域的最小外接矩形；
    目标配送区域确定模块，用于确定所述地理位置被所述第一外接矩形对应的配送区域覆盖的目标配送区域；
    可配送商户确定模块，用于将所述目标配送区域对应的商户作为所述地理位置对应的可配送商户；
    其中，所述索引树的叶子节点对应第一外接矩形，所述索引树的非叶子节点对应第二外接矩形，所述第二外接矩形为根据商圈内至少两个所述商户配送区域确定的最小外接矩形。
  15. 一种电子设备，包括：至少一个处理器；以及
    与所述至少一个处理器通信连接的存储器；
    其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行以实现：获取用户的地理位置，利用预先建立的索引树查找覆盖所述地理位置的第一外接矩形，其中，所述第一外接矩形为覆盖商户配送区域的最小外接矩形；确定所述地理位置被所述第一外接矩形对应的配送区域覆盖的目标配送区域；将所述目标配送区域对应的商户作为所述地理 位置对应的可配送商户；其中，所述索引树的叶子节点对应第一外接矩形，所述索引树的非叶子节点对应第二外接矩形，所述第二外接矩形为根据至少两个所述商户配送区域确定的最小外接矩形。
  16. 根据权利要求15所述的电子设备，其中，所述索引树的每个非叶子节点的子节点中包括第一数量的叶子节点，所述第一数量小于第一节点数阈值。
  17. 根据权利要求15所述的电子设备，其中，所述索引树的每个非叶子节点的子节点中包括第二数量的叶子节点和第三数量的非叶子节点；所述第二数量和第三数量的和小于第二节点数阈值。
  18. 根据权利要求15至17中任一所述的电子设备，其中，创建所述索引树时，包括由两个第三外接矩形确定动态变化的公共矩形；
    若所述两个第三外接矩形为相互包含，所述公共矩形等于所述两个第三外接矩形中的较大者；
    若所述两个第三外接矩形为部分重叠或相互分离，所述公共矩形等于覆盖所述两个第三外接矩形的最小外接矩形；
    其中，所述两个第三外接矩形包括一个所述第一外接矩形和一个公共矩形，或者包括两个所述第一外接矩形；
    所述索引树每一层级的所述第二外接矩形为创建完成时的索引树对应层级的所述公共矩形。
  19. 根据权利要求18所述的电子设备，其中，创建所述索引树还包括：
    从若干个待插入的第一外接矩形中选择与在建索引树最高层的公共矩形距离最近的第一外接矩形；
    根据所述距离最近的第一外接矩形与所述在建索引树中未饱和公共矩形的位置关系确定所述距离最近的第一外接矩形插入的层级；
    其中，所述在建索引树对应所述索引树创建完成之前的任一状态；所述未饱和公共矩形为子节点数小于所述节点数阈值的所述公共矩形。
  20. 根据权利要求19所述的电子设备，其中，所述根据所述距离最近的第一外接矩形与所述在建索引树中未饱和公共矩形的位置关系确定所述距离最近的第一外接矩形插入的层级，包括：
    若存在若干个所述未饱和公共矩形与所述距离最近的第一外接矩形的位置关系为包含所述距离最近的第一外接矩形，则确定所述插入层级为若干个所述 未饱和公共矩形中的最小公共矩形的下一层；
    若所述距离最近的第一外接矩形与所述在建索引树最高层的公共矩形的位置关系为部分重叠或相互分离，则确定所述插入层级为所述在建索引树的最高层。
  21. 根据权利要求15所述的电子设备，其中，所述获取用户的地理位置，利用预先建立的索引树查找覆盖所述地理位置的第一外接矩形，包括：在所述索引树中从根节点开始依次确定覆盖所述地理位置的每级第二外接矩形；从覆盖所述地理位置的最末级第二外接矩形包含的叶子节点中，确定覆盖所述地理位置的每个第一外接矩形。
  22. 根据权利要求21所述的电子设备，其中，所述在所述索引树中从根节点开始依次确定覆盖所述地理位置的每级第二外接矩形之前，还包括：
    根据所述地理位置确定所述用户所属的商圈及所述商圈对应的所述索引树。
  23. 根据权利要求15所述的电子设备，其中，所述利用预先建立的索引树查找覆盖所述地理位置的第一外接矩形，包括：判断所述地理位置是否位于所述第一外接矩形的经纬度极值区间内，若是，则确定所述第一外接矩形覆盖所述地理位置，否则，确定所述第一外接矩形未覆盖所述地理位置。
  24. 根据权利要求23所述的电子设备，其中，当覆盖所述地理位置的第一外接矩形为至少两个时，所述确定所述地理位置被所述第一外接矩形对应的配送区域覆盖的目标配送区域，包括：采用并行计算方式，同时判断所述地理位置是否被覆盖所述地理位置的每个所述第一外接矩形对应的配送区域覆盖，若是，则确定所述第一外接矩形对应的配送区域为目标配送区域。
  25. 根据权利要求15所述的电子设备，其中，在所述将所述目标配送区域对应的商户作为所述地理位置对应的可配送商户之后，包括：发送所述可配送商户到所述用户的终端设备，由所述终端设备显示所述可配送商户的信息。
  26. 根据权利要求15所述的电子设备，其中，所述地理位置和所述配送区域用经纬度信息表示。
  27. 根据权利要求26所述的电子设备，其中，所述第一外接矩形根据如下步骤确定：确定所述商户配送区域内的经纬度极值，所述经纬度极值包括最大经度、最小经度、最大纬度和最小纬度；根据所述经纬度极值确定所述第一外接矩形。
  28. 一种非易失性存储介质，用于存储计算机可读程序，所述计算机可读程序用于供计算机执行如权利要求1至13中任一项所述的商户查找方法。
PCT/CN2019/120839 2018-12-08 2019-11-26 商户查找方法、装置、电子设备和存储介质 WO2020114272A1 (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN201811498585.9 2018-12-08
CN201811498585.9A CN109634962A (zh) 2018-12-08 2018-12-08 商户查找方法、装置、电子设备和存储介质

Publications (1)

Publication Number Publication Date
WO2020114272A1 true WO2020114272A1 (zh) 2020-06-11

Family

ID=66072135

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2019/120839 WO2020114272A1 (zh) 2018-12-08 2019-11-26 商户查找方法、装置、电子设备和存储介质

Country Status (2)

Country Link
CN (1) CN109634962A (zh)
WO (1) WO2020114272A1 (zh)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109634962A (zh) * 2018-12-08 2019-04-16 拉扎斯网络科技（上海）有限公司 商户查找方法、装置、电子设备和存储介质
CN111144904B (zh) * 2019-12-19 2022-01-21 北京三快在线科技有限公司 商户召回方法、装置、电子设备及可读存储介质
CN113360637A (zh) * 2020-03-05 2021-09-07 北京三快在线科技有限公司 获取商户信息的方法、装置、存储介质和电子设备
CN112308600B (zh) * 2020-09-15 2023-04-07 天津五八到家货运服务有限公司 商圈划分方法、装置及存储介质
CN113254724B (zh) * 2021-06-02 2021-10-15 北京达佳互联信息技术有限公司 网络空间发现方法、装置、电子设备及存储介质

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020081178A1 (en) * 2000-12-26 2002-06-27 Masaharu Shimada System for improving efficiency of cargo transportation service
CN108171357A (zh) * 2016-12-08 2018-06-15 北京京东尚科信息技术有限公司 物流信息系统中的信息处理方法和装置
CN108665334A (zh) * 2017-03-31 2018-10-16 建汉科技股份有限公司 订单处理方法及系统
CN109634962A (zh) * 2018-12-08 2019-04-16 拉扎斯网络科技（上海）有限公司 商户查找方法、装置、电子设备和存储介质

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN107341625A (zh) * 2016-04-28 2017-11-10 阿里巴巴集团控股有限公司 一种物流服务能力信息查询方法、装置及系统
US10225234B2 (en) * 2016-08-31 2019-03-05 Fortress Cyber Security, LLC Systems and methods for geoprocessing-based computing network security

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020081178A1 (en) * 2000-12-26 2002-06-27 Masaharu Shimada System for improving efficiency of cargo transportation service
CN108171357A (zh) * 2016-12-08 2018-06-15 北京京东尚科信息技术有限公司 物流信息系统中的信息处理方法和装置
CN108665334A (zh) * 2017-03-31 2018-10-16 建汉科技股份有限公司 订单处理方法及系统
CN109634962A (zh) * 2018-12-08 2019-04-16 拉扎斯网络科技（上海）有限公司 商户查找方法、装置、电子设备和存储介质

Also Published As

Publication number Publication date
CN109634962A (zh) 2019-04-16

Similar Documents

Publication Publication Date Title
WO2020114272A1 (zh) 商户查找方法、装置、电子设备和存储介质
US11740102B2 (en) Method, apparatus, device and storage medium for determining point of interest area
TWI584137B (zh) Search, determine the active area of ​​the method with the server
WO2018227859A1 (zh) 配送区域划分方法、装置、电子设备及计算机可读存储介质
US8244715B2 (en) System and method for processing database queries
US20230078315A1 (en) Column ordering for input/output optimization in tabular data
CN104376053B (zh) 一种基于海量气象数据的存储与检索方法
WO2020168767A1 (zh) 基于用户位置确定地理围栏
US20190095939A1 (en) Micro-geographic aggregation system
CN109815419B (zh) 基于地理位置的兴趣点索引方法、装置、介质及电子设备
CN110148032A (zh) 基于地理位置的产品推荐方法、装置、存储介质和服务器
US20150371430A1 (en) Identifying Imagery Views Using Geolocated Text
WO2020114273A1 (zh) 商户查找方法、装置、电子设备和存储介质
CN107395680A (zh) 店铺群信息推送和输出方法及装置、设备
WO2024156238A1 (zh) 地图数据的聚合展示方法、装置、电子设备
Rahman et al. Hdbscan: Density based clustering over location based services
JP2022137281A (ja) データ照会方法、装置、電子デバイス、記憶媒体、及びプログラム
US20150154228A1 (en) Hierarchical spatial clustering of photographs
JP2012515994A (ja) 密度に基づいて検索結果を表示するシステム及び方法
CN104391947A (zh) 海量gis数据实时处理方法及系统
KR102170304B1 (ko) 부동산에 관한 정보를 제공하는 방법, 시스템 및 비일시성의 컴퓨터 판독 가능 기록 매체
CN107341221A (zh) 索引结构的建立、关联检索方法、装置、设备及存储介质
CN112632681B (zh) 基于虚幻引擎的数字孪生城市模型数据单体化实现方法、装置及存储介质
US20180011934A1 (en) Identifying spatial records
US10510095B2 (en) Searching based on a local density of entities

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 19892589

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 19892589

Country of ref document: EP

Kind code of ref document: A1

122 Ep: pct application non-entry in european phase

Ref document number: 19892589

Country of ref document: EP

Kind code of ref document: A1

32PN Ep: public notification in the ep bulletin as address of the adressee cannot be established

Free format text: NOTING OF LOSS OF RIGHTS PURSUANT TO RULE 112(1) EPC (EPO FORM 1205A DATED 26.01.2022)