开发者

Best datastructure for a heightmap

开发者 https://www.devze.com 2022-12-21 06:56 出处:网络
I have a heightmap (a 2D array of floating point values) and I wish to find the highest point on the map, once I have found this point, I want to change its value, and the values of all nearby points.

I have a heightmap (a 2D array of floating point values) and I wish to find the highest point on the map, once I have found this point, I want to change its value, and the values of all nearby points. What's the best datastructure to use for efficient retrieval of t开发者_StackOverflowhe highest point?

Requirements:

  • Find the highest point efficiently
  • Change the value of an arbitrary set of points, this set will always contain the highest current point, and a load of points nearby, the delta will be different for each point.

My current thinking is a priority queue, I can find the highest point in O(1) and I can change a load of values and heapify in O(n log n).

Nb. I've marked this as language-agnostic and Lua, because it is a largely language agnostic question, but I will be implementing the final solution in Lua.


If memory is not that big of an issue I would store each value in a priority queue as a table so that each table has its data value and references to its closest neighbors. Something like this: { data = number, neighbors = { ... } }.


While you are building your priority queue I'd simply be scanning the array and returning the indices of the highest value found. I can then access any element of the array 'nearby' in O(1).

Or am I missing something ?

0

精彩评论

暂无评论...
验证码 换一张
取 消