Method and system for matching an incident to a route

• US 20020069014A1
• Filed: 10/25/2001
• Published: 06/06/2002
• Est. Priority Date: 02/01/2000
• Status: Active Grant

• Current Assignee: Switchboard LLC
• Original Assignee: InfoSpace, Inc. (Blucora Incorporated)
• Inventors: Ranjan, Peeyush
• Granted Patent: US 7,103,473 B2
• Time in Patent Office: Days
• 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 online map of a route along with any incidents on the route, a consumer first provides the origination and destination addresses of the route. Once the consumer provides the origination and destination addresses of the route a proposed route is provided for their approval. The consumer may modify the proposed route or accept it as the final route they desire. Next, the route is analyzed to determine if any traffic incidents have occurred upon it based on retrieved incident information compared with the route. This analysis comprises preparing the route by creating regions of interest around the segments composing the route, examining if any traffic incidents fall within one or more of the regions of interest, and then determining for those incidents that do fall within a region of interest if the incident is closer than a threshold value to any segment on the route. If it is, then the incident is on the route, and the final analysis determines on which segment of the route the incident should be place. The final route along with any incidents on the route is then depicted for the consumer via a

Claims

1. A method for depicting incidents along a desired route, wherein the desired route comprises a plurality of segments, the method comprising:

receiving segment data describing at least one segment of the desired route;

locating at least one region of interest around each segment of the desired route;

receiving incident data describing any available incidents;

for each at least one region of interest, determining if any available incidents fall within the at least one region;

for each available incident falling within at least one region determining if the available incident has occurred on at least one segment; and

for each available incident occurring on at least one segment, depicting the incident on the desired route.

2. The method of claim 1, wherein the desired route comprises at least one segment having end points located utilizing a coordinate system.

3. The method of claim 2, wherein the coordinate system comprises latitudinal and longitudinal coordinates.

4. The method of claim 1, wherein the mode of transportation used to traverse the desired route is chosen from the group consisting of:

ground vehicles, watercraft and aircraft.

5. The method of claim 1, wherein locating the at least one region of interest comprises forming a perimeter around each at least one segment at a distance.

6. The method of claim 5, wherein the perimeter enclosing the at least one segment is substantially elliptical.

7. The method of claim 6, wherein the distance from the substantially elliptical perimeter to each at least one segment is padded by adding a distance which is half the average length of the plurality of segments.

8. The method of claim 1, wherein the incident data comprises a description of at least one incident occurring at a single location.

9. The method of claim 8, wherein the single location is described utilizing a coordinate system.

10. The method of claim 9, wherein the coordinate system comprises latitudinal and longitudinal coordinates.

11. The method of claim 1, wherein the incident data comprises a description of at least one incident occurring at a multi-point location comprising a plurality of incident points.

12. The method of claim 11, wherein the plurality of incident points are described utilizing a coordinate system.

13. The method of claim 12, wherein the coordinate system comprises latitudinal and longitudinal coordinates.

14. The method of claim 1, wherein the incident data is limited to any incident within a predetermined area of the desired route.

15. The method of claim 8, wherein determining if the available incident has occurred on the at least one segment comprises determining if the incident corresponding to the incident data is closer than a threshold distance to the at least one segment.

16. The method of claim 15, wherein determining if the available incident has occurred on at least one segment further comprises:

forming a triangle from the available incident to the end points of any at least one segment closer than a threshold distance, wherein the base of the triangle is the segment; and

choosing any segment in which the angles of said triangle formed with the base are ninety degrees or less.

17. The method of claim 15, wherein determining if the available incident has occurred on at least one segment further comprises:

forming a triangle from the available incident to the end points of any at least one segment closer than a threshold distance, wherein the base of the triangle is the segment;

choosing any segment in which the angles of said triangle formed with the base are ninety degrees or less;

otherwise

