iOS Foot of Perpendicular

Discussion in 'iOS Programming' started by xArtx, Apr 17, 2013.

  1. xArtx macrumors 6502a

    Joined:
    Mar 30, 2012
    #1
    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.
     
  2. ArtOfWarfare macrumors 604

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #2
    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.)
     
  3. xArtx thread starter macrumors 6502a

    Joined:
    Mar 30, 2012
    #3
    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.
     
  4. Duncan C macrumors 6502a

    Duncan C

    Joined:
    Jan 21, 2008
    Location:
    Northern Virginia
    #4
    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.
     
  5. xArtx thread starter macrumors 6502a

    Joined:
    Mar 30, 2012
    #5
    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.
     
  6. Duncan C macrumors 6502a

    Duncan C

    Joined:
    Jan 21, 2008
    Location:
    Northern Virginia
    #6
    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.)
     
  7. xArtx thread starter macrumors 6502a

    Joined:
    Mar 30, 2012
    #7
    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).
     
  8. Duncan C macrumors 6502a

    Duncan C

    Joined:
    Jan 21, 2008
    Location:
    Northern Virginia
    #8
    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.
     
  9. xArtx thread starter macrumors 6502a

    Joined:
    Mar 30, 2012
    #9
    It doesn't change a lot over a 32km square tile though.

    I see what you mean with the calculation though.
     
  10. Duncan C macrumors 6502a

    Duncan C

    Joined:
    Jan 21, 2008
    Location:
    Northern Virginia
    #10

    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.)
     
  11. xArtx, Apr 22, 2013
    Last edited: Apr 22, 2013

    xArtx thread starter macrumors 6502a

    Joined:
    Mar 30, 2012
    #11
    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.
    [​IMG]
    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.
     

Share This Page