Thursday, May 22, 2003

here's my shot at voronoi diagram

DATA STRUCTURE ?

for RANDOM POINTS
1. get all coordinates
2. pair all points with all other points
3. get all 3-pair of all points to their 2 nearest neighbours

for GENERATED TRIANGLES
1. get all mid points of all edges E1, E2, E3, E4, ... En

for GENERATED CIRCLES
1. get all centerpoints namely O1, O2, O3, O4, ... On

ALGO

1. calculate the longest distance (K) between two points

2. draw a circle using that K as diameter, O as centerpoint

3. get three random points (L, M, N) in the circumcircle of K which
distances between a point to next point along the circle are equal

4. draw lines from centerpoint O to L, M and N

5. draw extended lines perpendicular to OL, OM, ON
intersecting points of these lines are A, B, C are the biggest triangle's vertices

6. store midpoints as E1, E2, E3

7. draw all lines from each point (including A, B and C) to nearest neighbours || loop until all points connected
[watch there should not be intersecting lines, if there are; rewrite]

::: At this point, we have formed Delaunay triangulation
which could be store as "delaunay" drawing layer

8. store all triangle-edge's midpoints as E4, E5 ...En

9. draw circle which contain 3-pair nearest-neighbout-points in its circumcircle || loop until all 3-pairs created all circles
[watch there should not be a point within any circles, if there are; rewrite]

10. store all centerpoints as O1, O2, O3, ... On

::: At this point, we got >> all voronoi points represented as set of O
>> all midpoints of delaunay edges as set of E

11. draw line from all Os to all Es

::: At this point, we got >> all voronoi edges
which could be store as "voronoi" drawing layer

PROBLEM
there might be in the perimeter