Voronoi diagram: Difference between revisions
Content added Content deleted
Superbatfish (talk | contribs) (→{{header|Python}}: Added alternative Python implementation, using numpy/scipy.) |
Superbatfish (talk | contribs) |
||
Line 2,127: | Line 2,127: | ||
[[File:Voronoi_python.png|500px|thumb|center|Voronoi Diagram in Python]] |
[[File:Voronoi_python.png|500px|thumb|center|Voronoi Diagram in Python]] |
||
Alternatively, vectorized code leveraging numpy and scipy is 2x shorter and 10x faster |
Alternatively, vectorized code leveraging numpy and scipy is 2x shorter and 10x faster, as seen below. |
||
Note that for large numbers of points, using a KDTree will be much faster thanks to lookups in log(N) time rather than N comparisons at every coordinate. The code below has running time O(X*Y*log(N)), whereas the code above has running time O(X*Y*N). For 1000 points, the code below is 250x faster than the above. |
|||
<syntaxhighlight lang="python"> |
<syntaxhighlight lang="python"> |