iOS iOS Foot of Perpendicular

[xArtx]

Hi Guys,
There are several Apps that can find the nearest public toilet to you,
and they work, obviously by measuring the distance between you,
and a database of toilets with iOS distance calcs discussed here before.

Can you find the closest street, or any line on a map closest to you with
native iOS features?

http://img.photobucket.com/albums/v186/ArtArt/Lines_zps840f16b8.jpg

If you try to look for the closest line point to identify the closest line,
the scenario in the image above is a disaster if the red dot is the current position.
So you need to calculate the foot of the perpendicular for every line segment.

I have implemented it.. basically how lock to road works,
but it's heavy, and if an iOS way is cheaper, I'd try it.
Also, I'd like to know if that functionality is available.
If not, I should put time into it.
Cheers, Art.

 

[ArtOfWarfare]

Distance between a line segment and a point shouldn't take very long at all... And finding the nearest segment would take linear time. I seem to recall writing a function to find the distance between a point and a line that didn't use trig or roots... I'll see if I can dig up the code later (on my iPhone right now.)

 

[xArtx]

Distance between a line segment and a point shouldn't take very long at all... And finding the nearest segment would take linear time. I seem to recall writing a function to find the distance between a point and a line that didn't use trig or roots... I'll see if I can dig up the code later (on my iPhone right now.)

The one I'm using only uses square roots:
http://blog.csharphelper.com/2010/0...-between-a-point-and-a-line-segment-in-c.aspx
It's cost depends on how many iterations.. like anything,
so any small saving in time would be a big one.

That diagram was done to explain to someone that it won't do to identify the
closest line by looking for the closest programatically defined point of a line,
and I did have that implemented.

What I found when looking for the distance to the FOP of every line segment
instead is you gain time, but only because you get to skip any calc on the
first point of any line, because it only looks at a complete segment with start and end points. If the line has a lot of points, time catches up though.

 

[Duncan C]

The one I'm using only uses square roots:
http://blog.csharphelper.com/2010/0...-between-a-point-and-a-line-segment-in-c.aspx
It's cost depends on how many iterations.. like anything,
so any small saving in time would be a big one.

That diagram was done to explain to someone that it won't do to identify the
closest line by looking for the closest programatically defined point of a line,
and I did have that implemented.

What I found when looking for the distance to the FOP of every line segment
instead is you gain time, but only because you get to skip any calc on the
first point of any line, because it only looks at a complete segment with start and end points. If the line has a lot of points, time catches up though.

Sigh. I answered this post, but my reply got lost somehow. Let me try again.

You need the square root to calculate the distance between a point and a line, but to compare distances, you can simply change the sqrt() to an fabs(). It's much faster, and longer distances will still yield larger numbers, so it's fine for comparison.

You should probably also calculate the length of a degree of longitude for your current latitude and adjust for the fact that the longitude/latitude grid is not at all square near the poles. (Put simply, convert from lat/long distance to kilometers distance, allowing for the fact that lines of longitude are closer together as you get closer to the poles.) See this wiki article.

 

[xArtx]

Sigh. I answered this post, but my reply got lost somehow. Let me try again.

Thanks, the function is only used to compare, I'm using Haversine at the end
for distance display for the user, so I can try it easily when I get home.

As for the curvature of the Earth, the App covers only a small area,
so I don't think it's so necessary. The distance ruler doesn't perceivably change
from the top of the map to the bottom.

 

[Duncan C]

Thanks, the function is only used to compare, I'm using Haversine at the end
for distance display for the user, so I can try it easily when I get home.

As for the curvature of the Earth, the App covers only a small area,
so I don't think it's so necessary. The distance ruler doesn't perceivably change
from the top of the map to the bottom.

So get rid of the square root and replace it with fabs(). That will make your comparisons much faster, since you will only be using multiplication, addition, and one division. (You might be able to factor out the division as well.)

Also convert your delta latitude and delta longitude both to kilometers, allowing for the latitude, before plugging your numbers into the distance formula. Otherwise in northern latitudes you'll think east-west distances are much longer than they really are (since lines of longitude get much closer together in northern latitudes, and MUCH closer together near the poles.)

 

