dcearth/locationQuery.lua

--Shitty acceleration structure: get closest point in set.
--Assumed to be in world coordinates: ( -180, 180 ) x ( -100, 100 )
local t = {}
local math = math

local hash = function( x, y, debug )
  local s = "h"..("%2d%2d"):format(math.floor( 0.5 + (180 + x) / 20 ), math.floor( 0.5 + (100 + y) / 20 ) )
  return s
end

function t.getHashes( points )
  return assert( points.hashes )
end

function t.getClosestPoint( points, x, y )
  local hashes = t.getHashes( points )
  local closePoints = hashes[hash( x, y )]
  
  if not closePoints then
    return
  end
  
  local distance = math.huge
  local px, py, point
  for k, v in pairs(closePoints) do

    px, py = v.x, v.y
    local d = (x - px) * (x - px) + (y - py) * (y - py)
    if d < distance then
      distance = d
      point = v
    end

  end

  return point
end

function t.Edit( points, point, x, y )
  local hashes = t.getHashes( points )
  local h = hashes[hash( point.x, point.y )]
  if h then
    for i, p in pairs(h) do
      if p == point then
        table.remove( h, i )
        break
      end
    end
  end

  table.insert( hashes[ hash( x, y ) ], point )
  point.x = x
  point.y = y

end

function t.Add( points, x, y )

end

function t.New( points )
  local hashes = {}
  for i = 1, #points do
    local x, y = points[i].x, points[i].y
    local h = hash( x, y )
    hashes[h] = hashes[h] or {}
    hashes[h][#hashes[h] + 1] = points[i]
  end
  points.hashes = hashes
  
  do
    local count = 0
    for k, v in pairs(hashes) do count = count + 1 end
    print( "LOCATION QUERY. Points:", count )
  end
  return setmetatable( points, {__index = t} )
end

return t