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

result[R]

The result of the operation, a Geom2D::PolygonSet.

Public Class Methods

new(subject, clipping, operation) click to toggle source

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
run(subject, clipping, operation) click to toggle source

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

run() click to toggle source

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

compute_event_fields(event, prev) click to toggle source

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
connect_edges() click to toggle source

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
divide_segment(event, point) click to toggle source

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
next_event(events, event_pos, processed, event) click to toggle source

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
possible_intersection(ev1, ev2) click to toggle source

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
process_segment(segment, polygon_type) click to toggle source

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
trivial_operation(subject_bb, clipping_bb) click to toggle source

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