Find the missing edges of a voronoi map inside a square

I'm not entirely sure I understood your question correctly,
but to me it sounds like you want a ,,bounded voronoi diagram''.
Or, put differently, you want the intersection of the vornoi diagram
and a rectangle.

If that's what you want, I'll gladly tell how I've done it in one
of my projects.

Yes that is exactly what I want.

I have a solution created using a rather naive approach:

I traverse all the Voronoi sites and add all connected edges to a polygon created for that site.

Some of the polygons (the ones with two points at the edges/bounding box) will have gaps on them so I traverse all polygons and fill out the gaps as well.

I count and save the edge points - it the number of edge points on the same edge is 2 i connect those edge points.

That leaves the corners, so I use a different algorhitm that detects if the edge points are on different edges, and if they are I add a corner point and create two new edges for the polygon that connects that corner point with the edge points.

This is all well and good and it works, however the code is cumbersome and slow and I'm not very happy with it. I think that this could probably be solved in a simpler way, I just need to know the correct math or algorhitms to do it.

Okay, here's my code:
view on github.

I'm using the graph data structure and Voronoi algorithm of the LEDA library.
The LEDA API is actually pretty good, so you should have no trouble reading the code, even if you are unfamiliar
with the library.

The output of LEDA's Voronoi algorithm is a planar graph. Every edge is labeled with the site on its left side,
and every proper node is labeled with CIRCLE(a, b, c), where a, b, c are sites closest to that node.
The target nodes of unbounded edges have nodes at ,,infinity'' that store degenerated circles.
More information here.

The idea to bound the Voronoi Diagram, i.e., to intersect it with a quad, is as follows.
First of all, assume that we only want to get rid of unbounded regions. Then we can choose the quad so large
that is only intersects unbounded edges of the Voronoi Diagram.
The basic idea is to traverse all unbounded edges and move their target nodes from ,,infinity'' to the border
of the quad. So, for each unbounded edge you compute the intersection point with the quad. That's pretty cheap,
because the quad consists of only four segments. Also, you don't need to create new nodes or something like that.

You can efficiently find the next unbounded edge (in counter-clockwise order) by following the face cycle of
the unbounded ,,backface'' region.

While traversing, you could simply connect the target nodes of two adjacent unbounded edges with a new edge.

In addition, you have to add the four ,,corner nodes'' of the bounding quad.
In essence, I check for every pair of adjacent edges if there is a quad node between them. If that is the case,
I add it.
Because I traverse the backface in stricly counter-clockwise order, the quad nodes are added in that order, too.
So at any time, there is only one possible candidate node that I have to test.

For my particular application, I needed to bound the Voronoi Diagram with a fix-sized quad,
which might intersect edges of proper regions (I wanted to render a fix-sized section of the diagram).
Therefore, the code I show you first loops over all nodes and edges.
Every edge that intersects the quad is subdivided into two new edges: one new edge is outside the quad and can
be discarded. The other new edge is treated like an additional unbounded edge.

I implemented this algorithm because a naive approach using general segment intersection algorithms turned out
to be too slow.

Thank you for your time invested in this.

I read the code and that gave me some ideas for optimizing my own code. (for example just checking edge polygons for boundary points)

I can now reliably close all polygon edges and produce an arbitrary and visually pleasing map for my games.

I can also use the resulting voronoi as a dungeon where I make sure all rooms are accessible by creating a path that drills through 'walls' by visiting all voronoi sites.

One problem I seem to be having now is that some of the resulting polygons have holes in them after triangulation but that is a story for another day. :-)