16

我有一个环形欧几里得地图。那就是表面是一个平坦的欧几里得矩形，但是当一个点移动到右边界时，它会出现在左边界（在相同的y值处），由x_new = x_old % width给出

基本上，点的绘制基于： *见编辑

(x_new, y_new) = ( x_old % width, y_old % height)

想想吃豆人——离开屏幕的一个边缘会让你出现在对面的边缘。

计算两点之间最短距离的最佳方法是什么？典型的实现建议地图相对角上的点距离很远，而实际上，真正的包裹距离非常接近。

我能想到的最好方法是计算 Classical Delta X 和 Wrapped Delta X，以及 Classical Delta Y 和 Wrapped Delta Y，并使用 Sqrt(x^2+y^2) 距离公式中每对的较低值。

但这将涉及许多检查、计算、操作——我觉得有些可能是不必要的。

有没有更好的办法？

编辑

当一个对象移动时，它移动到位置 (x_old,y_old)，通过上面的公式运行它，并将 (x_new, y_new) 存储为它的位置。上面的公式只是为了阐明当物体越过边界时会发生什么；实际上，每个对象一次只存储一个 (x,y) 对。

4

7 回答 7

13

我能想到的最好方法是计算 Classical Delta X 和 Wrapped Delta X，以及 Classical Delta Y 和 Wrapped Delta Y，并使用 Sqrt(x^2+y^2) 距离公式中每对的较低值。

就是这样，我认为没有更快的方法。但计算起来并不难；你可以做类似的事情

dx = abs(x1 - x2);
if (dx > width/2)
  dx = width - dx;
// again with x -> y and width -> height

（我相信您可以将其翻译成您喜欢的语言）

于 2010-06-14T22:29:30.117 回答
4

在不使用任何循环的情况下，可以如下计算周期域中两点之间的最短距离。

    dx = x2-x1
    dx = dx - x_width*ANINT(dx/x_width)

这将给出一个有符号的最短距离。ANINT 是一个内在的 FORTRAN 函数，因此 ANINT(x) 给出最接近的整数，其幅度小于 abs(x)+0.5，符号与 x 相同。例如， ANINT(0.51)=1.0 、 ANINT(-0.51)=-1.0 等。其他语言也存在类似的功能。

于 2013-02-14T16:36:42.697 回答
3

要找到a-axis 中具有值a1和的新坐标的最小增量，-axis上的边界在a2哪里：aBoundarya

def delta(a1, a2, aBoundary):
  return min(abs(a2 - a1), abs(a2 + aBoundary - a1))

因此，如果您有两个具有新坐标x1,y1和的点x2,y2，您可以这样做：

sumOfSquares(delta(x1,x2,width), delta(y1,y2,height))

这实际上是您的建议，但我不会说这是“许多检查、计算和操作”。

于 2010-06-14T22:42:09.477 回答
0

距离不能大于宽度/2 和高度/2。如果您得到的差值 (X1-X2) 大于宽度/2，则减去宽度/2 以获得快捷距离。然后像往常一样计算距离。

于 2010-06-14T22:31:08.570 回答
0 
(delta_x, delta_y)= 
     (min(width - abs(x_new - x_new), abs(x_new - x_old)), 
      min(height - abs(y_new - y_old), abs(y_new - y_old)))
于 2010-06-14T22:24:44.773 回答
0

伙计，我做了一些不同的事情......

这里有一些额外的功能，但核心是包裹屏幕上的距离......

from math import sqrt
import pytweening

class ClosestPoint_WD(object):
def __init__(self, screen_size, point_from, point_to):
    self._width = screen_size[0]
    self._height = screen_size[1]
    self._point_from = point_from
    self._point_to = point_to
    self._points = {}
    self._path = []

def __str__(self):
    value = "The dictionary:" + '\n'
    for point in self._points:
        value = value + str(point) + ":" + str(self._points[point]) + '\n'

    return value

def distance(self, pos0, pos1):
    dx = pos1[0] - pos0[0]
    dy = pos1[1] - pos0[1]
    dz = sqrt(dx**2 + dy**2)

    return dz

def add_point_to_dict(self, x, y):
    point = x, y
    self._points[point] = 0

def gen_points(self):
    max_x = self._width * 1.5 - 1
    max_y = self._height * 1.5 - 1

    # point 1, original point
    self.add_point_to_dict(self._point_to[0], self._point_to[1])

    # add the second point: x-shifted
    if self._point_to[0] + self._width <= max_x:
        self.add_point_to_dict(self._point_to[0] + self._width, self._point_to[1])
    else:
        self.add_point_to_dict(self._point_to[0] - self._width, self._point_to[1])

    # add the third point: y-shifted
    if self._point_to[1] + self._height <= max_y:
        self.add_point_to_dict(self._point_to[0], self._point_to[1] + self._height)
    else:
        self.add_point_to_dict(self._point_to[0], self._point_to[1] - self._height)

    # add the fourth point: diagonally shifted
    if self._point_to[0] + self._width <= max_x:
        if self._point_to[1] + self._height <= max_y:
            self.add_point_to_dict(self._point_to[0] + self._width, self._point_to[1] + self._height)
        else:
            self.add_point_to_dict(self._point_to[0] + self._width, self._point_to[1] - self._height)
    else:
        if self._point_to[1] + self._height <= max_y:
            self.add_point_to_dict(self._point_to[0] - self._width, self._point_to[1] + self._height)
        else:
            self.add_point_to_dict(self._point_to[0] - self._width, self._point_to[1] - self._height)

def calc_point_distances(self):
    for point in self._points:
        self._points[point] = self.distance(self._point_from, point)

def closest_point(self):
    d = self._points
    return min(d, key=d.get)

def update(self, cur_pos, target):
    self._point_from = cur_pos
    self._point_to = target
    self._points = {}
    self.gen_points()
    self.calc_point_distances()
    self.shortest_path()

def shortest_path(self):
    path = pytweening.getLine(self._point_from[0], self._point_from[1], self.closest_point()[0], self.closest_point()[1])
    #path = pytweening.getLine((self._point_from)
    ret_path = []

    for point in path:
        ret_path.append((point[0] % self._width, point[1] % self._height))

    self._path = ret_path
    return self._path
于 2016-05-04T21:58:57.197 回答
-1

您不能将“abs”功能与 mod 运算符一起使用！

xd =(x1-x2+Width)%Width
yd=(y1-y2+Height)%Height
D=sqrt(xd^2+yd^2)
于 2010-06-14T23:01:39.320 回答