Creates an sf POINT layer of seed locations, one per cell of the Voronoi tessellation built on them: k-means centres of a cloud of points, points drawn uniformly inside a boundary, or points you provide.
Arguments
- boundary
Optional polygonal sf object defining the sampling area. Rows without a location, rows the repair leaves without a polygon, vertices at a latitude beyond 90 and mixed dimensions are handled as "Boundaries" in spatialkit-geometry says; "Sampling inside the boundary" gives how points are drawn in it.
- method
How to place the seeds:
"kmeans"(default; cluster centres ofsample_points, or of points drawn inboundary),"random"(uniform inboundary) or"provided"(the points inseeds).- n
Integer; number of seeds to return. Required for
method = "kmeans"andmethod = "random". Ignored formethod = "provided", where every row ofseedsis returned; a mismatch betweennandnrow(seeds)is reported as a warning.For
method = "kmeans"it is an upper bound only: k-means cannot produce more centres than there are distinct positions in the sampling cloud, nor as many centres as there are rows. Whennexceeds either ceiling it is clamped, with a warning naming the count used. Asking for as many seeds as there are points (n = nrow(sample_points)) givesnrow(sample_points) - 1. Checknrow()on the result; do not assumen.Besides a number,
naccepts what the level-selection step returned: the integer vector of ranked candidates fromdetermine_optimal_levels()(its first element is used; itsNAis refused with a note on where it came from), aselect_resolution()result (its$best), or aresolution_profile(). A profile built without anestimateis read withselect_resolution()bycp. A profile built withestimateis read bycriterion = "auto", the rule that goes with its estimate: a size for pooled values and the lowest leave-one-out error for plain means. The size is the profile's own when it was built at one, and 4.5 rows per cell otherwise, and the count is the profile's level for that size, or the built level nearest tomax(2, round(n / obs_per_cell))when the profile has none for it (with a warning of class"spatialkit_size_not_reached").select_resolution(profile)with nocriterionreads such a profile the same way, since its default criterion is"auto". A profile built withobs_per_celland without anestimateis read bycplike any profile without one; passselect_resolution(profile, criterion = "size")for the count its size gives. The result then carriesattr(, "n_from")saying which. A count read off a selection or a profile comes with what the selection found: a warning of class"spatialkit_bound_chosen"when the optimum sits on a bound of the ladder, so the bound chose the count, and one of class"spatialkit_no_structure"when one cell for the whole layer scores as well. A count set by a size has no optimum, so no bound can choose it; its"spatialkit_no_structure"warning says that the count stands and that the cell values will say little that one mean does not. A profile without an estimate and with nocpto read is an error (class"spatialkit_no_default_criterion"when another criterion is finite); seeresolution_profile().With
method = "kmeans", a selection or profile also carries the centres of the partition the profile scored at that count, and those are returned instead of a new k-means: a k-means partition, weighted or not, is the Voronoi partition of its centres, so their cells are the cells the criteria judged. On a profile without an estimate whose centres were fitted to a subsample,select_resolution()refits them to every point first, and those centres are returned, withattr(, "refit"): their cells are near the cells judged but not the same.sample_points, when given, is then only assigned to them (forattr(, "kmeans")) and gives the cover, andboundaryonly sets the CRS and the cover;kmeans_nstart,kmeans_iterandset_seedare not used, and neither arepartition,initand the density settings: the centres are of the kind the profile was built with, and naming another here is a warning of class"spatialkit_partition_unused". A call names what it supplies: apartitionor aninitpassed in the call; withpartition = "density"passed, both density settings at their values, defaults included; without it, a density setting other than its default. A call that supplies none of the four is told nothing, whichever kind and settings the profile was built with. Pass the count as a number (n = sel$best) for a fresh k-means instead.- seeds
sf POINT object of user-provided seeds (method = "provided"). Methods
"kmeans"and"random"do not read it, and ignore it with a warning; so does a call that passesseed =, which R matches toseeds(the seed of the random stream isset_seed). Seeds in another CRS thanboundaryare returned in the boundary's CRS; seeds that mix XY and XYZ (or XYM) points are then returned in XY, with a warning of class"spatialkit_zm_dropped", since sf reads a layer in the dimension of its first geometry.- sample_points
Optional sf POINT cloud for k-means clustering. Method
"random"places its seeds inboundaryand does not read it; it is ignored there with a warning. Only the first two coordinate columns are clustered, so a Z or M dimension does not join the distance calculation and dominate it; rows without a location (an empty point, a coordinate that is not finite or lies beyond 1e150, or in a geographic CRS a latitude beyond 90 degrees, read as given before any move) are dropped with a warning, so they never reachstats::kmeans(), which fails on them without naming a cause. A lon/lat cloud, or one with no CRS whose coordinates look like lon/lat (the heuristicensure_projected()applies, with its warning), is projected before clustering. A cloud that mixes XY and XYZ (or XYM) points is read without Z and M before it is projected or clustered, since sf reads a layer in the dimension of its first geometry.- kmeans_nstart
The number of starts, of which the best is kept.
NULL(default) uses 3 starts forpartition = "density"and 10 forpartition = "kmeans". Underpartition = "kmeans"from random starts it isnstartofstats::kmeans(). A fresh partition is not the oneresolution_profile()scored a count on; pass the selection or profile itself asnfor that one (seen). Underpartition = "density", and withinit = "kmeans++", it has to beNULLor a positive whole number, so a number that is not whole, whichpartition = "kmeans"takes, stops a call that names no kind. It is not read bymethod = "random"or"provided".- kmeans_iter
Integer;
iter.maxforstats::kmeans(). Default 100 for both kinds (voronoi_seeds_kmeans()uses 50 for plain k-means by default). Underpartition = "density"it is the most steps of Lloyd's iteration a start takes. Underpartition = "density", and withinit = "kmeans++", it has to be a positive whole number, and a kept start that was cut off at it is a warning of class"spatialkit_not_converged"(partition = "kmeans"from random starts keeps the warningstats::kmeans()gives).- set_seed
Optional integer seed for the random draws. Default
NULL: the draws come from the session's random-number stream, soset.seed()before the call makes it reproducible. A number gives the same seeds every time and leaves the caller's stream as it was. (voronoi_seeds_kmeans()defaults to 456 instead.)- partition
For
method = "kmeans": what the seeds minimise."density"(default) is the sum of squared distances from the points of the cloud to their nearest seed, each point weighted by its local density to the powerdensity_power: compact cells, many small ones where the points are dense and a few large ones where they are sparse. At the default power they hold about the same number of points each oncenis above the number of dense places (clusters) in the cloud; below that the counts are about as uneven as under"kmeans"."kmeans"is the same sum unweighted: compact cells, with several times the points in a cell of a dense place that a cell of a sparse place holds. It isstats::kmeans()from 10 random starts on the rows as they come, with the coordinates centred, divided by the diagonal of their bounding box and rounded to 2^-30 of it, so that the seeds do not move with the unit or the origin; where the locations span less than a kilometre a change of unit or origin can still move them (see "The partition" inresolution_profile()). The density kind follows the density ofsample_points; a cloud this function draws insideboundaryis uniform and has none to follow. Without the FNN package the density kind finds its weights by comparing every pair of distinct locations, so its time grows with the square of their number; the seeds are the same, and nothing stops the call. See "The partition" inresolution_profile()for what each kind does and how.- init
For
method = "kmeans": how each start is drawn,"random"(ndistinct locations at random, asstats::kmeans()draws them) or"kmeans++"(the seeds one at a time, each in proportion to its squared distance from those already drawn, times its weight underpartition = "density").NULL(default) is each kind's own rule:"random"forpartition = "kmeans"and"kmeans++"forpartition = "density". Underpartition = "kmeans"from random starts the cloud is clustered in the order its rows come in; withinit = "kmeans++", and underpartition = "density", the rows are put in coordinate order first, so the seeds do not depend on their order.- density_power
For
partition = "density": the power the local density is raised to for a point's weight, from 0 to 2. Default 1, which evens out the cell counts once the cells outnumber the dense places; 0 weights every point alike. Setting it underpartition = "kmeans"is a warning.- density_k
For
partition = "density": the number of nearest neighbours the local density is read from. Default 8.
Value
An sf POINT object with seed_id and method columns. With
method = "kmeans" it also carries attr(, "kmeans"), the run behind
the seeds: cluster (the seed_id each clustered cloud point was
assigned to), rows (those points' positions in the cloud, since rows
with unusable coordinates are dropped first), size (points per seed),
withinss and tot_withinss (the within-cluster sums of squares),
iter and nstart. For the scored centres of a selection or profile
(see n) it describes sample_points assigned to them, each point to
its nearest seed, with iter NA and nstart the profile's restarts,
and is absent when no sample_points were given. A point the same
distance from two seeds (squared distances within one part in ten
million) goes to the lower seed_id, the rule the profile scores its
cells by, so the record is the same in another unit or with another
origin. Under partition = "density" withinss and tot_withinss
count every point once, about its cell's mean. A run this call makes with partition = "density" or
init = "kmeans++" also records converged, whether the kept start
stopped before kmeans_iter, and under partition = "density"
objective, the weighted sum the seeds minimise; scored centres have
neither. Seeds placed with partition = "density" or init = "kmeans++", and the scored centres of a profile of the density kind or
from random starts, carry attr(, "partition"): a
list with kind, init, density_power and density_k, and for
seeds this call placed iter, iter_max and converged (the
iterations the kept start took, the limit, and whether it stopped
before the limit). build_tessellation() returns the list as
params$partition. Seeds with no such
record are plain k-means: from random starts when this call placed
them, or the scored centres of a k-means profile from k-means++ starts.
Every method also
attaches attr(, "cover") when the call says what ground the seeds stand
for (see "Details"): an sfc holding the boundary's polygons or the hull
of the clustered points, in its own CRS.
When n is a select_resolution() result that carries count_rule,
or a profile built with an estimate or read by cp, the seeds carry
that record as
attr(, "count_rule"): how the count was set, for which cell value, and
what the profile scored at it. Its scored_cells is TRUE for the
scored centres method = "kmeans" hands on, and FALSE for centres
refitted to every point (see n) and for seeds this
call places itself at that count: a k-means of its own when the
selection holds no centres at the count, and every method = "random"
seeding. method = "provided" does not read n and writes no record;
seeds that already carry one (sel$seeds) keep it, marked FALSE when
their number is not the record's count. build_tessellation() and
assign_features_to_polygons() hand the record on, and
summarize_by_cell() checks its result against it. A count given as a
number, or read off a profile without an estimate by cp or elbow,
has no record.
Details
Seeds lie inside the ground they stand for (k-means seeds inside the
hull of the points they were fitted to, random seeds inside the
boundary), so Voronoi cells clipped to the seeds' own hull would leave
its edge uncovered. The result therefore
carries that ground as attr(, "cover"): the boundary when one was
given, otherwise the convex hull of sample_points (for lon/lat points,
the hull of their coordinates in degrees, with the longitudes of points on
both sides of 180 degrees taken from 0 to 360, -170 as 190), otherwise
(for the scored centres of a resolution_profile() or a
select_resolution() result passed as n) the hull of the points the
profile was computed on.
build_tessellation() and
create_voronoi_polygons() derive their default boundary from it, so
build_tessellation(seeds, method = "voronoi") holds every observation
without a boundary. Seeds with no cover are tessellated over their own
hull unless a boundary or cover is passed then: method = "provided"
seeds given with neither boundary nor sample_points have none, and no
warning is raised for them, since they may be the observation sites
themselves. The attribute survives
sf::st_transform() and row subsetting; rbind() drops it.
A k-means seed is a mean of the points of its cluster, weighted under the
density kind, so it can lie outside a boundary that is not convex, in a
bay or a bend of a coast, even when every point lies inside. Tessellated
within that boundary, its cell is built if any of it lies inside: the part
of the study area nearer the seed than any other seed.
build_tessellation() gives the seed that cell in index, as it gives
every seed the cell it generates, so seeds$cell_id <- tess$index holds
each seed's cell for cell_values_at(). A seed with every part of the
study area nearer another seed has no cell, NA in index, and a
warning of class spatialkit_unassigned gives the number.
Sampling inside the boundary
Seeds drawn by method = "random", and the cloud method = "kmeans"
draws when no sample_points are given, are sampled inside boundary.
Its rows are repaired with sf::st_make_valid() before they are unioned.
In longitude and latitude the union runs with s2, and a row s2 still
refuses (crossing edges, a vertex listed twice) is repaired again, with
crossing edges split as GEOS splits them in a projected CRS; a row s2
refuses even then stops the call with an error of class
"spatialkit_cells_degenerate" that names it and says to transform
boundary to a projected CRS.
In longitude and latitude, a boundary whose bounding box is over 10,000
times its area (small pieces far apart), which sf does not sample whole,
is sampled piece by piece, the points shared among the pieces in
proportion to their areas; a piece whose own box is over 10,000 times its
area stops the call with an error that says to transform boundary to a
projected CRS. A boundary whose bounding box has no height or no width
(three vertices on one parallel) is refused. In longitude and latitude s2
reads the edges as great circles, which leave the bounding box read from
the coordinates, and sf (without lwgeom) draws in that box: a
boundary whose box has less than half its area on the sphere (three
vertices on or near one parallel) is refused too. That error, and the
error for a box with no height whose vertices lie on one parallel other
than the equator, say to transform boundary to a projected CRS in which
a parallel is a curve, such as the one ensure_projected() picks for it
(a polar one, such as EPSG:3413 or 3031, for a ring around a pole), where
the region has an area and lies in its box.
sf draws the points in the bounding box and keeps those inside, so it
draws the number asked for times the ratio of the box to the area. In any
CRS, a boundary that would take more than 10^6 points drawn in its box,
or 10 times the points asked for if more (small pieces far apart, a thin
strip at a slant), is sampled piece by piece in the same way (or whole,
in draws of at most 10^6 points in its box, where that takes less time),
and a piece that would still take more is drawn in such draws. Where the
points drawn in all would exceed 2e7 (or 10 times the points asked for,
if more), the call stops before any draw with an error that gives the
ratio and says to pass sample_points (method = "kmeans", whose cloud
is max(2000, 50 * n) points) or to ask for fewer seeds.
Examples
library(sf)
bnd <- st_sf(geometry = st_sfc(st_polygon(list(rbind(
c(0, 0), c(100, 0), c(100, 100), c(0, 100), c(0, 0)
))), crs = 32632))
get_voronoi_seeds(bnd, method = "random", n = 5, set_seed = 1)
#> Simple feature collection with 5 features and 2 fields
#> Geometry type: POINT
#> Dimension: XY
#> Bounding box: xmin: 20.16819 ymin: 6.178627 xmax: 90.82078 ymax: 94.46753
#> Projected CRS: WGS 84 / UTM zone 32N
#> seed_id method geometry
#> 1 1 random POINT (26.55087 89.83897)
#> 2 2 random POINT (37.21239 94.46753)
#> 3 3 random POINT (57.28534 66.07978)
#> 4 4 random POINT (90.82078 62.9114)
#> 5 5 random POINT (20.16819 6.178627)
# Seeds from a cloud with one dense place: density-weighted k-means (the
# default, 3 starts) against plain k-means. The fewest and most points a
# seed's cell holds under each kind, with more seeds than dense places:
set.seed(2)
cloud <- st_as_sf(data.frame(x = c(rnorm(150, 30, 5), runif(50, 0, 100)),
y = c(rnorm(150, 30, 5), runif(50, 0, 100))),
coords = c("x", "y"), crs = 32632)
dens <- get_voronoi_seeds(bnd, method = "kmeans", n = 20,
sample_points = cloud, set_seed = 1)
km <- get_voronoi_seeds(bnd, method = "kmeans", n = 20,
sample_points = cloud, set_seed = 1,
partition = "kmeans")
sizes <- list(density = attr(dens, "kmeans")$size,
kmeans = attr(km, "kmeans")$size)
sapply(sizes, range) # fewest and most points per seed
#> density kmeans
#> [1,] 6 1
#> [2,] 13 32