1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003 |
- <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
- <html>
- <head>
- <meta http-equiv="Content-Language" content="en-us">
- <meta http-equiv="Content-Type"
- content="text/html; charset=windows-1252">
- <title>Voronoi Diagram</title>
- <meta http-equiv="content-type" content="text/html; charset=utf-8">
- <meta http-equiv="content-type" content="text/html; charset=utf-8">
- </head>
- <body>
- <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
- cellpadding="0" cellspacing="0">
- <tbody>
- <tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1"
- valign="top">
- <div style="padding: 5px;" align="center"> <img
- src="images/boost.png" border="0" height="86" width="277"><a
- title="www.boost.org home page" tabindex="2"
- style="border: medium none ;" href="http://www.boost.org/"> </a></div>
- <div style="margin: 5px;">
- <h3 class="navbar">Contents</h3>
- <ul>
- <li><a href="index.htm">Boost.Polygon Main Page</a></li>
- <li><a href="gtl_design_overview.htm">Design Overview</a></li>
- <li><a href="gtl_isotropy.htm">Isotropy</a></li>
- <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
- <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
- <li><a href="gtl_point_concept.htm">Point Concept</a></li>
- <li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
- <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
- <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
- <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
- With Holes Concept</a></li>
- <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
- <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
- With Holes Concept</a></li>
- <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
- <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
- Holes Concept</a></li>
- <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
- Concept</a></li>
- <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
- Concept</a></li>
- <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
- <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
- Extraction 90</a></li>
- <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
- Extraction 45</a></li>
- <li><a href="gtl_connectivity_extraction.htm">Connectivity
- Extraction</a></li>
- <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
- <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
- <li><a href="gtl_property_merge.htm">Property Merge</a></li>
- <li><a href="voronoi_main.htm">Voronoi Main Page </a></li>
- <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a></li>
- <li><a href="voronoi_builder.htm">Voronoi Builder</a> </li>
- <li>Voronoi Diagram</li>
- </ul>
- <h3 class="navbar">Other Resources</h3>
- <ul>
- <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
- <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
- Presentation</a></li>
- <li><a href="analysis.htm">Performance Analysis</a></li>
- <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
- <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
- <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
- <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
- Tutorial</a></li>
- </ul>
- </div>
- <h3 class="navbar">Polygon Sponsor</h3>
- <div style="padding: 5px;" align="center"> <img
- src="images/intlogo.gif" border="0" height="51" width="127"><a
- title="www.adobe.com home page" tabindex="2"
- style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
- </td>
- <td
- style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
- valign="top" width="100%"><!-- End Header --> <br>
- <h1>Voronoi Diagram</h1>
- A Voronoi
- diagram is the computational geometry concept that represents partition
- of the given space onto regions, with bounds determined by distances to
- a
- specified family of objects. The application area of this concept
- varies <a
- href="http://www.ics.uci.edu/%7Eeppstein/gina/scot.drysdale.html">from
- Archaeology to Zoology</a>. The Boost.Polygon Voronoi extension
- provides
- implementation of
- the Voronoi diagram data structure in the 2D space. The internal
- representation
- consists of the three arrays, that respectively contain: Voronoi cells
- (represent the area around the input sites bounded by the Voronoi
- edges), Voronoi vertices
- (points where three or more Voronoi edges intersect), Voronoi edges
- (one dimensional curves containing points equidistant from the two
- closest input sites). Each of the primitives (cell, vertex, edge)
- contains pointers to the other linked primitives, so that it's always
- possible to efficiently traverse the Voronoi graph. The picture below
- shows
- the Voronoi vertices in red, Voronoi edges in black, input sites that
- correspond to the Voronoi cells in blue. It is considered, that each
- input segment consists of the three sites: segment itself and its
- endpoints. As the result, two additional Voronoi edges are constructed
- per each input segment. This is made to
- simplify the representation of the Voronoi diagram and Voronoi edges in
- particular.<br>
- <br>
- <img src="images/voronoi2.png" alt=""
- style="width: 600px; height: 600px;"><br>
- <h2>Important</h2>
- All
- the Voronoi primitive data structures (edge, vertex, cell) contain
- mutable color member. Color type is equivalent to the std::size_t type,
- except that the upper five bits are reserved for the internal usage.
- That means, that the maximum supported value by the color member is 32
- times less than the one supported by std::size_t.<br>
- <h2>Declaration</h2>
- Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">template
- <typename T, typename TRAITS = voronoi_diagram_traits<T> ></span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">class
- voronoi_diagram;<br>
- </span><font face="Courier New"><span
- style="font-family: 'Courier New',Courier,monospace;"><br>
- T</span></font>
- - the coordinate type of the Voronoi vertices.<br>
- <span style="font-family: Courier New,Courier,monospace;">TRAITS</span><font
- face="Courier New"><span
- style="font-family: 'Courier New',Courier,monospace;"></span></font>
- - the Voronoi diagram traits.<br>
- <h2>Member Functions</h2>
- <span style="font-family: Courier New,Courier,monospace;"> </span>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
- <tbody>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;"><span
- style="font-weight: bold;">voronoi_diagram</span>() </td>
- <td>Default constructor. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">clear</span>() </td>
- <td>Removes all primitives from the Voronoi diagram. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- cell_container_type& <span style="font-weight: bold;">cells</span>()
- const </td>
- <td>Returns the const
- reference to the cell container. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- vertex_container_type& <span style="font-weight: bold;">vertices</span>()
- const </td>
- <td>Returns the const
- reference to the vertex container. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- edge_container_type& <span style="font-weight: bold;">edges</span>()
- const </td>
- <td>Returns the const
- reference to the edge container. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">size_t
- <span style="font-weight: bold;">num_cells</span>() const </td>
- <td>Returns the number of the Voronoi
- cells in the Voronoi diagram. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">size_t
- <span style="font-weight: bold;">num_edges</span>() const </td>
- <td>Returns the number of the
- Voronoi edges (half-edges) in the Voronoi diagram. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">size_t
- <span style="font-weight: bold;">num_vertices</span>()
- const </td>
- <td>Returns the number of the
- Voronoi vertices in the Voronoi diagram. </td>
- </tr>
- </tbody>
- </table>
- <h2>Member Types</h2>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
- <tbody>
- <tr>
- <td style="font-weight: bold;">coordinate_type </td>
- <td>Coordinate type. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">cell_type </td>
- <td>Voronoi cell. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">vertex_type </td>
- <td>Voronoi vertex. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">edge_type </td>
- <td>Voronoi edge. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">cell_container_type </td>
- <td>Container of the Voronoi cells. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">const_cell_iterator </td>
- <td>Const cell container iterator. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">vertex_container_type </td>
- <td>Container of the Voronoi vertices. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">const_vertex_iterator </td>
- <td>Const vertex container iterator. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">edge_container_type </td>
- <td>Container of the Voronoi edges. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">const_edge_iterator </td>
- <td>Const edge container iterator. </td>
- </tr>
- </tbody>
- </table>
- <h1>Voronoi Geometry Type</h1>
- The Voronoi
- diagram data structure doesn't embed coordinates of the input
- geometries.
- Instead it links with those via source index and source category
- methods
- of the Voronoi cell primitive. Source index is incrementally given
- (starting from zero) to each input site inserted into the <a
- href="voronoi_builder.htm">Voronoi
- builder</a>.
- Considering the fact, that each input segment is splitted onto three
- separate sites with the same index, we distinguish between those using
- source category. For more examples check the <a
- href="voronoi_basic_tutorial.htm">Voronoi basic tutorial</a>.<br>
- <h2>GeometryCategory </h2>
- Defines geometric category of the input object.<br>
- Header: <a href="../../../boost/polygon/voronoi_geometry_type.hpp">boost/polygon/</a><a
- href="../../../boost/polygon/voronoi_geometry_type.hpp">voronoi_geometry_type.hpp</a><br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">enum
- GeometryCategory {</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- GEOMETRY_CATEGORY_POINT = 0x0,</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- GEOMETRY_CATEGORY_SEGMENT = 0x1</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">};</span><br>
- <h2>SourceCategory</h2>
- Defines semantic category of the input site.<br>
- Header: <a href="../../../boost/polygon/voronoi_geometry_type.hpp">boost/polygon/</a><a
- href="../../../boost/polygon/voronoi_geometry_type.hpp">voronoi_geometry_type.hpp</a><br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">enum
- SourceCategory {</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- // Point subtypes.</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- SOURCE_CATEGORY_SINGLE_POINT = 0x0,</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1,</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2,</span><br
- style="font-family: Courier New,Courier,monospace;">
- <br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- // Segment subtypes.</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8,</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9,</span><br
- style="font-family: Courier New,Courier,monospace;">
- <br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3,</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- SOURCE_CATEGORY_BITMASK = 0x1F</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">};</span><br>
- <h2>Member Functions</h2>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
- <tbody>
- <tr>
- <td style="vertical-align: top;"><span
- style="font-family: Courier New,Courier,monospace;">bool <span
- style="font-weight: bold;">belongs</span>(</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- SourceCategory source_category,</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- GeometryCategory geometry_category)</span> </td>
- <td style="vertical-align: middle;">Returns true if the
- given source
- category belongs to the given geometry category.<br>
- Returns false otherwise. </td>
- </tr>
- </tbody>
- </table>
- <h1>Voronoi Edge</h1>
- A Voronoi edge is a one-dimenstion curve, that contains points
- equidistant from the two closest input geometries. The Voronoi edge
- data structure is implemented as the enhanced classical <a
- href="http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml">half-edge</a>
- data structure. On the image below, the Voronoi edges are drawn as
- directed linear (e.g. AE) or curved (e.g. DE) dashed lines of either
- green (e.g. AE) or black (e.g DE) color. The green edges are considered
- to be secondary, as they are generated by an input segment and its
- endpoint (e.g. edge EA, made by segment MN and its endpoint M). All the
- other edges are considered to be primary (e.g. curved edge CD, made by
- segment KL and point N). Apart from that, each edge can be finite (e.g.
- ED) or infinite (e.g. edge starting at point B and going in the east
- direction).<br>
- <img src="images/voronoi1.png" alt=""
- style="width: 600px; height: 600px;"><br>
- Each Voronoi edge (consider directed edge BA) provides efficient access
- to the following primitives:<br>
- <ul>
- <li>Cell the edge belongs to (Voronoi cell P, with source
- segment MN)</li>
- <li>Start point of the edge (Voronoi vertex B, that is
- equidistant from the following input sites: O, L, MN)</li>
- <li>End point of the edge (Voronoi vertex A, that is
- equidistant from the following input sites: O, M, MN)</li>
- <li>Twin edge (Voronoi edge AB)</li>
- <li>CCW next edge inside the Voronoi cell, that the edge
- belongs to (green Voronoi edge AE)</li>
- <li>CCW previous edge inside the Voronoi cell, that the edge
- belongs to (Voronoi edge CB)</li>
- <li>CCW rotated next edge around the start point of the edge
- (Voronoi edge BC)</li>
- <li>CCW rotated previous edge around the start point of the
- edge (infinite Voronoi edge starting at the Voronoi vertex B and going
- in the east direction) </li>
- </ul>
- <h2>Declaration</h2>
- Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">template
- <typename T></span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">class
- voronoi_edge;<br>
- <br>
- T</span> - coordinate type.<br>
- <h2>Member Functions</h2>
- <span style="font-family: Courier New,Courier,monospace;"> </span>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
- <tbody>
- <tr>
- <td><span
- style="font-family: Courier New,Courier,monospace;"><span
- style="font-weight: bold;">voronoi_edge</span>(bool is_linear, bool
- is_primary)</span> </td>
- <td>Voronoi edge constructor. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_cell_type*
- <span style="font-weight: bold;">cell</span>() </td>
- <td>Returns the pointer to the
- Voronoi <span style="font-family: Courier New,Courier,monospace;"></span>cell
- that the edge belongs to. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- voronoi_cell_type* <span style="font-weight: bold;">cell</span>()
- const </td>
- <td>Returns the const pointer
- to the Voronoi cell that the edge belongs to. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">cell</span>(voronoi_cell_type*
- c) </td>
- <td>Sets the Voronoi cell
- pointer to the cell the current edge belongs to. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type*
- <span style="font-weight: bold;">vertex0</span>() </td>
- <td>Returns the pointer to the
- start point of the edge.<br>
- If the edge is infinite in that direction returns NULL. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- voronoi_vertex_type* <span style="font-weight: bold;">vertex0</span>()
- const </td>
- <td>Returns the const pointer
- to the start point vertex of the edge.<br>
- If the edge is infinite in that direction returns NULL. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">vertex0</span>(voronoi_vertex_type*
- v) </td>
- <td>Sets the start point
- pointer of the edge. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type*
- <span style="font-weight: bold;">vertex1</span>() </td>
- <td>Returns the pointer to the
- end point of the edge.<br>
- If the edge is infinite in that direction returns NULL. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- voronoi_vertex_type* <span style="font-weight: bold;">vertex1</span>()
- const </td>
- <td>Returns the const pointer
- to the end point of the edge.<br>
- If the edge is infinite in that direction returns NULL. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
- <span style="font-weight: bold;">twin</span>() </td>
- <td>Returns the pointer to the
- twin edge. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- voronoi_edge_type* <span style="font-weight: bold;">twin</span>()
- const </td>
- <td>Returns the const pointer
- to the twin edge. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">twin</span>(voronoi_edge_type*
- e) </td>
- <td>Sets the twin edge pointer
- of the edge. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
- <span style="font-weight: bold;">next</span>() </td>
- <td>Returns the pointer to the
- CCW next edge within the corresponding Voronoi cell.<br>
- Edges not necessarily share a common vertex (e.g. infinite edges). </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- voronoi_edge_type* <span style="font-weight: bold;">next</span>()
- const </td>
- <td>Returns the const pointer
- to the CCW next edge within the corresponding Voronoi cell.<br>
- Edges not necessarily share a common vertex (e.g. infinite edges). </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">next</span>(voronoi_edge_type*
- e) </td>
- <td>Sets the CCW next edge
- pointer of the edge. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
- <span style="font-weight: bold;">prev</span>() </td>
- <td>Returns the pointer to the
- CCW prev edge within the corresponding Voronoi cell.<br>
- Edges not necessarily share a common vertex (e.g. infinite edges). </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- voronoi_edge_type* <span style="font-weight: bold;">prev</span>()
- const </td>
- <td>Returns the const pointer
- to the CCW prev edge within the corresponding Voronoi cell.<br>
- Edges not necessarily share a common vertex (e.g. infinite edges). </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">prev</span>(voronoi_edge_type*
- e) </td>
- <td>Sets the CCW prev edge
- pointer of the edge. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">color_type
- <span style="font-weight: bold;">color</span>() const </td>
- <td>Returns the color value. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">color</span>(color_type
- color) const </td>
- <td>Sets the color of
- the edge.<br>
- Allows to associate the user provided data with the primitive. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
- <span style="font-weight: bold;">rot_next</span>() </td>
- <td>Returns the pointer to the
- CCW next edge rotated around the edge start point.<br>
- Works for infinite edges as well. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- voronoi_edge_type* <span style="font-weight: bold;">rot_next</span>()
- const </td>
- <td>Returns the const pointer
- to the CCW next edge rotated around the edge start point.<br>
- Works for infinite edges as well.</td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
- <span style="font-weight: bold;">rot_prev</span>() </td>
- <td>Returns the pointer to the
- CCW prev edge rotated around the edge start point.<br>
- Works for infinite edges as well. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- voronoi_edge_type* <span style="font-weight: bold;">rot_prev</span>()
- const </td>
- <td>Returns the const pointer
- to the CCW prev edge rotated around the edge start point.<br>
- Works for infinite edges as well.</td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_finite</span>() const </td>
- <td>Returns true if the both
- end points of the edge are finite, else false. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_infinite</span>() const</td>
- <td>Returns true if one of the
- end points of the edge is infinite, else false.</td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_linear</span>() const </td>
- <td>Returns true if the edge
- is linear (segment, ray, line), else false. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_curved</span>() const </td>
- <td>Returns true if the edge
- is curved (parabolic arc), else false. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_primary</span>() const </td>
- <td>Returns false if the edge
- goes through the endpoint of the segment site, else true. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_secondary</span>() const</td>
- <td>Returns true if the edge
- goes through the endpoint of the segment site, else false.</td>
- </tr>
- </tbody>
- </table>
- <span style="font-family: Courier New,Courier,monospace;"> </span>All
- the above methods have O(1) complexity. The size of
- the Voronoi edge structure is equal to: 5 * sizeof(void *) +
- sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span><br>
- <h2>Member Types</h2>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
- <tbody>
- <tr>
- <td style="font-weight: bold;">coordinate_type </td>
- <td>Coordinate type. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">voronoi_cell_type </td>
- <td>Voronoi cell type. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">voronoi_vertex_type </td>
- <td>Voronoi vertex type. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">voronoi_edge_type </td>
- <td>Voronoi edge type. </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-weight: bold;">color_type
- </td>
- <td style="vertical-align: top;">Color type (check the
- Important section). </td>
- </tr>
- </tbody>
- </table>
- <h1>Voronoi Cell</h1>
- A Voronoi cell represents a region of the Voronoi diagram bounded by
- the Voronoi edges. On the image below, there are 7 such regions: P, Q,
- R, S, T, U, V. Each Voronoi cell can contain a point (e.g. cells Q, S,
- T, U, V with corresponding input sources N, K, L, O, M respectively) or
- a segment
- (e.g. cells P and R with corresponding input sources MN and KL
- respectively) as its
- source. The Voronoi cell primitive doesn't contain coordinates of the
- source geometry, instead it stores the index and category of the source
- geometry. Source index corresponds to the unique id, issued to each
- input geometry (e.g. incremental counter, used by the Voronoi builder).
- Such an index uniquely identifies any input point (e.g. O), however
- doesn't make any distinction between segment (e.g. MN) and both its end
- points (e.g. M, N). In order to resolve possible ambiguity, the source
- category is used, that specifies the semantic topology of the input
- object (e.g. segment's startpoint, segment's endpoint or segment
- itself). The Voronoi cell data structure also provides access to a
- random Voronoi edge, located on the boundary of the cell (e.g. edge AE
- for
- the cell P).<br>
- <img style="width: 600px; height: 600px;" alt=""
- src="images/voronoi1.png"><br>
- <h2>Declaration</h2>
- Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">template
- <typename T><br>
- class voronoi_cell;<br>
- <br>
- </span><span style="font-family: Courier New,Courier,monospace;">T</span>
- - coordinate type.<br>
- <h2>Member Functions</h2>
- <span style="font-family: Courier New,Courier,monospace;"> </span>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
- <tbody>
- <tr>
- <td><span
- style="font-family: Courier New,Courier,monospace;"><span
- style="font-weight: bold;">voronoi_cell</span>(source_index_type
- source_index,</span><span
- style="font-family: Courier New,Courier,monospace;"><br>
-
- source_category_type source_category)</span> </td>
- <td>Voronoi cell constructor. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">source_index_type
- <span style="font-weight: bold;">source_index</span>()
- const </td>
- <td>Returns input site index among the other sites.<br>
- Both segment and its end points will have the same index. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">source_category_type
- <span style="font-weight: bold;">source_category</span>()
- const </td>
- <td>Returns input site category among the other sites.<br>
- Allows to distinguish between segment site and its endpoints. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
- <span style="font-weight: bold;">incident_edge</span>() </td>
- <td>Returns the pointer to the
- one of the boundary edges. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>()
- const </td>
- <td>Returns the const pointer
- to the one of the boundary edges. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type*
- e) </td>
- <td>Sets the incident boundary
- edge pointer of the cell. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">color_type
- <span style="font-weight: bold;">color</span>() const </td>
- <td>Returns the color associated with the cell.</td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">color</span>(color_type
- color) const </td>
- <td>Sets the color of
- the cell.<br>
- Allows to associate the user provided data with the primitive. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">contains_point</span>()
- const</td>
- <td>Returns true if the cell
- contains a point site, else false.</td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">contains_segment</span>()
- const</td>
- <td>Returns true if the cell
- contains a segment site, else false.</td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_degenerate</span>()
- const </td>
- <td>Returns true if the cell
- doesn't have an incident edge.<br>
- Can happen if a few input segments share a common endpoint.</td>
- </tr>
- </tbody>
- </table>
- <span style="font-family: Courier New,Courier,monospace;"> </span>All
- the above methods have O(1) complexity. The size of
- the Voronoi cell structure is equal to: sizeof(void *) + 2 *
- sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span>
- <h2>Member Types</h2>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
- <tbody>
- <tr>
- <td style="font-weight: bold;">coordinate_type </td>
- <td>Coordinate type. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">source_index_type</td>
- <td>Source index type. </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-weight: bold;">source_category_type
- </td>
- <td style="vertical-align: top;">Source category type. </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-weight: bold;">voronoi_edge_type
- </td>
- <td style="vertical-align: top;">Voronoi edge type. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">color_type </td>
- <td>Color type (check the Important section). </td>
- </tr>
- </tbody>
- </table>
- <h2>Miscellaneous</h2>
- The following code snippet effectively traverses the Voronoi edges
- around the
- Voronoi cell:<br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">const
- voronoi_edge<double>* edge = cell->incident_edge();</span><br>
- <span style="font-family: Courier New,Courier,monospace;">do {</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- edge = edge->next();</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- // Do smth. with edge.</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">} while
- (edge != cell->incident_edge());</span><br>
- <h1>Voronoi Vertex</h1>
- A Voronoi vertex represents a point, that is equidistant from the three
- or more input geometries. As a consequence, it corresponds to the point
- of the intersection of the three or more Voronoi edges. On the image
- below, there are 5 such vertices: A, B, C, D, E. The Voronoi vertex
- data structure embeds the coordinates of the underlying point and
- provides access to a random Voronoi edge originating from the vertex
- (e.g. edge
- BC for the vertex B).<br>
- <img style="width: 600px; height: 600px;" alt=""
- src="images/voronoi1.png"><br>
- <h2>Declaration</h2>
- Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">template
- <typename T></span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">class
- voronoi_vertex;<br>
- <br>
- </span><span style="font-family: Courier New,Courier,monospace;">T</span>
- - coordinate type.<br>
- <h2>Member Functions</h2>
- <span style="font-family: Courier New,Courier,monospace;"> </span>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
- <tbody>
- <tr>
- <td><span
- style="font-family: Courier New,Courier,monospace;"><span
- style="font-weight: bold;">voronoi_vertex</span>(const
- coordinate_type& x,<br>
-
- const coordinate_type& y)</span><span
- style="font-family: Courier New,Courier,monospace;"></span> </td>
- <td>Voronoi vertex constructor. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- coordinate_type& <span style="font-weight: bold;">x</span>() const </td>
- <td>Returns the x-coordinate of the point that represents
- the vertex. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- coordinate_type& <span style="font-weight: bold;">y</span>() const</td>
- <td>Returns the y-coordinate of the point that represents
- the vertex. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
- <span style="font-weight: bold;">incident_edge</span>() </td>
- <td>Returns the incident edge
- pointer. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
- voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>()
- const </td>
- <td>Returns the const pointer
- to the incident edge. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type*
- e) </td>
- <td>Sets the incident edge
- pointer. </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">color_type
- <span style="font-weight: bold;">color</span>() const </td>
- <td>Returns the color associated with the vertex.</td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">color</span>(color_type
- color) const </td>
- <td>Sets the color of
- the vertex.<br>
- Allows to associate the user provided data with the primitive.</td>
- </tr>
- </tbody>
- </table>
- <span style="font-family: Courier New,Courier,monospace;"> </span>All
- the above methods have O(1) complexity. The size of
- the Voronoi vertex structure is equal to: sizeof(void *) +
- sizeof(size_t) + 2 *
- sizeof(coordinate_type).<span
- style="font-family: Courier New,Courier,monospace;"></span>
- <h2>Member Types</h2>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
- <tbody>
- <tr>
- <td style="font-weight: bold;">coordinate_type </td>
- <td>Coordainte type. </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-weight: bold;">voronoi_edge_type
- </td>
- <td style="vertical-align: top;">Voronoi edge type. </td>
- </tr>
- <tr>
- <td style="font-weight: bold;">color_type </td>
- <td>Color type (check the Important section). </td>
- </tr>
- </tbody>
- </table>
- <h2>Miscellaneous</h2>
- The following code snippet effectively traverses the Voronoi edges
- around the
- Voronoi vertex:<br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">const
- voronoi_edge<double>* edge = vertex->incident_edge();</span><br>
- <span style="font-family: Courier New,Courier,monospace;">do {</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- edge = edge->next();</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">
- // Do smth. with edge.</span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">} while
- (edge != vertex->incident_edge()); </span>
- <h1>Voronoi Diagram Traits </h1>
- The Voronoi diagram traits are used to configure the Voronoi primitive
- types and predicates, used by the Voronoi diagram
- data
- structure.<br>
- The implementation includes default traits specialization for the
- double output coordinate type.<br>
- <h2>Declaration</h2>
- Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">template
- <typename T></span><br
- style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">struct
- voronoi_diagram_traits;<br>
- <br>
- </span><span style="font-family: Courier New,Courier,monospace;">T</span>
- - coordinate type.<br>
- <h2>Member Types</h2>
- <span style="font-family: Courier New,Courier,monospace;"> </span>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
- <tbody>
- <tr>
- <td
- style="font-family: Courier New,Courier,monospace; font-weight: bold;">coordinate_type
- </td>
- <td>Coordinate type
- of the Voronoi diagram primitives. </td>
- </tr>
- <tr>
- <td
- style="font-family: Courier New,Courier,monospace; font-weight: bold;">cell_type
- </td>
- <td>Voronoi cell type. </td>
- </tr>
- <tr>
- <td
- style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_type
- </td>
- <td>Voronoi vertex type. </td>
- </tr>
- <tr>
- <td
- style="font-family: Courier New,Courier,monospace; font-weight: bold;">edge_type
- </td>
- <td>Voronoi edge type. </td>
- </tr>
- <tr>
- <td
- style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_equality_predicate_type
- </td>
- <td>Predicate that returns
- true if the two points are considered to be equal.<br>
- False otherwise. It is used to unite nearby Voronoi vertices. </td>
- </tr>
- </tbody>
- </table>
- </td>
- </tr>
- <tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1"> </td>
- <td
- style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
- valign="top" width="100%">
- <table class="docinfo" id="table2" frame="void" rules="none">
- <colgroup> <col class="docinfo-name"><col
- class="docinfo-content"> </colgroup> <tbody valign="top">
- <tr>
- <th class="docinfo-name">Copyright:</th>
- <td>Copyright © Andrii Sydorchuk 2010-2013.</td>
- </tr>
- <tr class="field">
- <th class="docinfo-name">License:</th>
- <td class="field-body">Distributed under the Boost Software
- License, Version 1.0. (See accompanying file <tt class="literal"><span
- class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
- class="reference" target="_top"
- href="http://www.boost.org/LICENSE_1_0.txt">
- http://www.boost.org/LICENSE_1_0.txt</a>)</td>
- </tr>
- </tbody>
- </table>
- </td>
- </tr>
- </tbody>
- </table>
- </body>
- </html>
|