lib/geometry/polyline.rb in geometry-6 vs lib/geometry/polyline.rb in geometry-6.1
- old
+ new
@@ -14,11 +14,11 @@
class Polyline
attr_reader :edges, :vertices
# Construct a new Polyline from Points and/or Edges
- # The constructor will try to convert all of its arguments into {Point}s and
+ # @note The constructor will try to convert all of its arguments into {Point}s and
# {Edge}s. Then successive {Point}s will be collpased into {Edge}s. Successive
# {Edge}s that share a common vertex will be added to the new {Polyline}. If
# there's a gap between {Edge}s it will be automatically filled with a new
# {Edge}.
# @overload initialize(Edge, Edge, ...)
@@ -92,25 +92,98 @@
def eql?(other)
@vertices.zip(other.vertices).all? {|a,b| a == b}
end
alias :== :eql?
- # Offset the receiver by the specified distance. A positive distance
- # will offset to the left, and a negative distance to the right.
+ # Clone the receiver, close it, then return it
+ # @return [Polyline] the closed clone of the receiver
+ def close
+ clone.close!
+ end
+
+ # Close the receiver and return it
+ # @return [Polyline] the receiver after closing
+ def close!
+ push_edge Edge.new(@edges.last.last, @edges.first.first) unless @edges.empty? || closed?
+ self
+ end
+
+ # Check to see if the {Polyline} is closed (ie. is it a {Polygon}?)
+ # @return [Bool] true if the {Polyline} is closed (the first vertex is equal to the last vertex)
+ def closed?
+ @edges.last.last == @edges.first.first
+ end
+
+ # Clone the receiver, reverse it, then return it
+ # @return [Polyline] the reversed clone
+ def reverse
+ self.class.new *(edges.reverse.map! {|edge| edge.reverse! })
+ end
+
+ # Reverse the receiver and return it
+ # @return [Polyline] the reversed receiver
+ def reverse!
+ vertices.reverse!
+ edges.reverse!.map! {|edge| edge.reverse! }
+ self
+ end
+
+ # @group Bisectors
+
+ # Generate the angle bisector unit vectors for each vertex
+ # @note If the {Polyline} isn't closed (the normal case), then the first and
+ # last vertices will be given bisectors that are perpendicular to themselves.
+ # @return [Array<Vector>] the unit {Vector}s representing the angle bisector of each vertex
+ def bisectors
+ # Multiplying each bisector by the sign of k flips any bisectors that aren't pointing towards the interior of the angle
+ bisector_map {|b, k| k <=> 0 }
+ end
+
+ # Generate left-side angle bisector unit vectors for each vertex
+ # @note This is similar to the #bisector method, but generates vectors that always point to the left side of the {Polyline} instead of towards the inside of each corner
+ # @return [Array<Vector>] the unit {Vector}s representing the left-side angle bisector of each vertex
+ def left_bisectors
+ bisector_map
+ end
+
+ # Generate right-side angle bisector unit vectors for each vertex
+ # @note This is similar to the #bisector method, but generates vectors that always point to the right side of the {Polyline} instead of towards the inside of each corner
+ # @return [Array<Vector>] the unit {Vector}s representing the ride-side angle bisector of each vertex
+ def right_bisectors
+ bisector_map {|b, k| -1 }
+ end
+
+ # Generate the spokes for each vertex. A spoke is the same as a bisector, but in the oppostire direction (bisectors point towards the inside of each corner; spokes point towards the outside)
+ # @note If the {Polyline} isn't closed (the normal case), then the first and
+ # last vertices will be given bisectors that are perpendicular to themselves.
+ # @return [Array<Vector>] the unit {Vector}s representing the spoke of each vertex
+ def spokes
+ # Multiplying each bisector by the negated sign of k flips any bisectors that aren't pointing towards the exterior of the angle
+ bisector_map {|b, k| 0 <=> k }
+ end
+
+ # @endgroup Bisectors
+
+ # Offset the receiver by the specified distance
+ # @note A positive distance will offset to the left, and a negative distance to the right.
# @param [Number] distance The distance to offset by
- # @return [Polygon] A new {Polygon} outset by the given distance
+ # @return [Polyline] A new {Polyline} outset by the given distance
def offset(distance)
- bisectors = offset_bisectors(distance)
- offsets = bisectors.each_cons(2).to_a
+ bisector_pairs = if closed?
+ bisector_edges = offset_bisectors(distance)
+ bisector_edges.push(bisector_edges.first).each_cons(2)
+ else
+ offset_bisectors(distance).each_cons(2)
+ end
# Create the offset edges and then wrap them in Hashes so the edges
# can be altered while walking the array
- active_edges = edges.zip(offsets).map do |e,offset|
- offset = Edge.new(e.first+offset.first.vector, e.last+offset.last.vector)
+ active_edges = edges.zip(bisector_pairs).map do |e,offset|
+ offset_edge = Edge.new(e.first+offset.first.vector, e.last+offset.last.vector)
# Skip zero-length edges
- {:edge => (offset.first == offset.last) ? nil : offset}
+ {:edge => (offset_edge.first == offset_edge.last) ? nil : offset_edge}
end
# Walk the array and handle any intersections
for i in 0..(active_edges.count-1) do
e1 = active_edges[i][:edge]
@@ -141,39 +214,72 @@
end
alias :leftset :offset
# Rightset the receiver by the specified distance
# @param [Number] distance The distance to offset by
- # @return [Polygon] A new {Polygon} rightset by the given distance
+ # @return [Polyline] A new {Polyline} rightset by the given distance
def rightset(distance)
offset(-distance)
end
private
- # @group Helpers for offset()
-
- # Vertex bisectors suitable for offsetting
- # @param [Number] length The distance to offset by
- # @return [Array<Edge>] {Edge}s representing the bisectors
- def offset_bisectors(length)
- vectors = edges.map {|e| e.direction }
+ # Generate bisectors and k values with an optional mapping block
+ # @note If the {Polyline} isn't closed (the normal case), then the first and
+ # last vertices will be given bisectors that are perpendicular to themselves.
+ # @return [Array<Vector>] the unit {Vector}s representing the angle bisector of each vertex
+ def bisector_map
winding = 0
- sums = vectors.unshift(vectors.first).push(vectors.last).each_cons(2).map do |v1,v2|
+ tangent_loop.each_cons(2).map do |v1,v2|
k = v1[0]*v2[1] - v1[1]*v2[0] # z-component of v1 x v2
winding += k
if v1 == v2 # collinear, same direction?
- Vector[-v1[1], v1[0]]
+ bisector = Vector[-v1[1], v1[0]]
+ block_given? ? (bisector * yield(bisector, 1)) : bisector
elsif 0 == k # collinear, reverse direction
nil
else
- by = (v2[1] - v1[1])/k
- v = (0 == v1[1]) ? v2 : v1
- Vector[(v[0]*by - 1)/v[1], by]
+ bisector_y = (v2[1] - v1[1])/k
+
+ # If v1 or v2 happens to be horizontal, then the other one must be used when calculating
+ # the x-component of the bisector (to avoid a divide by zero). But, comparing floats
+ # with zero is problematic, so use the one with the largest y-component instead checking
+ # for a y-component equal to zero.
+ v = (v2[1].abs > v1[1].abs) ? v2 : v1
+
+ bisector = Vector[(v[0]*bisector_y - 1)/v[1], bisector_y]
+ block_given? ? (bisector * yield(bisector, k)) : bisector
end
end
+ end
- vertices.zip(sums).map {|v,b| b ? Edge.new(v, v+(b * length)) : nil}
+ # @group Helpers for offset()
+
+ # Vertex bisectors suitable for offsetting
+ # @param [Number] length The distance to offset by. Positive generates left offset bisectors, negative generates right offset bisectors
+ # @return [Array<Edge>] {Edge}s representing the bisectors
+ def offset_bisectors(length)
+ vertices.zip(left_bisectors).map {|v,b| b ? Edge.new(v, v+(b * length)) : nil}
+ end
+
+ # Generate the tangents and fake a circular buffer while accounting for closedness
+ # @return [Array<Vector>] the tangents
+ def tangent_loop
+ edges.map {|e| e.direction }.tap do |tangents|
+ # Generating a bisector for each vertex requires an edge on both sides of each vertex.
+ # Obviously, the first and last vertices each have only a single adjacent edge, unless the
+ # Polyline happens to be closed (like a Polygon). When not closed, duplicate the
+ # first and last direction vectors to fake the adjacent edges. This causes the first and last
+ # edges to have bisectors that are perpendicular to themselves.
+ if closed?
+ # Prepend the last direction vector so that the last edge can be used to find the bisector for the first vertex
+ tangents.unshift tangents.last
+ else
+ # Duplicate the first and last direction vectors to compensate for not having edges adjacent to the first and last vertices
+ tangents.unshift(tangents.first)
+ tangents.push(tangents.last)
+ end
+ end
end
# Find the next edge that intersects with e, starting at index i
def find_next_intersection(edges, i, e)
for j in i..(edges.count-1)