2

(I'm not 100% sure if the title is the best description, I'll edit if necessary)

I'm trying to create a voronoi region to do a split-screen effect in a game. I'm following the steps outlined in this PDF. As I understand them:

  1. Find a line running along the midway point between players
  2. Find the vertices of the intersections of each player's respective lines, bounded by the area in question
  3. Create a region for each player using the convex hull of those vertices.

I found the algorithms for step 3, where I'm stuck is how to find the vertices of each region. Using this image as an example:

enter image description here

Looking at player C, I worked out that I need to find the intersection point of the A/C line, the B/C line and the D/C line. Easy enough. Where I'm stuck is that if a line hits an edge, then I have to find vertices for where it hits an edge, plus any corners in the region (like the bottom left in this image). But I can't just throw the sides of the region in as lines, because with more than 4 players, a region isn't guaranteed to touch the edge of the screen, so those points would need to be discarded and I'm not sure how to factor that into the process.

If it makes any difference, I'm doing this in C# / Unity.

Salvatore Ambulando
  • 402
  • 1
  • 6
  • 13

1 Answers1

1

I think it might be beneficial for you to take a look at the wiki article on Voronoi_diagrams and their dual diagrams, called Delaunay triangulations. If you can construct a Voronoi diagram, then you can construct its dual Delaunay triangulation and vice versa. The vertices of the Voronoi diagram are the centers of the circles circumscribed around the triangles of the Delaunay triangulation. As such, every Voronoi vertex is the intersection point of the three orthogonal bisectors of its corresponding dual triangle from the Delaunay triangulation.

Particularly, for some specific algorithms, you can check out: Fortune's algorithm or the dual of Bowyer-Watson algorithm.

Futurologist
  • 1,874
  • 2
  • 7
  • 9
  • Yeah, I somehow missed those pages when I first asked the question but I've been reading them (and the dozens of related pages) and my issue is that they're really complex to implement, especially for only 10 points or fewer. So now I'm wondering if I can find an simpler way to do it like I described above. I also found this https://stackoverflow.com/questions/973094/easiest-algorithm-of-voronoi-diagram-to-implement and I'm digging through it but most of the answers are vague or incomplete, or not simple at all. I may need to edit the question – Salvatore Ambulando Mar 30 '21 at 17:25