class StraightSkeleton::Nodes
Attributes
direction[R]
Public Class Methods
new(data)
click to toggle source
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 10 def initialize(data) @active, @indices = Set[], Hash.new.compare_by_identity data.to_d.map do |points| next points unless points.length > 2 points.inject [] do |points, point| points.last == point ? points : points << point end end.map.with_index do |(*points, point), index| points.first == point ? [points, :ring, (index unless points.hole?)] : [points << point, :segments, nil] end.each do |points, pair, index| normals = points.send(pair).map(&:difference).map(&:normalised).map(&:perp) points.map do |point| Vertex.new self, point end.each do |node| @active << node end.send(pair).zip(normals).each do |edge, normal| Nodes.stitch normal, *edge @indices[normal] = index if index end end end
solve(n0, n1, n2, x0, x1, x2)
click to toggle source
################################# solve for vector p and scalar t:
n0.p - t = x0 n1.p - t = x1 n2.p - t = x2
#################################
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 39 def self.solve(n0, n1, n2, x0, x1, x2) det = n2.cross(n1) + n1.cross(n0) + n0.cross(n2) return if det.zero? travel = (x0 * n1.cross(n2) + x1 * n2.cross(n0) + x2 * n0.cross(n1)) / det point = [n1.minus(n2).perp.times(x0), n2.minus(n0).perp.times(x1), n0.minus(n1).perp.times(x2)].inject(&:plus) / det [point, travel] end
solve_asym(n0, n1, n2, x0, x1, x2)
click to toggle source
################################# solve for vector p and scalar t:
n0.p - t = x0 n1.p - t = x1 n2 x p = x2
#################################
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 54 def self.solve_asym(n0, n1, n2, x0, x1, x2) det = n0.minus(n1).dot(n2) return if det.zero? travel = (x0 * n1.dot(n2) - x1 * n2.dot(n0) + x2 * n0.cross(n1)) / det point = (n2.times(x0 - x1).plus n0.minus(n1).perp.times(x2)) / det [point, travel] end
stitch(normal, *edge)
click to toggle source
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 5 def self.stitch(normal, *edge) edge[1].neighbours[0], edge[0].neighbours[1] = edge edge[1].normals[0] = edge[0].normals[1] = normal end
Public Instance Methods
collapse(edge)
click to toggle source
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 62 def collapse(edge) (n00, n01), (n10, n11) = edge.map(&:normals) p0, p1 = edge.map(&:point) t0, t1 = edge.map(&:travel) return if p0.equal? p1 good = [n00 && !n00.cross(n01).zero?, n11 && !n11.cross(n10).zero?] point, travel = case when good.all? then Nodes::solve(n00, n01, n11, n00.dot(p0) - t0, n01.dot(p1) - t1, n11.dot(p1) - t1) when good[0] then Nodes::solve_asym(n00, n01, n10, n00.dot(p0) - t0, n01.dot(p0) - t0, n10.cross(p1)) when good[1] then Nodes::solve_asym(n11, n10, n10, n11.dot(p1) - t1, n10.dot(p1) - t1, n01.cross(p0)) end || return return if travel * direction < @travel * direction return if @limit && travel.abs > @limit.abs @candidates << Collapse.new(self, point, travel, edge) end
include?(node)
click to toggle source
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 104 def include?(node) @active.include? node end
index(node)
click to toggle source
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 291 def index(node) @indices.values_at(*node.normals).find(&:itself) end
insert(node)
click to toggle source
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 108 def insert(node) @active << node @track[node.normals[1]] << node if node.normals[1] 2.times.inject [node] do |nodes| [nodes.first.prev, *nodes, nodes.last.next].compact end.segments.uniq.each do |edge| collapse edge end split node if node.splits? end
nodeset()
click to toggle source
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 125 def nodeset [].tap do |result| pending, processed = @active.dup, Set[] while pending.any? nodes = pending.take 1 while node = nodes.last.next and !processed.include?(node) nodes.push node processed << node end while node = nodes.first.prev and !processed.include?(node) nodes.unshift node processed << node end pending.subtract nodes nodes << nodes.first if nodes.first == nodes.last.next result << nodes end end end
progress(limit: nil, rounding_angle: DEFAULT_ROUNDING_ANGLE, cutoff_angle: nil, interval: nil, splits: true) { |:interval, travel, readout(travel)| ... }
click to toggle source
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 147 def progress(limit: nil, rounding_angle: DEFAULT_ROUNDING_ANGLE, cutoff_angle: nil, interval: nil, splits: true, &block) return self if limit && limit.zero? nodeset.tap do @active.clear @indices = nil end.map do |*nodes, node| nodes.first == node ? [nodes, :ring] : [nodes << node, :segments] end.each.with_index do |(nodes, pair), index| normals = nodes.send(pair).map do |edge| edge[0].normals[1] end nodes.map do |node| Vertex.new self, node.project(@limit) end.each do |node| @active << node end.send(pair).zip(normals).each do |edge, normal| Nodes.stitch normal, *edge end end if @limit @candidates, @travel, @limit, @direction = AVLTree.new, 0, limit && limit.to_d, limit ? limit <=> 0 : 1 rounding_angle *= Math::PI / 180 cutoff_angle *= Math::PI / 180 if cutoff_angle @track = Hash.new do |hash, normal| hash[normal] = Set[] end.compare_by_identity @active.group_by(&:point).reject do |point, nodes| case nodes.length when 1 then true when 2 nodes[0].next&.point == nodes[1].prev&.point && nodes[1].next&.point == nodes[0].prev&.point else false end end.each do |point, nodes| @active.subtract nodes nodes.inject [] do |events, node| events << [:incoming, node.prev] if node.prev events << [:outgoing, node.next] if node.next events end.sort_by do |event, node| case event when :incoming then [-@direction * node.normals[1].angle, 1] when :outgoing then [-@direction * node.normals[0].negate.angle, 0] end end.ring.map(&:transpose).each do |events, neighbours| node = Vertex.new self, point case events when [:outgoing, :incoming] then next when [:outgoing, :outgoing] Nodes.stitch neighbours[1].normals[0], node, neighbours[1] when [:incoming, :incoming] Nodes.stitch neighbours[0].normals[1], neighbours[0], node when [:incoming, :outgoing] Nodes.stitch neighbours[0].normals[1], neighbours[0], node Nodes.stitch neighbours[1].normals[0], node, neighbours[1] end @active << node end end @active.reject(&:terminal?).select do |node| direction * Math::atan2(node.normals.inject(&:cross), node.normals.inject(&:dot)) < -cutoff_angle end.each do |node| @active.delete node 2.times.map do Vertex.new self, node.point end.each.with_index do |vertex, index| vertex.normals[index] = node.normals[index] vertex.neighbours[index] = node.neighbours[index] vertex.neighbours[index].neighbours[1-index] = vertex @active << vertex end end if cutoff_angle @active.reject(&:terminal?).select(&:reflex?).each do |node| angle = Math::atan2 node.normals.inject(&:cross).abs, node.normals.inject(&:dot) extras = (angle / rounding_angle).floor next unless extras > 0 extra_normals = extras.times.map do |n| node.normals[0].rotate_by(angle * (n + 1) * -direction / (extras + 1)) end.each do |normal| @indices[normal] = @indices[node.normals[0]] if @indices end extra_nodes = extras.times.map do Vertex.new self, node.point end.each do |extra_node| @active << extra_node end edges = [node.neighbours[0], node, *extra_nodes, node.neighbours[1]].segments normals = [node.normals[0], *extra_normals, node.normals[1]] edges.zip(normals).each do |edge, normal| Nodes.stitch normal, *edge end end @active.select(&:next).map do |node| [node, node.next] end.each do |edge| collapse edge @track[edge[0].normals[1]] << edge[0] end.map do |edge| [edge.map(&:point).transpose.map(&:minmax), edge] end.tap do |bounds_edges| @index = RTree.load bounds_edges end @active.select(&:splits?).each do |node| split node end if splits travel = 0 while candidate = @candidates.pop next unless candidate.viable? @travel = candidate.travel while travel < @travel yield :interval, travel, readout(travel) travel += interval end if interval && block_given? candidate.replace! do |node, index = 0| @active.delete node yield :nodes, *[node, candidate].rotate(index).map(&:original) if block_given? end end self end
readout(travel = @limit)
click to toggle source
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 279 def readout(travel = @limit) nodeset.map do |nodes| nodes.map do |node| node.project(travel).to_f end end.map do |points| points.segments.reject do |segment| segment.inject(&:==) end.map(&:last).unshift(points.first) end.reject(&:one?) end
split(node)
click to toggle source
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 78 def split(node) bounds = node.project(@limit).zip(node.point).map do |centre, coord| [coord, centre - @limit, centre + @limit].minmax end if @limit @index.search(bounds).map do |edge| p0, p1, p2 = [*edge, node].map(&:point) t0, t1, t2 = [*edge, node].map(&:travel) (n00, n01), (n10, n11), (n20, n21) = [*edge, node].map(&:normals) next if p0 == p2 || p1 == p2 next if node.terminal? and Split === node and node.source.normals[0].equal? n01 next if node.terminal? and Split === node and node.source.normals[1].equal? n01 next unless node.terminal? || [n20, n21].compact.inject(&:plus).dot(n01) < 0 point, travel = case when n20 && n21 then Nodes::solve(n20, n21, n01, n20.dot(p2) - t2, n21.dot(p2) - t2, n01.dot(p0) - t0) when n20 then Nodes::solve_asym(n01, n20, n20, n01.dot(p0) - t0, n20.dot(p2) - t2, n20.cross(p2)) when n21 then Nodes::solve_asym(n01, n21, n21, n01.dot(p0) - t0, n21.dot(p2) - t2, n21.cross(p2)) end || next next if travel * @direction < node.travel next if @limit && travel.abs > @limit.abs next if point.minus(p0).dot(n01) * @direction < 0 Split.new self, point, travel, node, edge[0] end.compact.each do |split| @candidates << split end end
track(normal)
click to toggle source
# File lib/nswtopo/geometry/straight_skeleton/nodes.rb, line 119 def track(normal) @track[normal].select(&:active?).map do |node| [node, node.next] end end