[xArtx]

Also convert your delta latitude and delta longitude both to kilometers, allowing for the latitude, before plugging your numbers into the distance formula. Otherwise in northern latitudes you'll think east-west distances are much longer than they really are (since lines of longitude get much closer together in northern latitudes, and MUCH closer together near the poles.)

Hang on, I thought we already went there.
It would expand me, but for a sole 32Km square tile (a single National Park),
it would only cripple the App, and take back the time you just gave me
The error in neglecting the longitude difference top to bottom of a tile
that size would be small compared to error already present in Haversine distance calcs
(unless you get very close to either pole I suppose).

 

[Duncan C]

Hang on, I thought we already went there.
It would expand me, but for a sole 32Km square tile (a single National Park),
it would only cripple the App, and take back the time you just gave me
The error in neglecting the longitude difference top to bottom of a tile
that size would be small compared to error already present in Haversine distance calcs
(unless you get very close to either pole I suppose).

I don't see why it would cripple you. If these points and line segments are in the same part of the world you could do a one-time calculation of kilometers-per-degree at the beginning and use that same value for all your calculations.


The distance per degree of longitude changes a LOT with latitude:

0° 110.574 km 111.320 km
15° 110.649 km 107.551 km
30° 110.852 km 96.486 km
45° 111.132 km 78.847 km
60° 111.412 km 55.800 km
75° 111.618 km 28.902 km
90° 111.694 km 0.000 km

Edinburgh, Scotland is at 55.9° north. It's distance-per-degree longitude is going to be around 70 km or less than 2/3 of the latitude distance.

Nome, Alaska is at 64° N. At that latitude degrees of latitude are almost twice as long as degrees of longitude, so you would over-represent east-west distances by almost by 2:1.

 

[xArtx]

I don't see why it would cripple you. If these points and line segments are in the same part of the world you could do a one-time calculation of kilometers-per-degree at the beginning and use that same value for all your calculations.


The distance per degree of longitude changes a LOT with latitude:

0° 110.574 km 111.320 km
15° 110.649 km 107.551 km
30° 110.852 km 96.486 km
45° 111.132 km 78.847 km
60° 111.412 km 55.800 km
75° 111.618 km 28.902 km
90° 111.694 km 0.000 km

Edinburgh, Scotland is at 55.9° north. It's distance-per-degree longitude is going to be around 70 km or less than 2/3 of the latitude distance.

Nome, Alaska is at 64° N. At that latitude degrees of latitude are almost twice as long as degrees of longitude, so you would over-represent east-west distances by almost by 2:1.

It doesn't change a lot over a 32km square tile though.

I see what you mean with the calculation though.

 

[Duncan C]

It doesn't change a lot over a 32km square tile though.

I see what you mean with the calculation though.

Exactly. Figure out the km/degree once at the beginning, and use the same multipliers for everything. You have to travel a long way to make the numbers change very much, and in most apps you operate in one local area. (One city, one park, one county/province/parish, or whatever.)

 

[xArtx]

Exactly. Figure out the km/degree once at the beginning, and use the same multipliers for everything. You have to travel a long way to make the numbers change very much, and in most apps you operate in one local area. (One city, one park, one county/province/parish, or whatever.)

This is the first time I've posted understanding you mean there is a difference
between the real value of one degree of lat, and one degree of long for every
calculation you make.

Sorry, I had it stuck in my head that you were on about the difference in long
at the top of a tile and long at the bottom of a tile (which is moot as the kids say).

I needed to be away from the computer to think about it.

So at the moment it compares distances on a square grid,
and displays distance figures calculated over the sphere.
I hope you can help me if I get stuck! The App is waiting for review now.
I can't do anything until I sort out my expired profile.

Luckily, the map tile is a little below Brisbane, Queensland, Australia.

Forgive the blurb, it's for a website. I got a commercial GPS that can load a converted
version of the detail file used in the App. The four same Sat image tiles too.
It has to run on the same batteries all day, so is too dumb to calc the distances
of everything for every frame, but can do one by one calcs.
I will be able to compare by measuring distances between exactly the same points.