if none of the segments forms a triangle in which the angles formed with the base are ninety degrees or less, choosing the closest of the segments to the available incident.

18. The method of claim 11, wherein for each available incident falling within at least one region determining, if the available incident has occurred on at least one segment further comprises:

for each incident point, determining in sequential order if any of the incident points is closer than a threshold distance to any segment;

for a first incident point determined to be closer than the threshold distance, setting the segment to which the first incident point is closer than the threshold distance as the first segment of the incident on the desired route;

for each incident point, determining in reverse sequential order a second incident point which is closer than the threshold distance to any segment; and

for the second incident point, setting the segment to which the second incident point is closer than the threshold distance as the last segment of the incident on the desired route.

19. The method of claim 18, further comprising:

if none of the incident points is determined to be closer than the threshold distance to any segment, then concluding the available incident does not fall on the desired route.

20. The method of claim 11, wherein determining, if the available incident has occurred on at least one segment further comprises:

for each incident point, determining in sequential order if any of the incident points is closer than a threshold distance to any segment;

for a first incident point determined to be closer than the threshold distance, forming a triangle from the incident point to the end points of the segment closer than the threshold distance, wherein the base of the triangle is the segment;

setting the segment to which the first incident point is closer than the threshold distance and in which the angles of said triangle formed with the base are ninety degrees or less, as the first segment of the incident on the desired route;

for each incident point, determining in reverse sequential order a second incident point which is closer than the threshold distance to any segment;

for the second incident point determined to be closer than the threshold distance, forming a triangle from the second incident point to the end points of the segment closer than the threshold distance, wherein the base of the triangle is the segment; and

setting the segment to which the second incident point is closer than the threshold distance and in which the angles of said triangle formed with the base are ninety degrees or less, as the last segment of the incident on the desired route.

21. The method of claim 20, further comprising:

if none of the incident points is determined to be closer than the threshold distance to any segment, then concluding the available incident does not fall on the desired route.

22. A system for depicting incidents along a desired route, comprising:

a route depiction device operative to depict the desired route, as well as any incidents along the desired route; and

an information server operative to;

receive segment data describing at least one segment of the desired route from a map server;

locate at least one region of interest around each segment of the desired route;

receive incident data describing any available incidents from an incident server;

for each at least one region, determine if any available incidents fall within the at least one region;

for each available incident falling within at least one region determine if the available incident has occurred along the at least one segment; and

for each available incident occurring on at least one segment, providing the route depiction device with the incident so that the route depiction device may depict the incident along the desired route.

23. The system of claim 22, wherein the desired route comprises at least one segment having end points located utilizing a coordinate system.

24. The system of claim 23, wherein the coordinate system comprises latitudinal and longitudinal coordinates.

25. The system of claim 22, wherein the mode of transportation used to traverse the desired route is chosen from the group consisting of:

ground vehicles, watercraft and aircraft.

26. The system of claim 22, further comprising a communications server operative to communicate with the information server and the route depiction device.

27. The system of claim 22, wherein the route depiction device is chosen from the group consisting of:

computers, telephones, cellular phones, automotive mapping devices, facsimile machines and pagers.

28. The system of claim 22, wherein the information server is operative to locate the at least one region of interest by forming a perimeter around each at least one segment at a distance.

29. The system of claim 28, wherein the perimeter enclosing the at least one segment is substantially elliptical.

30. The system of claim 29, wherein the distance from the substantially elliptical perimeter to each at least one segment is padded by adding a distance which is half the average length of the plurality of segments.

31. The system of claim 22, wherein the incident data comprises a description of at least one incident occurring at a single location.

32. The system of claim 31, wherein the single location is described utilizing a coordinate system.

33. The system of claim 32, wherein the coordinate system comprises latitudinal and longitudinal coordinates.

34. The system of claim 22, wherein the incident data comprises a description of at least one incident occurring at a multi-point location comprising a plurality of incident points.

