Find closest point on a Linestring to another point

Topics: Algorithms
Jun 8, 2007 at 6:04 PM
Hi everybody,

I'm working with the Pocket PC versions of SharpMap and NTS to implement a mobile navigation application. Before I can start with the path finding algorithm, I need to find the point somewhere on the road network, which is the closest Point to my GPS position. That's more or less a simple map matching. This point will be the starting point for the routing algorithm.

Until now I’ve got this nice function, which looks ok for me, but it isn’t doing what I want. There is probably some mistake in the for loop, but I just don’t get it.

Here is the offending piece of code:

Private Function matchPoint(ByVal dblX As Double, ByVal dblY As Double)
Dim dblDistance As Double
Dim dblDist_Alt As Double

Dim myNewCoord As TerraNova.NetTopologySuite.Geometries.Coordinate()
Dim myArcCoord As New TerraNova.NetTopologySuite.Geometries.Coordinate(0, 0)
Dim myShape As SharpMap.Data.Providers.ShapeFile = New SharpMap.Data.Providers.ShapeFile(STRROADSHAPEPATH2)
myShape.Open()

Dim currentPoint As New SharpMap.Geometries.Point(dblX, dblY)
Dim myPt As TerraNova.NetTopologySuite.Geometries.Geometry = SharpMap.Converters.NTS.GeometryConverter.ToNTSGeometry(currentPoint, New TerraNova.NetTopologySuite.Geometries.GeometryFactory())

Dim IDList As Generic.List(Of SharpMap.Geometries.Geometry)
IDList = myShape.GetGeometriesInView((myHybridMap.Envelope))

For Each geom As SharpMap.Geometries.Geometry In IDList

myArcs = SharpMap.Converters.NTS.GeometryConverter.ToNTSGeometry(geom, New TerraNova.NetTopologySuite.Geometries.GeometryFactory())

dblDistance = TerraNova.NetTopologySuite.Operation.Distance.DistanceOp.Distance(myPt, myArcs)

If dblDist_Alt > dblDistance Then
dblDist_Alt = dblDistance
myNewCoord = TerraNova.NetTopologySuite.Operation.Distance.DistanceOp.ClosestPoints(myPt, myArcs)

myArcCoord = myNewCoord(1)
Return myArcCoord
Else
Continue For

End If

Next geom


I hope, someone here can help me.

Thanks,
Madison
Jun 11, 2007 at 11:31 AM
Can nobody find the error in my code? Please help.
Thanks,
Madison
Jun 14, 2007 at 8:57 AM
Hi,

I'm working with the Pocket PC of the Sharpmap library. I don't know where is your error but I have a question for you:
so that you use NTS? or why do you use NTS?

Thanks in advanced
Developer
Jun 14, 2007 at 9:57 AM

I'm working with the Pocket PC versions of SharpMap and NTS to implement a mobile navigation application. Before I can start with the path finding algorithm, I need to find the point somewhere on the road network, which is the closest Point to my GPS position.


Try to look at the JTS documentation, as example:
http://www.google.it/search?hl=it&rlz=1B3GGGL_enIT219IT219&q=%2Bjts%2Bclosestpoint&btnG=Cerca&meta=
http://lists.jump-project.org/pipermail/jts-devel/2006-March/001536.html
Could be simple to translate this code in NTS

P.S: NTS for PPC is a very old version of NTS and maybe the results are not correct as you expect due to bugs... if you wish, we could work together for release a new version
Jun 16, 2007 at 4:37 PM
sorry, I didn't answer earlier, but I had a very busy couple of days. My function is a procedure now and looks like this:

Dim myShape2 As SharpMap.Data.Providers.ShapeFile = New SharpMap.Data.Providers.ShapeFile(STRROADSHAPEPATH2)
myShape2.Open()

Dim currentPoint As New SharpMap.Geometries.Point(dblX, dblY)
Dim myPt2 As TerraNova.NetTopologySuite.Geometries.Geometry = SharpMap.Converters.NTS.GeometryConverter.ToNTSGeometry(currentPoint, New TerraNova.NetTopologySuite.Geometries.GeometryFactory())

Dim myNewCoord As TerraNova.NetTopologySuite.Geometries.Coordinate()
Dim myArcCoord As New TerraNova.NetTopologySuite.Geometries.Coordinate(0, 0)

Dim dblDistance As Double
Dim dblMinDistance As Double = 30
Dim bbox As New SharpMap.Geometries.BoundingBox(dblX - 100, dblY - 100, dblX + 100, dblY + 100)

