Java: Nearest neighbour snap-to-path problem

Description
I'm working on a free app to provide some post-race metrics to racing drivers. It's actually already published in beta form <a href="https://play.google.com/store/apps/details?id=com.betaminus.bridgetogantry">here</a>. I have an array of data representing points on a racing track, and I have GPS coordinates and a time for where the driver actually is. What I need to do is merge these pieces of data - for each piece of real GPS data, I'd like to snap it to a known track point and store a time along with that.<div><br></div><div>Right now I have it working using a rather terrible algorithm. When I get the GPS location of the car, I just loop through my track points looking for the nearest one. Once I find it, I just store the current time as the driver's time at that location. However, this isn't a very effective algorithm - some of these points are up to 50m apart, and if the driver is in between two of them the time I'm storing is rather inaccurate.</div><div><br></div><div>What I need to do is some sort of interpolation. Let's say the user was nearest to point151 when they were 11520ms into the lap - I'd like to store their time to reach point151, but as they weren't exactly on top of point151, I need a routine to look at the points the user was between and extrapolate what estimated time to store with it.</div><div><br></div><div>To provide some real track data, here are some latitudes and longitudes from the circuit (taken straight from my data file):</div><div><br></div><div><pre>&lt;ns1:trkpt lat="50.3380166099213" lon="6.95193950979551" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3380062675389" lon="6.95191388176543" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3379957595993" lon="6.95188850286812" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.337985094874" lon="6.95186337482174" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3379742722664" lon="6.95183848559918" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3379632950658" lon="6.9518138369186" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3379521687542" lon="6.95178943565263" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3379409196454" lon="6.95176531788257" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3379295839205" lon="6.95174145783607" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3379181944719" lon="6.95171785035864" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3379068017341" lon="6.95169443359665" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3378954429847" lon="6.95167114397827" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3378841434413" lon="6.95164799353061" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.3378729381886" lon="6.95162499428077" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.337861822841" lon="6.9516020482938" name="T13"/&gt;<br>&lt;ns1:trkpt lat="50.337850844544" lon="6.95157912979734" name="T13"/&gt;</pre></div><div><br></div><div>Here's some 1Hz user data driving through those points (starting some time before the sample section and ending some time after):</div><div><br></div><div><pre>&lt;trkpt lat="50.3397496" lon="6.95531779" timems="1121000" /&gt;<br>&lt;trkpt lat="50.33950633" lon="6.9550101"&nbsp;timems="1122000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33925474" lon="6.9546348"&nbsp;timems="1123000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33905295" lon="6.95429496"&nbsp;timems="1124000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33884795" lon="6.9539545"&nbsp;timems="1125000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33864306" lon="6.95361408"&nbsp;timems="1126000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33847615" lon="6.9534302"&nbsp;timems="1127000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33835164" lon="6.95352938"&nbsp;timems="1128000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33822384" lon="6.95342014"&nbsp;timems="1129000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33813311" lon="6.95327948"&nbsp;timems="1130000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33803794" lon="6.95311709"&nbsp;timems="1131000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33806849" lon="6.95288742"&nbsp;timems="1132000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33809851" lon="6.9526515"&nbsp;timems="1133000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33810632" lon="6.95239526"&nbsp;timems="1134000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33806433" lon="6.95215214"&nbsp;timems="1135000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33796515" lon="6.95187056"&nbsp;timems="1136000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33784908" lon="6.95160509"&nbsp;timems="1137000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33775417" lon="6.95139649"&nbsp;timems="1138000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33768453" lon="6.95123702"&nbsp;timems="1139000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33765852" lon="6.95113942"&nbsp;timems="1140000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33766282" lon="6.95105284"&nbsp;timems="1141000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33769396" lon="6.95094115"&nbsp;timems="1142000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33775149" lon="6.95080879"&nbsp;timems="1143000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33784332" lon="6.95063043"&nbsp;timems="1144000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33794861" lon="6.95042364"&nbsp;timems="1145000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33805339" lon="6.95021855"&nbsp;timems="1146000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33818716" lon="6.9499658"&nbsp;timems="1147000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33833022" lon="6.94971674"&nbsp;timems="1148000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33848778" lon="6.94946282"&nbsp;timems="1149000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33866403" lon="6.9492251"&nbsp;timems="1150000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33884954" lon="6.94901455"&nbsp;timems="1151000"&nbsp;/&gt;<br>&lt;trkpt lat="50.3390533" lon="6.94879301"&nbsp;timems="1152000"&nbsp;/&gt;<br>&lt;trkpt lat="50.33920326" lon="6.94862311"&nbsp;timems="1153000"&nbsp;/&gt;</pre></div><div><br></div><div>What I'd ideally like is a routine where I pass in a latitude and longitude and a list of points, and it will calculate the nearest point, and the time in ms that the driver would have been at that point, and store it. The way my data is currently stored, the track data is in this class:</div><div><br></div><div><pre>public class TrackCrumb {<br><span class="Apple-tab-span" style="white-space:pre"> </span>public double lat, lon;<br><span class="Apple-tab-span" style="white-space:pre"> </span>public long timeAt;<br>}</pre></div><div><br></div><div>So I'd like a routine with a prototype something like:</div><div><br></div><div><pre>private void storeNearestPoint(double lat, double lon, long timems,&nbsp;<br><span class="Apple-tab-span" style="white-space:pre"> </span>List&lt;TrackCrumb&gt; trackdata) {<br>}</pre></div><div><br></div><div>Any help very much appreciated!</div>
Discussion
  • {{comment.username}}
Status
Active
submission(s) pending review
Bounty expires in
Bounty expired
Bounty
0
Tags
(no tags)