Method and system for matching an incident to a route

• US 6,353,795 B1
• Filed: 02/01/2000
• Issued: 03/05/2002
• 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:
  US09/495,812
• Time in Patent Office: 763 Days
• Field of Search: 701/202, 701/200, 701/210, 701/211, 701/117, 701/113, 340/905, 340/988, 340/989, 340/935
• 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 comprising a description of at least one incident occurring at a single location;

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 by;

determining if the incident corresponding to the incident data is closer than a threshold distance to the at least one segment;

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; and

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

2. 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 comprising a description of at least one incident occurring at a single location;

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 by;

determining if the incident corresponding to the incident data is closer than a threshold distance to the at least one segment;

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; and

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

3. 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 comprising a description of at least one incident occurring at a multi-point location comprising a plurality of incident points;

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 by;

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; and

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

4. The method of claim 3, 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.

5. 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 comprising a description of at least one incident occurring at a multi-point location comprising a plurality of incident points;

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 by;

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; and

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

6. The method of claim 5, 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.

7. 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 comprising a description of at least one incident occurring at a single location 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 by;

determining if the incident corresponding to the incident data is closer than a threshold distance to the at least one segment;

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; 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.

8. 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 comprising a description of at least one incident occurring at a single location 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 by;

determining if the incident corresponding to the incident data is closer than a threshold distance to the at least one segment;

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; 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.

9. 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 comprising a description of at least one incident occurring at a multi-point location comprising a plurality of incident points 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 by;

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; 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.

10. The system of claim 9, 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.

11. 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 comprising a description of at least one incident occurring at a multi-point location comprising a plurality of incident points 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 by;

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; 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.

12. The system of claim 11, 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.

13. 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 comprising a description of at least one incident occurring at a single location;

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 wherein comparing the incident 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;

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; and

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

14. 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 comprising a description of at least one incident occurring at a single location;

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 wherein comparing the incident 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;

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; and

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

15. 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 comprising a description of at least one incident occurring at a multi-point location comprising a plurality of incident points;

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 wherein comparing the incident data to the desired route 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; and

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

16. The computer-readable medium of claim 15, 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.

17. 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 comprising a description of at least one incident occurring at a multi-point location comprising a plurality of incident points;

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 wherein comparing the incident data to the desired route 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; and

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

18. The computer-readable medium of claim 17, 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.