ÿþ<html> <head><title> Furthest Point Voronoi Diagrams: Algorithms </title> </head> <body vlink="#FF0000"> <h2><center>How are they Calculated?</center></h2> <p>Here you will find the algorithms used to calculate the convex hull and furthest point Voronoi diagram. I have included a copy of the original algorithm, before the version utilised in the program with comments on the changes. <p> <h3><a name = "convex">The Convex Hull</a></h3> </p> <p> The convex hull is calculated with a gift-wrapping algorithm, called the Jarvis March. <br>Designed in 1973 by R.A. Jarvis this is an O(nk) algorithm, where <i>n</i> is the total number of points and <i>k</i> is the number of points in the convex hull. <br>In the worst case, where all the points are located on the convex hull this has <i>n²</i> efficiency. However the best scenario approaches O(n), where there is a large number of points with only a few in the convex hull. </p> <p> <h4>The Algorithm</h4> Input: Set of Points = <i>P</i> <br>Output: Set of Points = <i>H</i> <ul><li>Locate the lowest Point <i>a</i> in <i>P</i> <li>If (>1 Points at the same height) <ul><li>Select the Point furthest left. </ul> <li>Set <i>start</i> := <i>a</i> <li>While (true) <ul><li>Add <i>a</i> to <i>H</i> <li>Locate <i>b</i> where all remaining Points lie right of <i>ab</i> <li>If (<i>b</i> = <i>start</i>) <ul><li>End While </ul> <li>Set <i>a</i> := <i>b</i> </ul> </ul> </p> <p> <h4>Comments</h4> This algorithm was unchanged in its implementation. In testing that all points lie to the right of <i>ab</i> I used the following equation; </p> <center><i>Signet Area = a<font size = -2>x</font>(b<font size = -2>y</font> - c<font size = -2>y</font>) + b<font size = -2>x</font>(c<font size = -2>y</font> - a<font size = -2>y</font>) + c<font size = -2>x</font>(a<font size = -2>y</font> - b<font size = -2>y</font>) </i></center> <p> This equation can be used to test the orientation of the triangle plotted by the 3 points. </p> <p> <center> <table border = "1"> <tr><td><img src="images/+triangle.gif" width="286" height="171" alt = "Positive triangle"></td><td><img src="images/-triangle.gif" width="286" height="171" alt = "Negative triangle"></td></tr> </table> </center> </p> <p> As demonstrated in the diagrams above, a positive value for the <i>Signet Area</i> indicates that <i>c</i> is further left than <i>b</i>. </p> <hr size=1> <p> <h3><a name = "furthestVoronoi">The Furthest Point Voronoi Diagram</a></h3> </p> <p> This algorithm was actually designed to calculate the smallest enclosing circle for a set of points. Thus the applet also incorporates an option to display the smallest circle. It was designed in 1990 by S. Skyum, taking the convex hull of a set of points as its input and performs to an efficiency of <i>n log(n)</i>. </p> <p> <h4>The Algorithm</h4> Input: Convex Hull (<i>P</i>) = <i>H</i> <br>Output: Furthest Point Voronoi Diagram <ul><li>if (|<i>H</i>| `" 1) <ul><li> <i>finish</i> := false </ul> <li>While (<i>finish</i> = false) <ul><li>Find the largest circle that passes through 3 consecutive Points in <i>H</i> <li>If (angle(<i>Point 1</i>, <i>Point 2</i>, <i>Point 3</i>) <= À/2) <ul><li><i>finish</i> := true </ul> <li>Else <ul><li>Remove Point 2 </ul> </ul> </ul> </p> <p> <h4>The Implemented Algorithm</h4> Input: Convex Hull (<i>P</i>) = <i>H</i> <br>Output: Furthest Point Voronoi Diagram <ul><li>Calculate the boundary for the plane. <li>While (|<i>H</i>| >= 3) <ul><li>Find the <i>centre</i> of largest circle that passes through 3 consecutive Points in <i>H</i> <li>If (<i>centre</i> is within plane boundary) <ul><li>Create vertex <i>v</i> at the centre of the circle <li>Calculate line associated to <i>Point 1</i> and <i>Point 2</i> <li>Calculate line associated to <i>Point 3</i> and <i>Point 2</i> <li>If (<i>H</i> contains only 3 Points) <ul><li>Calculate line associated to <i>Point 1</i> and <i>Point 3</i> <li>End While </ul> </ul> <li>Remove <i>Point 2</i>. </ul> <li>If (|<i>H</i>| = 2) <ul><li>Create vertex <i>v</i> in the middle of the two Points <li>Calculate line from <i>v</i> to boundary <li>Calculate line from <i>v</i> to opposite boundary </ul> </ul> </p> <p> <h4>Comments</h4> As can be seen, the first change introduced involves finding the boundary of the plane and this is simply the size of the applet window. Since we need only be concerned with what the user can see, anything which exists outside of the boundary can be ignored and the lines can be considered as reaching infinity. </p> <p> <center> <table border = "1"> <tr><td><img src="images/boundary01.gif" width="231" height="246" alt = "Boundary"></td> <td><img src="images/boundary02.gif" width="231" height="246" alt = "Boundary"></td> <td><img src="images/boundary03.gif" width="231" height="246" alt = "Boundary"></td></tr> </table> </center> </p> <p>The remaining changes are due to the focus on the furthest Voronoi diagram as opposed to the smallest circle. </p> <hr size=5> <p><a href="main.html">Introduction</a></p> <p><a href="voronoi.html">What are Voronoi diagrams?</a></p> <p><a href="algorithm.html">How the Diagrams are Calculated</a></p> <p><a href="applet.html">The Demonstration Applet</a></p> <p><a href="links.html">Other Sites on Computational Geometry</a></p> <p><a href = "author.html">About the Author</a></p> <hr size=5> </font> </body> </html>