# Finding the Starting Point of a Route

• 08-19-2003
Anonymous
Finding the Starting Point of a Route
Nico Bontenbal shares a method for determining the starting point of a route by examining the pixels in the map image using Window API calls

http://www.mp2kmag.com/images/articles/nico/map2.gif
• 08-22-2003
Anonymous
Nico,

I was exploring a similar method a couple of months back after deciding the extrapolation method was simply too slow to be practical. After kicking around several approaches, I decided the image analysis approach was feasible, but didn't take the time to finish writing it.

One major suggestion:

If you change the map display to "Data Map" and turn off the map layers, the route line is displayed very clearly. So clearly in fact, that if you cut and paste to an image buffer, it's fairly straightforward to determine the straight line that runs through the center of the route line in pixel coordinates. And since you're analyzing the image buffer, there's no impact on the map redrawing and flashing.

In order to convert to lat / long, just get the lat / long coords of the bounding region previously copied to the image buffer and extrapolate. It's not precise, but over even fairly sizeable areas, it works very well.

One minor suggestion:

Rather than just determine the straight line, I had planned to identify the "turn" nodes, feed them into a curve fitting algorithm and represent the route path as an equation rather than a series of line segments. That way, you can draw the line at any level of detail instead of being stuck with the original screen capture. We plan on using this technique to display route lines for multiple days at a time on the map.

We've been holding off until the MP 2004 release before coding, just to make sure that methods haven't been introduced to make all the preceding unnecessary.

Cheers,
Chris
• 08-22-2003
Mattys Consulting
Hi Nico and Group,

I could very well be wrong, but I did not find using the API necessary because
using Gilles' CalcPos determined the coordinates very well.

Here's an example:

Iterating through WayPoints, I select a SegmentDirection
oRoute.Waypoints(intWpt).SegmentDirections(intDir) .Select

To be sure that MapPoint changes selection, I force the issue
Call oMapCtl_SelectionChange (oRoute.Waypoints(intWpt).SegmentDirections(intDir ).Location, oMap.Location)

I save the calculation from CalcPos in DirLat and DirLong,
which can also be made public properties were I to need them.

'Declarations Section of cMapPt

Private dblDirLat As Double
Private dblDirLong As Double
Private DirLat As Double
Private Dirlong As Double

'Event Proc of MapPoint ActiveX
Private Sub oMapCtl_SelectionChange (ByVal NewSelection As Object, ByVal OldSelection As Object)

CalcPos oMap, NewSelection.Location, dblCtrLat, dblCtrLong
Debug.Print dblCtrLat & ", " & dblCtrLong
DirLat = dblCtrLat
Dirlong = dblCtrLong

End Sub

Michael R Mattys
www.mattysconsulting.com
• 08-26-2003
nicob
Chris,

<<If you change the map display to "Data Map" and turn off the map layers, the route line is displayed very clearly.>>
Great suggestion.

<<So clearly in fact, that if you cut and paste to an image buffer, it's fairly straightforward to determine the straight line that runs through the center of the route line in pixel coordinates. And since you're analyzing the image buffer, there's no impact on the map redrawing and flashing.>>
I've been thinking about a solution like this. I thought about saving the map as a jpg image, but I suppose copy paste is faster.

<<We've been holding off until the MP 2004 release before coding, just to make sure that methods haven't been introduced to make all the preceding unnecessary.>>
I believe it is in MapPoint.Net, so maybe it will be in 2004 also. Just a few weeks and we'll know.

Thanks,

Nico
• 08-26-2003
nicob
Michael,

<<I could very well be wrong, but I did not find using the API necessary because using Gilles' CalcPos determined the coordinates very well.>>
Yes but this finds the middle of the route segment. Not the starting point. The title of the article is not entirely correct. It should have been something like: 'finding the starting point of each direction of a route'.

Thanks,

Nico
• 08-27-2003
Mattys Consulting
Hi Nico

<Yes but this finds the middle of the route segment. Not the starting point. >

Confirmed. In fact, I added pushpins to each one and it's even
worse than middle, it's within about a mile if you're lucky.

I have another idea I'd like to try out ...
will get back to you shortly.

