Class: Geom2D::Algorithms::PolygonOperation

Inherits:
Object
  • Object
show all
Includes:
Utils
Defined in:
lib/geom2d/algorithms/polygon_operation.rb

Overview

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.

Defined Under Namespace

Classes: SweepEvent

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(subject, clipping, operation) ⇒ PolygonOperation

Creates a new boolean operation object, performing the operation (either :intersection, :union, :difference or :xor) on the subject and clipping Geom2D::PolygonSet objects.



181
182
183
184
185
186
187
188
189
190
191
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 181

def initialize(subject, clipping, operation)
  @subject = subject
  @clipping = clipping
  @operation = operation

  @result = PolygonSet.new
  @event_queue = Utils::SortedList.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::SortedList.new {|a, b| a.segment_below?(b) }
  @sorted_events = []
end

Instance Attribute Details

#result ⇒ Object (readonly)

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



177
178
179
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 177

def result
  @result
end

Class Method Details

.run(subject, clipping, operation) ⇒ Object

Performs the given operation (:union, :intersection, :difference, :xor) on the subject and clipping polygon sets.



172
173
174
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 172

def self.run(subject, clipping, operation)
  new(subject, clipping, operation).run.result
end

Instance Method Details

#run ⇒ Object

Performs the boolean polygon operation.



194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 194

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
      prevprev_event, prev_event, next_event = @sweep_line.insert(event)

      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
        compute_event_fields(prev_event, prevprev_event)
        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
      prev_ev, next_ev = @sweep_line.delete(event)
      if prev_ev && next_ev
        possible_intersection(prev_ev, next_ev)
      end
    end
  end
  connect_edges
  self
end