## Expanding Wave-method

 Hide textShow text Hide pseudo-codeShow pseudo-code Find the Delaunay triangulation for the given point set using the Expanding Wave method. The required auxiliary points have been created around the point set and the first point to be handled has been put into the queue. ```1. Let Q be a queue 2. Initialize the helper vertices into a rectangle around the input vertices 3. Insert lower left help vertex to Q 4. While Q is not empty 5. Let A be the anchor vertex and N the neighbour vertex 6. dequeue a vertex from Q and set it to A 7. Find a known neighbour of A and set it to N 8. if N has not been queueud, queue N 9. while A has more possible neighbours 10. Let N1 be the next neighbour vertex 11. make connections (A,N1), (N,N1) 12. set value of N to N1 13. if N has not been queued, queue N ``` ```1. Return the connected neighbour vertex from which the clockwise angle before encountering another connected neighbour of A is the largest. ``` ```0. Let A be the anchor vertex and N the current neighbour and let R be half the distance between A and N and let T be the number of iterations, initially 1 1. while R*T is smaller than maximum distance between border vertices 2. Draw a circle clockwise from the A-N line segment with the radius R that has A and N on its circumference 3. Set all points clockwise from the A-N line segment that are inside the circle as neighbour candidates 4. if the set of possible neighbour candidates is not empty 5. select the candidate C for which angle A-C-N is the largest and return it 6. if several candidates create the same angle, select the one closest to A and return it 7. otherwise increase T to T+1 8. if the while loop exits without finding candidate vertex, report that no candidates were found ```