10 #ifndef QD_CPP_DCEL_H_INCLUDED_IVILAB
11 #define QD_CPP_DCEL_H_INCLUDED_IVILAB 1
14 #include <l/l_sys_lib.h>
15 #include <l/l_sys_io.h>
234 Face_record(
size_t o,
const std::vector<size_t>&
i=std::vector<size_t>())
249 m_cycle_table_valid(1)
258 m_vtab.swap(dcel.m_vtab);
259 m_etab.swap(dcel.m_etab);
260 m_ftab.swap(dcel.m_ftab);
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);
277 return brute_force_merge(d);
313 return m_cycles.at(ei);
321 KJB(
ASSERT(0 <= cn && cn < (
int)m_edge_of_cyc.size()));
322 return m_edge_of_cyc.at(cn);
330 return m_edge_of_cyc.size();
334 std::vector< Vertex_record > m_vtab;
336 std::vector< Edge_record > m_etab;
339 std::vector< Face_record > m_ftab;
342 typedef std::map< RatPoint, size_t > VtxLookup;
343 mutable VtxLookup m_vertex_lookup;
344 mutable bool m_lookup_valid;
347 mutable bool m_cycle_table_valid;
348 mutable std::vector< int > m_cycles, m_edge_of_cyc;
354 void previous_next_link(
size_t e_engine,
size_t e_caboose)
356 m_etab.at(e_engine).prev = e_caboose;
357 m_etab.at(e_caboose).next = e_engine;
360 void walk_cycle_and_set_its_face(
size_t,
size_t);
365 int is_valid(
const Doubly_connected_edge_list&);
369 std::vector< size_t >
out_edges(
const Doubly_connected_edge_list&,
size_t);
374 const Doubly_connected_edge_list&,
375 const std::vector< size_t >&
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
size_t face
Definition: dcel.h:216
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
size_t twin
Definition: dcel.h:215
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
size_t origin
Definition: dcel.h:215
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
size_t prev
Definition: dcel.h:216
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
size_t next
Definition: dcel.h:216
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
size_t outedge
Definition: dcel.h:209
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
RatPoint location
Definition: dcel.h:208
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