Dim IDList As Generic.List(Of SharpMap.Geometries.Geometry)
IDList = myShape2.GetGeometriesInView(bbox)

For Each geom As SharpMap.Geometries.Geometry In IDList

myArcs2 = SharpMap.Converters.NTS.GeometryConverter.ToNTSGeometry(geom, New TerraNova.NetTopologySuite.Geometries.GeometryFactory())

Try

dblDistance = TerraNova.NetTopologySuite.Operation.Distance.DistanceOp.Distance(myPt2, myArcs2)
Catch ex As InvalidCastException
MessageBox.Show("InvalidCastException: Überprüfe Variablen!")

End Try

If dblDistance > 0 Then
If dblMinDistance > dblDistance Then
dblMinDistance = dblDistance

myNewCoord = TerraNova.NetTopologySuite.Operation.Distance.DistanceOp.ClosestPoints(myPt2, myArcs2)
myArcCoord = myNewCoord(1)

End If
Else

myArcCoord.X = dblX
myArcCoord.Y = dblY

Exit For
End If
Next geom

It's actually working most of the times, but it's still somewhat slow. The restrictions derived from the bbox and the initial minimum distance help to increase the working speed a bit, but now I have to write some code, which increases the initial minimum and repeats the for loop, if there's no point in a distance lower than the minimum one.

@D_Guidi:
I really feel honoured, that you asked me that. I'd love to do that, but I think my programming skills are nowhere near up to this.
Well, I had found the second one of your links some time ago, and included the concerning LinearReferencing classes in my PocketNTS, but I don't think, I had to change that much. If you still want, we can talk about it in a month again, because I'm in the final phase of my diploma thesis just now.

So, back to that jump project link. the way which is described there seems to be more elegant than mine, but I'm not sure, if it's faster. Because the waiting time can be really annoying.

@VansFannel
Why I use NTS? Well, I use SharpMap for displaying my maps but as far as I know, you can't do much more with it. I'm developing (or trying to :-) ) an bicycle navigation application, i.e. it has to be able to do more than just display a map. Actually it should be able to work with spatial relationships like in my procedure you can see here, to the point, where it can calculate the shortest route from point A to point B.

Jun 18, 2007 at 10:38 PM
Hi Madison,

Thanks for your answer. As you can see I don't know very much about SharpMap and NTS.

I'm working on a Pocket Pc project that display a map and some POIs. The user can "click" on the Image and I need to know the Point(x, y) that the user has clicked. Any idea? I think that NTS can do it, so I ask upu about it.

Sorry for my English.

See you!
Coordinator
Jun 19, 2007 at 7:04 AM
All -

We're in the process of replacing the SharpMap geometries with the NTS geometries for the kind of spatial analysis you are looking for. Please check the changesets within the next few days (hopefully). It would be very helpful if you could use the new update, since it would help us test and improve it.
Jun 19, 2007 at 8:28 AM
Thanks!

And for Pocket PC? Why we don't mantain a port of SharpMap for Compact Framework? We can start using the port that was made for Pocket Terra.

It's an idea.

Bye
Developer
Jun 19, 2007 at 10:29 AM
The main problem with PocketTerra porting is that this port was terribly slow... :(
In any case, if we launch a PPC port of SharpMap/NTS, count on me for any help :D
Coordinator
Jun 19, 2007 at 10:47 AM
And the main problem with maintaining a Compact Framework port is the value given by the equation (amount of resources - amount of effort) is negative. However, now that D_Guidi is volunteering. ;)

What would be involved? What is the cause of the slowness? Is it heap usage or rendering or data access? My experience in developing in small packages is limited to robots, not PPCs running the CF, unfortunately, so while I know what the usual problems would be, I don't know how they'd be tackled in this case.
Developer
Jun 19, 2007 at 1:34 PM
I've played in the past months (uhhh... years?) with sharpMap/PocketTerra and the main problem is that rendering functions in CF 2.0 are not native but emulated via XrossGDIPlus library: i think it's the main cause for the slow performances :(
Jun 19, 2007 at 3:49 PM
Count on me too for any help!

I see there are limitations with graphics, matrix (no rotation). I think the slow performance is for Compact Framework graphics.
Coordinator
Jun 19, 2007 at 4:56 PM
Ah, good to know. With v2.0 of SharpMap, we could create a CF renderer, and use System.Drawing or even Managed DirectX. The latter is surprisingly good on PPC.