# Based on:
# Fast Point-Feature Label Placement Algorithm for Real Time Screen Maps
# (Missae Yamamoto, Gilberto Camara, Luiz Antonio Nogueira Lorena)
require_relative 'labels/barriers'
require_relative 'labels/convex_hull'
require_relative 'labels/convex_hulls'
require_relative 'labels/label'
module NSWTopo
module Labels
using Helpers
include VectorRender, Log
CENTRELINE_FRACTION = 0.35
DEFAULT_SAMPLE = 5
INSET = 1
LABEL_ATTRIBUTES = %w[
coexist
curved
font-family
font-size
font-style
font-variant
font-weight
format
knockout
letter-spacing
line-height
margin
max-angle
max-turn
min-radius
optional
orientation
position
sample
separation
separation-all
separation-along
shield
upcase
word-spacing
]
LABEL_TRANSFORMS = %w[
buffer
fallback
keep-largest
minimum-area
minimum-hole
minimum-length
offset
reduce
remove
remove-holes
smooth
trim
]
LABEL_PARAMS = LABEL_ATTRIBUTES + LABEL_TRANSFORMS + SVG_ATTRIBUTES
DEFAULTS = YAML.load <<~YAML
knockout: true
preserve: true
stroke: none
fill: black
font-style: italic
font-family: Arial, Helvetica, sans-serif
font-size: 1.8
line-height: 110%
margin: 1.0
max-turn: 60
min-radius: 0
max-angle: #{StraightSkeleton::DEFAULT_ROUNDING_ANGLE}
sample: #{DEFAULT_SAMPLE}
YAML
DEBUG_PARAMS = YAML.load <<~YAML
debug:
dupe: ~
fill: none
opacity: 0.5
knockout: false
debug feature:
stroke: hsl(260,100%,50%)
stroke-width: 0.2
symbol:
circle:
r: 0.3
stroke: none
fill: hsl(260,100%,50%)
debug candidate:
stroke: hsl(300,100%,50%)
stroke-width: 0.2
YAML
def barriers
@barriers ||= Barriers.new
end
def label_features
@label_features ||= []
end
def conflicts
@conflicts ||= Hash.new do |conflicts, label|
conflicts[label] = Set[]
end
end
extend Forwardable
delegate :<< => :barriers
def add(layer)
label_params = layer.params.fetch("labels", {})
label_params.except(*LABEL_PARAMS).select do |key, value|
Hash === value
end.transform_keys do |categories|
Array(categories).map do |category|
[layer.name, category].join(?\s)
end
end.then do |params|
{ layer.name => label_params }.merge(params)
end.transform_values do |params|
params.slice(*LABEL_PARAMS)
end.transform_values do |params|
# handle legacy format for separation, separation-all, separation-along
params.each.with_object("separation" => Hash[]) do |(key, value), hash|
case [key, value]
in ["separation", Hash] then hash["separation"].merge! value
in ["separation", *] then hash["separation"].merge! "self" => value
in ["separation-all", *] then hash["separation"].merge! "other" => value
in ["separation-along", *] then hash["separation"].merge! "along" => value
else hash[key] = value
end
end
end.then do |category_params|
@params.merge! category_params
end
feature_count = feature_total = 0
layer.labeling_features.tap do |features|
feature_total = features.length
end.map(&:multi).group_by do |feature|
Set[layer.name, *feature["category"]]
end.each do |categories, features|
transforms = params_for(categories).slice(*LABEL_TRANSFORMS)
attributes, point_attributes, line_attributes = [nil, "point", "line"].map do |extra_category|
categories | Set[*extra_category]
end.map do |categories|
params_for(categories).slice(*LABEL_ATTRIBUTES).merge(categories: categories)
end
features.map do |feature|
log_update "collecting labels: %s: feature %i of %i" % [layer.name, feature_count += 1, feature_total]
text = feature["label"]
text = case
when REXML::Element === text then text
when attributes["format"] then attributes["format"] % text
else Array(text).map(&:to_s).map(&:strip).join(?\s)
end
dual = feature["dual"]
text.upcase! if String === text && attributes["upcase"]
dual.upcase! if String === dual && attributes["upcase"]
feature_attributes = { text: text, dual: dual, layer_name: layer.name }
transforms.inject([feature]) do |features, (transform, (arg, *args))|
next features unless arg
opts, args = args.partition do |arg|
Hash === arg
end
opts = opts.inject({}, &:merge).transform_keys(&:to_sym)
features.flat_map do |feature|
case transform
when "reduce"
case arg
when "skeleton"
feature.respond_to?(arg) ? feature.send(arg) : feature
when "centrelines"
feature.respond_to?(arg) ? feature.send(arg, **opts) : feature
when "centrepoints"
interval = Float(opts.delete(:interval) || DEFAULT_SAMPLE)
feature.respond_to?(arg) ? feature.send(arg, interval: interval, **opts) : feature
when "centres"
interval = Float(opts.delete(:interval) || DEFAULT_SAMPLE)
feature.respond_to?(arg) ? feature.send(arg, interval: interval, **opts) : feature
when "centroids"
feature.respond_to?(arg) ? feature.send(arg) : feature
when "samples"
interval = Float(opts.delete(:interval) || DEFAULT_SAMPLE)
feature.respond_to?(arg) ? feature.send(arg, interval) : feature
else
raise "unrecognised label transform: reduce: %s" % arg
end
when "fallback"
case arg
when "samples"
next feature unless feature.respond_to? arg
interval = Float(opts.delete(:interval) || DEFAULT_SAMPLE)
[feature, *feature.send(arg, interval)]
else
raise "unrecognised label transform: fallback: %s" % arg
end
when "offset", "buffer"
next feature unless feature.respond_to? transform
margins = [arg, *args].map { |value| Float(value) }
feature.send transform, *margins, **opts
when "smooth"
next feature unless feature.respond_to? transform
margin = Float(arg)
max_turn = attributes["max-turn"] * Math::PI / 180
feature.send transform, margin, cutoff_angle: max_turn, **opts
when "minimum-area"
area = Float(arg)
case feature
when GeoJSON::MultiLineString
feature.reject_linestrings do |linestring|
linestring.closed? && linestring.signed_area.abs < area
end
when GeoJSON::MultiPolygon
feature.reject_polygons do |polygon|
polygon.area < area
end
else
feature
end
when "minimum-length"
next feature unless GeoJSON::MultiLineString === feature
distance = Float(arg)
feature.reject_linestrings do |linestring|
linestring.path_length < distance
end
when "minimum-hole", "remove-holes"
next feature unless GeoJSON::MultiPolygon === feature
area = Float(arg).abs unless true == arg
feature.remove_holes do |ring|
area ? (-area...0) === ring.signed_area : true
end
when "remove"
remove = [arg, *args].any? do |value|
case value
when true then true
when String then text == value
when Regexp then text =~ value
when Numeric then text == value.to_s
end
end
remove ? [] : feature
when "keep-largest"
case feature
when GeoJSON::MultiLineString
feature.max_by(&:path_length).multi
when GeoJSON::MultiPolygon
feature.max_by(&:area).multi
else
feature
end
when "trim"
next feature unless GeoJSON::MultiLineString === feature
distance = Float(arg)
feature.trim distance
end
end
rescue ArgumentError
raise "invalid label transform: %s: %s" % [transform, [arg, *args].join(?,)]
end.reject(&:empty?).map do |feature|
case feature
when GeoJSON::MultiPoint then feature.with_properties(**feature_attributes, **point_attributes)
when GeoJSON::MultiLineString then feature.with_properties(**feature_attributes, **line_attributes)
when GeoJSON::MultiPolygon then feature.with_properties(**feature_attributes, **line_attributes)
end
end.flat_map(&:explode)
end.then do |features|
next features unless label_params["collate"]
features.flatten.group_by do |feature|
feature[:text]
end.values
end.each do |features|
label_features << features
end
end
end
def map_contains?(label)
@labelling_neatline ||= @map.neatline(mm: -INSET).first
@labelling_neatline.contains? label.hull
end
def point_candidates(feature)
margin = feature["margin"]
line_height = feature["line-height"]
font_size = feature["font-size"]
text = feature[:text]
point = feature.coordinates
lines = Font.in_two text, feature.properties
lines = [[text, Font.glyph_length(text, feature.properties)]] if lines.map(&:first).map(&:length).min == 1
height = lines.map { font_size }.inject { |total| total + line_height }
# if feature["shield"]
# width += SHIELD_X * font_size
# height += SHIELD_Y * font_size
# end
[*feature["position"] || "over"].map do |position|
dx = position =~ /right$/ ? 1 : position =~ /left$/ ? -1 : 0
dy = position =~ /^below/ ? 1 : position =~ /^above/ ? -1 : 0
next dx, dy, dx * dy == 0 ? 1 : 0.6
end.uniq.map.with_index do |(dx, dy, f), position_index|
text_elements, baselines = lines.map.with_index do |(line, text_length), index|
offset_x = dx * (f * margin + 0.5 * text_length)
offset_y = dy * (f * margin + 0.5 * height)
offset_y += (index - 0.5) * 0.5 * height unless lines.one?
anchor = point + Vector[offset_x, offset_y]
text_element = REXML::Element.new("text")
text_element.add_attribute "transform", "translate(%s)" % POINT % anchor
text_element.add_attribute "text-anchor", "middle"
text_element.add_attribute "textLength", VALUE % text_length
text_element.add_attribute "y", VALUE % (CENTRELINE_FRACTION * font_size)
text_element.add_text line
offset = Vector[0.5 * text_length, 0]
baseline = GeoJSON::LineString.new [anchor - offset, anchor + offset]
next text_element, baseline
end.transpose
priority = [position_index, feature[:feature_index]]
Label.new baselines.inject(&:+), feature, priority, text_elements, &barriers
end.reject do |candidate|
candidate.optional? && candidate.barriers?
end.select do |candidate|
map_contains? candidate
end.tap do |candidates|
candidates.combination(2).each do |candidate1, candidate2|
conflicts[candidate1] << candidate2
conflicts[candidate2] << candidate1
end
end
end
def line_string_candidates(feature)
orientation = feature["orientation"]
max_turn = feature["max-turn"] * Math::PI / 180
min_radius = feature["min-radius"]
max_angle = feature["max-angle"] * Math::PI / 180
curved = feature["curved"]
sample = feature["sample"]
font_size = feature["font-size"]
text = feature[:text]
closed = feature.closed?
text_length = case text
when REXML::Element then feature.path_length
when String then Font.glyph_length text, feature.properties
end
points, deltas, angles, avoid = feature.coordinates.each_cons(2).flat_map do |p0, p1|
next [p0] if REXML::Element === text
distance = (p1 - p0).norm
next [p0] if curved && distance >= text_length
(0...1).step(sample/distance).map do |fraction|
p0 * (1 - fraction) + p1 * fraction
end
end.then do |points|
if closed
p0, p2 = points.last, points.first
points.unshift(p0).push(p2)
else
points.push(feature.coordinates.last).unshift(nil).push(nil)
end
end.each_cons(3).map do |p0, p1, p2|
next p1, 0, 0, false unless p0
next p1, (p1 - p0).norm, 0, false unless p2
o01, o12, o20 = p1 - p0, p2 - p1, p0 - p2
l01, l12, l20 = o01.norm, o12.norm, o20.norm
h01, h12 = o01 / l01, o12 / l12
angle = Math::atan2 h01.cross(h12), h01.dot(h12)
semiperimeter = (l01 + l12 + l20) / 2
area_squared = [0, semiperimeter * (semiperimeter - l01) * (semiperimeter - l12) * (semiperimeter - l20)].max
curvature = 4 * Math::sqrt(area_squared) / (l01 * l12 * l20)
avoid = angle.abs > max_angle || min_radius * (curvature || 0) > 1
next p1, l01, angle, avoid
end.transpose
total, distances = deltas.inject([0, []]) do |(total, distances), delta|
next total += delta, distances << total
end
start = points.length.times
stop = closed ? points.length.times.cycle : points.length.times
indices = [stop.next]
Enumerator.produce do
while indices.length > 1 && deltas.values_at(*indices).drop(1).sum >= text_length do
start.next
indices.shift
end
until indices.length > 1 && deltas.values_at(*indices).drop(1).sum >= text_length do
indices.push stop.next
end
interior = indices.values_at(1...-1)
angle_sum, angle_sum_min, angle_sum_max, angle_square_sum = interior.inject [0, 0, 0, 0] do |(sum, min, max, square_sum), index|
next sum += angles[index], [min, sum].min, [max, sum].max, square_sum + angles[index]**2
end
redo if angle_sum_max - angle_sum_min > max_turn
redo if curved && indices.length < 3
redo if avoid.values_at(*interior).any?
baseline = GeoJSON::LineString.new(points.values_at *indices).crop(text_length).then do |baseline|
case orientation
when "uphill", "anticlockwise" then true
when "downhill", "clockwise" then false
else baseline.coordinates.values_at(0, -1).map(&:x).inject(&:<=)
end ? baseline : baseline.reverse
end
along = distances.values_at(indices.first, indices.last).then do |d0, d1|
(d0 + ((d1 - d0) % total) / 2) % total
end
priority = [angle_square_sum, (total - 2 * along).abs / total]
path_id = [@name, "path", *feature.values_at(:layer_name, :label_index, :feature_index), indices.first, indices.last].join ?.
path_element = REXML::Element.new("path")
path_element.add_attributes "id" => path_id, "d" => baseline.svg_path_data, "pathLength" => VALUE % text_length
text_element = REXML::Element.new("text")
case text
when REXML::Element
fixed = true
text_element.add_element text, "href" => "#%s" % path_id
when String
text_path = text_element.add_element "textPath", "href" => "#%s" % path_id, "textLength" => VALUE % text_length, "spacing" => "auto"
text_path.add_element("tspan", "dy" => VALUE % (CENTRELINE_FRACTION * font_size)).add_text(text)
end
Label.new baseline, feature, priority, [text_element, path_element], along: along, fixed: fixed, &barriers
end.reject do |candidate|
candidate.optional? && candidate.barriers?
end.select do |candidate|
map_contains? candidate
end.then do |candidates|
neighbours = Hash.new do |hash, candidate|
hash[candidate] = Set[]
end
candidates.each.with_index do |candidate1, index1|
index2 = index1
loop do
index2 = (index2 + 1) % candidates.length
break if index2 == (closed ? index1 : 0)
candidate2 = candidates[index2]
offset = candidate2.along - candidate1.along
break unless offset % total < sample || (closed && -offset % total < sample)
neighbours[candidate2] << candidate1
neighbours[candidate1] << candidate2
end
end
removed = Set[]
candidates.sort.each.with_object Array[] do |candidate, sampled|
next if removed === candidate
removed.merge neighbours[candidate]
sampled << candidate
end.tap do |candidates|
next unless separation = feature.dig("separation", "along")
separation += text_length
sorted = candidates.sort_by(&:along)
sorted.each.with_index do |candidate1, index1|
index2 = index1
loop do
index2 = (index2 + 1) % candidates.length
break if index2 == (closed ? index1 : 0)
candidate2 = sorted[index2]
offset = candidate2.along - candidate1.along
break unless offset % total < separation || (closed && -offset % total < separation)
conflicts[candidate2] << candidate1
conflicts[candidate1] << candidate2
end
end
end
end
end
def label_candidates(&debug)
label_features.flat_map.with_index do |features, label_index|
log_update "compositing %s: feature %i of %i" % [@name, label_index + 1, label_features.length]
features.map do |feature|
font_size = feature["font-size"]
properties = feature.slice(*FONT_SCALED_ATTRIBUTES).transform_values do |value|
/^\d+%$/ === value ? value.to_i * font_size * 0.01 : value
end.then do |scaled_properties|
feature.except(*FONT_SCALED_ATTRIBUTES).merge(scaled_properties)
end
feature.with_properties(**properties)
end.flat_map do |feature|
case feature
when GeoJSON::Point, GeoJSON::LineString
feature
when GeoJSON::Polygon
feature.rings.explode
end
end.tap do |features|
features.each.with_object("feature", &debug) if Config["debug"]
end.map.with_index do |feature, feature_index|
feature.add_properties label_index: label_index, feature_index: feature_index
end.flat_map do |feature|
case feature
when GeoJSON::Point
point_candidates(feature)
when GeoJSON::LineString
line_string_candidates(feature)
end
end.tap do |candidates|
candidates.reject!(&:point?) unless candidates.all?(&:point?)
end.sort.each.with_index do |candidate, index|
candidate.priority.replace [index]
end
end.tap do |candidates|
log_update "compositing %s: choosing label positions" % @name
if Config["debug"]
candidates.flat_map(&:explode).map do |ring|
GeoJSON::LineString.new [*ring, ring.first]
end.each.with_object("candidate", &debug)
candidates.clear
end
Enumerator.new do |yielder|
# separation/self: minimum distance between a label and another label for the same feature
candidates.group_by do |label|
label.label_index
end.values.each do |group|
Label.overlaps(group) do |label|
label.separation["self"]
end.each(&yielder)
end
# separation/same: minimum distance between a label and another label with the same text
candidates.group_by do |label|
[label.layer_name, label.text]
end.values.each do |group|
Label.overlaps(group) do |label|
label.separation["same"]
end.each(&yielder)
end
candidates.group_by do |candidate|
candidate.layer_name
end.each do |layer_name, group|
# separation/other: minimum distance between a label and another label from the same layer
Label.overlaps(group) do |label|
label.separation["other"]
end.each(&yielder)
# separation/<layer>: minimum distance between a label and any label from <layer>
Label.overlaps(group, candidates) do |label|
label.separation[layer_name]
end.each(&yielder)
end
# separation/dual: minimum distance between any two dual labels
candidates.select(&:dual).group_by do |label|
[label.layer_name, Set[label.text, label.dual]]
end.values.each do |group|
Label.overlaps(group) do |label|
label.separation["dual"]
end.each(&yielder)
end
# separation/all: minimum distance between a label and *any* other label
Label.overlaps(candidates) do |label|
# default of zero prevents any two labels overlapping
label.separation["all"] || 0
end.reject do |label1, label2|
label1.coexists_with?(label2) ||
label2.coexists_with?(label1)
end.each(&yielder)
end.each do |label1, label2|
conflicts[label1] << label2
conflicts[label2] << label1
end
end
end
def drawing_features
debug_features = []
candidates = label_candidates do |feature, category|
debug_features << [feature, Set["debug", category]]
end
ordered, unlabeled = AVLTree.new, Hash.new(true)
remaining = candidates.to_set.classify(&:label_index)
Enumerator.produce do |label|
if label
removals = Set[label] | conflicts[label]
if first = unlabeled[label.label_index]
removals.merge remaining[label.label_index].select(&:barriers?)
unlabeled[label.label_index] = false
end
removals.each do |candidate|
remaining[candidate.label_index].delete candidate
ordered.delete candidate
end
conflicts.values_at(*removals).inject(Set[], &:|).subtract(removals).each do |candidate|
conflicts[candidate].subtract removals
end.tap do |changed|
changed.merge remaining[label.label_index] if first
end
else
candidates
end.each do |candidate|
conflict_count = conflicts[candidate].each.with_object Set[] do |other, indices|
indices << other.label_index
end.delete(candidate.label_index).size
conflict_count += candidate.barrier_count
unsafe = conflicts[candidate].classify(&:label_index).any? do |label_index, conflicts|
next false unless unlabeled[label_index]
others = remaining[label_index].reject(&:optional?)
others.any? && others.all?(conflicts)
end
ordinal = [
candidate.fixed ? 0 : 1, # fixed grid-line labels
candidate.optional? ? 1 : 0, # non-optional candidates
unsafe ? 1 : 0, # candidates which don't prevent another feature being labeled altogether
unlabeled[candidate.label_index] ? 0 : 1, # candidates for unlabeled features
conflict_count, # candidates with fewer conflicts
candidate.priority # better quality candidates
]
unless candidate.ordinal == ordinal
ordered.delete candidate
candidate.ordinal.replace ordinal
ordered.insert candidate
end
end
ordered.first or raise StopIteration
end.to_set.tap do |labels|
grouped = candidates.group_by(&:indices)
5.times do
labels.select(&:point?).each do |label|
labels.delete label
labels << grouped[label.indices].min_by do |candidate|
[(labels & conflicts[candidate] - Set[label]).count, candidate.priority]
end
end
end
end.flat_map do |label|
label.elements.map.with_object(label.categories).entries
end.tap do |result|
next unless debug_features.any?
@params = DEBUG_PARAMS.deep_merge @params
result.concat debug_features
end
end
end
end