require_relative 'edge'
require_relative 'polyline'
module Geometry
=begin rdoc
A {Polygon} is a closed path comprised entirely of lines so straight they don't even curve.
{http://en.wikipedia.org/wiki/Polygon}
The {Polygon} class is generally intended to represent {http://en.wikipedia.org/wiki/Simple_polygon Simple polygons},
but there's currently nothing that enforces simplicity.
== Usage
=end
class Polygon < Polyline
# Construct a new Polygon from Points and/or Edges
# The constructor will try to convert all of its arguments into {Points} and
# {Edges}. Then successive {Points} will be collpased into {Edges}. Successive
# {Edges} that share a common vertex will be added to the new {Polygon}. If
# there's a gap between {Edges} it will be automatically filled with a new
# {Edge}. The resulting Polygon will then be closed, if it isn't already.
# @overload initialize(Edge, Edge, ...)
# @return [Polygon]
# @overload initialize(Point, Point, ...)
# @return [Polygon]
def initialize(*args)
super
close! # A Polygon is always closed
end
# This method returns the receiver because a {Polygon} is always closed
# @return [Polygon] the receiver
def close
close!
end
# Check the orientation of the {Polygon}
# @return [Boolean] True if the {Polygon} is clockwise, otherwise false
def clockwise?
edges.map {|e| (e.last.x - e.first.x) * (e.last.y + e.first.y)}.reduce(:+) >= 0
end
# @return [Polygon] A new {Polygon} with orientation that's the opposite of the receiver
def reverse
self.class.new *(self.vertices.reverse)
end
# Reverse the receiver and return it
# @return [Polygon] the reversed receiver
def reverse!
super
# Simply reversing the vertex array causes the reversed polygon to
# start at what had been the last vertex, instead of starting at
# the same vertex and just going the other direction.
vertices.unshift vertices.pop
self
end
# @group Boolean operators
# Test a {Point} for inclusion in the receiver using a simplified winding number algorithm
# @param [Point] point The {Point} to test
# @return [Number] 1 if the {Point} is inside the {Polygon}, -1 if it's outside, and 0 if it's on an {Edge}
def <=>(point)
sum = edges.reduce(0) do |sum, e|
direction = e.last.y <=> e.first.y
# Ignore edges that don't cross the point's x coordinate
next sum unless ((point.y <=> e.last.y) + (point.y <=> e.first.y)).abs <= 1
if 0 == direction # Special case horizontal edges
return 0 if ((point.x <=> e.last.x) + (point.x <=> e.first.x)).abs <= 1
next sum # Doesn't intersect
else
is_left = e <=> point
return 0 if 0 == is_left
next sum unless is_left
sum += 0 <=> (direction + is_left)
end
end
(0 == sum) ? -1 : 1
end
# Create a new {Polygon} that's the union of the receiver and a passed {Polygon}
# This is a simplified implementation of the alogrithm outlined in the
# paper {http://gvu.gatech.edu/people/official/jarek/graphics/papers/04PolygonBooleansMargalit.pdf An algorithm for computing the union, intersection or difference of two polygons}.
# In particular, this method assumes the receiver and passed {Polygon}s are "island" type and that the desired output is "regular", as those terms are described in the paper.
# @param [Polygon] other The {Polygon} to union with the receiver
# @return [Polygon] The union of the receiver and the passed {Polygon}
def union(other)
# Table 1: Both polygons are islands and the operation is union, so both must have the same orientation
# Reverse the other polygon if the orientations are different
other = other.reverse if self.clockwise? != other.clockwise?
# Receiver's vertex ring
ringA = VertexRing.new
self.vertices.each {|v| ringA.push v, (other <=> v)}
# The other vertex ring
ringB = VertexRing.new
other.vertices.each {|v| ringB.push v, (self <=> v)}
# Find intersections
offsetA = 0
edgesB = other.edges.dup
self.edges.each_with_index do |a, indexA|
offsetB = 0
ringB.edges_with_index do |b, indexB|
intersection = a.intersection(b)
if intersection === true
if (a.first == b.first) and (a.last == b.last) # Equal edges
elsif (a.first == b.last) and (a.last == b.first) # Ignore equal but opposite edges
else
if a.direction == b.direction # Same direction?
offsetA += 1 if ringA.insert_boundary(indexA + 1 + offsetA, b.first)
offsetB += 1 if ringB.insert_boundary(indexB + 1 + offsetB, a.last)
else # Opposite direction
offsetA += 1 if ringA.insert_boundary(indexA + 1 + offsetA, b.last)
offsetB += 1 if ringB.insert_boundary(indexB + 1 + offsetB, a.first)
end
end
elsif intersection.is_a?(Point)
offsetA += 1 if ringA.insert_boundary(indexA + 1 + offsetA, intersection)
offsetB += 1 if ringB.insert_boundary(indexB + 1 + offsetB, intersection)
end
end
end
# Table 2: Both polygons are islands and the operation is union, so select outside from both polygons
edgeFragments = []
[[ringA, other], [ringB, self]].each do |ring, other_polygon|
ring.edges do |v1,v2|
if (v1[:type] == -1) or (v2[:type] == -1)
edgeFragments.push :first => v1[:vertex], :last => v2[:vertex]
elsif (v1[:type] == 0) and (v2[:type] == 0)
if (other_polygon <=> Point[(v1[:vertex] + v2[:vertex])/2]) <= 0
edgeFragments.push :first => v1[:vertex], :last => v2[:vertex]
end
end
end
end
# Delete any duplicated edges. Array#uniq doesn't do the right thing, so using inject instead.
edgeFragments = edgeFragments.inject([]) {|result,h| result << h unless result.include?(h); result}
# Delete any equal-and-opposite edges
edgeFragments = edgeFragments.reject {|f| edgeFragments.find {|f2| (f[:first] == f2[:last]) and (f[:last] == f2[:first])} }
# Construct the output polygons
output = edgeFragments.reduce([Array.new]) do |output, fragment|
next output if fragment.empty?
polygon = output.last
polygon.push fragment[:first], fragment[:last] if polygon.empty?
while 1 do
adjacent_fragment = edgeFragments.find {|f| fragment[:last] == f[:first]}
break unless adjacent_fragment
polygon.push adjacent_fragment[:first], adjacent_fragment[:last]
fragment = adjacent_fragment.dup
adjacent_fragment.clear
break if polygon.first == polygon.last # closed?
end
output << Array.new
end
# If everything worked properly there should be only one output Polygon
output.reject! {|a| a.empty?}
output = Polygon.new *(output[0])
# Table 4: Both input polygons are "island" type and the operation
# is union, so the output polygon's orientation should be the same
# as the input polygon's orientation
(self.clockwise? != output.clockwise?) ? output.reverse : output
end
alias :+ :union
# @endgroup
# @group Convex Hull
# Returns the convex hull of the {Polygon}
# @return [Polygon] A convex {Polygon}, or the original {Polygon} if it's already convex
def convex
wrap
end
# Returns the convex hull using the {http://en.wikipedia.org/wiki/Gift_wrapping_algorithm Gift Wrapping algorithm}
# This implementation was cobbled together from many sources, but mostly from this implementation of the {http://butunclebob.com/ArticleS.UncleBob.ConvexHullTiming Jarvis March}
# @return [Polygon]
def wrap
# Start with a Point that's guaranteed to be on the hull
leftmost_point = vertices.min_by {|v| v.x}
current_point = vertices.select {|v| v.x == leftmost_point.x}.min_by {|v| v.y}
current_angle = 0.0
hull_points = [current_point]
while true
min_angle = 4.0
min_point = nil
vertices.each do |v1|
next if current_point.equal? v1
angle = pseudo_angle_for_edge(current_point, v1)
min_point, min_angle = v1, angle if (angle >= current_angle) && (angle <= min_angle)
end
current_angle = min_angle
current_point = min_point
break if current_point == hull_points.first
hull_points << min_point
end
Polygon.new *hull_points
end
# @endgroup
# Outset the receiver by the specified distance
# @param [Number] distance The distance to offset by
# @return [Polygon] A new {Polygon} outset by the given distance
def outset(distance)
bisector_edges = outset_bisectors(distance)
bisector_pairs = bisector_edges.push(bisector_edges.first).each_cons(2)
# Create the offset edges and then wrap them in Hashes so the edges
# can be altered while walking the array
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_edge.first == offset_edge.last) ? nil : offset_edge}
end
# Walk the array and handle any intersections
active_edges.each_with_index do |e, i|
e1 = e[:edge]
next unless e1 # Ignore deleted edges
intersection, j = find_last_intersection(active_edges, i, e1)
if intersection
e2 = active_edges[j][:edge]
wrap_around_is_shortest = ((i + active_edges.count - j) < (j-i))
if intersection.is_a? Point
if wrap_around_is_shortest
active_edges[i][:edge] = Edge.new(intersection, e1.last)
active_edges[j][:edge] = Edge.new(e2.first, intersection)
else
active_edges[i][:edge] = Edge.new(e1.first, intersection)
active_edges[j][:edge] = Edge.new(intersection, e2.last)
end
else
# Handle the collinear case
active_edges[i][:edge] = Edge.new(e1.first, e2.last)
active_edges[j].delete(:edge)
wrap_around_is_shortest = false
end
# Delete everything between e1 and e2
if wrap_around_is_shortest # Choose the shortest path
for k in 0...i do
active_edges[k].delete(:edge)
end
for k in j...active_edges.count do
next if k==j # Exclude e2
active_edges[k].delete(:edge)
end
else
for k in i...j do
next if k==i # Exclude e1 and e2
active_edges[k].delete(:edge)
end
end
redo # Recheck the modified edges
end
end
Polygon.new *(active_edges.map {|e| e[:edge]}.compact.map {|e| [e.first, e.last]}.flatten)
end
# Vertex bisectors suitable for outsetting
# @param [Number] length The distance to offset by
# @return [Array<Edge>] {Edge}s representing the bisectors
def outset_bisectors(length)
vertices.zip(spokes).map {|v,b| b ? Edge.new(v, v+(b * length)) : nil}
end
# Generate the unit-length spokes for each vertex
# @return [Array<Vector>] the unit {Vector}s representing the spoke of each vertex
def spokes
clockwise? ? left_bisectors : right_bisectors
end
private
# Return a number that increases with the slope of the {Edge}
# @return [Number] A number in the range [0,4)
def pseudo_angle_for_edge(point0, point1)
delta = Point[point1.x.to_f, point1.y.to_f] - Point[point0.x.to_f, point0.y.to_f]
if delta.x >= 0
if delta.y >= 0
quadrant_one_psuedo_angle(delta.x, delta.y)
else
1 + quadrant_one_psuedo_angle(delta.y.abs, delta.x)
end
else
if delta.y >= 0
3 + quadrant_one_psuedo_angle(delta.y, delta.x.abs)
else
2 + quadrant_one_psuedo_angle(delta.x.abs, delta.y.abs)
end
end
end
def quadrant_one_psuedo_angle(dx, dy)
dx / (dx + dy)
end
end
private
class VertexRing
attr_reader :vertices
def initialize
@vertices = []
end
# @param [Integer] index The index to insert the new {Point} before
# @param [Point] point The {Point} to insert
# @param [Integer] type The vertex type: 1 is inside, 0 is boundary, -1 is outside
def insert(index, point, type)
if v = @vertices.find {|v| v[:vertex] == point }
v[:type] = type
false
else
@vertices.insert(index, {:vertex => point, :type => type})
true
end
end
# Insert a boundary vertex
# @param [Integer] index The index to insert the new {Point} before
# @param [Point] point The {Point} to insert
def insert_boundary(index, point)
self.insert(index, point, 0)
end
# @param [Point] point The {Point} to push
# @param [Integer] type The vertex type: 1 is inside, 0 is boundary, -1 is outside
def push(point, type)
@vertices << {:vertex => point, :type => type}
end
# Enumerate the pairs of vertices corresponding to each edge
def edges
(@vertices + [@vertices.first]).each_cons(2) {|v1,v2| yield v1, v2}
end
def edges_with_index
index = 0
(@vertices + [@vertices.first]).each_cons(2) {|v1,v2| yield(Edge.new(v1[:vertex], v2[:vertex]), index); index += 1}
end
end
end