-module(geokit@simplify).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/geokit/simplify.gleam").
-export([line_string/2, compute/2]).
-export_type([simplify_error/0]).
-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.
?MODULEDOC(
" Douglas-Peucker line simplification.\n"
"\n"
" Reduces the number of points in a `LineString` while preserving\n"
" its general shape: any point further than `tolerance` from the\n"
" straight line between its neighbours is kept; closer ones are\n"
" discarded.\n"
"\n"
" `tolerance` is a distance in *degrees* on the lat/lng plane — no\n"
" projection is applied. For polylines spanning more than a few\n"
" degrees, project to Web Mercator first\n"
" (see [`geokit/mercator`](./mercator.html)) and convert your\n"
" tolerance to pixels. For short segments (city-scale and below)\n"
" the planar approximation is well within rendering tolerance.\n"
"\n"
" Reference:\n"
" Douglas, D.; Peucker, T. (1973), \"Algorithms for the reduction\n"
" of the number of points required to represent a digitized line\n"
" or its caricature\".\n"
).
-type simplify_error() :: {negative_tolerance, float()}.
-file("src/geokit/simplify.gleam", 187).
-spec merge_skipping_duplicate_pivot(
list(geokit@latlng:lat_lng()),
list(geokit@latlng:lat_lng())
) -> list(geokit@latlng:lat_lng()).
merge_skipping_duplicate_pivot(Left, Right) ->
case Right of
[] ->
Left;
[_ | Tail] ->
lists:append(Left, Tail)
end.
-file("src/geokit/simplify.gleam", 267).
-spec newton_sqrt(float(), float(), integer()) -> float().
newton_sqrt(Value, Guess, Iterations) ->
gleam@bool:guard(
(Iterations =< 0) orelse (Guess =:= +0.0),
Guess,
fun() -> newton_sqrt(Value, (Guess + (case Guess of
+0.0 -> +0.0;
-0.0 -> -0.0;
Gleam@denominator -> Value / Gleam@denominator
end)) / 2.0, Iterations - 1) end
).
-file("src/geokit/simplify.gleam", 262).
-spec sqrt_nonneg(float()) -> float().
sqrt_nonneg(Value) ->
gleam@bool:guard(
Value =< +0.0,
+0.0,
fun() -> newton_sqrt(Value, Value, 32) end
).
-file("src/geokit/simplify.gleam", 235).
-spec perpendicular_distance(
geokit@latlng:lat_lng(),
geokit@latlng:lat_lng(),
geokit@latlng:lat_lng()
) -> float().
perpendicular_distance(P, A, B) ->
X = geokit@latlng:lng(P),
Y = geokit@latlng:lat(P),
X1 = geokit@latlng:lng(A),
Y1 = geokit@latlng:lat(A),
X2 = geokit@latlng:lng(B),
Y2 = geokit@latlng:lat(B),
Dx = X2 - X1,
Dy = Y2 - Y1,
Length_squared = (Dx * Dx) + (Dy * Dy),
case Length_squared =:= +0.0 of
true ->
Edx = X - X1,
Edy = Y - Y1,
sqrt_nonneg((Edx * Edx) + (Edy * Edy));
false ->
Cross = ((X - X1) * Dy) - ((Y - Y1) * Dx),
Abs_cross = case Cross < +0.0 of
true ->
+0.0 - Cross;
false ->
Cross
end,
case sqrt_nonneg(Length_squared) of
+0.0 -> +0.0;
-0.0 -> -0.0;
Gleam@denominator -> Abs_cross / Gleam@denominator
end
end.
-file("src/geokit/simplify.gleam", 199).
-spec max_perp_distance(
list(geokit@latlng:lat_lng()),
geokit@latlng:lat_lng(),
geokit@latlng:lat_lng(),
integer(),
float(),
integer()
) -> {float(), integer()}.
max_perp_distance(Middle, A, B, Index, Best_dist, Best_index) ->
case Middle of
[] ->
{Best_dist, Best_index};
[Head | Tail] ->
D = perpendicular_distance(Head, A, B),
case D > Best_dist of
true ->
max_perp_distance(Tail, A, B, Index + 1, D, Index);
false ->
max_perp_distance(
Tail,
A,
B,
Index + 1,
Best_dist,
Best_index
)
end
end.
-file("src/geokit/simplify.gleam", 282).
-spec first_or_default(list(geokit@latlng:lat_lng())) -> geokit@latlng:lat_lng().
first_or_default(Points) ->
case Points of
[] ->
geokit@latlng:wrap(+0.0, +0.0);
[Head | _] ->
Head
end.
-file("src/geokit/simplify.gleam", 289).
-spec last_or_default(list(geokit@latlng:lat_lng()), geokit@latlng:lat_lng()) -> geokit@latlng:lat_lng().
last_or_default(Points, Fallback) ->
case Points of
[] ->
Fallback;
[Single] ->
Single;
[_ | Tail] ->
last_or_default(Tail, Fallback)
end.
-file("src/geokit/simplify.gleam", 305).
-spec drop_last(list(geokit@latlng:lat_lng())) -> list(geokit@latlng:lat_lng()).
drop_last(Points) ->
case Points of
[] ->
[];
[_] ->
[];
[Head | Tail] ->
[Head | drop_last(Tail)]
end.
-file("src/geokit/simplify.gleam", 297).
-spec middle_of(list(geokit@latlng:lat_lng())) -> list(geokit@latlng:lat_lng()).
middle_of(Points) ->
case Points of
[] ->
[];
[_] ->
[];
[_ | Tail] ->
drop_last(Tail)
end.
-file("src/geokit/simplify.gleam", 156).
-spec dp(list(geokit@latlng:lat_lng()), float()) -> list(geokit@latlng:lat_lng()).
dp(Points, Tolerance) ->
Length = erlang:length(Points),
case Length =< 2 of
true ->
Points;
false ->
First = first_or_default(Points),
Last = last_or_default(Points, First),
Middle = middle_of(Points),
{Max_dist, Max_index} = max_perp_distance(
Middle,
First,
Last,
1,
+0.0,
0
),
case Max_dist > Tolerance of
true ->
Left_part = gleam@list:take(Points, Max_index + 1),
Right_part = gleam@list:drop(Points, Max_index),
Left = dp(Left_part, Tolerance),
Right = dp(Right_part, Tolerance),
merge_skipping_duplicate_pivot(Left, Right);
false ->
[First, Last]
end
end.
-file("src/geokit/simplify.gleam", 54).
?DOC(
" Simplify a sequence of points using Douglas-Peucker.\n"
" `tolerance` is in degrees. Larger values keep fewer points.\n"
"\n"
" A tolerance of `0.0` is the **canonical Douglas-Peucker\n"
" behaviour**: it drops every intermediate point that lies\n"
" *exactly* on the straight line between its surviving neighbours,\n"
" because the comparison `perpendicular_distance >. tolerance` is\n"
" strict. Use a tiny positive value (for example `1.0e-12`) if you\n"
" want to preserve every point.\n"
"\n"
" ```gleam\n"
" import geokit/simplify\n"
" import geokit/latlng\n"
"\n"
" let assert Ok(a) = latlng.new(lat: 0.0, lng: 0.0)\n"
" let assert Ok(b) = latlng.new(lat: 0.0, lng: 0.5)\n"
" let assert Ok(c) = latlng.new(lat: 0.0, lng: 1.0)\n"
" let assert Ok(simplified) =\n"
" simplify.line_string(points: [a, b, c], tolerance: 0.001)\n"
" // simplified == [a, c] (b is on the straight line between a and c)\n"
" ```\n"
).
-spec line_string(list(geokit@latlng:lat_lng()), float()) -> {ok,
list(geokit@latlng:lat_lng())} |
{error, simplify_error()}.
line_string(Points, Tolerance) ->
gleam@bool:guard(
Tolerance < +0.0,
{error, {negative_tolerance, Tolerance}},
fun() -> case Points of
[] ->
{ok, []};
[Single] ->
{ok, [Single]};
[A, B] ->
{ok, [A, B]};
_ ->
{ok, dp(Points, Tolerance)}
end end
).
-file("src/geokit/simplify.gleam", 120).
-spec simplify_rings(
list(list(geokit@latlng:lat_lng())),
float(),
list(list(geokit@latlng:lat_lng()))
) -> {ok, list(list(geokit@latlng:lat_lng()))} | {error, simplify_error()}.
simplify_rings(Rings, Tolerance, Acc) ->
case Rings of
[] ->
{ok, lists:reverse(Acc)};
[Head | Tail] ->
gleam@result:'try'(
line_string(Head, Tolerance),
fun(Simplified) ->
simplify_rings(Tail, Tolerance, [Simplified | Acc])
end
)
end.
-file("src/geokit/simplify.gleam", 137).
-spec simplify_polygons(
list(list(list(geokit@latlng:lat_lng()))),
float(),
list(list(list(geokit@latlng:lat_lng())))
) -> {ok, list(list(list(geokit@latlng:lat_lng())))} | {error, simplify_error()}.
simplify_polygons(Polygons, Tolerance, Acc) ->
case Polygons of
[] ->
{ok, lists:reverse(Acc)};
[Head | Tail] ->
gleam@result:'try'(
simplify_rings(Head, Tolerance, []),
fun(Simplified) ->
simplify_polygons(Tail, Tolerance, [Simplified | Acc])
end
)
end.
-file("src/geokit/simplify.gleam", 88).
?DOC(
" Simplify any [`Geometry`](../geometry.html#Geometry), matching the\n"
" [`bbox.compute`](../bbox.html#compute) /\n"
" [`centroid.compute`](../centroid.html#compute) call shape.\n"
"\n"
" - `Point` is returned unchanged.\n"
" - `LineString` is simplified via [`line_string`](#line_string).\n"
" - `Polygon` simplifies each ring; closure is preserved by always\n"
" keeping the first and last vertex of each ring.\n"
" - `MultiPolygon` recurses into each polygon.\n"
"\n"
" ```gleam\n"
" import geokit/geometry\n"
" import geokit/simplify\n"
"\n"
" let result =\n"
" geometry.LineString([a, b, c])\n"
" |> simplify.compute(tolerance: 0.001)\n"
" ```\n"
).
-spec compute(geokit@geometry:geometry(), float()) -> {ok,
geokit@geometry:geometry()} |
{error, simplify_error()}.
compute(Geometry, Tolerance) ->
gleam@bool:guard(
Tolerance < +0.0,
{error, {negative_tolerance, Tolerance}},
fun() -> case Geometry of
{point, _} ->
{ok, Geometry};
{line_string, Points} ->
gleam@result:map(
line_string(Points, Tolerance),
fun(Simplified) -> {line_string, Simplified} end
);
{polygon, Rings} ->
gleam@result:map(
simplify_rings(Rings, Tolerance, []),
fun(New_rings) -> {polygon, New_rings} end
);
{multi_polygon, Polygons} ->
gleam@result:map(
simplify_polygons(Polygons, Tolerance, []),
fun(New_polygons) -> {multi_polygon, New_polygons} end
)
end end
).
