class Geom2D::Algorithms::PolygonOperation
Performs intersection, union, difference and xor operations on Geom2D::PolygonSet
objects.
The entry method is PolygonOperation.run
.
The algorithm is described in the paper “A simple algorithm for Boolean operations on polygons” by Martinez et al (see dl.acm.org/citation.cfm?id=2494701). This implementation is based on the public domain code from www4.ujaen.es/~fmartin/bool_op.html, which is the original implementation from the authors of the paper.
Attributes
The result of the operation, a Geom2D::PolygonSet
.
Public Class Methods
Creates a new boolean operation object, performing the operation
(either :intersection, :union, :difference or :xor) on the subject and clipping Geom2D::PolygonSet
objects.
# File lib/geom2d/algorithms/polygon_operation.rb, line 180 def initialize(subject, clipping, operation) @subject = subject @clipping = clipping @operation = operation @result = PolygonSet.new @event_queue = Utils::SortedLinkedList.new {|a, b| a.process_after?(b) } # @sweep_line should really be a sorted data structure with O(log(n)) for insert/search! @sweep_line = Utils::SortedLinkedList.new {|a, b| a.segment_below?(b) } @sorted_events = [] end
Performs the given operation (:union, :intersection, :difference, :xor) on the subject and clipping polygon sets.
# File lib/geom2d/algorithms/polygon_operation.rb, line 171 def self.run(subject, clipping, operation) new(subject, clipping, operation).run.result end
Public Instance Methods
Performs the boolean polygon operation.
# File lib/geom2d/algorithms/polygon_operation.rb, line 193 def run subject_bb = @subject.bbox clipping_bb = @clipping.bbox min_of_max_x = [subject_bb.max_x, clipping_bb.max_x].min return self if trivial_operation(subject_bb, clipping_bb) @subject.each_segment {|segment| process_segment(segment, :subject) } @clipping.each_segment {|segment| process_segment(segment, :clipping) } until @event_queue.empty? event = @event_queue.last if (@operation == :intersection && event.point.x > min_of_max_x) || (@operation == :difference && event.point.x > subject_bb.max_x) connect_edges return self end @sorted_events.push(event) @event_queue.pop if event.left # the segment hast to be inserted into status line node = @sweep_line.insert(event) prev_event = (node.prev_node.anchor? ? nil : node.prev_node.value) next_event = (node.next_node.anchor? ? nil : node.next_node.value) compute_event_fields(event, prev_event) if next_event && possible_intersection(event, next_event) == 2 compute_event_fields(event, prev_event) compute_event_fields(next_event, event) end if prev_event && possible_intersection(prev_event, event) == 2 prevprev_ev = (node.prev_node.prev_node.anchor? ? nil : node.prev_node.prev_node.value) compute_event_fields(prev_event, prevprev_ev) compute_event_fields(event, prev_event) end else # the segment has to be removed from the status line event = event.other_event # use left event node = @sweep_line.find_node(event) next_node = node.next_node prev_node = node.prev_node node.delete unless prev_node.anchor? || next_node.anchor? possible_intersection(prev_node.value, next_node.value) end end end connect_edges self end
Private Instance Methods
Computes the fields of the sweep event, using information from the previous event.
The argument prev
is either the previous event or nil
if there is no previous event.
# File lib/geom2d/algorithms/polygon_operation.rb, line 281 def compute_event_fields(event, prev) if prev.nil? event.in_out = false event.other_in_out = true elsif event.polygon_type == prev.polygon_type event.in_out = !prev.in_out event.other_in_out = prev.other_in_out else event.in_out = !prev.other_in_out event.other_in_out = (prev.vertical? ? !prev.in_out : prev.in_out) end if prev event.prev_in_result = if !prev.in_result?(@operation) || prev.vertical? prev.prev_in_result else prev end end event.in_result = event.in_result?(@operation) end
Connects the edges of the segments that are in the result.
# File lib/geom2d/algorithms/polygon_operation.rb, line 373 def connect_edges events = @sorted_events.select do |ev| (ev.left && ev.in_result) || (!ev.left && ev.other_event.in_result) end # events may not be fully sorted due to overlapping edges events.sort! {|a, b| a.process_after?(b) ? 1 : -1 } event_pos = {} events.each_with_index do |event, index| event_pos[event] = index unless event.left event_pos[event], event_pos[event.other_event] = event_pos[event.other_event], event_pos[event] end end processed = {} events.each do |event| next if processed[event] initial_point = event.point polygon = Geom2D::Polygon.new @result << polygon polygon << initial_point while event.other_event.point != initial_point processed[event] = true processed[event.other_event] = true if polygon.nr_of_vertices > 1 && Algorithms.ccw(polygon[-2], polygon[-1], event.other_event.point) == 0 polygon.pop end polygon << event.other_event.point event = next_event(events, event_pos, processed, event) end if Algorithms.ccw(polygon[-2], polygon[-1], polygon[0]) == 0 polygon.pop end processed[event] = processed[event.other_event] = true end end
Divides the event's segment at the given point (which has to be inside the segment) and adds the resulting events to the event queue.
# File lib/geom2d/algorithms/polygon_operation.rb, line 364 def divide_segment(event, point) right = SweepEvent.new(false, point, event.polygon_type, other_event: event) left = SweepEvent.new(true, point, event.polygon_type, other_event: event.other_event) event.other_event.other_event = left event.other_event = right @event_queue.push(left).push(right) end
Chooses the next event based on the argument.
# File lib/geom2d/algorithms/polygon_operation.rb, line 416 def next_event(events, event_pos, processed, event) pos = event_pos[event] + 1 while pos < events.size && events[pos].point == event.other_event.point if processed[events[pos]] pos += 1 else return events[pos] end end pos = event_pos[event] - 1 pos -= 1 while processed[events[pos]] events[pos] end
Checks for possible intersections of the segments of the two events and returns 0 for no intersections, 1 for intersection in one point, 2 if the segments are equal or have the same left endpoint, and 3 for all other cases.
# File lib/geom2d/algorithms/polygon_operation.rb, line 306 def possible_intersection(ev1, ev2) result = ev1.segment.intersect(ev2.segment) result_is_point = result.kind_of?(Geom2D::Point) if result.nil? || (result_is_point && (ev1.point == ev2.point || ev1.other_event.point == ev2.other_event.point)) return 0 elsif !result_is_point && ev1.polygon_type == ev2.polygon_type raise "Edges of the same polygon overlap - not supported" end if result_is_point divide_segment(ev1, result) if ev1.point != result && ev1.other_event.point != result divide_segment(ev2, result) if ev2.point != result && ev2.other_event.point != result return 1 end events = [] if ev1.point == ev2.point events.push(nil) elsif ev1.process_after?(ev2) events.push(ev2, ev1) else events.push(ev1, ev2) end if ev1.other_event.point == ev2.other_event.point events.push(nil) elsif ev1.other_event.process_after?(ev2.other_event) events.push(ev2.other_event, ev1.other_event) else events.push(ev1.other_event, ev2.other_event) end if events.size == 2 || (events.size == 3 && events[2]) # segments are equal or have the same left endpoint ev1.edge_type = :non_contributing ev2.edge_type = (ev1.in_out == ev2.in_out ? :same_transition : :different_transition) if events.size == 3 divide_segment(events[2].other_event, events[1].point) end 2 elsif events.size == 3 # segments have the same right endpoint divide_segment(events[0], events[1].point) 3 elsif events[0] != events[3].other_event # partial segment overlap divide_segment(events[0], events[1].point) divide_segment(events[1], events[2].point) 3 else # one segments includes the other divide_segment(events[0], events[1].point) divide_segment(events[3].other_event, events[2].point) 3 end end
Processes the segment by adding the needed SweepEvent
objects into the event queue.
# File lib/geom2d/algorithms/polygon_operation.rb, line 269 def process_segment(segment, polygon_type) return if segment.degenerate? start_point_is_left = (segment.start_point == segment.min) e1 = SweepEvent.new(start_point_is_left, segment.start_point, polygon_type) e2 = SweepEvent.new(!start_point_is_left, segment.end_point, polygon_type, other_event: e1) e1.other_event = e2 @event_queue.push(e1).push(e2) end
Returns true
if the operation is a trivial one, e.g. if one polygon set is empty.
# File lib/geom2d/algorithms/polygon_operation.rb, line 247 def trivial_operation(subject_bb, clipping_bb) if @subject.nr_of_contours * @clipping.nr_of_contours == 0 if @operation == :difference @result = @subject elsif @operation == :union || @operation == :xor @result = (@subject.nr_of_contours == 0 ? @clipping : @subject) end true elsif subject_bb.min_x > clipping_bb.max_x || clipping_bb.min_x > subject_bb.max_x || subject_bb.min_y > clipping_bb.max_y || clipping_bb.min_y > subject_bb.max_y if @operation == :difference @result = @subject elsif @operation == :union || @operation == :xor @result = @subject + @clipping end true else false end end