StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This problem is not as easy as it looks on the surface. Your problem is that both sides of the border of two regions need to have the same height, which is to say, the height at a given pixel is determined by more than just one nearest neighbor.</p> <p>If I understand it correctly, you need at least two algorithms (and a third piece of jargon).</p> <p>To do this correctly, you need to break the plane into a <a href="http://en.wikipedia.org/wiki/Voronoi_diagram" rel="nofollow noreferrer">Voronoi tesselation</a>.</p> <p>You are probably going to want to use a <a href="http://en.wikipedia.org/wiki/Kd-tree" rel="nofollow noreferrer">kd-tree</a> to help you find the nearest neighbor. Instead of taking O(n^2), this will bring it down to O(n log(n)) (the added benefit is that your Voronoi region generation phase will be fast enough in development to work on the height calculation phase).</p> <p>Now that you have a 2-D map indexing each point to its nearest neighbor i, you need to walk across every x,y point on the map and calculate its height.</p> <p>To do that for a given point x,y, first grab its nearest neighbor i and stick that into a list, then collect all contiguous regions on the Voronoi diagram. An easy way is to use <a href="http://en.wikipedia.org/wiki/Flood_fill" rel="nofollow noreferrer">flood fill</a> to find all the points in the region, then look around the border and collect up the other identities.</p> <p>Using this list of all the nearest neighbors, you now have a shot at interpolating correctly! (See other answers for interpolation schemes).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload