Module: FastPolylines

Defined in:
ext/fast_polylines/fast_polylines.c,
lib/fast_polylines/version.rb,
ext/fast_polylines/fast_polylines.c

Overview

Implementation of the Google polyline algorithm.

Install it with gem install fast-polylines, and then:

require "fast_polylines"

FastPolylines.encode([[38.5, -120.2], [40.7, -120.95], [43.252, -126.453]])
# "_p~iF~ps|U_ulLnnqC_mqNvxq`@"

FastPolylines.decode("_p~iF~ps|U_ulLnnqC_mqNvxq`@")
# [[38.5, -120.2], [40.7, -120.95], [43.252, -126.453]]

You can set an arbitrary precision for your coordinates to be encoded/decoded. It may be from 1 to 13 decimal digits. However, 13 may be too much.

https://xkcd.com/2170/

Defined Under Namespace

Modules: Decoder, Encoder

Constant Summary collapse

VERSION =
"2.2.0"

Class Method Summary collapse

Class Method Details

.decode(polyline, precision = 5) ⇒ Array

Decode a polyline to a list of coordinates (lat, lng tuples). You may set an arbitrary coordinate precision, however, it must match the precision that was used for encoding.

Returns:

  • (Array)

78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
# File 'ext/fast_polylines/fast_polylines.c', line 78

static VALUE
rb_FastPolylines__decode(int argc, VALUE *argv, VALUE self) {
	rb_check_arity(argc, 1, 2);
	Check_Type(argv[0], T_STRING);
	char* polyline = StringValueCStr(argv[0]);
	uint precision = _get_precision(argc > 1 ? argv[1] : Qnil);
	double precision_value = _fast_pow10(precision);

	VALUE ary = rb_ary_new();
	// Helps keeping track of whether we are computing lat (0) or lng (1).
	uint8_t index = 0;
	size_t shift = 0;
	int64_t delta = 0;
	VALUE sub_ary[2];
	double latlng[2] = {0.0, 0.0};
	// Loops until end of string nul character is encountered.
	while (*polyline) {
		int64_t chunk = *polyline++;

		if (chunk < 63 || chunk > 126) {
			rb_raise(rb_eArgError, "invalid character '%c'", (char)chunk);
		}

		chunk -= 63;
		delta = delta | ((chunk & ~0x20) << shift);
		shift += 5;

		if (!(chunk & 0x20)) {
			delta = (delta & 1) ? ~(delta >> 1) : (delta >> 1);
			latlng[index] += delta;
			sub_ary[index] = rb_float_new((double) latlng[index] / precision_value);
			// When both coordinates are parsed, we can push those to the result ary.
			if (index) rb_ary_push(ary, rb_ary_new_from_values(2, sub_ary));
			// Reinitilize since we are done for current coordinate.
			index = 1 - index; delta = 0; shift = 0;
		}
	}
	return ary;
}

.encode([[lat, lng], ...], precision = 5) ⇒ String

Encode a list of coordinates to a polyline, you may give a specific precision if you want to retain more (or less) than 5 digits of precision. The maximum is 13, and may really be too much.

Returns:

  • (String)

143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
# File 'ext/fast_polylines/fast_polylines.c', line 143

static VALUE
rb_FastPolylines__encode(int argc, VALUE *argv, VALUE self) {
	rb_check_arity(argc, 1, 2);
	Check_Type(argv[0], T_ARRAY);
	size_t len = RARRAY_LEN(argv[0]);
	uint64_t i;
	VALUE current_pair;
	int64_t prev_pair[2] = {0, 0};
	uint precision = _get_precision(argc > 1 ? argv[1] : Qnil);
	dbg("rb_FastPolylines__encode(..., %u)\n", precision);
	rdbg(argv[0]);
	double precision_value = _fast_pow10(precision);

	// This is the maximum possible size the polyline may have. This
	// being **without** null character. To copy it later as a Ruby
	// string we'll have to use `rb_str_new` with the length.
	dbg("allocated size: %u * 2 * %lu = %lu\n",
	    MAX_ENCODED_CHUNKS(precision),
	    len,
	    MAX_ENCODED_CHUNKS(precision) * 2 * len);
	char *chunks = malloc(MAX_ENCODED_CHUNKS(precision) * 2 * len * sizeof(char));
	size_t chunks_index = 0;
	for (i = 0; i < len; i++) {
			current_pair = RARRAY_AREF(argv[0], i);
			uint8_t j;
			Check_Type(current_pair, T_ARRAY);
			if (RARRAY_LEN(current_pair) != 2) {
				free(chunks);
				rb_raise(rb_eArgError, "wrong number of coordinates");
			}
			for (j = 0; j < 2; j++) {
				VALUE current_value =	RARRAY_AREF(current_pair, j);
				switch (TYPE(current_value)) {
					case T_BIGNUM:
					case T_FLOAT:
					case T_FIXNUM:
					case T_RATIONAL:
						break;
					default:
						free(chunks);
						rb_raise(rb_eTypeError, "no implicit conversion to Float from %s", rb_obj_classname(current_value));
				};

				double parsed_value = NUM2DBL(current_value);
				if (-180.0 > parsed_value || parsed_value > 180.0) {
					free(chunks);
					rb_raise(rb_eArgError, "coordinates must be between -180.0 and 180.0");
				}
				int64_t rounded_value = round(parsed_value * precision_value);
				int64_t delta = rounded_value - prev_pair[j];
				prev_pair[j] = rounded_value;
				// We pass a pointer to the current chunk that need to be filled. Doing so
				// avoid having to copy the string every single iteration.
				chunks_index += _polyline_encode_number(chunks + chunks_index * sizeof(char), delta);
				dbg("%s\n", chunks);
			}
	}
	dbg("final chunks_index: %zu\n", chunks_index);
	VALUE polyline = rb_str_new(chunks, chunks_index);
	free(chunks);
	return polyline;
}