Problem Detail: Is there a known/existing algorithm for taking a 2D canvas covered in arbitrarily/randomly distributed points and dividing it entirely into a set of non-overlapping polygons? An example of the kind of result I’m looking for:
Asked By : CaptainRad
Answered By : D.W.
You might be looking for a Voronoi diagram. Given a set $S$ of points, it creates one cell per point, where the cell for point $p$ contains everything that is closer to $p$ than to any other point in $S$. There are algorithms to compute a Voronoi diagram in $O(n lg n)$ time, where $n$ is the number of points in your set.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/45021
