计算最佳位置以捕捉尽可能多的物体

Question

我正在尝试计算位置，以便用 R=9 的圆捕捉尽可能多的物体。我可以用附近最多的其他物体收集最佳目标，但我越来越难在我的物体之间获得最佳位置。对我来说唯一的可能性听起来我必须计算我可以从 table 获得的所有组合的平均位置，并选择在 R=9.

范围内拥有最多对象的位置

我的 Table 目前是这样的：

function ObjectPosition (object)
return x,y
end

table ={
object1, ---Object1 is already the one with the most other objects in a range of R=9,
object2,

object3
....
....
}

table 中的对象数量动态变化，因此我需要每秒重新计算几次。

对我来说不可能的事情是获得一个函数来计算平均位置的所有可能性。感谢您抽出宝贵时间！

table 中的 return 需要如下所示：

    tableTwo = {
[1] = {object1},
[2] = {object1, object3},
[3] = {object1, object2},
[4] = {object1, object2, object3},
[5] = {object2},
[6] = {object2, object3},
[7] = {object3}
}

Answer 1

如果我没理解错，对象是一个点，那么你可以只检查那些在其周长上有 2 个这样的 point-objects 的圆。每对物体会有两个圆圈。它们中的每一个都由它的半径和两个点决定。

为什么就够了？因为你可以想象任何最匹配的圆圈移动而不会丢失任何对象，直到两个对象成为它的边界。因此，任何最佳解决方案都与受此 "two points" 规则限制的最佳子集圈一样好。

Answer 2

下面是一个与ephemerr的想法非常相似的实现：

function get_best_center(all_points, R)
   -- returns x_center, y_center, array of indices of points inside the circle
   local neighbors = {}   
   local diam2 = (2 * R) ^ 2
   local zone_min = math.atan2(-1, 0)
   local zone_max = math.atan2(1, 0)
   for j = 1, #all_points - 1 do
      local jx, jy = all_points[j][1], all_points[j][2]
      for k = j + 1, #all_points do
         local kx, ky = all_points[k][1], all_points[k][2]
         local dist2 = (kx - jx) ^ 2 + (ky - jy) ^ 2
         if dist2 <= diam2 then
            if dist2 == 0 then
               neighbors[j] = neighbors[j] or {{-math.huge, math.huge, j}}
               neighbors[k] = neighbors[k] or {{-math.huge, math.huge, k}}
               table.insert(neighbors[j], {-math.huge, math.huge, k})
               table.insert(neighbors[k], {-math.huge, math.huge, j})
            else
               local delta = math.acos((dist2 / diam2) ^ .5)
               local center = math.atan2(ky - jy, kx - jx)
               local azimuth_min = center - delta
               local azimuth_max = center + delta
               if azimuth_min <= zone_max and zone_min <= azimuth_max then
                  neighbors[j] = neighbors[j] or {{-math.huge, math.huge, j}}
                  table.insert(neighbors[j], {azimuth_min, azimuth_max, k})
               end
               center = math.atan2(jy - ky, jx - kx)
               azimuth_min = center - delta
               azimuth_max = center + delta
               if azimuth_min <= zone_max and zone_min <= azimuth_max then
                  neighbors[k] = neighbors[k] or {{-math.huge, math.huge, k}}
                  table.insert(neighbors[k], {azimuth_min, azimuth_max, j})
               end
            end
         end
      end
   end
   if not next(neighbors) then
      local point = all_points[1] or {}
      return point[1], point[2], point and {1} or {}
   end

   local function compare_first_elem(a, b)
      return a[1] < b[1]
   end

   local best_set = {} -- array of indices of points
   local best_x, best_y

   for k, neighbors_k in pairs(neighbors) do

      local current_set = {}
      local current_size = 0
      local come_seq, leave_seq = {}, {}
      for _, n in ipairs(neighbors_k) do
         local come, leave, idx = n[1], n[2], n[3]
         if come <= zone_min and leave >= zone_min then
            current_set[idx] = true
            current_size = current_size + 1
         end
         if come > zone_min then
            table.insert(come_seq, {come, idx})
         end
         if leave < zone_max then
            table.insert(leave_seq, {leave, idx})
         end
      end
      table.sort(come_seq, compare_first_elem)
      table.insert(come_seq, {})
      table.sort(leave_seq, compare_first_elem)
      table.insert(leave_seq, {math.huge})
      local next_come_pos = 1
      local next_leave_pos = 1
      local az = zone_min

      repeat
         if current_size > #best_set then
            local i = 1
            for j in pairs(current_set) do
               best_set[i] = j
               i = i + 1
            end
            best_x = all_points[k][1] + R * math.cos(az)
            best_y = all_points[k][2] + R * math.sin(az)
         end
         az = come_seq[next_come_pos][1]
         if az then
            repeat
               local idx = come_seq[next_come_pos][2]
               current_set[idx] = true
               current_size = current_size + 1
               next_come_pos = next_come_pos + 1
            until come_seq[next_come_pos][1] ~= az
            while leave_seq[next_leave_pos][1] < az do
               local idx = leave_seq[next_leave_pos][2]
               current_set[idx] = nil
               current_size = current_size - 1
               next_leave_pos = next_leave_pos + 1
            end
         end
      until not az

   end

   return best_x, best_y, best_set

end

用法：

function ObjectPosition(object)
   return object.x, object.y
end

all_objects = {
   object1,
   object2,
   object3
   ....
}

-- create array of points {x, y}
local all_points = {}
for j = 1, #all_objects do
   all_points[j] = {ObjectPosition(all_objects[j])}
end

local x, y, indices = get_best_center(all_points, 9)

-- print coordinates of center of circle
print(x, y)  
-- print list of objects inside the circle
for _, idx in ipairs(indices) do
   print(all_objects[idx])
end

注意：圆圈没有很好地居中。一两个物体躺在它的圆周上。

计算最佳位置以捕捉尽可能多的物体

Calculating the best position to catch as many objects as possible

lua

lua-table