Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
1999-06-25
2001-07-17
Zanelli, Michael J. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S201000, C701S211000, C340S995190
Reexamination Certificate
active
06263278
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computerized mapping software programs, and more specifically, to computerized mapping software programs that calculate a route between multiple destinations and allow alterations to the calculated route.
BACKGROUND OF THE INVENTION
Computerized mapping products are achieving widespread use today. Such mapping programs are commonly used to automate the task of calculating a route from a starting destination to an ending destination. For the purpose of this discussion, the term “destination” means a point or location on the map at which the user indicates a desire to either start a trip, end the trip, or visit along the trip. A destination may also be known by other names, such as via, vertex, node, stop, or the like. Most mapping programs allow a user to include additional destinations to be visited along the route. The route is typically displayed in a graphical format, allowing the user to visualize the trip. However, existing mapping programs suffer from several problems related to altering a route once it has been calculated.
First, existing mapping programs do not provide a simple mechanism for a user to add a destination to a trip after the route has already been calculated. In other words, if the user identifies some number of destinations to be visited on a trip and then calculates a route to visit all of those destinations, the user cannot easily add a new destination to the trip or substitute a new destination for an existing destination. One reason for the difficulty is that the mapping program must be able to identify where along the route a new destination should be inserted. When adding a new destination, the mapping program must insert the new destination at a point that ensures the new route is reasonably efficient. That task is much more computationally burdensome than it might at first appear.
Computing an ideal order for the destinations to be visited prior to calculating the new route is a problem that mapping-program designers struggle with constantly. Those skilled in the art will appreciate that if a mapping program must compute an ideal order for the destinations, the time required to perform that computation results in an undesirable delay to the user. As a result, most mapping programs simply do not compute a new order, but, rather, add the new destination to the end of the list of existing destinations, which most often results in disjointed routes that are not practical. It would be preferable to allow the user to directly identify the order in which the destinations are visited and, ideally, without undue delay to the user. However, with existing mapping programs, allowing the user to directly identify the order requires substantial manual input and is not intuitively achieved. With existing mapping programs, the user must perform the several steps of deleting an existing destination, inserting the new destination (and possibly having to manually reorder the destinations), and then calculating the entire route anew.
Another problem with existing mapping programs is that imperfect data sometimes results in a route that is impassable. For example, if a one-way street is incorrectly identified as two-way in the mapping data, the mapping program may calculate a route that travels the wrong way down that one-way street. Although the user may have personal knowledge of the inaccuracy, existing mapping programs do not allow the user to easily redirect the route around the one-way street.
Yet another problem with existing mapping programs is that they do not easily allow the user to redirect the route along an alternative path. Often, the user may have a desire to include a particular street or highway along the route as an alternative to those calculated. Perhaps the desired highway borders an ocean or a lake and provides a pleasant view. Perhaps the user has personal knowledge of construction occurring along the calculated route. Existing mapping programs are unable to easily accommodate the user's desire. For two given destinations, the mapping program calculates the same route every time based on route-selection criteria defined in the mapping program. Existing mapping programs do not have a mechanism for easily allowing the user to override the route-selection criteria for a portion of the route and thereby redirect that portion of the route to an alternative path.
Still another problem with existing mapping programs is the situation where a user attempts to calculate a route between generally-described destinations, such as between two cities. Often, the user provides to the mapping program the name of a city as a destination without a more specific descriptor, such as an address. In that case, the mapping program is forced to pick an arbitrary destination within the city, often a pre-selected “city center,” the centroid of the city or a famous landmark, for the destination of the route. The user may desire to move the pre-selected destination to a more accurate destination, such as a particular address or building. With existing mapping programs, the user cannot easily relocate the arbitrarily selected destination without reentering the destinations with the more specific descriptors.
Those and other problems render the existing systems and methods less than satisfactory. Until now, an adequate solution to those problems has eluded those skilled in the art. Accordingly, there is a need for a system or method of allowing a user to input, in a simple manner, additional or alternative destinations to be visited along a pre-calculated route. The system or method should also provide the ability to redirect a portion of the calculated route if desired.
SUMMARY OF THE INVENTION
The present invention overcomes the problems identified above by providing a system and method for altering a portion of a pre-calculated route by allowing a user to graphically indicate the portion of the route to alter. The user indicates the portion to be altered by navigating a pointer to a point along a graphical representation of the route and selecting the point. The point identifies which portion of the route is to be altered. The user may then alter the route by dragging and dropping the selected portion to a new destination. In essence, the user redirects the route to the new destination by dragging the selected portion of the route to the new destination.
In this manner, the user is able to add a new destination to be visited by simply dragging a portion of the route to the new destination. The need for the mapping program to calculate which portion of the route to alter is eliminated because the user selects the appropriate portion directly. In short, the present invention allows a mapping program to identify the appropriate portion of a pre-calculated route to alter based on the user's first selection, and to identify a new destination through which the route will be redirected based on where the user drops the route. The portion may be either a destination along the route or part of the route itself The invention simplifies the act of replacing an existing destination with a new destination. The user drags the route from an existing destination to a new destination, which results in replacing the existing destination with the new destination in one simplified and intuitive step.
One advantage of the present invention is that the entire route need not be completely recalculated each time an alteration is made. Only the portion of the route that was altered need be recalculated. In other words, if a pre-calculated route travels from point one to point two to point three, and the user graphically selects the portion of the route between point two and point three, then only the portion of the route between point two and point three need be recalculated, not the entire route. Consequently, not only does the present invention simplify the task of altering a portion of the route, the computational time for recalculating the altered route is shortened as well.
Another advantage of the present invention is that
Berry Nicholas
Nikiel Mark A.
Christensen O'Connor Johnson & Kindness PLLC
Microsoft Corporation
Zanelli Michael J.
LandOfFree
System and method for graphically altering a pre-calculated... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for graphically altering a pre-calculated..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for graphically altering a pre-calculated... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2555657