Rafael Romão's Coding Labs

Lab L22 · Java + Go

Implementing a trajectory processor

Build a per-vehicle location history. Store timestamped GPS points (sorted by time even when they arrive out of order, keeping only the newest capacity), turn each pair of consecutive points into a segment with distance and speed, and flag segments whose speed is physically implausible — a GPS glitch. Separately, snap a point onto the nearest road segment and report whether the choice was ambiguous.

The task

A trip receipt charges by distance travelled, computed from GPS. A glitch that jumps 3 km in 2 seconds would inflate the fare, so segments faster than a plausible maximum are flagged for exclusion. Phones batch and resend points, so they can arrive late or twice. Map matching starts with the simplest question: which road segment is this point closest to, and is the runner-up so close that the answer is uncertain? Coordinates for matching are local metres (x, y), not degrees.

0 s5 s10 s55.6 m · 11 m/s12 s3.3 km in 2 s→ implausibleabpproject(p, a, b)t clamped to [0, 1]
Left: consecutive points become segments; the last jump is too fast to be real. Right: snapping a point to a road is a clamped perpendicular projection onto the segment.

What you implement

public final class Trajectory {
    public record Observation(long millis, NearbyIndex.Point position) {}
    public record Segment(long fromMillis, long toMillis, double meters,
                          double speedMetersPerSecond, boolean implausible) {}
    public Trajectory(int capacity);                    // max distinct timestamps kept
    public void put(Observation o);
    public List<Segment> segments(double maxSpeedMetersPerSecond);
}

public final class SegmentMatcher {
    public record XY(double x, double y) {}                       // local metres
    public record Road(String id, XY a, XY b) {}
    public record Match(String id, XY position, double distance, boolean ambiguous) {}
    public static XY project(XY p, XY a, XY b);                   // closest point on segment ab
    public static Match nearest(XY p, List<Road> roads, double tolerance);
}

Rules

  • put: negative millis or invalid coordinates → IllegalArgumentException. A point at an existing timestamp replaces it. Beyond capacity distinct timestamps, drop the oldest — a late old point may be dropped immediately.
  • segments: one per adjacent pair in time order. meters = haversine (L19), speed = meters / seconds, implausible = speed > maxSpeed. maxSpeed <= 0 or non-finite → IllegalArgumentException.
  • project: t = clamp(((p − a)·(b − a)) / |b − a|², 0, 1), result a + t(b − a); a zero-length road projects to a. Non-finite or |coordinate| > 1e6 → IllegalArgumentException.
  • nearest: the road with the smallest distance to its projection (ties by id). ambiguous when the second-best is within tolerance of the best. Empty list, duplicate road ids or negative tolerance → IllegalArgumentException.

Worked example

  1. capacity = 3. put(0 ms, (0, 0)), put(10000, (0, 0.001)), put(5000, (0, 0.0005)) (late).
  2. segments(50) → two segments of ~55.6 m at ~11.1 m/s, both plausible.
  3. put(12000, (0.03, 0.001)) → the 0 ms point is dropped; the new last segment covers ~3.3 km in 2 s ≈ 1,668 m/s → implausible.
  4. Road r1 from (0, 0) to (100, 0); p = (30, 5) → projection (30, 0), distance 5.

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: SegmentMatcher.java, Trajectory.java · tests: SegmentMatcherTest.java, TrajectoryTest.java. Go starter: projection.go, track.go · tests: projection_test.go, track_test.go.

cd java
./gradlew test --tests 'labs.trajectory.*'

cd go
go test -race -count=1 ./trajectory
Reveal the reference solutions

Java: SegmentMatcher.java, Trajectory.java
Go: projection.go, track.go

When to use

Use this lab for one object's bounded location history. Observations have nonnegative signed-integer millisecond timestamps and valid latitude/longitude positions. Insertions can arrive out of order. An equal timestamp replaces the existing observation; only the newest configured number of distinct timestamps remain. An older insertion may therefore be pruned immediately. This is a count bound, not a time-duration bound or durable retention policy.

The processor emits segments between adjacent retained observations. Each segment contains its time endpoints, spherical distance in metres, speed in metres per second, and an implausible-speed flag. It uses the same explicit spherical model as the nearby-search lab. It does not infer the actual road followed, reconstruct discarded history, or guarantee GPS measurement accuracy.

Steps

  1. Specify duplicate meaning. Timestamp replacement is the complete deduplication policy here. If different sources or revisions can report the same timestamp, a production contract may need a source sequence or observation identity; arrival order alone is not proof of freshness.
  2. Sort before computing movement. Java stores observations in an ordered map; Go uses binary search and a sorted slice. Updating an earlier observation can change two neighboring segment metrics. Compute results from the current retained history rather than incrementally adding distances that can no longer be corrected after disorder.
  3. Retain deliberately. Remove the oldest timestamp when capacity is exceeded. A late observation outside the retained suffix does not replace the newest data. Do not advertise a lifetime distance total from this suffix; it omits earlier movement by design.
  4. Calculate speed with units. Divide spherical distance by positive elapsed seconds, converting milliseconds explicitly. Unique timestamps prevent a zero time denominator. Flag a segment only when speed exceeds the configured positive finite threshold. Keep flagged distances visible; silently deleting them would hide evidence and change aggregate semantics.
  5. Test mutations of history. Insert time two before time zero, insert time one, and replace time one's position. Check chronological segments, then add a fourth observation to a capacity-three track and verify oldest eviction. Insert a very old observation afterward and verify the retained suffix is unchanged. A stationary segment must report zero speed.
  6. Separate projection from path inference. The local-metre segment extension computes endpoint-clamped projections and nearest-road ambiguity. Scoring connected candidate sequences remains a separate map-matching problem. A nearest segment alone does not establish the travelled road, and degree-space projection is not a metre-distance computation. Keep that limitation visible when interpreting the returned candidate.

Checklist

Projection extension and recall

Rebuild timestamp replacement before reading Go or Java. The Project/SegmentMatcher extension uses finite local projected metres bounded within plus/minus one million, clamps projection to segment endpoints, and flags near-equal nearest roads as ambiguous. It does not accept latitude/longitude or infer a connected route. Variation: two parallel roads equidistant from one point. Acceptance: deterministic identity tie-breaking is accompanied by ambiguity, not a claim of correct road identification.

  • Coordinate order, distance model, and timestamp units are explicit
  • Duplicate timestamps replace and late observations preserve sorted retention
  • Segment time differences are positive
  • Implausible jumps remain observable rather than silently disappearing
  • Retained-history metrics are not presented as lifetime totals

Signals

Working: replacing an earlier position recomputes its neighboring speeds, and old insertions cannot displace newer retained observations.

Going wrong: milliseconds are treated as seconds, zero elapsed time produces an infinite speed, or a short retained trace is presented as complete travel history. Queries are O(n); Java insertion is O(log n), while Go insertion and pruning can shift O(n) entries. Locking gives one consistent track view but does not make the source observations reliable.

Related