Class: RGeo::Cartesian::PlanarGraph::HalfEdge

Inherits:
Object
  • Object
show all
Includes:
Comparable
Defined in:
lib/rgeo/cartesian/planar_graph.rb

Overview

HalfEdge represents an edge as 2 directed edges. One half-edge will have it’s origin at edge.s, the other at edge.e. Both half-edges will be linked as each other’s twins.

HalfEdges also contain references to the next and prev half-edges, where next’s origin is this half-edges destination. Prev’s destination is this half-edge’s origin.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(origin) ⇒ HalfEdge 



42
43
44
45
46
47
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 42

def initialize(origin)
  @origin = origin
  @twin = nil
  @next = nil
  @prev = nil
end

Instance Attribute Details

#next ⇒ Object

Returns the value of attribute next.



49
50
51
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 49

def next
  @next
end

#origin ⇒ Object (readonly)

Returns the value of attribute origin.



48
49
50
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 48

def origin
  @origin
end

#prev ⇒ Object

Returns the value of attribute prev.



49
50
51
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 49

def prev
  @prev
end

#twin ⇒ Object

Returns the value of attribute twin.



49
50
51
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 49

def twin
  @twin
end

Class Method Details

.from_edge(edge) ⇒ Array

Creates 2 half edges from an edge. They will be assigned as each other’s twins. The Half Edges will be returned in the order of points of the edge (start, end).



33
34
35
36
37
38
39
40
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 33

def self.from_edge(edge)
  e1 = new(edge.s)
  e2 = new(edge.e)

  e1.twin = e2
  e2.twin = e1
  [e1, e2]
end

Instance Method Details

#<=>(other) ⇒ Object

HalfEdges will be sorted around their shared vertex in a CW fashion. This means that face interiors will be a CCW.



54
55
56
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 54

def <=>(other)
  angle <=> other.angle
end

#and_connected {|_self| ... } ⇒ Enumerator

Will find attempt to find a cycle starting at this HalfEdge. Will end upon finding the first repeated HalfEdge or a HalfEdge where next is nil.

If a block is given, each HalfEdge seen will be yielded to the block.

Yields:

  • (_self)

Yield Parameters:



65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 65

def and_connected
  return to_enum(__method__) unless block_given?

  hedges = Set.new
  yield(self)
  hedges << self

  n = self.next
  until hedges.include?(n) || n.nil?
    yield(n)
    hedges << n
    n = n.next
  end
end

#angle ⇒ Float

Compute the angle from the positive x-axis. Used for sorting at each node.



91
92
93
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 91

def angle
  @angle ||= Math.atan2(destination.y - origin.y, destination.x - origin.x)
end

#destination ⇒ RGeo::Feature::Point

Return the destination of the half edge



83
84
85
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 83

def destination
  twin&.origin
end

#inspect ⇒ Object 



95
96
97
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 95

def inspect
  "#<#{self.class}:0x#{object_id.to_s(16)} #{self}>"
end

#to_s ⇒ Object 



99
100
101
102
103
104
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 99

def to_s
  dst = destination
  pr = prev&.origin
  n = @next&.origin
  "HalfEdge(#{origin}, #{dst}), Prev: #{pr},  Next: #{n}"
end