# US 2018/0321048 A1 · Route-deviation recognition method, terminal, and storage medium > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2018/0321048 A1 - Document ID: US20180321048A1 - Status: Published application - Kind: A1 - Application number: 16/026,731 - Filed: 2018-07-03 - Published: 2018-11-08 - Earliest claimed: 2016-03-23 - Assignees: Tencent Technology (Shenzhen) Company Limited - Applicants: Tencent Technology (Shenzhen) Company Limited - Inventors: Bingguo LI; Wangyu XIAO; Shuaiwen YANG; Menglin CHEN - Web page: https://patentgrep.com/patent/US20180321048A1 ## CPC - G01C 21/3415: {Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents} - G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) - G01C 21/30: Map- or contour-matching - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) ## Abstract A route-deviation recognition method is provided. The method includes obtaining a current positioned-location; and determining a candidate region covering the positioned-location. Road network data corresponding to the candidate region is obtained to generate a plurality of road-segment tree structures according to the obtained road network data. The method also includes obtaining a matching weight between the positioned-location and each road-segment branch in each of the road-segment tree structures. Further, according to the matching weight, a road-segment branch matching the positioned-location is determined as a matched road-segment branch. The method further includes, when the matched road-segment branch does not belong to a planned navigation route, determining that route-deviation occurs. ## Claims ### Claim 1 A route-deviation recognition method, comprising: obtaining a current positioned-location; determining a candidate region covering the positioned-location; obtaining road network data corresponding to the candidate region to generate a plurality of road-segment tree structures according to the obtained road network data; obtaining a matching weight between the positioned-location and each road-segment branch in each of the road-segment tree structures; determining, according to the matching weight, a road-segment branch matching the positioned-location as a matched road-segment branch; and when the matched road-segment branch does not belong to a planned navigation route, determining that route-deviation occurs. ### Claim 2 (depends on 1) The method according to claim 1, wherein the determining a candidate region covering the positioned-location comprises: defining the candidate region of a preset shape and of a preset size by using the positioned-location as a geometric center of the preset shape. ### Claim 3 (depends on 2) The method according to claim 2, wherein the defining the candidate region of a preset shape and of a preset size by using the positioned-location as a geometric center of the preset shape comprises: extending towards four transverse and longitudinal directions from the positioned-location, to obtain a rectangular candidate region covering the positioned-location. ### Claim 4 (depends on 1) The method according to claim 1, wherein the obtaining road network data corresponding to the candidate region to generate a plurality of road-segment tree structures according to the obtained road network data comprises: traversing road segment topology structures in the road network data, to obtain all road segments within the candidate region; and analyzing the topology structures between the obtained road segments to combine the obtained road segments into the plurality of road-segment tree structures according to corresponding topology structures. ### Claim 5 (depends on 1) The method according to claim 1, wherein the obtaining a matching weight between the positioned-location and each road-segment branch in each of the road-segment tree structures comprises: traversing each road-segment branch in each of the road-segment tree structures; obtaining a projection distance between the positioned-location and the traversed road-segment branch; obtaining a direction difference between a direction of the positioned-location and a direction of the traversed road-segment branch; and calculating the matching weight between the positioned-location and the traversed road-segment branch according to the projection distance and the direction difference. ### Claim 6 (depends on 5) The method according to claim 5, wherein: the calculating the matching weight between the positioned-location and the traversed road-segment branch according to the projection distance and the direction difference comprises: obtaining a historical direction difference accumulated value of the traversed road-segment branch; and summing the projection distance, the direction difference, and the historical direction difference accumulated value according to a corresponding non-negative weight to obtain a weight sum as the matching weight between the positioned-location and the traversed road-segment branch; and the determining, according to the matching weight, a road-segment branch matching the positioned-location comprises: determining a road-segment branch having a smallest matching weight as the road-segment branch matching the positioned-location. ### Claim 7 (depends on 1) The method according to claim 1, further comprising: after determining that route-deviation occurs, obtaining a destination of the planned navigation route and, using the positioned-location as a start point, generating a new navigation route from the start point to the destination, and navigating according to the new navigation route. ### Claim 8 A terminal, comprising: a memory storing computer-readable instructions; and a processor coupled to the memory and, when executing the computer-readable instructions, configured to perform: obtaining a current positioned-location; determining a candidate region covering the positioned-location; obtaining road network data corresponding to the candidate region to generate a plurality of road-segment tree structures according to the obtained road network data; obtaining a matching weight between the positioned-location and each road-segment branch in each of the road-segment tree structures; determining, according to the matching weight, a road-segment branch matching the positioned-location as a matched road-segment branch; and when the matched road-segment branch does not belong to a planned navigation route, determining that route-deviation occurs. ### Claim 9 (depends on 8) The terminal according to claim 8, wherein the determining a candidate region covering the positioned-location comprises: defining the candidate region of a preset shape and of a preset size by using the positioned-location as a geometric center of the preset shape. ### Claim 10 (depends on 9) The terminal according to claim 9, wherein the defining the candidate region of a preset shape and of a preset size by using the positioned-location as a geometric center of the preset shape comprises: extending towards four transverse and longitudinal directions from the positioned-location, to obtain a rectangular candidate region covering the positioned-location. ### Claim 11 (depends on 8) The terminal according to claim 8, wherein the obtaining road network data corresponding to the candidate region to generate a plurality of road-segment tree structures according to the obtained road network data comprises: traversing road segment topology structures in the road network data, to obtain all road segments within the candidate region; and analyzing the topology structures between the obtained road segments to combine the obtained road segments into the plurality of road-segment tree structures according to corresponding topology structures. ### Claim 12 (depends on 8) The terminal according to claim 8, wherein the obtaining a matching weight between the positioned-location and each road-segment branch in each of the road-segment tree structures comprises: traversing each road-segment branch in each of the road-segment tree structures; obtaining a projection distance between the positioned-location and the traversed road-segment branch; obtaining a direction difference between a direction of the positioned-location and a direction of the traversed road-segment branch; and calculating the matching weight between the positioned-location and the traversed road-segment branch according to the projection distance and the direction difference. ### Claim 13 (depends on 12) The terminal according to claim 12, wherein: the calculating the matching weight between the positioned-location and the traversed road-segment branch according to the projection distance and the direction difference comprises: obtaining a historical direction difference accumulated value of the traversed road-segment branch; and summing the projection distance, the direction difference, and the historical direction difference accumulated value according to a corresponding non-negative weight to obtain a weight sum as the matching weight between the positioned-location and the traversed road-segment branch; and the determining, according to the matching weight, a road-segment branch matching the positioned-location comprises: determining a road-segment branch having a smallest matching weight as the road-segment branch matching the positioned-location. ### Claim 14 (depends on 8) The terminal according to claim 8, where the processor is further configured to perform: after determining that route-deviation occurs, obtaining a destination of the planned navigation route and, using the positioned-location as a start point, generating a new navigation route from the start point to the destination, and navigating according to the new navigation route. ### Claim 15 A non-transitory computer-readable storage medium storing computer program instructions executable by at least one processor to perform: obtaining a current positioned-location; determining a candidate region covering the positioned-location; obtaining road network data corresponding to the candidate region to generate a plurality of road-segment tree structures according to the obtained road network data; obtaining a matching weight between the positioned-location and each road-segment branch in each of the road-segment tree structures; determining, according to the matching weight, a road-segment branch matching the positioned-location as a matched road-segment branch; and when the matched road-segment branch does not belong to a planned navigation route, determining that route-deviation occurs. ### Claim 16 (depends on 15) The non-transitory computer-readable storage medium according to claim 15, wherein the determining a candidate region covering the positioned-location comprises: defining the candidate region of a preset shape and of a preset size by using the positioned-location as a geometric center of the preset shape. ### Claim 17 (depends on 15) The non-transitory computer-readable storage medium according to claim 15, wherein the obtaining road network data corresponding to the candidate region to generate a plurality of road-segment tree structures according to the obtained road network data comprises: traversing road segment topology structures in the road network data, to obtain all road segments within the candidate region; and analyzing the topology structures between the obtained road segments to combine the obtained road segments into the plurality of road-segment tree structures according to corresponding topology structures. ### Claim 18 (depends on 15) The non-transitory computer-readable storage medium according to claim 15, wherein the obtaining a matching weight between the positioned-location and each road-segment branch in each of the road-segment tree structures comprises: traversing each road-segment branch in each of the road-segment tree structures; obtaining a projection distance between the positioned-location and the traversed road-segment branch; obtaining a direction difference between a direction of the positioned-location and a direction of the traversed road-segment branch; and calculating the matching weight between the positioned-location and the traversed road-segment branch according to the projection distance and the direction difference. ### Claim 19 (depends on 18) The non-transitory computer-readable storage medium according to claim 18, wherein: the calculating the matching weight between the positioned-location and the traversed road-segment branch according to the projection distance and the direction difference comprises: obtaining a historical direction difference accumulated value of the traversed road-segment branch; and summing the projection distance, the direction difference, and the historical direction difference accumulated value according to a corresponding non-negative weight to obtain a weight sum as the matching weight between the positioned-location and the traversed road-segment branch; and the determining, according to the matching weight, a road-segment branch matching the positioned-location comprises: determining a road-segment branch having a smallest matching weight as the road-segment branch matching the positioned-location. ### Claim 20 (depends on 15) The non-transitory computer-readable storage medium according to claim 15, further containing computer program instructions executable by the at least one processor to perform: after determining that route-deviation occurs, obtaining a destination of the planned navigation route and, using the positioned-location as a start point, generating a new navigation route from the start point to the destination, and navigating according to the new navigation route.