Extracting cell center and corner points from rasterized Voronoi diagram

Question

I currently have this code which I copied from Rosetta code:

// version 1.1.3 import java.awt.Color import java.awt.Graphics import java.awt.Graphics2D import java.awt.geom.Ellipse2D import java.awt.image.BufferedImage import java.util.Random import javax.swing.JFrame fun distSq(x1: Int, x2: Int, y1: Int, y2: Int): Int { val x = x1 - x2 val y = y1 - y2 return x * x + y * y } class Voronoi(val cells: Int, val size: Int) : JFrame("Voronoi Diagram") { val bi: BufferedImage init { setBounds(0, 0, size, size) defaultCloseOperation = EXIT_ON_CLOSE val r = Random() bi = BufferedImage(size, size, BufferedImage.TYPE_INT_RGB) val px = IntArray(cells) { r.nextInt(size) } val py = IntArray(cells) { r.nextInt(size) } val cl = IntArray(cells) { r.nextInt(16777215) } for (x in 0 until size) { for (y in 0 until size) { var n = 0 for (i in 0 until cells) { if (distSq(px[i], x, py[i], y) < distSq(px[n], x, py[n], y)) n = i } bi.setRGB(x, y, cl[n]) } } val g = bi.createGraphics() g.color = Color.BLACK for (i in 0 until cells) { g.fill(Ellipse2D.Double(px[i] - 2.5, py[i] - 2.5, 5.0, 5.0)) } } override fun paint(g: Graphics) { g.drawImage(bi, 0, 0, this) } } fun main(args: Array<String>) { Voronoi(70, 700).isVisible = true }

The problem is, this code has a JFrame graphical output while I want an Array<Vector2> one, consisting of polygon points and centre points.

I'd try to manipulate this myself, but the code is too complex for me to understand. I'd appreciate a version of this code that returns such output.

if someone could explain the code above my problem would be solved, and how i would un-rasterise it and just get an array output

(Summarizing in a comment for future readers) As we discussed in the chat linked above, I think trying to extract the feature points you want from a rasterized version of the diagram like this is unlikely to give you good results. I think it would be better to use a different algorithm, which natively finds the polygon vertices, without a rasterization pass. — DMGregory
– DMGregory ♦, Commented Nov 28, 2021 at 19:16

Engineer · Accepted Answer · 2021-11-28 20:58:04Z

It is better to generate a Voronoi diagram as vectors first, e.g. via Fortune's Sweepline Algorithm, then rasterise.

If, however, you are dead set on using the rasterised version as a basis, then you need, per uniquely IDed (colored) Voronoi Cell, to:

Collect the list of pixels / texels for that cell, via flood-fill.
Average the centres of those pixels to get and store centre coordinates for that cell.
Seek all neighbour pixels of that cell, storing only unique adjacent colors / IDs in a set or dictionary to prevent duplicates. Set up a neighbours list to store those IDs for this cell.

You can now draw a graph of all centres connected to one another using these neighbour lists. This is called the Delaunay Triangulation of the Voronoi diagram (it produces triangles). However, you need the corners rather than (just) the centres of the cells.

Produce the graph dual of the Delaunay Triangulation, which is the Voronoi diagram. The easiest way to do this is, for each triangle in your Delaunay Triangulation, to calculate the centroid as the average of its 3 corners / vertices. You will then need to figure out that triangle's neighbours according to which other triangles share its edges. Then this triangle's centre will connect to their centres. This gives you the corners you seek.

Needless to say that while possible, this is not quite trivial, and very inefficient vs. just using a proper Voronoi graph generation algorithm which outputs vectors, but it does avoid your needing to find or implement such an algorithm.

i think i'm a bit of lost, i just need a voronoi generator that will output array<Vector2> — random person
– random person, Commented Nov 29, 2021 at 15:11
after a bit of actual thinking about this post, the thing is, i wont ever need rasterized versions of the voronoi diagram, i will directly use the array<vector2> to draw stuff in my game, the thing is, most of the tutorials on creating a fortune's algorithm is too complex for me to understand, and i might need a bit of help on that part. also i dont understand why i need fortune's algorithm, courses.cs.washington.edu/courses/cse326/00wi/projects/… this thing seems to do the same thing as well, albeit a bit complex too but simpler — random person
– random person, Commented Nov 29, 2021 at 16:00

Stack Exchange Network

Extracting cell center and corner points from rasterized Voronoi diagram

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Extracting cell center and corner points from rasterized Voronoi diagram

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions