Voronoi diagram - introduction

And so we start - again!
This is a first post from what I expect to be quite a long story. I will try to show all the steps needed to create a Sketchup plugin that will allow You to create a Voronoi diagram.
Some of the readers will ask what that is - well picture is worth more than words:

Graphic by www.cs.wustl.edu/

From wikipedia:

"A Voronoi diagram is a way of dividing space into a number of regions. ... The regions are called Voronoi cells. It is dual to the Delaunay triangulation."

So as You can see on the picture above, In Sketchup You have to draw a set of polygons around specified points. But how do You know where are the vertices of every polygon located? What steps You have to take ?

So to create a Voronoi diagram from group of points we will write a function called "Voronoi tesselation", that will return voronoi cells as a polygons. Sounds easy, but in fact there will be a lat of steps involved.

To avoid things to get overcomplicated we will work with 2D Voronoi ( Yes, You can also make a 3D Voronoi).

In fact we will be working in 3D space, but voronoi cells will be flat. So the first step will be in fact making sure that all the points sits on the same plane. To do that we will make another function "Flatten to plane". But this will be more detailed in next post. So our flow diagram will look like this:

To be continued...