Class: Geom2D::Algorithms::PolygonOperation::SweepEvent

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

Overview

Represents one event of the sweep line phase, i.e. a (left or right) endpoint of a segment together with processing information.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(left, point, polygon_type, other_event = nil) ⇒ SweepEvent

Creates a new SweepEvent.



69
70
71
72
73
74
75
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 69

def initialize(left, point, polygon_type, other_event = nil)
  @left = left
  @point = point
  @other_event = other_event
  @polygon_type = polygon_type
  @edge_type = :normal
end

Instance Attribute Details

#edge_type ⇒ Object

The edge type of the event’s segment, either :normal, :non_contributing, :same_transition or :different_transition.



51
52
53
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 51

def edge_type
  @edge_type
end

#in_out ⇒ Object

True if the segment represents an inside-outside transition from (point.x, -infinity) into the polygon set to which the segment belongs.



55
56
57
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 55

def in_out
  @in_out
end

#in_result ⇒ Object

True if this event’s segment is part of the result polygon set.



62
63
64
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 62

def in_result
  @in_result
end

#left ⇒ Object

True if the #point is the left endpoint of the segment.



38
39
40
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 38

def left
  @left
end

#other_event ⇒ Object

The other event. This event together with the other event represents a segment.



47
48
49
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 47

def other_event
  @other_event
end

#other_in_out ⇒ Object

True if the closest segment downwards from this segment that belongs to the other polygon set represents an inside-outside transition from (point.x, -infinity).



59
60
61
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 59

def other_in_out
  @other_in_out
end

#point ⇒ Object (readonly)

The point of this event, a Geom2D::Point instance.



41
42
43
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 41

def point
  @point
end

#polygon_type ⇒ Object (readonly)

The type of polygon, either :clipping or :subject.



44
45
46
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 44

def polygon_type
  @polygon_type
end

#prev_in_result ⇒ Object

The previous event/segment downwards from this segment that is part of the result polygon set.



66
67
68
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 66

def prev_in_result
  @prev_in_result
end

Instance Method Details

#above?(point) ⇒ Boolean

Returns true if this event’s line #segment is above the point p.

Returns:

  • (Boolean) 


87
88
89
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 87

def above?(point)
  !below?(point)
end

#below?(p) ⇒ Boolean

Returns true if this event’s line #segment is below the point p.

Returns:

  • (Boolean) 


78
79
80
81
82
83
84
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 78

def below?(p)
  if left
    Algorithms.ccw(@point, @other_event.point, p) > 0
  else
    Algorithms.ccw(@other_event.point, @point, p) > 0
  end
end

#in_result?(operation) ⇒ Boolean

Returns true if this event’s segment should be in the result based on the boolean operation.

Returns:

  • (Boolean) 


145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 145

def in_result?(operation)
  case edge_type
  when :normal
    case operation
    when :intersection then !other_in_out
    when :union then other_in_out
    when :difference then polygon_type == :subject ? other_in_out : !other_in_out
    when :xor then true
    end
  when :same_transition
    operation == :intersection || operation == :union
  when :different_transition
    operation == :difference
  when :non_contributing
    false
  end
end

#process_after?(event) ⇒ Boolean

Returns true if this event should be *processed after the given event*.

This method is used for sorting events in the event queue of the main algorithm.

Returns:

  • (Boolean) 


99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 99

def process_after?(event)
  if (cmp = float_compare(point.x, event.point.x)) != 0
    cmp > 0 # different x-coordinates, true if point.x is greater
  elsif (cmp = float_compare(point.y, event.point.y)) != 0
    cmp > 0 # same x-, different y-coordinates, true if point.y is greater
  elsif left != event.left
    left # same point; one is left, one is right endpoint; true if left endpoint
  elsif Algorithms.ccw(point, other_event.point, event.other_event.point) != 0
    above?(event.other_event.point) # both left or right; not collinear; true if top segment
  else
    polygon_type < event.polygon_type # true if clipping polygon
  end
end

#segment ⇒ Object

Returns this event’s line segment (point, other_event.point).



164
165
166
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 164

def segment
  Geom2D::Segment(point, other_event.point)
end

#segment_below?(event) ⇒ Boolean

Returns true it this event’s segment is below the segment of the other event.

This method is used for sorting events in the sweep line status data structure of the main algorithm.

This method is intended to be used only on left events!

Returns:

  • (Boolean) 


119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 119

def segment_below?(event)
  if self == event
    false
  elsif Algorithms.ccw(point, other_event.point, event.point) != 0 ||
      Algorithms.ccw(point, other_event.point, event.other_event.point) != 0
    # segments are not collinear
    if point == event.point
      below?(event.other_event.point)
    elsif float_compare(point.x, event.point.x) == 0
      float_compare(point.y, event.point.y) < 0
    elsif process_after?(event)
      event.above?(point)
    else
      below?(event.point)
    end
  elsif polygon_type != event.polygon_type
    polygon_type > event.polygon_type
  elsif point == event.point
    object_id < event.object_id # just need any consistency criterion
  else
    process_after?(event)
  end
end

#vertical? ⇒ Boolean

Returns true if this event’s line segment is vertical.

Returns:

  • (Boolean) 


92
93
94
 
# File 'lib/geom2d/algorithms/polygon_operation.rb', line 92

def vertical?
  float_equal(@point.x, other_event.point.x)
end