My work involves using voronoi diagrams, and my next task is to split a cell inside this diagram in half(aprox.)

More accurately: I have a set of (x,y) points, I am using a library which takes care of drawing this diagram, and I have to find a new (x,y) point (or two, I am not really sure), insert it into that set, redraw it, so that the original cell is divided in half.

My idea was that I should use the average coordinates of the neighbors and insert that new point, but this works only with cells in the center of the diagram. Those cells which are close to the edge of the box remain quite big after splitting it with this strategy.

I assume that this is a geometry problem, and any help would be appreciated.

I have attached two images, the first one is the initial diagram, and in the second one you can see how all cells have been split using the average strategy. It's obvious that the splitting is not working as I want it to.

Before image After image


In order to reduce border effects, imagine you are working on a cylinder, or better said on a torus; this will be realized by replicating the set of points on each ide of the original square or rectangle as shown on the figure below where you can see that the exceptional cells have no influence on the cells of the central square, the only square that will be kept.

enter image description here

  • $\begingroup$ I was too lazy to implement this method(I have to compute too many things, and I can't afford any time for this), however I think that this is the best approach. $\endgroup$ – sundri23 Mar 28 '17 at 17:56

Just replace the original point with two points very close together. The split will bisect the line joining them.

What "very close together" means will depend on the original spacing of the other points. Much closer than the smallest original spacing is what is required.

  • $\begingroup$ Thanks, this was the easiest and fastest method to implement. I have searched for a neighbor cell which Y coordinate is the closest to the one that has to be divided, and added a new point to my list between these two. However I think that JeanMarie's approach is better $\endgroup$ – sundri23 Mar 28 '17 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.