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

Returns a new instance of 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).

Parameters:

Returns:

  • (Array) 


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:

Returns:

  • (Enumerator) 


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.

Returns:

  • (Float) 


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

Returns:



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