Tell me more ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.
up vote 2 down vote favorite

I'm implementing alghorithm to search POI near the route (array of Lat, Long points). My problem is that I don't know how to calculate distance beetween line segment and POI. Look at picture that I attached. Can somebody give me some formula for fast calculation this distance?

Notes: Using PHP and MySQL with Spatial Extension.

Look at picture

Assumptions:
- I have database of POI with lat, long - 
- I have array of points (lat, long) in correct (drive) order - route
- The calculations will be made on max 20 km area so flat surface assumption is ok.
- The POI must be returned in order that the driver will be passing the route.

Any ideas?

share|improve this question
you want to implemente it completely by your own? It seems like simple math problem then, maybe this would help: math.ucsd.edu/~wgarner/math4c/derivations/distance/… or paulbourke.net/geometry/pointline that also contains source code – Mykolas Simutis Sep 6 '11 at 13:26
Yes I want to implement it completely. The problem is that I don't know if I can use formulas from the websites above because of lat,lng coordinate system. In those sites there is no example how to calculate with latitude and longitude values. – Marcin Sep 6 '11 at 13:37
Is the "array of points (lat,long) - route" ordered in the same direction "that the driver will be passing"? – Allan Adair Sep 6 '11 at 14:25
Yes. The array of points that represent the route is ordered in the same direction "that the driver will be passing" – Marcin Sep 7 '11 at 6:37

2 Answers

up vote 1 down vote

You don't specify what programming language/database/GIS system you are using, so you'll only get a generic answer. A quick googling turned up this site which explains the maths in sufficient detail to code up a solution.

Without any form of spatial partitioning, the number of tests will be combinatorial, because you'll need to check every PoI against every line segment, discarding all but the nearest. You also won't be able to discard PoIs that have been previously found because a PoI could be the closest for more than one line segment.

I suggest you clarify what type of system you are using because SE users tend to disregard vague or open questions. Also, think about doing a general search using a search engine before asking this type of question.

share|improve this answer
I'm using PHP and MySQL with Spatial Extension. The POI data is filtered and fetched very fast from the database. More accurate calculations will be in PHP such as this alghorithm for calculate shorthest distance from point to the route. I was also digging in internet and found that this distance is also called Cross Track Error. – Marcin Sep 6 '11 at 13:42
up vote 0 down vote

I would suggest putting all your cities and your route into psql + postgis database. The cities will be (lon, lat) points and you split your route in separate parts as LINESTRINGs. So from point 0 to 1 will be a linestring 1, from point 1 to point 2 will be linestring 2, etc.

Postgis offers a simple function called ST_Distance (see: ST_Distance).

This calculates the distance between 2 geometries. If you query the distance between all your cities and route parts and limit this to how close you want to detect a city to your route, you are done. You don't actually need to understand how to calculate the distance between a point and a line. This function does it for you.

share|improve this answer
I know that PostgreSQL have more powerful extension for spatial analysis but in this scenario I can't use even PostgreSQL. There is only MySQL on this hosting provider. The route in MySQL is written as Point Geometry and I have Spatial Index on this column. Using some joins technique with my POI points is great way to filter huge amount of unnecessery POI points for the route (array of points in some order) – Marcin Sep 6 '11 at 13:51
I don't know how many possible points (cities) you have and what language you program, but it should be fairly easy to find a function on the net that calculates the distance between a line and a point. If you do this with the line pieces as i described above you are sure to get them in the right order. Unless you have some realtime timing constraints this should be doable for quite a few thousand poi's. – mrg Sep 6 '11 at 14:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.