Mike Mattys
• 08-29-2003
Anonymous
an alternative algorithm for finding the intersection route
Nico and I have communicated re the algorithm below privately, but I wished to make it public in hopes of obtaining some comments from others. It's in visual foxpro (which looks enough like VB that no one familiar with VB should have any trouble with it), and it's a function which returns a location object which represents the intersection points of 2 adjacent route segments.

In my limited testing it has worked well for me, but there's nothing like testing by others, so please do and let me know what you think.

Chip Orange

(corange@psc.state.fl.us or acorange@comcast.net)

---------
FUNCTION FindIntersection
* return the location object of an intersection of 2 roads, each represented by a location object somewhere on the road.
LPARAMETER oOrgLoc, oLoc, nMaxSecs
LOCAL oRoute, lnSeparation, lnLastSeparation
* now, walk the end point of our route back towards us until it stops moving
lnStartSecs = Seconds()
oRoute = goMap.ActiveRoute
lnSeparation = oOrgLoc.DistanceTo(oLoc)
lnLastSeparation = 100000
DO WHILE Abs(lnSeparation-lnLastSeparation) > 0.001 AND ;
Seconds()-lnStartSecs < nMaxSecs
oRoute.Clear
oRoute.Calculate
lnLastSeparation = lnSeparation
* now move the end point closer to us by using the location object of the 2nd route segment as the next end point.
oLoc = oRoute.Directions(2).Location
lnSeparation = oOrgLoc.DistanceTo(oLoc)
* and now, if it hasn't moved much, it's as close to us on the MapPoint road as it's likely to get.
ENDDO
RETURN oLoc
• 09-12-2003
nicob
Another method?
When experimenting with Chip's algorithm, I found another feature of Mappoint that might make it possible to find the starting point of a route segment. While browsing the Mappoint object model I found that the Direction object also has a DistanceTo method. This returns the distance between a point and the point on the route closest to this point. So the starting point of direction 2 should be a point that has a distance of (almost) 0 to direction 2, and to direction 1. The staring point of direction 3 is a point with a distance of 0 to direction 2, and direction 3.
The trick is to find this point. I'm thinking of the following algorithem.
1. Draw a square around the location of a direction with a size half the length of the direction, the starting point of the direction should be within this square.
2. Draw 10 horizontal and 10 vertical lines inside the square, for each crossing point of these lines determine the combined distance to the direction, and the previous direction. The crossing point with the smallest combined distance is likely to be close to the intersection of the two segments.
3. Draw a new circle around this point 1/5 the size of the previous square.
4. Repeat steps 2 and 3 until the combined distance is (almost) 0.

This is only theory. Because I only program Mappoint 'for fun' I don't think I'll ever explore this technique any further. The solution I described in my article is sufficient for me. There probably are some pitfalls with this technique (if possible at all). One will be tunnels that make it possible for two directions to cross each other. But I think this technique deserves some exploration. And if not for this technique, there are probably some other good uses for the DistanceTo method of a direction.

Nico
• 09-12-2003
PC
Finding Starting Point of Route
DistanceTo will only be any good if you have no waypoint other than start and finish in the route(unless your using 2004 and this bug been Fixed??? Can anyone tell us)

Otherwise it should be fairly easy to iterate away from the centre point ( the location of the segment) until both ends are found, i.e there is no iteration that does not increase the distance from the route.

PC
• 10-14-2003
Anonymous
Here are my suggestions for improving this code:

Store the initial objmap.location before you start manipulating the map. Restore when finished.
Store initial map style before changing to data style. Restore when finished.
If the current route segment is not found using Nico's method the first time try increasing the altitude.

Also if you want to store the anchors when available you can do the following:

<START PSEUDO CODE>
Code:

```Store all the route waypoint anchors in an array. Iterate through each anchor pair calculating the route between them         Store location of beginning anchor.           Make sure this location is not the same &#40;+- 0.0001 Lat of Long&#41; as previous &#40;needed if sending data to GPS&#41;           Store locations as previous location         Store the starting location of each route segment.           Make sure this location is not the same &#40;+- 0.0001 Lat of Long&#41;  as previous &#40;needed if sending data to GPS&#41;           Store locations as previous location         Store  the location of ending anchor.           Make sure this location is not the same &#40;+- 0.0001 Lat of Long&#41;  as previous &#40;needed if sending data to GPS&#41;           Store locations as previous location Restore original route from array of anchors```
<END PSEUDO CODE>

Hope this helps.

Hypercubed