Method and system for matching an incident to a route

• US 7,103,473 B2
• Filed: 10/25/2001
• Issued: 09/05/2006
• Est. Priority Date: 02/01/2000
• Status: Expired due to Term

• Current Assignee: Switchboard LLC
• Original Assignee: InfoSpace, Inc. (Blucora Incorporated)
• Inventors: Ranjan, Peeyush
• Primary Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US10/050,807
• Publication Number:
  US 20020069014A1
• Time in Patent Office: 1,776 Days
• Field of Search: 701/202, 701/210, 701/117, 701/204, 340/905, 340/988, 340/990, 340/991, 340/989, 340/992, 340/917, 340/922, 340/932, 455/456
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G01C 21/3694 Output thereof on a road map
• CPC Class Codes: G08G 1/164 Centralised systems, e.g. external to vehicles

Abstract

The present invention provides a method and system for depicting an online map of a route along with any incidents on the route. To create the map, a consumer first provides the origination and destination addresses of the route, then a proposed route is provided for their approval. The consumer may modify the proposed route or accept it. Next, the route is analyzed to determine if any incidents have occurred upon it. This analysis comprises preparing the route by creating regions of interest around segments composing the route, examining if any traffic incidents fall within one or more of the regions of interest, and determining for those incidents if the incident is closer than a threshold value to any segment on the route. The final route along with any incidents on the route is then depicted for the consumer.

Claims

1. A method of determining if an incident is on a travel route, the method comprising:

dynamically generating regions of interest surrounding each of a plurality of segments of the travel route;

determining that the incident is within one region of interest;

determining that the incident is on the travel route; and

wherein the dynamically generated regions of interest are substantially elliptical.

5. A computer readable medium, containing computer interactions for performing any of the methods of claims 1, 2, 3 or 4.

6. A computing apparatus, operative to perform any of the methods of claims 1, 2, 3 or 4.

2. A method of determining if an incident is on a travel route, the method comprising:

dynamically generating regions of interest surrounding each of a plurality of segments of the travel route;

determining that the incident is within one region of interest;

determining that the incident is on the travel route; and

wherein each of said dynamically generated regions of interest have perimeters where distances to end points of each of said segments are substantially uniform and each of said distances are dynamically increased in relation to the length of said segments.

3. The method of claim 2, wherein said distances are increased by half the average length of said segments.

4. A method of determining if an incident is on a travel route, the method comprising:

generating regions of interest surrounding each of a plurality of segments of the travel route;

determining that the incident is within one region of interest;

determining that the incident is on the travel route; and

wherein the plurality of segments are dynamically determined by generating the travel route comprising said segments once a request has been made for the travel route and dynamically generating said regions of interest surrounding each of said segments comprises dynamically forming a substantially elliptical region of interest around each of said segments.

7. A computer-implemented method for dynamically matching an incident to a route, the method comprising:

obtaining route information comprising a plurality of route segments, each route segment represented by a line having a route segment start-point and a route segment end-point;

obtaining at least one incident represented by an incident point;

determining if the incident point is proximate to any of the route segments; and

associating the incident with at least one route segment to which it is determined that the incident point is proximate.

8. The method of claim 7, wherein determining if the incident point is proximate to any of the route segments comprises:

selecting at least one of the route segments comprising the route;

assuming a triangle having;

a base-side substantially defined by the selected route segment;

an incident vertex opposite the base-side that is substantially defined by the incident point;

a first-side of the triangle substantially defined from the selected route segment start-point to the incident vertex;

a second-side of the triangle substantially defined from the selected route segment end-point to the incident vertex;

determining a length of the base-side;

calculating a length of the first-side;

calculating a length of the second-side;

assuming a substantially elliptical zone of interest defined by the selected route segment start-point and end-point as foci plus a padding value; and

determining that the incident is within a zone of interest if the length of the first-side plus the length of the second-side is less than or equal to the length of the base-side plus the padding value.

9. The method of claim 8, wherein associating the incident with at least one route segment further comprises:

determining whether a distance to the incident vertex from the selected route segment is less than or equal to a minimum distance value; and

associating the incident with the selected route segment if the distance to the incident vertex is less than or equal to a minimum distance value.

10. The method of claim 9, further comprising displaying the incident together with at least one route segment to which the incident is associated.

11. The method of claim 8, wherein associating the incident with at least one route segment further comprises:

calculating a first vertex value representing the angle formed by the first-side of the triangle and the base-side;

calculating a second vertex value representing the angle formed by the second-side of the triangle and the base-side; and

associating the incident with the selected route segment if both the first vertex value and the second vertex value are equal to ninety degrees or less.

12. The method of claim 11, further comprising displaying the incident together with at least one route segment to which the incident is associated.

13. The method of claim 11, wherein the incident is represented by a plurality of incident points and the method of associating the incident with at least one route segment is performed for more than one of the plurality of the incident points.

14. The method of claim 13, wherein the plurality of incident points includes an incident start-point and an incident end-point, the method further comprising:

iteratively processing each incident point from the incident start-point to the incident end-point until the incident is associated with at least one of the route segments or all the route segments have been processed; and

iteratively processing each incident point from the incident end-point to the incident start-point until the incident is associated with at least one of the route segments or all the route segments have been processed.

15. The method of claim 14, displaying the incident together with each route segment with which the incident is associated.

16. The method of claim 14, displaying the incident together with any one route segment with which the incident start-point is associated.

17. The method of claim 14, displaying the incident together with any one route segment with which the incident end-point is associated.

18. The method of claim 13, wherein the route is automatically generated based upon an origination location and a destination location.

19. The method of claim 13, wherein the route information is automatically generated based upon an origination location, a destination location and at least one route location requirement.

20. The method of claim 19, further comprising:

displaying the automatically generated route information;

receiving the at least one route location requirement through a user interface;

obtaining revised route information meeting the at least one route location requirement; and

associating the incident with the revised route information.

21. The method of any one of claims 7 though 20 encoded as computer-readable program instructions.