Class: RGeo::Cartesian::PlanarGraph

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

Overview

A Doubly Connected Edge List (DCEL) implementation of a Planar Graph. It represents geometries as vertices and half-edges.

It includes an incident_edges hash that maps vertices to an array of half-edges whose origins are that vertex.

Upon instantiation, the graph will compute the intersections using the SweeplineIntersector, populate the incident_edges map, and link all cyclic edges.

Direct Known Subclasses

GeometryGraph

Defined Under Namespace

Classes: HalfEdge

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(edges = []) ⇒ PlanarGraph

Create a new PlanarGraph

Parameters:



110
111
112
113
114
115
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 110

def initialize(edges = [])
  @edges = []
  @incident_edges = {}

  add_edges(edges)
end

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



116
117
118
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 116

def edges
  @edges
end

#incident_edges ⇒ Object (readonly)

Returns the value of attribute incident_edges.



116
117
118
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 116

def incident_edges
  @incident_edges
end

Instance Method Details

#add_edge(edge) ⇒ Object

Insert an edge into the graph. This will automatically calculate intersections and add new vertices if necessary.

Parameters:



122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 122

def add_edge(edge)
  @edges << edge
  create_half_edge(edge)

  # Check if a new intersection was made and handle it.
  intersection_map.each do |seg, ints|
    compute_split_edges(seg, ints)
  end

  link_half_edges
end

#add_edges(new_edges) ⇒ Object

Insert multiple edges into the graph. Like add_edge, this automatically calculates intersections and adds new vertices.

Parameters:



138
139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/rgeo/cartesian/planar_graph.rb', line 138

def add_edges(new_edges)
  @edges.concat(new_edges)
  new_edges.each do |edge|
    create_half_edge(edge)
  end

  intersection_map.each do |seg, ints|
    compute_split_edges(seg, ints)
  end

  link_half_edges
end