polyline6.go
1// Package geo provides polyline6 encoding/decoding utilities for working with
2// geographic coordinates. It wraps the github.com/twpayne/go-polyline library
3// with a custom codec using dimension 2 and scale 1e6 (polyline6 format).
4//
5// All coordinate operations use Maplibre format [lon, lat] and convert
6// appropriately when calling the underlying library functions which use
7// [lat, lon] format.
8//
9// The Polyline6 type handles JSON escaping transparently - when unmarshaling
10// from JSON, escaped backslashes (\\) are unescaped to (\), and when
11// marshaling to JSON, backslashes are escaped.
12//
13// Example usage:
14//
15// points := [][]float64{{-120.2, 38.5}, {-120.95, 40.7}}
16// encoded, err := geo.Encode(points)
17// decoded, err := geo.Decode(encoded)
18// combined, err := geo.Combine(encoded1, encoded2)
19// geojson, err := geo.ToGeoJSON(encoded, geo.WithProperty("name", "Route"))
20package geo
21
22import (
23 "encoding/json"
24 "fmt"
25 "log/slog"
26 "strings"
27
28 "github.com/twpayne/go-polyline"
29)
30
31// codec is the polyline6 codec: 2 dimensions (lat, lon), 1e6 scale factor
32var codec = polyline.Codec{Dim: 2, Scale: 1e6}
33
34// Encode encodes Maplibre format points [lon, lat] to a polyline6 string.
35// The polyline format uses [lat, lon] internally, so this function swaps
36// the coordinates before encoding.
37func Encode(points [][]float64) (Polyline6, error) {
38 if len(points) == 0 {
39 return "", nil
40 }
41
42 // Convert from Maplibre [lon, lat] to polyline [lat, lon] format
43 coords := make([][]float64, len(points))
44 for i, pt := range points {
45 if len(pt) != 2 {
46 return "", fmt.Errorf("point %d: expected 2 coordinates, got %d", i, len(pt))
47 }
48 // Swap: [lon, lat] -> [lat, lon]
49 coords[i] = []float64{pt[1], pt[0]}
50 }
51
52 encoded := codec.EncodeCoords(nil, coords)
53 return Polyline6(encoded), nil
54}
55
56// Decode decodes a polyline6 string to Maplibre format points [lon, lat].
57// The polyline format uses [lat, lon] internally, so this function swaps
58// the coordinates after decoding.
59//
60// This function is defensive against malformed polylines that may have trailing
61// garbage bytes. If the initial decode fails, it will try progressively trimming
62// trailing bytes (up to 5) to find a valid polyline.
63func Decode(p Polyline6) ([][]float64, error) {
64 if p == "" {
65 return [][]float64{}, nil
66 }
67
68 coords, _, err := codec.DecodeCoords([]byte(p))
69 if err != nil {
70 // Defensive: try trimming trailing bytes that might be garbage
71 // This handles cases where the routing API returns extra bytes
72 // or there's a duplicate terminator at the end
73 for trim := 1; trim <= 5 && trim < len(p); trim++ {
74 trimmed := p[:len(p)-trim]
75 retryCoords, _, retryErr := codec.DecodeCoords([]byte(trimmed))
76 if retryErr == nil && len(retryCoords) > 0 {
77 // Successfully decoded after trimming
78 slog.Debug("polyline decoded successfully after trimming trailing bytes",
79 "trimmedBytes", trim,
80 "originalLength", len(p),
81 "decodedCoords", len(retryCoords))
82 return convertCoords(retryCoords)
83 }
84 }
85 return nil, fmt.Errorf("decode error: %w (polyline length=%d, first20=%q)", err, len(p), string([]byte(p)[:min(20, len(p))]))
86 }
87
88 return convertCoords(coords)
89}
90
91// DecodeManual decodes a polyline6 string using a clean-room implementation
92// of the Google polyline algorithm with 1e6 precision.
93// Returns points in Maplibre format [lon, lat].
94func DecodeManual(p Polyline6) ([][]float64, error) {
95 if p == "" {
96 return [][]float64{}, nil
97 }
98
99 var points [][]float64
100 var lat, lng int64 // Accumulated values in 1e6 precision
101
102 for i := 0; i < len(p); {
103 // Decode latitude delta
104 latDelta, bytesRead := decodeSignedNumber(string(p), i)
105 if bytesRead == 0 {
106 return nil, fmt.Errorf("failed to decode latitude at position %d", i)
107 }
108 i += bytesRead
109 lat += latDelta
110
111 // Decode longitude delta
112 if i >= len(p) {
113 return nil, fmt.Errorf("incomplete polyline: missing longitude after latitude at position %d", i)
114 }
115 lngDelta, bytesRead := decodeSignedNumber(string(p), i)
116 if bytesRead == 0 {
117 return nil, fmt.Errorf("failed to decode longitude at position %d", i)
118 }
119 i += bytesRead
120 lng += lngDelta
121
122 // Convert from 1e6 fixed point to float64 and swap to [lon, lat]
123 points = append(points, []float64{
124 float64(lng) / 1e6,
125 float64(lat) / 1e6,
126 })
127 }
128
129 return points, nil
130}
131
132// decodeSignedNumber decodes a single signed variable-length number
133// from the polyline starting at position pos. Returns the decoded value
134// and the number of bytes consumed.
135func decodeSignedNumber(s string, pos int) (int64, int) {
136 var result int64
137 var shift uint
138
139 for {
140 if pos >= len(s) {
141 return 0, 0 // Error: incomplete number
142 }
143
144 // Get next character and decode
145 b := int64(s[pos] - 63)
146 pos++
147
148 // Extract 5 bits and add to result
149 result |= (b & 0x1F) << shift
150 shift += 5
151
152 // Check continuation bit
153 if (b & 0x20) == 0 {
154 break
155 }
156
157 // Sanity check: prevent infinite loop on malformed data
158 if shift > 64 {
159 return 0, 0
160 }
161 }
162
163 // Handle sign: if result is odd, negate it after shifting
164 if result&1 == 1 {
165 result = ^(result >> 1)
166 } else {
167 result = result >> 1
168 }
169
170 return result, int(shift / 5)
171}
172
173// convertCoords converts polyline [lat, lon] coordinates to Maplibre [lon, lat] format
174func convertCoords(coords [][]float64) ([][]float64, error) {
175 points := make([][]float64, len(coords))
176 for i, coord := range coords {
177 if len(coord) != 2 {
178 return nil, fmt.Errorf("decoded point %d: expected 2 coordinates, got %d", i, len(coord))
179 }
180 // Swap: [lat, lon] -> [lon, lat]
181 points[i] = []float64{coord[1], coord[0]}
182 }
183 return points, nil
184}
185
186// Polyline6 is an unescaped polyline6 string.
187// It implements json.Marshaler and json.Unmarshaler to handle JSON escaping
188// transparently - JSON responses with escaped backslashes are unescaped when
189// unmarshaling, and backslashes are escaped when marshaling to JSON.
190type Polyline6 string
191
192// UnmarshalJSON implements json.Unmarshaler.
193// It removes JSON escaping from backslashes (\\\\ becomes \\).
194func (p *Polyline6) UnmarshalJSON(data []byte) error {
195 // Remove surrounding quotes
196 var s string
197 if err := json.Unmarshal(data, &s); err != nil {
198 return err
199 }
200 // Unescape: replace \\ with \ (undo JSON escaping)
201 *p = Polyline6(strings.ReplaceAll(s, `\\`, `\`))
202 return nil
203}
204
205// MarshalJSON implements json.Marshaler.
206// It adds JSON escaping to backslashes (\ becomes \\).
207func (p Polyline6) MarshalJSON() ([]byte, error) {
208 // Escape: replace \ with \\
209 escaped := strings.ReplaceAll(string(p), `\`, `\\`)
210 return json.Marshal(escaped)
211}
212
213// Combine concatenates two polylines, removing any repeated points at the junction.
214// It decodes both polylines, removes duplicate points where they meet, and re-encodes.
215// Returns an unescaped polyline6.
216func Combine(first, second Polyline6) (Polyline6, error) {
217 // Handle empty cases
218 if first == "" {
219 return second, nil
220 }
221 if second == "" {
222 return first, nil
223 }
224
225 // Decode both polylines
226 firstPoints, err := Decode(first)
227 if err != nil {
228 return "", fmt.Errorf("decode first polyline: %w", err)
229 }
230
231 secondPoints, err := Decode(second)
232 if err != nil {
233 return "", fmt.Errorf("decode second polyline: %w", err)
234 }
235
236 // Find and remove overlapping points from the end of first and start of second
237 // Compare from the end of first with start of second
238 overlap := 0
239 maxOverlap := min(len(firstPoints), len(secondPoints))
240
241 for i := 1; i <= maxOverlap; i++ {
242 // Check if last i points of first match first i points of second
243 matches := true
244 for j := 0; j < i; j++ {
245 firstIdx := len(firstPoints) - i + j
246 if !pointsEqual(firstPoints[firstIdx], secondPoints[j]) {
247 matches = false
248 break
249 }
250 }
251 if matches {
252 overlap = i
253 }
254 }
255
256 // Combine: all of first + second without the overlapping prefix
257 var combined [][]float64
258 combined = append(combined, firstPoints...)
259 if overlap < len(secondPoints) {
260 combined = append(combined, secondPoints[overlap:]...)
261 }
262
263 return Encode(combined)
264}
265
266// pointsEqual checks if two points are equal within floating point tolerance
267func pointsEqual(a, b []float64) bool {
268 if len(a) != 2 || len(b) != 2 {
269 return false
270 }
271 const epsilon = 0.00001
272 return abs(a[0]-b[0]) < epsilon && abs(a[1]-b[1]) < epsilon
273}
274
275func min(a, b int) int {
276 if a < b {
277 return a
278 }
279 return b
280}
281
282// abs returns the absolute value of a float64
283func abs(f float64) float64 {
284 if f < 0 {
285 return -f
286 }
287 return f
288}
289
290// GeoJSONFeature represents a GeoJSON Feature object with LineString geometry
291type GeoJSONFeature struct {
292 Type string `json:"type"`
293 Geometry GeoJSONLineString `json:"geometry"`
294 Properties map[string]interface{} `json:"properties"`
295}
296
297// GeoJSONLineString represents a GeoJSON LineString geometry
298type GeoJSONLineString struct {
299 Type string `json:"type"`
300 Coordinates [][]float64 `json:"coordinates"`
301}
302
303// GeoJSONOption is a functional option for configuring GeoJSON output
304type GeoJSONOption func(*GeoJSONFeature)
305
306// WithProperty adds a custom property to the GeoJSON Feature
307func WithProperty(key string, value interface{}) GeoJSONOption {
308 return func(f *GeoJSONFeature) {
309 f.Properties[key] = value
310 }
311}
312
313// ToGeoJSON converts a polyline6 to a GeoJSON Feature with LineString geometry.
314// Coordinates are in Maplibre format [lon, lat].
315// Use functional options to add custom properties.
316func ToGeoJSON(p Polyline6, opts ...GeoJSONOption) (*GeoJSONFeature, error) {
317 points, err := Decode(p)
318 if err != nil {
319 return nil, fmt.Errorf("decode polyline: %w", err)
320 }
321
322 feature := &GeoJSONFeature{
323 Type: "Feature",
324 Geometry: GeoJSONLineString{
325 Type: "LineString",
326 Coordinates: points,
327 },
328 Properties: make(map[string]interface{}),
329 }
330
331 // Apply functional options
332 for _, opt := range opts {
333 opt(feature)
334 }
335
336 return feature, nil
337}
