<a href="cell_8cc.html">Go to the documentation of this file.</a><div class="fragment"><div class="line"><a name="l00001"></a><span class="lineno"> 1</span> <span class="comment">// Voro++, a 3D cell-based Voronoi library</span></div>
<div class="line"><a name="l00008"></a><span class="lineno"> 8</span> <span class="comment"> * \brief Function implementations for the voronoicell and related classes. */</span></div>
<div class="line"><a name="l00013"></a><span class="lineno"> 13</span> <span class="preprocessor">#include "<a class="code" href="config_8hh.html" title="Master configuration file for setting various compile-time options.">config.hh</a>"</span></div>
<div class="line"><a name="l00014"></a><span class="lineno"> 14</span> <span class="preprocessor">#include "<a class="code" href="common_8hh.html" title="Header file for the small helper functions.">common.hh</a>"</span></div>
<div class="line"><a name="l00015"></a><span class="lineno"> 15</span> <span class="preprocessor">#include "<a class="code" href="cell_8hh.html" title="Header file for the voronoicell and related classes.">cell.hh</a>"</span></div>
<div class="line"><a name="l00019"></a><span class="lineno"> 19</span> <span class="comment">/** Constructs a Voronoi cell and sets up the initial memory. */</span></div>
<div class="line"><a name="l00042"></a><span class="lineno"> 42</span> <span class="comment">/** The voronoicell destructor deallocates all the dynamic memory. */</span></div>
<div class="line"><a name="l00052"></a><span class="lineno"> 52</span> <span class="comment">/** Ensures that enough memory is allocated prior to carrying out a copy.</span></div>
<div class="line"><a name="l00053"></a><span class="lineno"> 53</span> <span class="comment"> * \param[in] vc a reference to the specialized version of the calling class.</span></div>
<div class="line"><a name="l00054"></a><span class="lineno"> 54</span> <span class="comment"> * \param[in] vb a pointered to the class to be copied. */</span></div>
<div class="line"><a name="l00062"></a><span class="lineno"> 62</span> <span class="comment">/** Copies the vertex and edge information from another class. The routine</span></div>
<div class="line"><a name="l00063"></a><span class="lineno"> 63</span> <span class="comment"> * assumes that enough memory is available for the copy.</span></div>
<div class="line"><a name="l00064"></a><span class="lineno"> 64</span> <span class="comment"> * \param[in] vb a pointer to the class to copy. */</span></div>
<div class="line"><a name="l00065"></a><span class="lineno"><a class="code" href="classvoro_1_1voronoicell__base.html#a47d450e9b9be0fab103f401ddcaeefac"> 65</a></span> <span class="keywordtype">void</span> <a class="code" href="classvoro_1_1voronoicell__base.html#a47d450e9b9be0fab103f401ddcaeefac">voronoicell_base::copy</a>(<a class="code" href="classvoro_1_1voronoicell__base.html" title="A class representing a single Voronoi cell.">voronoicell_base</a>* vb) {</div>
<div class="line"><a name="l00077"></a><span class="lineno"> 77</span> <span class="comment">/** Copies the information from another voronoicell class into this</span></div>
<div class="line"><a name="l00079"></a><span class="lineno"> 79</span> <span class="comment"> * \param[in] c the class to copy. */</span></div>
<div class="line"><a name="l00080"></a><span class="lineno"><a class="code" href="classvoro_1_1voronoicell__neighbor.html#ac6036ae44845e301da1e3656e0e98403"> 80</a></span> <span class="keywordtype">void</span> <a class="code" href="classvoro_1_1voronoicell__neighbor.html#ac6036ae44845e301da1e3656e0e98403">voronoicell_neighbor::operator=</a>(<a class="code" href="classvoro_1_1voronoicell.html" title="Extension of the voronoicell_base class to represent a Voronoi cell without neighbor information...">voronoicell</a> &c) {</div>
<div class="line"><a name="l00081"></a><span class="lineno"> 81</span>  <a class="code" href="classvoro_1_1voronoicell__base.html" title="A class representing a single Voronoi cell.">voronoicell_base</a> *vb=((<a class="code" href="classvoro_1_1voronoicell__base.html" title="A class representing a single Voronoi cell.">voronoicell_base</a>*) &c);</div>
<div class="line"><a name="l00090"></a><span class="lineno"> 90</span> <span class="comment">/** Copies the information from another voronoicell_neighbor class into this</span></div>
<div class="line"><a name="l00092"></a><span class="lineno"> 92</span> <span class="comment"> * \param[in] c the class to copy. */</span></div>
<div class="line"><a name="l00093"></a><span class="lineno"><a class="code" href="classvoro_1_1voronoicell__neighbor.html#a0754fe4a44916b68bf3cda3d129b3a69"> 93</a></span> <span class="keywordtype">void</span> <a class="code" href="classvoro_1_1voronoicell__neighbor.html#ac6036ae44845e301da1e3656e0e98403">voronoicell_neighbor::operator=</a>(<a class="code" href="classvoro_1_1voronoicell__neighbor.html" title="Extension of the voronoicell_base class to represent a Voronoi cell with neighbor information...">voronoicell_neighbor</a> &c) {</div>
<div class="line"><a name="l00094"></a><span class="lineno"> 94</span>  <a class="code" href="classvoro_1_1voronoicell__base.html" title="A class representing a single Voronoi cell.">voronoicell_base</a> *vb=((<a class="code" href="classvoro_1_1voronoicell__base.html" title="A class representing a single Voronoi cell.">voronoicell_base</a>*) &c);</div>
<div class="line"><a name="l00103"></a><span class="lineno"> 103</span> <span class="comment">/** Translates the vertices of the Voronoi cell by a given vector.</span></div>
<div class="line"><a name="l00104"></a><span class="lineno"> 104</span> <span class="comment"> * \param[in] (x,y,z) the coordinates of the vector. */</span></div>
<div class="line"><a name="l00113"></a><span class="lineno"> 113</span> <span class="comment">/** Increases the memory storage for a particular vertex order, by increasing</span></div>
<div class="line"><a name="l00114"></a><span class="lineno"> 114</span> <span class="comment"> * the size of the of the corresponding mep array. If the arrays already exist,</span></div>
<div class="line"><a name="l00115"></a><span class="lineno"> 115</span> <span class="comment"> * their size is doubled; if they don't exist, then new ones of size</span></div>
<div class="line"><a name="l00116"></a><span class="lineno"> 116</span> <span class="comment"> * init_n_vertices are allocated. The routine also ensures that the pointers in</span></div>
<div class="line"><a name="l00117"></a><span class="lineno"> 117</span> <span class="comment"> * the ed array are updated, by making use of the back pointers. For the cases</span></div>
<div class="line"><a name="l00118"></a><span class="lineno"> 118</span> <span class="comment"> * where the back pointer has been temporarily overwritten in the marginal</span></div>
<div class="line"><a name="l00119"></a><span class="lineno"> 119</span> <span class="comment"> * vertex code, the auxiliary delete stack is scanned to find out how to update</span></div>
<div class="line"><a name="l00120"></a><span class="lineno"> 120</span> <span class="comment"> * the ed value. If the template has been instantiated with the neighbor</span></div>
<div class="line"><a name="l00121"></a><span class="lineno"> 121</span> <span class="comment"> * tracking turned on, then the routine also reallocates the corresponding mne</span></div>
<div class="line"><a name="l00123"></a><span class="lineno"> 123</span> <span class="comment"> * \param[in] i the order of the vertex memory to be increased. */</span></div>
<div class="line"><a name="l00172"></a><span class="lineno"> 172</span> <span class="comment">/** Doubles the maximum number of vertices allowed, by reallocating the ed, nu,</span></div>
<div class="line"><a name="l00173"></a><span class="lineno"> 173</span> <span class="comment"> * and pts arrays. If the allocation exceeds the absolute maximum set in</span></div>
<div class="line"><a name="l00174"></a><span class="lineno"> 174</span> <span class="comment"> * max_vertices, then the routine exits with a fatal error. If the template has</span></div>
<div class="line"><a name="l00175"></a><span class="lineno"> 175</span> <span class="comment"> * been instantiated with the neighbor tracking turned on, then the routine</span></div>
<div class="line"><a name="l00176"></a><span class="lineno"> 176</span> <span class="comment"> * also reallocates the ne array. */</span></div>
<div class="line"><a name="l00198"></a><span class="lineno"> 198</span> <span class="comment">/** Doubles the maximum allowed vertex order, by reallocating mem, mep, and mec</span></div>
<div class="line"><a name="l00199"></a><span class="lineno"> 199</span> <span class="comment"> * arrays. If the allocation exceeds the absolute maximum set in</span></div>
<div class="line"><a name="l00200"></a><span class="lineno"> 200</span> <span class="comment"> * max_vertex_order, then the routine causes a fatal error. If the template has</span></div>
<div class="line"><a name="l00201"></a><span class="lineno"> 201</span> <span class="comment"> * been instantiated with the neighbor tracking turned on, then the routine</span></div>
<div class="line"><a name="l00202"></a><span class="lineno"> 202</span> <span class="comment"> * also reallocates the mne array. */</span></div>
<div class="line"><a name="l00208"></a><span class="lineno"> 208</span> <span class="preprocessor"></span> fprintf(stderr,<span class="stringliteral">"Vertex order memory scaled up to %d\n"</span>,i);</div>
<div class="line"><a name="l00223"></a><span class="lineno"> 223</span> <span class="comment">/** Doubles the size allocation of the main delete stack. If the allocation</span></div>
<div class="line"><a name="l00224"></a><span class="lineno"> 224</span> <span class="comment"> * exceeds the absolute maximum set in max_delete_size, then routine causes a</span></div>
<div class="line"><a name="l00238"></a><span class="lineno"> 238</span> <span class="comment">/** Doubles the size allocation of the auxiliary delete stack. If the</span></div>
<div class="line"><a name="l00239"></a><span class="lineno"> 239</span> <span class="comment"> * allocation exceeds the absolute maximum set in max_delete2_size, then the</span></div>
<div class="line"><a name="l00253"></a><span class="lineno"> 253</span> <span class="comment">/** Initializes a Voronoi cell as a rectangular box with the given dimensions.</span></div>
<div class="line"><a name="l00254"></a><span class="lineno"> 254</span> <span class="comment"> * \param[in] (xmin,xmax) the minimum and maximum x coordinates.</span></div>
<div class="line"><a name="l00255"></a><span class="lineno"> 255</span> <span class="comment"> * \param[in] (ymin,ymax) the minimum and maximum y coordinates.</span></div>
<div class="line"><a name="l00256"></a><span class="lineno"> 256</span> <span class="comment"> * \param[in] (zmin,zmax) the minimum and maximum z coordinates. */</span></div>
<div class="line"><a name="l00282"></a><span class="lineno"> 282</span> <span class="comment">/** Initializes a Voronoi cell as a regular octahedron.</span></div>
<div class="line"><a name="l00283"></a><span class="lineno"> 283</span> <span class="comment"> * \param[in] l The distance from the octahedron center to a vertex. Six</span></div>
<div class="line"><a name="l00284"></a><span class="lineno"> 284</span> <span class="comment"> * vertices are initialized at (-l,0,0), (l,0,0), (0,-l,0),</span></div>
<div class="line"><a name="l00306"></a><span class="lineno"> 306</span> <span class="comment">/** Initializes a Voronoi cell as a tetrahedron. It assumes that the normal to</span></div>
<div class="line"><a name="l00307"></a><span class="lineno"> 307</span> <span class="comment"> * the face for the first three vertices points inside.</span></div>
<div class="line"><a name="l00308"></a><span class="lineno"> 308</span> <span class="comment"> * \param (x0,y0,z0) a position vector for the first vertex.</span></div>
<div class="line"><a name="l00309"></a><span class="lineno"> 309</span> <span class="comment"> * \param (x1,y1,z1) a position vector for the second vertex.</span></div>
<div class="line"><a name="l00310"></a><span class="lineno"> 310</span> <span class="comment"> * \param (x2,y2,z2) a position vector for the third vertex.</span></div>
<div class="line"><a name="l00311"></a><span class="lineno"> 311</span> <span class="comment"> * \param (x3,y3,z3) a position vector for the fourth vertex. */</span></div>
<div class="line"><a name="l00328"></a><span class="lineno"> 328</span> <span class="comment">/** Checks that the relational table of the Voronoi cell is accurate, and</span></div>
<div class="line"><a name="l00329"></a><span class="lineno"> 329</span> <span class="comment"> * prints out any errors. This algorithm is O(p), so running it every time the</span></div>
<div class="line"><a name="l00330"></a><span class="lineno"> 330</span> <span class="comment"> * plane routine is called will result in a significant slowdown. */</span></div>
<div class="line"><a name="l00337"></a><span class="lineno"> 337</span> <span class="comment">/** This routine checks for any two vertices that are connected by more than</span></div>
<div class="line"><a name="l00338"></a><span class="lineno"> 338</span> <span class="comment"> * one edge. The plane algorithm is designed so that this should not happen, so</span></div>
<div class="line"><a name="l00339"></a><span class="lineno"> 339</span> <span class="comment"> * any occurrences are most likely errors. Note that the routine is O(p), so</span></div>
<div class="line"><a name="l00340"></a><span class="lineno"> 340</span> <span class="comment"> * running it every time the plane routine is called will result in a</span></div>
<div class="line"><a name="l00348"></a><span class="lineno"> 348</span> <span class="comment">/** Constructs the relational table if the edges have been specified. */</span></div>
<div class="line"><a name="l00362"></a><span class="lineno"> 362</span> <span class="comment">/** Starting from a point within the current cutting plane, this routine attempts</span></div>
<div class="line"><a name="l00363"></a><span class="lineno"> 363</span> <span class="comment"> * to find an edge to a point outside the cutting plane. This prevents the plane</span></div>
<div class="line"><a name="l00364"></a><span class="lineno"> 364</span> <span class="comment"> * routine from .</span></div>
<div class="line"><a name="l00365"></a><span class="lineno"> 365</span> <span class="comment"> * \param[in] vc a reference to the specialized version of the calling class.</span></div>
<div class="line"><a name="l00366"></a><span class="lineno"> 366</span> <span class="comment"> * \param[in,out] up */</span></div>
<div class="line"><a name="l00384"></a><span class="lineno"> 384</span> <span class="comment">/** Adds a point to the auxiliary delete stack if it is not already there.</span></div>
<div class="line"><a name="l00385"></a><span class="lineno"> 385</span> <span class="comment"> * \param[in] vc a reference to the specialized version of the calling class.</span></div>
<div class="line"><a name="l00386"></a><span class="lineno"> 386</span> <span class="comment"> * \param[in] lp the index of the point to add.</span></div>
<div class="line"><a name="l00387"></a><span class="lineno"> 387</span> <span class="comment"> * \param[in,out] stackp2 a pointer to the end of the stack entries. */</span></div>
<div class="line"><a name="l00395"></a><span class="lineno"> 395</span> <span class="comment">/** Cuts the Voronoi cell by a particle whose center is at a separation of</span></div>
<div class="line"><a name="l00396"></a><span class="lineno"> 396</span> <span class="comment"> * (x,y,z) from the cell center. The value of rsq should be initially set to</span></div>
<div class="line"><a name="l00398"></a><span class="lineno"> 398</span> <span class="comment"> * \param[in] vc a reference to the specialized version of the calling class.</span></div>
<div class="line"><a name="l00399"></a><span class="lineno"> 399</span> <span class="comment"> * \param[in] (x,y,z) the normal vector to the plane.</span></div>
<div class="line"><a name="l00400"></a><span class="lineno"> 400</span> <span class="comment"> * \param[in] rsq the distance along this vector of the plane.</span></div>
<div class="line"><a name="l00401"></a><span class="lineno"> 401</span> <span class="comment"> * \param[in] p_id the plane ID (for neighbor tracking only).</span></div>
<div class="line"><a name="l00402"></a><span class="lineno"> 402</span> <span class="comment"> * \return False if the plane cut deleted the cell entirely, true otherwise. */</span></div>
<div class="line"><a name="l00413"></a><span class="lineno"> 413</span>  <span class="comment">// Test approximately sqrt(n)/4 points for their proximity to the plane</span></div>
<div class="line"><a name="l00414"></a><span class="lineno"> 414</span>  <span class="comment">// and keep the one which is closest</span></div>
<div class="line"><a name="l00417"></a><span class="lineno"> 417</span>  <span class="comment">// Starting from an initial guess, we now move from vertex to vertex,</span></div>
<div class="line"><a name="l00418"></a><span class="lineno"> 418</span>  <span class="comment">// to try and find an edge which intersects the cutting plane,</span></div>
<div class="line"><a name="l00419"></a><span class="lineno"> 419</span>  <span class="comment">// or a vertex which is on the plane</span></div>
<div class="line"><a name="l00423"></a><span class="lineno"> 423</span>  <span class="comment">// The test point is inside the cutting plane.</span></div>
<div class="line"><a name="l00460"></a><span class="lineno"> 460</span>  <span class="comment">// If the last point in the iteration is within the</span></div>
<div class="line"><a name="l00461"></a><span class="lineno"> 461</span>  <span class="comment">// plane, we need to do the complicated setup</span></div>
<div class="line"><a name="l00462"></a><span class="lineno"> 462</span>  <span class="comment">// routine. Otherwise, we use the regular iteration.</span></div>
<div class="line"><a name="l00507"></a><span class="lineno"> 507</span>  <span class="comment">// Our original test point was on the plane, so we</span></div>
<div class="line"><a name="l00508"></a><span class="lineno"> 508</span>  <span class="comment">// automatically head for the complicated setup</span></div>
<div class="line"><a name="l00514"></a><span class="lineno"> 514</span>  <span class="comment">// This routine is a fall-back, in case floating point errors</span></div>
<div class="line"><a name="l00515"></a><span class="lineno"> 515</span>  <span class="comment">// cause the usual search routine to fail. In the fall-back</span></div>
<div class="line"><a name="l00516"></a><span class="lineno"> 516</span>  <span class="comment">// routine, we just test every edge to find one straddling</span></div>
<div class="line"><a name="l00517"></a><span class="lineno"> 517</span>  <span class="comment">// the plane.</span></div>
<div class="line"><a name="l00526"></a><span class="lineno"> 526</span>  <span class="comment">// The point is inside the cutting space. Now</span></div>
<div class="line"><a name="l00527"></a><span class="lineno"> 527</span>  <span class="comment">// see if we can find a neighbor which isn't.</span></div>
<div class="line"><a name="l00548"></a><span class="lineno"> 548</span>  <span class="comment">// The point is outside the cutting space. See</span></div>
<div class="line"><a name="l00549"></a><span class="lineno"> 549</span>  <span class="comment">// if we can find a neighbor which isn't.</span></div>
<div class="line"><a name="l00570"></a><span class="lineno"> 570</span>  <span class="comment">// The point is in the plane, so we just</span></div>
<div class="line"><a name="l00571"></a><span class="lineno"> 571</span>  <span class="comment">// proceed with the complicated setup routine</span></div>
<div class="line"><a name="l00580"></a><span class="lineno"> 580</span>  <span class="comment">// We're about to add the first point of the new facet. In either</span></div>
<div class="line"><a name="l00581"></a><span class="lineno"> 581</span>  <span class="comment">// routine, we have to add a point, so first check there's space for</span></div>
<div class="line"><a name="l00587"></a><span class="lineno"> 587</span>  <span class="comment">// We want to be strict about reaching the conclusion that the</span></div>
<div class="line"><a name="l00588"></a><span class="lineno"> 588</span>  <span class="comment">// cell is entirely within the cutting plane. It's not enough</span></div>
<div class="line"><a name="l00589"></a><span class="lineno"> 589</span>  <span class="comment">// to find a vertex that has edges which are all inside or on</span></div>
<div class="line"><a name="l00590"></a><span class="lineno"> 590</span>  <span class="comment">// the plane. If the vertex has neighbors that are also on the</span></div>
<div class="line"><a name="l00591"></a><span class="lineno"> 591</span>  <span class="comment">// plane, we should check those too.</span></div>
<div class="line"><a name="l00594"></a><span class="lineno"> 594</span>  <span class="comment">// The search algorithm found a point which is on the cutting</span></div>
<div class="line"><a name="l00595"></a><span class="lineno"> 595</span>  <span class="comment">// plane. We leave that point in place, and create a new one at</span></div>
<div class="line"><a name="l00596"></a><span class="lineno"> 596</span>  <span class="comment">// the same location.</span></div>
<div class="line"><a name="l00601"></a><span class="lineno"> 601</span>  <span class="comment">// Search for a collection of edges of the test vertex which</span></div>
<div class="line"><a name="l00602"></a><span class="lineno"> 602</span>  <span class="comment">// are outside of the cutting space. Begin by testing the</span></div>
<div class="line"><a name="l00609"></a><span class="lineno"> 609</span>  <span class="comment">// The first edge is either inside the cutting space,</span></div>
<div class="line"><a name="l00610"></a><span class="lineno"> 610</span>  <span class="comment">// or lies within the cutting plane. Test the edges</span></div>
<div class="line"><a name="l00611"></a><span class="lineno"> 611</span>  <span class="comment">// sequentially until we find one that is outside.</span></div>
<div class="line"><a name="l00616"></a><span class="lineno"> 616</span>  <span class="comment">// If we reached the last edge with no luck</span></div>
<div class="line"><a name="l00617"></a><span class="lineno"> 617</span>  <span class="comment">// then all of the vertices are inside</span></div>
<div class="line"><a name="l00618"></a><span class="lineno"> 618</span>  <span class="comment">// or on the plane, so the cell is completely</span></div>
<div class="line"><a name="l00626"></a><span class="lineno"> 626</span>  <span class="comment">// We found an edge outside the cutting space. Keep</span></div>
<div class="line"><a name="l00627"></a><span class="lineno"> 627</span>  <span class="comment">// moving through these edges until we find one that's</span></div>
<div class="line"><a name="l00628"></a><span class="lineno"> 628</span>  <span class="comment">// inside or on the plane.</span></div>
<div class="line"><a name="l00636"></a><span class="lineno"> 636</span>  <span class="comment">// Compute the number of edges for the new vertex. In</span></div>
<div class="line"><a name="l00637"></a><span class="lineno"> 637</span>  <span class="comment">// general it will be the number of outside edges</span></div>
<div class="line"><a name="l00638"></a><span class="lineno"> 638</span>  <span class="comment">// found, plus two. But we need to recognize the</span></div>
<div class="line"><a name="l00639"></a><span class="lineno"> 639</span>  <span class="comment">// special case when all but one edge is outside, and</span></div>
<div class="line"><a name="l00640"></a><span class="lineno"> 640</span>  <span class="comment">// the remaining one is on the plane. For that case we</span></div>
<div class="line"><a name="l00641"></a><span class="lineno"> 641</span>  <span class="comment">// have to reduce the edge count by one to prevent</span></div>
<div class="line"><a name="l00649"></a><span class="lineno"> 649</span>  <span class="comment">// Add memory for the new vertex if needed, and</span></div>
<div class="line"><a name="l00657"></a><span class="lineno"> 657</span>  <span class="comment">// Copy the edges of the original vertex into the new</span></div>
<div class="line"><a name="l00658"></a><span class="lineno"> 658</span>  <span class="comment">// one. Delete the edges of the original vertex, and</span></div>
<div class="line"><a name="l00675"></a><span class="lineno"> 675</span>  <span class="comment">// In this case, the zeroth edge is outside the cutting</span></div>
<div class="line"><a name="l00676"></a><span class="lineno"> 676</span>  <span class="comment">// plane. Begin by searching backwards from the last</span></div>
<div class="line"><a name="l00677"></a><span class="lineno"> 677</span>  <span class="comment">// edge until we find an edge which isn't outside.</span></div>
<div class="line"><a name="l00684"></a><span class="lineno"> 684</span>  <span class="comment">// If i reaches zero, then we have a point in</span></div>
<div class="line"><a name="l00685"></a><span class="lineno"> 685</span>  <span class="comment">// the plane all of whose edges are outside</span></div>
<div class="line"><a name="l00686"></a><span class="lineno"> 686</span>  <span class="comment">// the cutting space, so we just exit</span></div>
<div class="line"><a name="l00702"></a><span class="lineno"> 702</span>  <span class="comment">// Compute the number of edges for the new vertex. In</span></div>
<div class="line"><a name="l00703"></a><span class="lineno"> 703</span>  <span class="comment">// general it will be the number of outside edges</span></div>
<div class="line"><a name="l00704"></a><span class="lineno"> 704</span>  <span class="comment">// found, plus two. But we need to recognize the</span></div>
<div class="line"><a name="l00705"></a><span class="lineno"> 705</span>  <span class="comment">// special case when all but one edge is outside, and</span></div>
<div class="line"><a name="l00706"></a><span class="lineno"> 706</span>  <span class="comment">// the remaining one is on the plane. For that case we</span></div>
<div class="line"><a name="l00707"></a><span class="lineno"> 707</span>  <span class="comment">// have to reduce the edge count by one to prevent</span></div>
<div class="line"><a name="l00716"></a><span class="lineno"> 716</span>  <span class="comment">// Add memory to store the vertex if it doesn't exist</span></div>
<div class="line"><a name="l00722"></a><span class="lineno"> 722</span>  <span class="comment">// Copy the edges of the original vertex into the new</span></div>
<div class="line"><a name="l00723"></a><span class="lineno"> 723</span>  <span class="comment">// one. Delete the edges of the original vertex, and</span></div>
<div class="line"><a name="l00759"></a><span class="lineno"> 759</span>  <span class="comment">// Add this point to the auxiliary delete stack</span></div>
<div class="line"><a name="l00763"></a><span class="lineno"> 763</span>  <span class="comment">// Look at the edges on either side of the group that was</span></div>
<div class="line"><a name="l00765"></a><span class="lineno"> 765</span>  <span class="comment">// moving along one of them. We are going to end up coming back</span></div>
<div class="line"><a name="l00766"></a><span class="lineno"> 766</span>  <span class="comment">// along the other one.</span></div>
<div class="line"><a name="l00776"></a><span class="lineno"> 776</span>  <span class="comment">// The search algorithm found an intersected edge between the</span></div>
<div class="line"><a name="l00777"></a><span class="lineno"> 777</span>  <span class="comment">// points lp and up. Create a new vertex between them which</span></div>
<div class="line"><a name="l00778"></a><span class="lineno"> 778</span>  <span class="comment">// lies on the cutting plane. Since u and l differ by at least</span></div>
<div class="line"><a name="l00779"></a><span class="lineno"> 779</span>  <span class="comment">// the tolerance, this division should never screw up.</span></div>
<div class="line"><a name="l00787"></a><span class="lineno"> 787</span>  <span class="comment">// This point will always have three edges. Connect one of them</span></div>
<div class="line"><a name="l00788"></a><span class="lineno"> 788</span>  <span class="comment">// to lp.</span></div>
<div class="line"><a name="l00809"></a><span class="lineno"> 809</span>  <span class="comment">// When the code reaches here, we have initialized the first point, and</span></div>
<div class="line"><a name="l00810"></a><span class="lineno"> 810</span>  <span class="comment">// we have a direction for moving it to construct the rest of the facet</span></div>
<div class="line"><a name="l00814"></a><span class="lineno"> 814</span>  <span class="comment">// We're currently tracing round an intersected facet. Keep</span></div>
<div class="line"><a name="l00815"></a><span class="lineno"> 815</span>  <span class="comment">// moving around it until we find a point or edge which</span></div>
<div class="line"><a name="l00816"></a><span class="lineno"> 816</span>  <span class="comment">// intersects the plane.</span></div>
<div class="line"><a name="l00822"></a><span class="lineno"> 822</span>  <span class="comment">// The point is still in the cutting space. Just add it</span></div>
<div class="line"><a name="l00823"></a><span class="lineno"> 823</span>  <span class="comment">// to the delete stack and keep moving.</span></div>
<div class="line"><a name="l00832"></a><span class="lineno"> 832</span>  <span class="comment">// The point is outside of the cutting space, so we've</span></div>
<div class="line"><a name="l00833"></a><span class="lineno"> 833</span>  <span class="comment">// found an intersected edge. Introduce a regular point</span></div>
<div class="line"><a name="l00834"></a><span class="lineno"> 834</span>  <span class="comment">// at the point of intersection. Connect it to the</span></div>
<div class="line"><a name="l00835"></a><span class="lineno"> 835</span>  <span class="comment">// point we just tested. Also connect it to the previous</span></div>
<div class="line"><a name="l00836"></a><span class="lineno"> 836</span>  <span class="comment">// new point in the facet we're constructing.</span></div>
<div class="line"><a name="l00865"></a><span class="lineno"> 865</span>  <span class="comment">// We've found a point which is on the cutting plane.</span></div>
<div class="line"><a name="l00866"></a><span class="lineno"> 866</span>  <span class="comment">// We're going to introduce a new point right here, but</span></div>
<div class="line"><a name="l00867"></a><span class="lineno"> 867</span>  <span class="comment">// first we need to figure out the number of edges it</span></div>
<div class="line"><a name="l00871"></a><span class="lineno"> 871</span>  <span class="comment">// If the previous vertex detected a double edge, our</span></div>
<div class="line"><a name="l00872"></a><span class="lineno"> 872</span>  <span class="comment">// new vertex will have one less edge.</span></div>
<div class="line"><a name="l00878"></a><span class="lineno"> 878</span>  <span class="comment">// Start testing the edges of the current point until</span></div>
<div class="line"><a name="l00879"></a><span class="lineno"> 879</span>  <span class="comment">// we find one which isn't outside the cutting space</span></div>
<div class="line"><a name="l00887"></a><span class="lineno"> 887</span>  <span class="comment">// Now we need to find out whether this marginal vertex</span></div>
<div class="line"><a name="l00888"></a><span class="lineno"> 888</span>  <span class="comment">// we are on has been visited before, because if that's</span></div>
<div class="line"><a name="l00889"></a><span class="lineno"> 889</span>  <span class="comment">// the case, we need to add vertices to the existing</span></div>
<div class="line"><a name="l00890"></a><span class="lineno"> 890</span>  <span class="comment">// new vertex, rather than creating a fresh one. We also</span></div>
<div class="line"><a name="l00891"></a><span class="lineno"> 891</span>  <span class="comment">// need to figure out whether we're in a case where we</span></div>
<div class="line"><a name="l00892"></a><span class="lineno"> 892</span>  <span class="comment">// might be creating a duplicate edge.</span></div>
<div class="line"><a name="l00896"></a><span class="lineno"> 896</span>  <span class="comment">// If we're heading into the final part of the</span></div>
<div class="line"><a name="l00897"></a><span class="lineno"> 897</span>  <span class="comment">// new facet, then we never worry about the</span></div>
<div class="line"><a name="l00904"></a><span class="lineno"> 904</span>  <span class="comment">// This vertex was visited before, so</span></div>
<div class="line"><a name="l00905"></a><span class="lineno"> 905</span>  <span class="comment">// count those vertices to the ones we</span></div>
<div class="line"><a name="l00909"></a><span class="lineno"> 909</span>  <span class="comment">// The only time when we might make a</span></div>
<div class="line"><a name="l00910"></a><span class="lineno"> 910</span>  <span class="comment">// duplicate edge is if the point we're</span></div>
<div class="line"><a name="l00911"></a><span class="lineno"> 911</span>  <span class="comment">// going to move to next is also a</span></div>
<div class="line"><a name="l00912"></a><span class="lineno"> 912</span>  <span class="comment">// marginal point, so test for that</span></div>
<div class="line"><a name="l00916"></a><span class="lineno"> 916</span>  <span class="comment">// Now see whether this marginal point</span></div>
<div class="line"><a name="l00917"></a><span class="lineno"> 917</span>  <span class="comment">// has been visited before.</span></div>
<div class="line"><a name="l00921"></a><span class="lineno"> 921</span>  <span class="comment">// Now see if the last edge of that other</span></div>
<div class="line"><a name="l00922"></a><span class="lineno"> 922</span>  <span class="comment">// marginal point actually ends up here.</span></div>
<div class="line"><a name="l00929"></a><span class="lineno"> 929</span>  <span class="comment">// That marginal point hasn't been visited</span></div>
<div class="line"><a name="l00930"></a><span class="lineno"> 930</span>  <span class="comment">// before, so we probably don't have to worry</span></div>
<div class="line"><a name="l00931"></a><span class="lineno"> 931</span>  <span class="comment">// about duplicate edges, except in the</span></div>
<div class="line"><a name="l00932"></a><span class="lineno"> 932</span>  <span class="comment">// case when that's the way into the end</span></div>
<div class="line"><a name="l00933"></a><span class="lineno"> 933</span>  <span class="comment">// of the facet, because that way always creates</span></div>
<div class="line"><a name="l00934"></a><span class="lineno"> 934</span>  <span class="comment">// an edge.</span></div>
<div class="line"><a name="l00943"></a><span class="lineno"> 943</span>  <span class="comment">// The vertex hasn't been visited</span></div>
<div class="line"><a name="l00944"></a><span class="lineno"> 944</span>  <span class="comment">// before, but let's see if it's</span></div>
<div class="line"><a name="l00962"></a><span class="lineno"> 962</span>  <span class="comment">// k now holds the number of edges of the new vertex</span></div>
<div class="line"><a name="l00963"></a><span class="lineno"> 963</span>  <span class="comment">// we are forming. Add memory for it if it doesn't exist</span></div>
<div class="line"><a name="l00968"></a><span class="lineno"> 968</span>  <span class="comment">// Now create a new vertex with order k, or augment</span></div>
<div class="line"><a name="l00969"></a><span class="lineno"> 969</span>  <span class="comment">// the existing one</span></div>
<div class="line"><a name="l00972"></a><span class="lineno"> 972</span>  <span class="comment">// If we're augmenting a vertex but we don't</span></div>
<div class="line"><a name="l00973"></a><span class="lineno"> 973</span>  <span class="comment">// actually need any more edges, just skip this</span></div>
<div class="line"><a name="l01019"></a><span class="lineno"> 1019</span>  <span class="comment">// Unless the previous case was a double edge, connect</span></div>
<div class="line"><a name="l01020"></a><span class="lineno"> 1020</span>  <span class="comment">// the first available edge of the new vertex to the</span></div>
<div class="line"><a name="l01021"></a><span class="lineno"> 1021</span>  <span class="comment">// last one in the facet</span></div>
<div class="line"><a name="l01031"></a><span class="lineno"> 1031</span>  <span class="comment">// Copy in the edges of the underlying vertex,</span></div>
<div class="line"><a name="l01032"></a><span class="lineno"> 1032</span>  <span class="comment">// and do one less if this was a double edge</span></div>
<div class="line"><a name="l01050"></a><span class="lineno"> 1050</span>  <span class="comment">// Update the double_edge flag, to pass it</span></div>
<div class="line"><a name="l01051"></a><span class="lineno"> 1051</span>  <span class="comment">// to the next instance of this routine</span></div>
<div class="line"><a name="l01056"></a><span class="lineno"> 1056</span>  <span class="comment">// Connect the final created vertex to the initial one</span></div>
<div class="line"><a name="l01072"></a><span class="lineno"> 1072</span>  <span class="comment">// Add the points in the auxiliary delete stack,</span></div>
<div class="line"><a name="l01073"></a><span class="lineno"> 1073</span>  <span class="comment">// and reset their back pointers</span></div>
<div class="line"><a name="l01102"></a><span class="lineno"> 1102</span>  <span class="comment">// Delete them from the array structure</span></div>
<div class="line"><a name="l01139"></a><span class="lineno"> 1139</span>  <span class="comment">// Check for any vertices of zero order</span></div>
<div class="line"><a name="l01142"></a><span class="lineno"> 1142</span>  <span class="comment">// Collapse any order 2 vertices and exit</span></div>
<div class="line"><a name="l01146"></a><span class="lineno"> 1146</span> <span class="comment">/** During the creation of a new facet in the plane routine, it is possible</span></div>
<div class="line"><a name="l01147"></a><span class="lineno"> 1147</span> <span class="comment"> * that some order two vertices may arise. This routine removes them.</span></div>
<div class="line"><a name="l01148"></a><span class="lineno"> 1148</span> <span class="comment"> * Suppose an order two vertex joins c and d. If there's a edge between</span></div>
<div class="line"><a name="l01149"></a><span class="lineno"> 1149</span> <span class="comment"> * c and d already, then the order two vertex is just removed; otherwise,</span></div>
<div class="line"><a name="l01150"></a><span class="lineno"> 1150</span> <span class="comment"> * the order two vertex is removed and c and d are joined together directly.</span></div>
<div class="line"><a name="l01151"></a><span class="lineno"> 1151</span> <span class="comment"> * It is possible this process will create order two or order one vertices,</span></div>
<div class="line"><a name="l01152"></a><span class="lineno"> 1152</span> <span class="comment"> * and the routine is continually run until all of them are removed.</span></div>
<div class="line"><a name="l01153"></a><span class="lineno"> 1153</span> <span class="comment"> * \return False if the vertex removal was unsuccessful, indicative of the cell</span></div>
<div class="line"><a name="l01154"></a><span class="lineno"> 1154</span> <span class="comment"> * reducing to zero volume and disappearing; true if the vertex removal</span></div>
<div class="line"><a name="l01155"></a><span class="lineno"> 1155</span> <span class="comment"> * was successful. */</span></div>
<div class="line"><a name="l01162"></a><span class="lineno"> 1162</span>  <span class="comment">// Pick a order 2 vertex and read in its edges</span></div>
<div class="line"><a name="l01172"></a><span class="lineno"> 1172</span>  <span class="comment">// Scan the edges of j to see if joins k</span></div>
<div class="line"><a name="l01177"></a><span class="lineno"> 1177</span>  <span class="comment">// If j doesn't already join k, join them together.</span></div>
<div class="line"><a name="l01178"></a><span class="lineno"> 1178</span>  <span class="comment">// Otherwise delete the connection to the current</span></div>
<div class="line"><a name="l01179"></a><span class="lineno"> 1179</span>  <span class="comment">// vertex from j and k.</span></div>
<div class="line"><a name="l01206"></a><span class="lineno"> 1206</span>  <span class="comment">// Collapse any order 1 vertices if they were created</span></div>
<div class="line"><a name="l01212"></a><span class="lineno"> 1212</span> <span class="comment">/** Order one vertices can potentially be created during the order two collapse</span></div>
<div class="line"><a name="l01213"></a><span class="lineno"> 1213</span> <span class="comment"> * routine. This routine keeps removing them until there are none left.</span></div>
<div class="line"><a name="l01214"></a><span class="lineno"> 1214</span> <span class="comment"> * \return False if the vertex removal was unsuccessful, indicative of the cell</span></div>
<div class="line"><a name="l01215"></a><span class="lineno"> 1215</span> <span class="comment"> * having zero volume and disappearing; true if the vertex removal was</span></div>
<div class="line"><a name="l01246"></a><span class="lineno"> 1246</span> <span class="comment">/** This routine deletes the kth edge of vertex j and reorganizes the memory.</span></div>
<div class="line"><a name="l01247"></a><span class="lineno"> 1247</span> <span class="comment"> * If the neighbor computation is enabled, we also have to supply an handedness</span></div>
<div class="line"><a name="l01248"></a><span class="lineno"> 1248</span> <span class="comment"> * flag to decide whether to preserve the plane on the left or right of the</span></div>
<div class="line"><a name="l01250"></a><span class="lineno"> 1250</span> <span class="comment"> * \return False if a zero order vertex was formed, indicative of the cell</span></div>
<div class="line"><a name="l01251"></a><span class="lineno"> 1251</span> <span class="comment"> * disappearing; true if the vertex removal was successful. */</span></div>
<div class="line"><a name="l01295"></a><span class="lineno"> 1295</span> <span class="comment">/** Calculates the volume of the Voronoi cell, by decomposing the cell into</span></div>
<div class="line"><a name="l01296"></a><span class="lineno"> 1296</span> <span class="comment"> * tetrahedra extending outward from the zeroth vertex, whose volumes are</span></div>
<div class="line"><a name="l01297"></a><span class="lineno"> 1297</span> <span class="comment"> * evaluated using a scalar triple product.</span></div>
<div class="line"><a name="l01298"></a><span class="lineno"> 1298</span> <span class="comment"> * \return A floating point number holding the calculated volume. */</span></div>
<div class="line"><a name="l01333"></a><span class="lineno"> 1333</span> <span class="comment">/** Calculates the areas of each face of the Voronoi cell and prints the</span></div>
<div class="line"><a name="l01334"></a><span class="lineno"> 1334</span> <span class="comment"> * results to an output stream.</span></div>
<div class="line"><a name="l01335"></a><span class="lineno"> 1335</span> <span class="comment"> * \param[out] v the vector to store the results in. */</span></div>
<div class="line"><a name="l01370"></a><span class="lineno"> 1370</span> <span class="comment">/** Calculates the total surface area of the Voronoi cell.</span></div>
<div class="line"><a name="l01404"></a><span class="lineno"> 1404</span> <span class="comment">/** Calculates the centroid of the Voronoi cell, by decomposing the cell into</span></div>
<div class="line"><a name="l01405"></a><span class="lineno"> 1405</span> <span class="comment"> * tetrahedra extending outward from the zeroth vertex.</span></div>
<div class="line"><a name="l01406"></a><span class="lineno"> 1406</span> <span class="comment"> * \param[out] (cx,cy,cz) references to floating point numbers in which to</span></div>
<div class="line"><a name="l01407"></a><span class="lineno"> 1407</span> <span class="comment"> * pass back the centroid vector. */</span></div>
<div class="line"><a name="l01450"></a><span class="lineno"> 1450</span> <span class="comment">/** Computes the maximum radius squared of a vertex from the center of the</span></div>
<div class="line"><a name="l01451"></a><span class="lineno"> 1451</span> <span class="comment"> * cell. It can be used to determine when enough particles have been testing an</span></div>
<div class="line"><a name="l01452"></a><span class="lineno"> 1452</span> <span class="comment"> * all planes that could cut the cell have been considered.</span></div>
<div class="line"><a name="l01453"></a><span class="lineno"> 1453</span> <span class="comment"> * \return The maximum radius squared of a vertex.*/</span></div>
<div class="line"><a name="l01466"></a><span class="lineno"> 1466</span> <span class="comment">/** Calculates the total edge distance of the Voronoi cell.</span></div>
<div class="line"><a name="l01467"></a><span class="lineno"> 1467</span> <span class="comment"> * \return A floating point number holding the calculated distance. */</span></div>
<div class="line"><a name="l01483"></a><span class="lineno"> 1483</span> <span class="comment">/** Outputs the edges of the Voronoi cell in POV-Ray format to an open file</span></div>
<div class="line"><a name="l01484"></a><span class="lineno"> 1484</span> <span class="comment"> * stream, displacing the cell by given vector.</span></div>
<div class="line"><a name="l01485"></a><span class="lineno"> 1485</span> <span class="comment"> * \param[in] (x,y,z) a displacement vector to be added to the cell's position.</span></div>
<div class="line"><a name="l01486"></a><span class="lineno"> 1486</span> <span class="comment"> * \param[in] fp a file handle to write to. */</span></div>
<div class="line"><a name="l01504"></a><span class="lineno"> 1504</span> <span class="comment">/** Outputs the edges of the Voronoi cell in gnuplot format to an output stream.</span></div>
<div class="line"><a name="l01505"></a><span class="lineno"> 1505</span> <span class="comment"> * \param[in] (x,y,z) a displacement vector to be added to the cell's position.</span></div>
<div class="line"><a name="l01506"></a><span class="lineno"> 1506</span> <span class="comment"> * \param[in] fp a file handle to write to. */</span></div>
<div class="line"><a name="l01534"></a><span class="lineno"> 1534</span> <span class="comment">/** Outputs the Voronoi cell in the POV mesh2 format, described in section</span></div>
<div class="line"><a name="l01535"></a><span class="lineno"> 1535</span> <span class="comment"> * 1.3.2.2 of the POV-Ray documentation. The mesh2 output consists of a list of</span></div>
<div class="line"><a name="l01536"></a><span class="lineno"> 1536</span> <span class="comment"> * vertex vectors, followed by a list of triangular faces. The routine also</span></div>
<div class="line"><a name="l01537"></a><span class="lineno"> 1537</span> <span class="comment"> * makes use of the optional inside_vector specification, which makes the mesh</span></div>
<div class="line"><a name="l01538"></a><span class="lineno"> 1538</span> <span class="comment"> * object solid, so the the POV-Ray Constructive Solid Geometry (CSG) can be</span></div>
<div class="line"><a name="l01540"></a><span class="lineno"> 1540</span> <span class="comment"> * \param[in] (x,y,z) a displacement vector to be added to the cell's position.</span></div>
<div class="line"><a name="l01541"></a><span class="lineno"> 1541</span> <span class="comment"> * \param[in] fp a file handle to write to. */</span></div>
<div class="line"><a name="l01566"></a><span class="lineno"> 1566</span> <span class="comment">/** Several routines in the class that gather cell-based statistics internally</span></div>
<div class="line"><a name="l01567"></a><span class="lineno"> 1567</span> <span class="comment"> * track their progress by flipping edges to negative so that they know what</span></div>
<div class="line"><a name="l01568"></a><span class="lineno"> 1568</span> <span class="comment"> * parts of the cell have already been tested. This function resets them back</span></div>
<div class="line"><a name="l01569"></a><span class="lineno"> 1569</span> <span class="comment"> * to positive. When it is called, it assumes that every edge in the routine</span></div>
<div class="line"><a name="l01570"></a><span class="lineno"> 1570</span> <span class="comment"> * should have already been flipped to negative, and it bails out with an</span></div>
<div class="line"><a name="l01571"></a><span class="lineno"> 1571</span> <span class="comment"> * internal error if it encounters a positive edge. */</span></div>
<div class="line"><a name="l01580"></a><span class="lineno"> 1580</span> <span class="comment">/** Checks to see if a given vertex is inside, outside or within the test</span></div>
<div class="line"><a name="l01581"></a><span class="lineno"> 1581</span> <span class="comment"> * plane. If the point is far away from the test plane, the routine immediately</span></div>
<div class="line"><a name="l01582"></a><span class="lineno"> 1582</span> <span class="comment"> * returns whether it is inside or outside. If the routine is close the the</span></div>
<div class="line"><a name="l01583"></a><span class="lineno"> 1583</span> <span class="comment"> * plane and within the specified tolerance, then the special check_marginal()</span></div>
<div class="line"><a name="l01584"></a><span class="lineno"> 1584</span> <span class="comment"> * routine is called.</span></div>
<div class="line"><a name="l01585"></a><span class="lineno"> 1585</span> <span class="comment"> * \param[in] n the vertex to test.</span></div>
<div class="line"><a name="l01586"></a><span class="lineno"> 1586</span> <span class="comment"> * \param[out] ans the result of the scalar product used in evaluating the</span></div>
<div class="line"><a name="l01587"></a><span class="lineno"> 1587</span> <span class="comment"> * location of the point.</span></div>
<div class="line"><a name="l01588"></a><span class="lineno"> 1588</span> <span class="comment"> * \return -1 if the point is inside the plane, 1 if the point is outside the</span></div>
<div class="line"><a name="l01589"></a><span class="lineno"> 1589</span> <span class="comment"> * plane, or 0 if the point is within the plane. */</span></div>
<div class="line"><a name="l01603"></a><span class="lineno"> 1603</span> <span class="comment">/** Checks to see if a given vertex is inside, outside or within the test</span></div>
<div class="line"><a name="l01604"></a><span class="lineno"> 1604</span> <span class="comment"> * plane, for the case when the point has been detected to be very close to the</span></div>
<div class="line"><a name="l01605"></a><span class="lineno"> 1605</span> <span class="comment"> * plane. The routine ensures that the returned results are always consistent</span></div>
<div class="line"><a name="l01606"></a><span class="lineno"> 1606</span> <span class="comment"> * with previous tests, by keeping a table of any marginal results. The routine</span></div>
<div class="line"><a name="l01607"></a><span class="lineno"> 1607</span> <span class="comment"> * first sees if the vertex is in the table, and if it finds a previously</span></div>
<div class="line"><a name="l01608"></a><span class="lineno"> 1608</span> <span class="comment"> * computed result it uses that. Otherwise, it computes a result for this</span></div>
<div class="line"><a name="l01609"></a><span class="lineno"> 1609</span> <span class="comment"> * vertex and adds it the table.</span></div>
<div class="line"><a name="l01610"></a><span class="lineno"> 1610</span> <span class="comment"> * \param[in] n the vertex to test.</span></div>
<div class="line"><a name="l01611"></a><span class="lineno"> 1611</span> <span class="comment"> * \param[in] ans the result of the scalar product used in evaluating</span></div>
<div class="line"><a name="l01612"></a><span class="lineno"> 1612</span> <span class="comment"> * the location of the point.</span></div>
<div class="line"><a name="l01613"></a><span class="lineno"> 1613</span> <span class="comment"> * \return -1 if the point is inside the plane, 1 if the point is outside the</span></div>
<div class="line"><a name="l01614"></a><span class="lineno"> 1614</span> <span class="comment"> * plane, or 0 if the point is within the plane. */</span></div>
<div class="line"><a name="l01635"></a><span class="lineno"> 1635</span> <span class="comment">/** For each face of the Voronoi cell, this routine prints the out the normal</span></div>
<div class="line"><a name="l01636"></a><span class="lineno"> 1636</span> <span class="comment"> * vector of the face, and scales it to the distance from the cell center to</span></div>
<div class="line"><a name="l01637"></a><span class="lineno"> 1637</span> <span class="comment"> * that plane.</span></div>
<div class="line"><a name="l01638"></a><span class="lineno"> 1638</span> <span class="comment"> * \param[out] v the vector to store the results in. */</span></div>
<div class="line"><a name="l01649"></a><span class="lineno"> 1649</span> <span class="comment">/** This inline routine is called by normals(). It attempts to construct a</span></div>
<div class="line"><a name="l01650"></a><span class="lineno"> 1650</span> <span class="comment"> * single normal vector that is associated with a particular face. It first</span></div>
<div class="line"><a name="l01651"></a><span class="lineno"> 1651</span> <span class="comment"> * traces around the face, trying to find two vectors along the face edges</span></div>
<div class="line"><a name="l01652"></a><span class="lineno"> 1652</span> <span class="comment"> * whose vector product is above the numerical tolerance. It then constructs</span></div>
<div class="line"><a name="l01653"></a><span class="lineno"> 1653</span> <span class="comment"> * the normal vector using this product. If the face is too small, and none of</span></div>
<div class="line"><a name="l01654"></a><span class="lineno"> 1654</span> <span class="comment"> * the vector products are large enough, the routine may return (0,0,0) as the</span></div>
<div class="line"><a name="l01655"></a><span class="lineno"> 1655</span> <span class="comment"> * normal vector.</span></div>
<div class="line"><a name="l01656"></a><span class="lineno"> 1656</span> <span class="comment"> * \param[in] v the vector to store the results in.</span></div>
<div class="line"><a name="l01657"></a><span class="lineno"> 1657</span> <span class="comment"> * \param[in] i the initial vertex of the face to test.</span></div>
<div class="line"><a name="l01658"></a><span class="lineno"> 1658</span> <span class="comment"> * \param[in] j the index of an edge of the vertex.</span></div>
<div class="line"><a name="l01659"></a><span class="lineno"> 1659</span> <span class="comment"> * \param[in] k the neighboring vertex of i, set to ed[i][j]. */</span></div>
<div class="line"><a name="l01670"></a><span class="lineno"> 1670</span>  <span class="comment">// Test to see if the length of this edge is above the tolerance</span></div>
<div class="line"><a name="l01679"></a><span class="lineno"> 1679</span>  <span class="comment">// Construct the vector product of this edge with</span></div>
<div class="line"><a name="l01680"></a><span class="lineno"> 1680</span>  <span class="comment">// the previous one</span></div>
<div class="line"><a name="l01686"></a><span class="lineno"> 1686</span>  <span class="comment">// Test to see if this vector product of the</span></div>
<div class="line"><a name="l01687"></a><span class="lineno"> 1687</span>  <span class="comment">// two edges is above the tolerance</span></div>
<div class="line"><a name="l01690"></a><span class="lineno"> 1690</span>  <span class="comment">// Construct the normal vector and print it</span></div>
<div class="line"><a name="l01696"></a><span class="lineno"> 1696</span>  <span class="comment">// Mark all of the remaining edges of this</span></div>
<div class="line"><a name="l01697"></a><span class="lineno"> 1697</span>  <span class="comment">// face and exit</span></div>
<div class="line"><a name="l01719"></a><span class="lineno"> 1719</span> <span class="comment">/** Returns the number of faces of a computed Voronoi cell.</span></div>
<div class="line"><a name="l01720"></a><span class="lineno"> 1720</span> <span class="comment"> * \return The number of faces. */</span></div>
<div class="line"><a name="l01742"></a><span class="lineno"> 1742</span> <span class="comment">/** Returns a vector of the vertex orders.</span></div>
<div class="line"><a name="l01743"></a><span class="lineno"> 1743</span> <span class="comment"> * \param[out] v the vector to store the results in. */</span></div>
<div class="line"><a name="l01758"></a><span class="lineno"> 1758</span> <span class="comment">/** Returns a vector of the vertex vectors using the local coordinate system.</span></div>
<div class="line"><a name="l01759"></a><span class="lineno"> 1759</span> <span class="comment"> * \param[out] v the vector to store the results in. */</span></div>
<div class="line"><a name="l01770"></a><span class="lineno"> 1770</span> <span class="comment">/** Outputs the vertex vectors using the local coordinate system.</span></div>
<div class="line"><a name="l01771"></a><span class="lineno"> 1771</span> <span class="comment"> * \param[out] fp the file handle to write to. */</span></div>
<div class="line"><a name="l01780"></a><span class="lineno"> 1780</span> <span class="comment">/** Returns a vector of the vertex vectors in the global coordinate system.</span></div>
<div class="line"><a name="l01781"></a><span class="lineno"> 1781</span> <span class="comment"> * \param[out] v the vector to store the results in.</span></div>
<div class="line"><a name="l01782"></a><span class="lineno"> 1782</span> <span class="comment"> * \param[in] (x,y,z) the position vector of the particle in the global</span></div>
<div class="line"><a name="l01794"></a><span class="lineno"> 1794</span> <span class="comment">/** Outputs the vertex vectors using the global coordinate system.</span></div>
<div class="line"><a name="l01795"></a><span class="lineno"> 1795</span> <span class="comment"> * \param[out] fp the file handle to write to.</span></div>
<div class="line"><a name="l01796"></a><span class="lineno"> 1796</span> <span class="comment"> * \param[in] (x,y,z) the position vector of the particle in the global</span></div>
<div class="line"><a name="l01805"></a><span class="lineno"> 1805</span> <span class="comment">/** This routine returns the perimeters of each face.</span></div>
<div class="line"><a name="l01806"></a><span class="lineno"> 1806</span> <span class="comment"> * \param[out] v the vector to store the results in. */</span></div>
<div class="line"><a name="l01836"></a><span class="lineno"> 1836</span> <span class="comment">/** For each face, this routine outputs a bracketed sequence of numbers</span></div>
<div class="line"><a name="l01837"></a><span class="lineno"> 1837</span> <span class="comment"> * containing a list of all the vertices that make up that face.</span></div>
<div class="line"><a name="l01838"></a><span class="lineno"> 1838</span> <span class="comment"> * \param[out] v the vector to store the results in. */</span></div>
<div class="line"><a name="l01864"></a><span class="lineno"> 1864</span> <span class="comment">/** Outputs a list of the number of edges in each face.</span></div>
<div class="line"><a name="l01865"></a><span class="lineno"> 1865</span> <span class="comment"> * \param[out] v the vector to store the results in. */</span></div>
<div class="line"><a name="l01888"></a><span class="lineno"> 1888</span> <span class="comment">/** Computes the number of edges that each face has and outputs a frequency</span></div>
<div class="line"><a name="l01889"></a><span class="lineno"> 1889</span> <span class="comment"> * table of the results.</span></div>
<div class="line"><a name="l01890"></a><span class="lineno"> 1890</span> <span class="comment"> * \param[out] v the vector to store the results in. */</span></div>
<div class="line"><a name="l01914"></a><span class="lineno"> 1914</span> <span class="comment">/** This routine tests to see whether the cell intersects a plane by starting</span></div>
<div class="line"><a name="l01915"></a><span class="lineno"> 1915</span> <span class="comment"> * from the guess point up. If up intersects, then it immediately returns true.</span></div>
<div class="line"><a name="l01916"></a><span class="lineno"> 1916</span> <span class="comment"> * Otherwise, it calls the plane_intersects_track() routine.</span></div>
<div class="line"><a name="l01917"></a><span class="lineno"> 1917</span> <span class="comment"> * \param[in] (x,y,z) the normal vector to the plane.</span></div>
<div class="line"><a name="l01918"></a><span class="lineno"> 1918</span> <span class="comment"> * \param[in] rsq the distance along this vector of the plane.</span></div>
<div class="line"><a name="l01919"></a><span class="lineno"> 1919</span> <span class="comment"> * \return False if the plane does not intersect the plane, true if it does. */</span></div>
<div class="line"><a name="l01926"></a><span class="lineno"> 1926</span> <span class="comment">/** This routine tests to see if a cell intersects a plane. It first tests a</span></div>
<div class="line"><a name="l01927"></a><span class="lineno"> 1927</span> <span class="comment"> * random sample of approximately sqrt(p)/4 points. If any of those are</span></div>
<div class="line"><a name="l01928"></a><span class="lineno"> 1928</span> <span class="comment"> * intersect, then it immediately returns true. Otherwise, it takes the closest</span></div>
<div class="line"><a name="l01929"></a><span class="lineno"> 1929</span> <span class="comment"> * point and passes that to plane_intersect_track() routine.</span></div>
<div class="line"><a name="l01930"></a><span class="lineno"> 1930</span> <span class="comment"> * \param[in] (x,y,z) the normal vector to the plane.</span></div>
<div class="line"><a name="l01931"></a><span class="lineno"> 1931</span> <span class="comment"> * \param[in] rsq the distance along this vector of the plane.</span></div>
<div class="line"><a name="l01932"></a><span class="lineno"> 1932</span> <span class="comment"> * \return False if the plane does not intersect the plane, true if it does. */</span></div>
<div class="line"><a name="l01952"></a><span class="lineno"> 1952</span> <span class="comment">/* This routine tests to see if a cell intersects a plane, by tracing over the cell from</span></div>
<div class="line"><a name="l01953"></a><span class="lineno"> 1953</span> <span class="comment"> * vertex to vertex, starting at up. It is meant to be called either by plane_intersects()</span></div>
<div class="line"><a name="l01954"></a><span class="lineno"> 1954</span> <span class="comment"> * or plane_intersects_track(), when those routines cannot immediately resolve the case.</span></div>
<div class="line"><a name="l01955"></a><span class="lineno"> 1955</span> <span class="comment"> * \param[in] (x,y,z) the normal vector to the plane.</span></div>
<div class="line"><a name="l01956"></a><span class="lineno"> 1956</span> <span class="comment"> * \param[in] rsq the distance along this vector of the plane.</span></div>
<div class="line"><a name="l01957"></a><span class="lineno"> 1957</span> <span class="comment"> * \param[in] g the distance of up from the plane.</span></div>
<div class="line"><a name="l01958"></a><span class="lineno"> 1958</span> <span class="comment"> * \return False if the plane does not intersect the plane, true if it does. */</span></div>
<div class="line"><a name="l01963"></a><span class="lineno"> 1963</span>  <span class="comment">// The test point is outside of the cutting space</span></div>
<div class="line"><a name="l01979"></a><span class="lineno"> 1979</span>  <span class="comment">// Test all the neighbors of the current point</span></div>
<div class="line"><a name="l01980"></a><span class="lineno"> 1980</span>  <span class="comment">// and find the one which is closest to the</span></div>
<div class="line"><a name="l02005"></a><span class="lineno"> 2005</span> <span class="comment">/** Counts the number of edges of the Voronoi cell.</span></div>
<div class="line"><a name="l02006"></a><span class="lineno"> 2006</span> <span class="comment"> * \return the number of edges. */</span></div>
<div class="line"><a name="l02013"></a><span class="lineno"> 2013</span> <span class="comment">/** Outputs a custom string of information about the Voronoi cell. The string</span></div>
<div class="line"><a name="l02014"></a><span class="lineno"> 2014</span> <span class="comment"> * of information follows a similar style as the C printf command, and detailed</span></div>
<div class="line"><a name="l02015"></a><span class="lineno"> 2015</span> <span class="comment"> * information about its format is available at</span></div>
<div class="line"><a name="l02017"></a><span class="lineno"> 2017</span> <span class="comment"> * \param[in] format the custom string to print.</span></div>
<div class="line"><a name="l02018"></a><span class="lineno"> 2018</span> <span class="comment"> * \param[in] i the ID of the particle associated with this Voronoi cell.</span></div>
<div class="line"><a name="l02019"></a><span class="lineno"> 2019</span> <span class="comment"> * \param[in] (x,y,z) the position of the particle associated with this Voronoi</span></div>
<div class="line"><a name="l02021"></a><span class="lineno"> 2021</span> <span class="comment"> * \param[in] r a radius associated with the particle.</span></div>
<div class="line"><a name="l02022"></a><span class="lineno"> 2022</span> <span class="comment"> * \param[in] fp the file handle to write to. */</span></div>
<div class="line"><a name="l02098"></a><span class="lineno"> 2098</span> <span class="comment">/** This initializes the class to be a rectangular box. It calls the base class</span></div>
<div class="line"><a name="l02099"></a><span class="lineno"> 2099</span> <span class="comment"> * initialization routine to set up the edge and vertex information, and then</span></div>
<div class="line"><a name="l02100"></a><span class="lineno"> 2100</span> <span class="comment"> * sets up the neighbor information, with initial faces being assigned ID</span></div>
<div class="line"><a name="l02101"></a><span class="lineno"> 2101</span> <span class="comment"> * numbers from -1 to -6.</span></div>
<div class="line"><a name="l02102"></a><span class="lineno"> 2102</span> <span class="comment"> * \param[in] (xmin,xmax) the minimum and maximum x coordinates.</span></div>
<div class="line"><a name="l02103"></a><span class="lineno"> 2103</span> <span class="comment"> * \param[in] (ymin,ymax) the minimum and maximum y coordinates.</span></div>
<div class="line"><a name="l02104"></a><span class="lineno"> 2104</span> <span class="comment"> * \param[in] (zmin,zmax) the minimum and maximum z coordinates. */</span></div>
<div class="line"><a name="l02120"></a><span class="lineno"> 2120</span> <span class="comment">/** This initializes the class to be an octahedron. It calls the base class</span></div>
<div class="line"><a name="l02121"></a><span class="lineno"> 2121</span> <span class="comment"> * initialization routine to set up the edge and vertex information, and then</span></div>
<div class="line"><a name="l02122"></a><span class="lineno"> 2122</span> <span class="comment"> * sets up the neighbor information, with the initial faces being assigned ID</span></div>
<div class="line"><a name="l02123"></a><span class="lineno"> 2123</span> <span class="comment"> * numbers from -1 to -8.</span></div>
<div class="line"><a name="l02124"></a><span class="lineno"> 2124</span> <span class="comment"> * \param[in] l The distance from the octahedron center to a vertex. Six</span></div>
<div class="line"><a name="l02125"></a><span class="lineno"> 2125</span> <span class="comment"> * vertices are initialized at (-l,0,0), (l,0,0), (0,-l,0),</span></div>
<div class="line"><a name="l02139"></a><span class="lineno"> 2139</span> <span class="comment">/** This initializes the class to be a tetrahedron. It calls the base class</span></div>
<div class="line"><a name="l02140"></a><span class="lineno"> 2140</span> <span class="comment"> * initialization routine to set up the edge and vertex information, and then</span></div>
<div class="line"><a name="l02141"></a><span class="lineno"> 2141</span> <span class="comment"> * sets up the neighbor information, with the initial faces being assigned ID</span></div>
<div class="line"><a name="l02142"></a><span class="lineno"> 2142</span> <span class="comment"> * numbers from -1 to -4.</span></div>
<div class="line"><a name="l02143"></a><span class="lineno"> 2143</span> <span class="comment"> * \param (x0,y0,z0) a position vector for the first vertex.</span></div>
<div class="line"><a name="l02144"></a><span class="lineno"> 2144</span> <span class="comment"> * \param (x1,y1,z1) a position vector for the second vertex.</span></div>
<div class="line"><a name="l02145"></a><span class="lineno"> 2145</span> <span class="comment"> * \param (x2,y2,z2) a position vector for the third vertex.</span></div>
<div class="line"><a name="l02146"></a><span class="lineno"> 2146</span> <span class="comment"> * \param (x3,y3,z3) a position vector for the fourth vertex. */</span></div>
<div class="line"><a name="l02157"></a><span class="lineno"> 2157</span> <span class="comment">/** This routine checks to make sure the neighbor information of each face is</span></div>
<div class="line"><a name="l02189"></a><span class="lineno"> 2189</span> <span class="comment">/** The class destructor frees the dynamically allocated memory for storing</span></div>
<div class="line"><a name="l02197"></a><span class="lineno"> 2197</span> <span class="comment">/** Computes a vector list of neighbors. */</span></div>
<div class="line"><a name="l02218"></a><span class="lineno"> 2218</span> <span class="comment">/** Prints the vertices, their edges, the relation table, and also notifies if</span></div>
<div class="line"><a name="l02219"></a><span class="lineno"> 2219</span> <span class="comment"> * any memory errors are visible. */</span></div>
<div class="line"><a name="l02236"></a><span class="lineno"> 2236</span> <span class="comment">/** This prints out the neighbor information for vertex i. */</span></div>
<div class="line"><a name="l02247"></a><span class="lineno"> 2247</span> <span class="keyword">template</span> <span class="keywordtype">bool</span> <a class="code" href="classvoro_1_1voronoicell__base.html#a33184cd45a3090291a080c4aff08a2fd">voronoicell_base::nplane</a>(<a class="code" href="classvoro_1_1voronoicell.html" title="Extension of the voronoicell_base class to represent a Voronoi cell without neighbor information...">voronoicell</a>&,<span class="keywordtype">double</span>,<span class="keywordtype">double</span>,<span class="keywordtype">double</span>,<span class="keywordtype">double</span>,<span class="keywordtype">int</span>);</div>
<div class="line"><a name="l02248"></a><span class="lineno"> 2248</span> <span class="keyword">template</span> <span class="keywordtype">bool</span> <a class="code" href="classvoro_1_1voronoicell__base.html#a33184cd45a3090291a080c4aff08a2fd">voronoicell_base::nplane</a>(<a class="code" href="classvoro_1_1voronoicell__neighbor.html" title="Extension of the voronoicell_base class to represent a Voronoi cell with neighbor information...">voronoicell_neighbor</a>&,<span class="keywordtype">double</span>,<span class="keywordtype">double</span>,<span class="keywordtype">double</span>,<span class="keywordtype">double</span>,<span class="keywordtype">int</span>);</div>
<div class="line"><a name="l02249"></a><span class="lineno"> 2249</span> <span class="keyword">template</span> <span class="keywordtype">void</span> <a class="code" href="classvoro_1_1voronoicell__base.html#af2c9d916f946ba8d9c7e4c0a7e65215b">voronoicell_base::check_memory_for_copy</a>(<a class="code" href="classvoro_1_1voronoicell.html" title="Extension of the voronoicell_base class to represent a Voronoi cell without neighbor information...">voronoicell</a>&,<a class="code" href="classvoro_1_1voronoicell__base.html" title="A class representing a single Voronoi cell.">voronoicell_base</a>*);</div>
<div class="line"><a name="l02250"></a><span class="lineno"> 2250</span> <span class="keyword">template</span> <span class="keywordtype">void</span> <a class="code" href="classvoro_1_1voronoicell__base.html#af2c9d916f946ba8d9c7e4c0a7e65215b">voronoicell_base::check_memory_for_copy</a>(<a class="code" href="classvoro_1_1voronoicell__neighbor.html" title="Extension of the voronoicell_base class to represent a Voronoi cell with neighbor information...">voronoicell_neighbor</a>&,<a class="code" href="classvoro_1_1voronoicell__base.html" title="A class representing a single Voronoi cell.">voronoicell_base</a>*);</div>