001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.gpx;
003
004import java.util.ArrayList;
005import java.util.Date;
006import java.util.List;
007import java.util.concurrent.TimeUnit;
008
009import org.openstreetmap.josm.spi.preferences.Config;
010import org.openstreetmap.josm.tools.Logging;
011import org.openstreetmap.josm.tools.Pair;
012
013/**
014 * Correlation logic for {@code CorrelateGpxWithImages}.
015 * @since 14205
016 */
017public final class GpxImageCorrelation {
018
019    private GpxImageCorrelation() {
020        // Hide public constructor
021    }
022
023    /**
024     * Match a list of photos to a gpx track with a given offset.
025     * All images need a exifTime attribute and the List must be sorted according to these times.
026     * @param images images to match
027     * @param selectedGpx selected GPX data
028     * @param offset offset
029     * @param forceTags force tagging of all photos, otherwise prefs are used
030     * @return number of matched points
031     */
032    public static int matchGpxTrack(List<? extends GpxImageEntry> images, GpxData selectedGpx, long offset, boolean forceTags) {
033        int ret = 0;
034
035        long prevWpTime = 0;
036        WayPoint prevWp = null;
037
038        List<List<List<WayPoint>>> trks = new ArrayList<>();
039
040        for (IGpxTrack trk : selectedGpx.tracks) {
041            List<List<WayPoint>> segs = new ArrayList<>();
042            for (IGpxTrackSegment seg : trk.getSegments()) {
043                List<WayPoint> wps = new ArrayList<>(seg.getWayPoints());
044                if (!wps.isEmpty()) {
045                    //remove waypoints at the beginning of the track/segment without timestamps
046                    int wp;
047                    for (wp = 0; wp < wps.size(); wp++) {
048                        if (wps.get(wp).hasDate()) {
049                            break;
050                        }
051                    }
052                    if (wp == 0) {
053                        segs.add(wps);
054                    } else if (wp < wps.size()) {
055                        segs.add(wps.subList(wp, wps.size()));
056                    }
057                }
058            }
059            //sort segments by first waypoint
060            if (!segs.isEmpty()) {
061                segs.sort((o1, o2) -> {
062                    if (o1.isEmpty() || o2.isEmpty())
063                        return 0;
064                    return o1.get(0).compareTo(o2.get(0));
065                });
066                trks.add(segs);
067            }
068        }
069        //sort tracks by first waypoint of first segment
070        trks.sort((o1, o2) -> {
071            if (o1.isEmpty() || o1.get(0).isEmpty()
072             || o2.isEmpty() || o2.get(0).isEmpty())
073                return 0;
074            return o1.get(0).get(0).compareTo(o2.get(0).get(0));
075        });
076
077        boolean trkInt, trkTag, segInt, segTag;
078        int trkTime, trkDist, trkTagTime, segTime, segDist, segTagTime;
079
080        if (forceTags) { //temporary option to override advanced settings and activate all possible interpolations / tagging methods
081            trkInt = trkTag = segInt = segTag = true;
082            trkTime = trkDist = trkTagTime = segTime = segDist = segTagTime = Integer.MAX_VALUE;
083        } else {
084            // Load the settings
085            trkInt = Config.getPref().getBoolean("geoimage.trk.int", false);
086            trkTime = Config.getPref().getBoolean("geoimage.trk.int.time", false) ?
087                    Config.getPref().getInt("geoimage.trk.int.time.val", 60) : Integer.MAX_VALUE;
088            trkDist = Config.getPref().getBoolean("geoimage.trk.int.dist", false) ?
089                    Config.getPref().getInt("geoimage.trk.int.dist.val", 50) : Integer.MAX_VALUE;
090
091            trkTag = Config.getPref().getBoolean("geoimage.trk.tag", true);
092            trkTagTime = Config.getPref().getBoolean("geoimage.trk.tag.time", true) ?
093                    Config.getPref().getInt("geoimage.trk.tag.time.val", 2) : Integer.MAX_VALUE;
094
095            segInt = Config.getPref().getBoolean("geoimage.seg.int", true);
096            segTime = Config.getPref().getBoolean("geoimage.seg.int.time", true) ?
097                    Config.getPref().getInt("geoimage.seg.int.time.val", 60) : Integer.MAX_VALUE;
098            segDist = Config.getPref().getBoolean("geoimage.seg.int.dist", true) ?
099                    Config.getPref().getInt("geoimage.seg.int.dist.val", 50) : Integer.MAX_VALUE;
100
101            segTag = Config.getPref().getBoolean("geoimage.seg.tag", true);
102            segTagTime = Config.getPref().getBoolean("geoimage.seg.tag.time", true) ?
103                    Config.getPref().getInt("geoimage.seg.tag.time.val", 2) : Integer.MAX_VALUE;
104        }
105        boolean isFirst = true;
106
107        for (int t = 0; t < trks.size(); t++) {
108            List<List<WayPoint>> segs = trks.get(t);
109            for (int s = 0; s < segs.size(); s++) {
110                List<WayPoint> wps = segs.get(s);
111                for (int i = 0; i < wps.size(); i++) {
112                    WayPoint curWp = wps.get(i);
113                    // Interpolate timestamps in the segment, if one or more waypoints miss them
114                    if (!curWp.hasDate()) {
115                        //check if any of the following waypoints has a timestamp...
116                        if (i > 0 && wps.get(i - 1).hasDate()) {
117                            long prevWpTimeNoOffset = wps.get(i - 1).getTimeInMillis();
118                            double totalDist = 0;
119                            List<Pair<Double, WayPoint>> nextWps = new ArrayList<>();
120                            for (int j = i; j < wps.size(); j++) {
121                                totalDist += wps.get(j - 1).getCoor().greatCircleDistance(wps.get(j).getCoor());
122                                nextWps.add(new Pair<>(totalDist, wps.get(j)));
123                                if (wps.get(j).hasDate()) {
124                                    // ...if yes, interpolate everything in between
125                                    long timeDiff = wps.get(j).getTimeInMillis() - prevWpTimeNoOffset;
126                                    for (Pair<Double, WayPoint> pair : nextWps) {
127                                        pair.b.setTimeInMillis((long) (prevWpTimeNoOffset + (timeDiff * (pair.a / totalDist))));
128                                    }
129                                    break;
130                                }
131                            }
132                            if (!curWp.hasDate()) {
133                                break; //It's pointless to continue with this segment, because none of the following waypoints had a timestamp
134                            }
135                        } else {
136                            // Timestamps on waypoints without preceding timestamps in the same segment can not be interpolated, so try next one
137                            continue;
138                        }
139                    }
140
141                    final long curWpTime = curWp.getTimeInMillis() + offset;
142                    boolean interpolate = true;
143                    int tagTime = 0;
144                    if (i == 0) {
145                        if (s == 0) { //First segment of the track, so apply settings for tracks
146                            if (!trkInt || isFirst || prevWp == null ||
147                                    Math.abs(curWpTime - prevWpTime) > TimeUnit.MINUTES.toMillis(trkTime) ||
148                                    prevWp.getCoor().greatCircleDistance(curWp.getCoor()) > trkDist) {
149                                isFirst = false;
150                                interpolate = false;
151                                if (trkTag) {
152                                    tagTime = trkTagTime;
153                                }
154                            }
155                        } else { //Apply settings for segments
156                            if (!segInt || prevWp == null ||
157                                    Math.abs(curWpTime - prevWpTime) > TimeUnit.MINUTES.toMillis(segTime) ||
158                                    prevWp.getCoor().greatCircleDistance(curWp.getCoor()) > segDist) {
159                                interpolate = false;
160                                if (segTag) {
161                                    tagTime = segTagTime;
162                                }
163                            }
164                        }
165                    }
166                    ret += matchPoints(images, prevWp, prevWpTime, curWp, curWpTime, offset, interpolate, tagTime, false);
167                    prevWp = curWp;
168                    prevWpTime = curWpTime;
169                }
170            }
171        }
172        if (trkTag) {
173            ret += matchPoints(images, prevWp, prevWpTime, prevWp, prevWpTime, offset, false, trkTagTime, true);
174        }
175        return ret;
176    }
177
178    static Double getElevation(WayPoint wp) {
179        if (wp != null) {
180            String value = wp.getString(GpxConstants.PT_ELE);
181            if (value != null && !value.isEmpty()) {
182                try {
183                    return Double.valueOf(value);
184                } catch (NumberFormatException e) {
185                    Logging.warn(e);
186                }
187            }
188        }
189        return null;
190    }
191
192    private static int matchPoints(List<? extends GpxImageEntry> images, WayPoint prevWp, long prevWpTime, WayPoint curWp, long curWpTime,
193            long offset, boolean interpolate, int tagTime, boolean isLast) {
194
195        int ret = 0;
196
197        // i is the index of the timewise last photo that has the same or earlier EXIF time
198        int i;
199        if (isLast) {
200            i = images.size() - 1;
201        } else {
202            i = getLastIndexOfListBefore(images, curWpTime);
203        }
204
205        // no photos match
206        if (i < 0)
207            return 0;
208
209        Double speed = null;
210        Double prevElevation = null;
211
212        if (prevWp != null && interpolate) {
213            double distance = prevWp.getCoor().greatCircleDistance(curWp.getCoor());
214            // This is in km/h, 3.6 * m/s
215            if (curWpTime > prevWpTime) {
216                speed = 3600 * distance / (curWpTime - prevWpTime);
217            }
218            prevElevation = getElevation(prevWp);
219        }
220
221        Double curElevation = getElevation(curWp);
222
223        if (!interpolate || isLast) {
224            final long half = Math.abs(curWpTime - prevWpTime) / 2;
225            while (i >= 0) {
226                final GpxImageEntry curImg = images.get(i);
227                final GpxImageEntry curTmp = curImg.getTmp();
228                final long time = curImg.getExifTime().getTime();
229                if ((!isLast && time > curWpTime) || time < prevWpTime) {
230                    break;
231                }
232                long tagms = TimeUnit.MINUTES.toMillis(tagTime);
233                if (curTmp.getPos() == null &&
234                        (Math.abs(time - curWpTime) <= tagms
235                        || Math.abs(prevWpTime - time) <= tagms)) {
236                    if (prevWp != null && time < curWpTime - half) {
237                        curTmp.setPos(prevWp.getCoor());
238                    } else {
239                        curTmp.setPos(curWp.getCoor());
240                    }
241                    curTmp.setGpsTime(new Date(curImg.getExifTime().getTime() - offset));
242                    curTmp.flagNewGpsData();
243                    ret++;
244                }
245                i--;
246            }
247        } else if (prevWp != null) {
248            // This code gives a simple linear interpolation of the coordinates between current and
249            // previous track point assuming a constant speed in between
250            while (i >= 0) {
251                GpxImageEntry curImg = images.get(i);
252                GpxImageEntry curTmp = curImg.getTmp();
253                final long imgTime = curImg.getExifTime().getTime();
254                if (imgTime < prevWpTime) {
255                    break;
256                }
257                if (curTmp.getPos() == null) {
258                    // The values of timeDiff are between 0 and 1, it is not seconds but a dimensionless variable
259                    double timeDiff = (double) (imgTime - prevWpTime) / Math.abs(curWpTime - prevWpTime);
260                    curTmp.setPos(prevWp.getCoor().interpolate(curWp.getCoor(), timeDiff));
261                    curTmp.setSpeed(speed);
262                    if (curElevation != null && prevElevation != null) {
263                        curTmp.setElevation(prevElevation + (curElevation - prevElevation) * timeDiff);
264                    }
265                    curTmp.setGpsTime(new Date(curImg.getExifTime().getTime() - offset));
266                    curTmp.flagNewGpsData();
267
268                    ret++;
269                }
270                i--;
271            }
272        }
273        return ret;
274    }
275
276    private static int getLastIndexOfListBefore(List<? extends GpxImageEntry> images, long searchedTime) {
277        int lstSize = images.size();
278
279        // No photos or the first photo taken is later than the search period
280        if (lstSize == 0 || searchedTime < images.get(0).getExifTime().getTime())
281            return -1;
282
283        // The search period is later than the last photo
284        if (searchedTime > images.get(lstSize - 1).getExifTime().getTime())
285            return lstSize-1;
286
287        // The searched index is somewhere in the middle, do a binary search from the beginning
288        int curIndex;
289        int startIndex = 0;
290        int endIndex = lstSize-1;
291        while (endIndex - startIndex > 1) {
292            curIndex = (endIndex + startIndex) / 2;
293            if (searchedTime > images.get(curIndex).getExifTime().getTime()) {
294                startIndex = curIndex;
295            } else {
296                endIndex = curIndex;
297            }
298        }
299        if (searchedTime < images.get(endIndex).getExifTime().getTime())
300            return startIndex;
301
302        // This final loop is to check if photos with the exact same EXIF time follows
303        while ((endIndex < (lstSize - 1)) && (images.get(endIndex).getExifTime().getTime()
304                == images.get(endIndex + 1).getExifTime().getTime())) {
305            endIndex++;
306        }
307        return endIndex;
308    }
309}