A Voronoi diagram is a diagram consisting of a number of sites.

Each Voronoi site s also has a Voronoi cell consisting of all points closest to s.



Task

Demonstrate how to generate and display a Voroni diagram.



See algo K-means++ clustering.




include c:\cxpl\codes;          \intrinsic 'code' declarations
 
def     N = 15;                 \number of sites
int     SiteX(N), SiteY(N),     \coordinates of sites
        Dist2, MinDist2, MinI,  \distance squared, and minimums
        X, Y, I;
[SetVid($13);                   \set 320x200x8 graphics
for I:= 0 to N-1 do             \create a number of randomly placed sites
        [SiteX(I):= Ran(160);  SiteY(I):= Ran(100)];
for Y:= 0 to 100-1 do           \generate Voronoi diagram
    for X:= 0 to 160-1 do       \for all points...
        [MinDist2:= -1>>1;      \find closest site
        for I:= 0 to N-1 do
                [Dist2:= sq(X-SiteX(I)) + sq(Y-SiteY(I));
                if Dist2 < MinDist2 then
                        [MinDist2:= Dist2;  MinI:= I];
                ];
        if MinDist2 then Point(X, Y, MinI+1);   \leave center black
        ];
I:= ChIn(1);                    \wait for keystroke
SetVid($03);                    \restore normal text screen
]