35. The system of claim 34, wherein the plurality of incident points are described utilizing a coordinate system.

36. The system of claim 35, wherein the coordinate system comprises latitudinal and longitudinal coordinates.

37. The system of claim 22, wherein the incident data is limited to any incident within a predetermined area of the desired route.

38. The system of claim 31, wherein when the information server is operative to determine if the available incident has occurred on the at least one segment by determining if the incident corresponding to the incident data is closer than a threshold distance to the at least one segment.

39. The system of claim 38, wherein when the information server is operative to determine if the available incident has occurred on at least one segment by also:

forming a triangle from the available incident to the end points of any at least one segment closer than a threshold distance, wherein the base of the triangle is the segment; and

choosing any segment in which the angles of said triangle formed with the base are ninety degrees or less.

40. The system of claim 38, wherein when the information server is operative to determine if the available incident has occurred on at least one segment by also:

forming a triangle from the available incident to the end points of any at least one segment closer than a threshold distance, wherein the base of the triangle is the segment;

choosing any segment in which the angles of said triangle formed with the base are ninety degrees or less;

otherwise

if none of the segments forms a triangle in which the angles formed with the base are ninety degrees or less, choosing the closest of the segments to the available incident.

41. The system of claim 34, wherein the information server is operative for each available incident falling within at least one region to determine, if the available incident has occurred on at least one segment by also:

for each incident point, determining in sequential order if any of the incident points is closer than a threshold distance to any segment;

for a first incident point determined to be closer than the threshold distance, setting the segment to which the first incident point is closer than the threshold distance as the first segment of the incident on the desired route;

for each incident point, determining in reverse sequential order a second incident point which is closer than the threshold distance to any segment; and

for the second incident point, setting the segment to which the second incident point is closer than the threshold distance as the last segment of the incident on the desired route.

42. The system of claim 41, wherein the information server is operative to determine if none of the incident points is determined to be closer than the threshold distance to any segment, then to conclude the available incident does not fall on the desired route.

43. The system of claim 34, wherein the information server is operative to determine, if the available incident has occurred on at least one segment by also:

for each incident point, determining in sequential order if any of the incident points is closer than a threshold distance to any segment;

for a first incident point determined to be closer than the threshold distance, forming a triangle from the incident point to the end points of the segment closer than the threshold distance, wherein the base of the triangle is the segment;

setting the segment to which the first incident point is closer than the threshold distance and in which the angles of said triangle formed with the base are ninety degrees or less, as the first segment of the incident on the desired route;

for each incident point, determining in reverse sequential order a second incident point which is closer than the threshold distance to any segment;

for the second incident point determined to be closer than the threshold distance, forming a triangle from the second incident point to the end points of the segment closer than the threshold distance, wherein the base of the triangle is the segment; and

setting the segment to which the second incident point is closer than the threshold distance and in which the angles of said triangle formed with the base are ninety degrees or less, as the last segment of the incident on the desired route.

44. The system of claim 43, wherein the information server is operative to determine if none of the incident points is determined to be closer than the threshold distance to any segment, then to conclude that the available incident does not fall on the desired route.

46. The computer-readable medium of claim 45, wherein the desired route comprises at least one segment having end points located utilizing a coordinate system.

47. The computer-readable medium of claim 46, wherein the coordinate system comprises latitudinal and longitudinal coordinates.

48. The computer-readable medium of claim 47, wherein the mode of transportation used to traverse the desired route is chosen from the group consisting of:

ground vehicles, watercraft and aircraft.

49. The computer-readable medium of claim 45, wherein the predetermined region of interest is formed by drawing a perimeter around each at least one segment at a distance.

50. The computer-readable medium of claim 49, wherein the perimeter enclosing the at least one segment is substantially elliptical.

51. The computer-readable medium of claim 50, wherein the distance from the substantially elliptical perimeter to each at least one segment is padded by adding a distance which is half the average length of the plurality of segments.

