Voronoi Diagram Algorithm

Delaunay Triangulation Algorithm

 

VD

Input:

 

A set S of n sites, assume that there are at least 2 sites in the input set S.

 

Sweep Line Status:

 

The algorithm maintains the current set of sites that define the beach line in the HE data structure. Note that the parabolic arcs of the beach line exist solely for conceptual purposes.

 

Events:

 

There are two types of events in PQ data structure.

Site events:

When the sweep line passes over a new site a new arc will be inserted into the beach line.

Vertex events:

When the length of a parabolic arc shrinks to zero, the arc disappears and a new Voronoi vertex will be created at this point.

 

Algorithms:

 

DrawVor (S)

{

Sort the set S of n points;

Get a single in-storage site as the bottom site;

Get a new site;

 

While (true)

{

Get the lowest vector intersection from PQ;

If the new site has a smaller y value than the lowest vector intersection,

{

// Site event;

// Process the site;

 

Get the first HE to the left of the new site;

Get the first HE to the right of the new site;

Create a new HE caused by the new site;

Insert this new HE between the left and right HE;

If the new HE intersects with the left HE;

{

Remove the left HE’s vertex from PQ;

Put in PQ the new intersection;

}

Get a new site;

}

Else,

{

// Vector event;

// Process the vector intersection;

 

Pop off the HE with the lowest vector;

Get the HE to the left of the above HE;

Get the HE to the right of the above HE;

Get the HE to the right of the HE to the right of the lowest HE;

 

Get the vertex that caused this event;

Set the endpoint of the left HE to be this vector;

Set the endpoint of the right HE to be this vector;

Delete the left HE;

Remove all vertex events to do with the right HE from PQ;

Delete the right HE;

 

Create a HE and insert to the right of the left HE;

 

If left HE and the new HE intersect,

{

Remove the left HE’s vertex from PQ;

Put in PQ the new intersection;

}

If right HE and the new HE intersect,

{

Put in PQ the new intersection;

}

}

}

}

 

Output:

 

Voronoi Diagram.

 

 


DT

Input:

 

A set S of n sites, assume that there are at least 4 sites in the input set S.

 

Algorithms:

 

Start (S)

{

Read in coordinates x and y of n sites and compute z = x2 + y2;

 

// Construct the entire 3D hull H;

ConstructHull();

 

// Loop over all faces and identify which are on the lower hull.

LowerFaces();

}

 

ConstructHull(S)

{

Create the initial polytope with the first 4 sites.

For each site of the rest sites,

{

//Add the site in the polytope;

Addone(s);

 

// Delete superfluous parts of the data structure and prepares for the next iteration;

Cleanup(s);

}

}

 

Addone(s)

{

Determine which faces of the previously constructed hull are “visible” to s;

If no face is visible from s,

{

       // s lie inside the hull H;

       Mark s for deletion;

}

 

// Add a cone of faces to s;

// The portion of the polytope visible from s forms a connected region on the surface;

For each edge of H,

{

If the edge has two adjacent faces both visible,

{

// It is interior to the visible region;

Delete it;

              }

              If the edge has just one adjacent visible face,

              {

                     // It is on the border of the visible region;

                     Add a new face take the edge as the base and s as apex;

}

}

}

 

LowerFaces(S)

{

       For each face,

       {

              If the z coordinate of a vector normal to the face is negative,

              {

                     Mark the face as a lower face;

              }

              Else

              {

                     Remove the face from the face list;

}

       }

}

 

Output:

 

Delaunay Triangulation.

 


Back to the Applet Page

Acknowledgement
How to use this Applet