KJB
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
dcel.h
Go to the documentation of this file.
1 
6 /*
7  * $Id: dcel.h 18278 2014-11-25 01:42:10Z ksimek $
8  */
9 
10 #ifndef QD_CPP_DCEL_H_INCLUDED_IVILAB
11 #define QD_CPP_DCEL_H_INCLUDED_IVILAB 1
12 
13 #include <qd_cpp/intersection.h>
14 #include <l/l_sys_lib.h>
15 #include <l/l_sys_io.h>
16 #include <l_cpp/l_util.h>
17 
18 #include <vector>
19 #include <set>
20 #include <iosfwd>
21 
22 
23 namespace kjb
24 {
25 namespace qd
26 {
27 
28 
204 {
205 public:
207  {
209  size_t outedge;
210  Vertex_record(const RatPoint& l, size_t oe): location(l),outedge(oe) {}
211  };
212 
213  struct Edge_record // commonly known as a "half-edge" since it is directed.
214  {
215  size_t origin, twin; // these must always be correct
216  size_t face, next, prev; // sometimes these are temporarily incorrect
217  Edge_record(size_t o, size_t t, size_t f, size_t n, size_t p)
218  : origin(o), twin(t), face(f), next(n), prev(p)
219  {}
220  };
221 
222  struct Face_record
223  {
224  // The following field is not used in the index-0 face table entry.
225  // In all other records, it contains the index of a representative edge
226  // of the CCW edge cycle that forms the outer fence around the face.
228 
229  // Each entry (if any) points to a representative edge of a CW edge
230  // cycle of the outer boundary of a hole in the face.
231  // Distinct entries point to distinct cycles.
232  std::vector< size_t > inner_components;
233 
234  Face_record(size_t o,const std::vector<size_t>&i=std::vector<size_t>())
236  {}
237  };
238 
239  const std::vector< Vertex_record >& get_vertex_table()const{return m_vtab;}
240 
241  const std::vector< Edge_record >& get_edge_table() const { return m_etab; }
242 
243  const std::vector< Face_record >& get_face_table() const { return m_ftab; }
244 
245  // blank DCEL
247  : m_ftab(1, Face_record(0)),
248  m_lookup_valid(1), // actually it is valid, in a vacuous way
249  m_cycle_table_valid(1) // ditto
250  {}
251 
252  // single-segment DCEL
254 
255  // swap the state of two DCELs
257  {
258  m_vtab.swap(dcel.m_vtab);
259  m_etab.swap(dcel.m_etab);
260  m_ftab.swap(dcel.m_ftab);
261 
262  // swap caches
263  m_vertex_lookup.swap(dcel.m_vertex_lookup);
264  std::swap(m_lookup_valid, dcel.m_lookup_valid);
265  m_cycles.swap(dcel.m_cycles);
266  m_edge_of_cyc.swap(dcel.m_edge_of_cyc);
267  std::swap(m_cycle_table_valid, dcel.m_cycle_table_valid);
268  }
269 
270  // look up a vertex index number by its location,
271  // linear time for the first time, log time for second and later lookups
272  size_t lookup_vertex(const RatPoint&, bool* = 00) const;
273 
274  // create a new DCEL by merging this one with another (a big deal)
276  {
277  return brute_force_merge(d);
278  }
279 
282 
296 
298  Doubly_connected_edge_list& transform(const std::vector<RatPoint::Rat>& x)
299  {
300  if (x.size() != 9) KJB_THROW_2(Illegal_argument, "Need 3x3 RM matrix");
301  return transform(& x.front());
302  }
303 
304 
305  void build_cycle_table() const; // "const" since it just touches mutables.
306 
307 
309  int get_cycle(size_t ei) const
310  {
311  if (!m_cycle_table_valid) build_cycle_table();
312  KJB(ASSERT(ei < m_cycles.size()));
313  return m_cycles.at(ei);
314  }
315 
316 
318  size_t get_edge_of_cycle(int cn) const
319  {
320  if (!m_cycle_table_valid) build_cycle_table();
321  KJB(ASSERT(0 <= cn && cn < (int)m_edge_of_cyc.size()));
322  return m_edge_of_cyc.at(cn);
323  }
324 
325 
327  size_t get_number_of_cycles() const
328  {
329  if (!m_cycle_table_valid) build_cycle_table();
330  return m_edge_of_cyc.size();
331  }
332 
333 private:
334  std::vector< Vertex_record > m_vtab;
335 
336  std::vector< Edge_record > m_etab;
337 
338  // face zero is always the unbounded outermost face, outer_component is 0.
339  std::vector< Face_record > m_ftab;
340 
341  // cached lookup table
342  typedef std::map< RatPoint, size_t > VtxLookup;
343  mutable VtxLookup m_vertex_lookup;
344  mutable bool m_lookup_valid;
345 
346  // cached cycle table
347  mutable bool m_cycle_table_valid;
348  mutable std::vector< int > m_cycles, m_edge_of_cyc;
349 
350  Doubly_connected_edge_list brute_force_merge(
352  ) const;
353 
354  void previous_next_link(size_t e_engine, size_t e_caboose)
355  {
356  m_etab.at(e_engine).prev = e_caboose;
357  m_etab.at(e_caboose).next = e_engine;
358  }
359 
360  void walk_cycle_and_set_its_face(size_t, size_t);
361 };
362 
363 
365 int is_valid(const Doubly_connected_edge_list&);
366 
367 
369 std::vector< size_t > out_edges(const Doubly_connected_edge_list&, size_t);
370 
371 
373 std::vector< size_t > twin_edges(
374  const Doubly_connected_edge_list&,
375  const std::vector< size_t >&
376 );
377 
378 
380 inline std::vector< size_t > in_edges(
381  const Doubly_connected_edge_list& dcel,
382  size_t vertex_index
383 )
384 {
385  return twin_edges(dcel, out_edges(dcel, vertex_index));
386 }
387 
388 
390 inline size_t vertex_degree(const Doubly_connected_edge_list& d, size_t v)
391 {
392  return out_edges(d, v).size();
393 }
394 
395 
403 inline
405 {
407  &e = d.get_edge_table().at(ei), &f = d.get_edge_table().at(e.twin);
408  return RatPoint_line_segment( d.get_vertex_table().at(e.origin).location,
409  d.get_vertex_table().at(f.origin).location );
410 }
411 
412 
414 std::ostream& operator<<(
415  std::ostream&,
417 );
418 
419 
420 
421 
422 
423 }
424 }
425 
426 #endif /* QD_CPP_DCEL_H_INCLUDED_IVILAB */
size_t outer_component
Definition: dcel.h:227
const std::vector< Vertex_record > & get_vertex_table() const
Definition: dcel.h:239
Declaration for Bentley-Ottmann line intersection algorithm.
int get_cycle(size_t ei) const
Query with an edge index, return value is a cycle number.
Definition: dcel.h:309
void build_cycle_table() const
Definition: dcel.cpp:1096
#define KJB(x)
Definition: l_util.h:9
Doubly_connected_edge_list()
Definition: dcel.h:246
size_t get_edge_of_cycle(int cn) const
Query with a cycle number, return the index of some edge on it.
Definition: dcel.h:318
#define ASSERT(condition, message)
Definition: Assert.h:45
std::vector< size_t > inner_components
Definition: dcel.h:232
const std::vector< Edge_record > & get_edge_table() const
Definition: dcel.h:241
int is_valid(const Doubly_connected_edge_list &dcel)
slowly test invariants on the structure, return ERROR or NO_ERROR
Definition: dcel.cpp:1530
data structure for a planar subdivision made by edges
Definition: dcel.h:203
std::vector< size_t > in_edges(const Doubly_connected_edge_list &dcel, size_t vertex_index)
inbound half-edges at a particular vertex (specified by number)
Definition: dcel.h:380
RatPoint_line_segment get_edge(const Doubly_connected_edge_list &d, size_t ei)
get line segment represented by a DCEL edge (specified by index)
Definition: dcel.h:404
Edge_record(size_t o, size_t t, size_t f, size_t n, size_t p)
Definition: dcel.h:217
std::vector< size_t > twin_edges(const Doubly_connected_edge_list &dcel, const std::vector< size_t > &edge_list)
Get the indices of twin edges of a given set of edges.
Definition: dcel.cpp:1183
Doubly_connected_edge_list merge(const Doubly_connected_edge_list &d) const
Definition: dcel.h:275
size_t vertex_degree(const Doubly_connected_edge_list &d, size_t v)
return number of segments (not edges) incident to this vertex
Definition: dcel.h:390
size_t lookup_vertex(const RatPoint &, bool *=00) const
look up a vertex index by its location
Definition: dcel.cpp:1243
x
Definition: APPgetLargeConnectedEdges.m:100
void swap(Doubly_connected_edge_list &dcel)
Definition: dcel.h:256
Doubly_connected_edge_list & transform(const std::vector< RatPoint::Rat > &x)
transform using a row-major 3x3 homogeneous matrix on each vertex
Definition: dcel.h:298
const std::vector< Face_record > & get_face_table() const
Definition: dcel.h:243
size_t get_number_of_cycles() const
Return the number of (real) edge cycles in the DCEL.
Definition: dcel.h:327
very basic structure to represent X, Y points with rational coords.
Definition: ratpoint.h:38
closed line segment with rational coords
Definition: ratpoint.h:277
std::ostream & operator<<(std::ostream &o, const Doubly_connected_edge_list &d)
Print a text representation of the DCEL tables (but not the cache)
Definition: dcel.cpp:1270
#define KJB_THROW_2(ex, msg)
Definition: l_exception.h:48
boost::rational< long long > Rat
Definition: ratpoint.h:48
void swap(kjb::Gsl_Multimin_fdf &m1, kjb::Gsl_Multimin_fdf &m2)
Swap two wrapped multimin objects.
Definition: gsl_multimin.h:693
Doubly_connected_edge_list & transform(const RatPoint::Rat[])
Transform using a row-major 3x3 homogeneous matrix on each vertex.
Definition: dcel.cpp:1570
Doubly_connected_edge_list & translate(const RatPoint &)
Transform by translation (rigid motion by an x and y offset)
Definition: dcel.cpp:1554
Vertex_record(const RatPoint &l, size_t oe)
Definition: dcel.h:210
Object thrown when an argument to a function is not acceptable.
Definition: l_exception.h:377
get the indices of edges in each direction for i
Definition: APPgetLargeConnectedEdges.m:48
std::vector< size_t > out_edges(const Doubly_connected_edge_list &dcel, size_t vertex_index)
outbound half-edges at a particular vertex (specified by number)
Definition: dcel.cpp:1159
Face_record(size_t o, const std::vector< size_t > &i=std::vector< size_t >())
Definition: dcel.h:234