52. The computer-readable medium of claim 45, wherein the incident data comprises a description of at least one incident occurring at a single location.

53. The computer-readable medium of claim 52, wherein the single location is described utilizing a coordinate system.

54. The computer-readable medium of claim 53, wherein the coordinate system comprises latitudinal and longitudinal coordinates.

55. The computer-readable medium of claim 45, wherein the incident data comprises a description of at least one incident occurring at a multi-point location comprising a plurality of incident points.

56. The computer-readable medium of claim 55, wherein the plurality of incident points are described utilizing a coordinate system.

57. The computer-readable medium of claim 56, wherein the coordinate system comprises latitudinal and longitudinal coordinates.

58. The computer-readable medium of claim 45, wherein the incident data is limited to any incident within a predetermined area of the desired route.

59. The computer-readable medium of claim 52, wherein comparing the incident data to the desired route comprises determining if the incident corresponding to the incident data is closer than a threshold distance to the at least one segment.

60. The computer-readable medium of claim 59, wherein comparing the incident data to the desired route further comprises:

forming a triangle from the available incident to the end points of any at least one segment closer than a threshold distance, wherein the base of the triangle is the segment; and

choosing any segment in which the angles of said triangle formed with the base are ninety degrees or less.

61. The computer-readable medium of claim 59, wherein comparing the incident data to the desired route further comprises:

forming a triangle from the available incident to the end points of any at least one segment closer than a threshold distance, wherein the base of the triangle is the segment;

choosing any segment in which the angles of said triangle formed with the base are ninety degrees or less;

otherwise

if none of the segments forms a triangle in which the angles formed with the base are ninety degrees or less, choosing the closest of the segments to the available incident.

62. The computer-readable medium of claim 55, wherein for each available incident falling within at least one region, comparing the incident data to the desired route further comprises:

for each incident point, determining in sequential order if any of the incident points is closer than a threshold distance to any segment;

for a first incident point determined to be closer than the threshold distance, setting the segment to which the first incident point is closer than the threshold distance as the first segment of the incident on the desired route;

for each incident point, determining in reverse sequential order a second incident point which is closer than the threshold distance to any segment; and

for the second incident point, setting the segment to which the second incident point is closer than the threshold distance as the last segment of the incident on the desired route.

63. The computer-readable medium of claim 62, further comprising:

if none of the incident points is determined to be closer than the threshold distance to any segment, then concluding the available incident does not fall on the desired route.

64. The computer-readable medium of claim 55, wherein comparing the incident data to the desired route further comprises:

for each incident point, determining in sequential order if any of the incident points is closer than a threshold distance to any segment;

for a first incident point determined to be closer than the threshold distance, forming a triangle from the incident point to the end points of the segment closer than the threshold distance, wherein the base of the triangle is the segment;

setting the segment to which the first incident point is closer than the threshold distance and in which the angles of said triangle formed with the base are ninety degrees or less, as the first segment of the incident on the desired route;

for each incident point, determining in reverse sequential order a second incident point which is closer than the threshold distance to any segment;

for the second incident point determined to be closer than the threshold distance, forming a triangle from the second incident point to the end points of the segment closer than the threshold distance, wherein the base of the triangle is the segment; and

setting the segment to which the second incident point is closer than the threshold distance and in which the angles of said triangle formed with the base are ninety degrees or less, as the last segment of the incident on the desired route.

65. The computer-readable medium of claim 64, further comprising:

if none of the incident points is determined to be closer than the threshold distance to any segment, then concluding the available incident does not fall on the desired route.

45. A computer-readable medium having a computer executable component for depicting incidents along a desired route, wherein the computer executable component depicts a desired route by:

obtaining incident data describing any available incidents within a particular geographic area;

comparing the incident data to the desired route to determine if any available incidents fall within a predetermined region of interest surrounding the desired route; and

depicting the desired route along with any available incidents determined to fall within the region of interest.