16

トロイダルっぽいユークリッドっぽい地図があります。つまり、サーフェスは平らなユークリッド長方形ですが、ポイントが右の境界に移動すると、x_new = x_old％widthで与えられるように、左の境界に（同じy値で）表示されます。

基本的に、ポイントは以下に基づいてプロットされます。*編集を参照

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

パックマンを考えてみてください。画面の一方の端から離れると、反対側の端に表示されます。

2点間の最短距離を計算する最良の方法は何ですか？典型的な実装では、実際には実際のラップされた距離が非常に近い場合でも、マップの反対側のコーナーにあるポイントの距離が大きいことが示唆されています。

私が考えることができる最良の方法は、古典的なデルタXとラップされたデルタX、および古典的なデルタYとラップされたデルタYを計算し、Sqrt（x ^ 2 + y ^ 2）距離式の各ペアの低い方を使用することです。

しかし、それには多くのチェック、計算、操作が含まれます-私が感じるいくつかは不要かもしれません。

もっと良い方法はありますか？

編集

オブジェクトが移動すると、オブジェクトは位置（x_old、y_old）に移動し、上記の式を実行して、その位置として（x_new、y_new）を格納します。上記の式は、オブジェクトが境界を越えて移動したときに何が起こるかを明確にするためにのみ追加されました。実際には、一度に1つの（x、y）ペアのみが各オブジェクトに格納されます。

4

7 に答える 7

13

私が考えることができる最良の方法は、古典的なデルタXとラップされたデルタX、および古典的なデルタYとラップされたデルタ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

周期領域の2点間の最短距離は、ループを使用せずに次のように計算できます。

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

これにより、署名された最短距離が得られます。ANINTは、ANINT（x）が、xと同じ符号で、大きさがabs（x）+0.5未満の最も近い整数を与えるような固有のFORTRAN関数です。たとえば、ANINT（0.51）= 1.0、ANINT（-0.51）=-1.0などです。他の言語にも同様の関数があります。

于 2013-02-14T16:36:42.697 に答える
3

値と、aを持つ新しい座標の-軸で最小のデルタを見つけるには、 -軸の境界は次のとおりです。a1a2aBoundarya

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

したがって、新しい座標x1,y1とx2,y2の2つのポイントがある場合は、次のようにすることができます。

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

これは事実上あなたが提案することですが、私はそれが「多くのチェック、計算、および操作」であるとは言いません。

于 2010-06-14T22:42:09.477 に答える
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

距離は幅/2および高さ/2より大きくすることはできません。width / 2より大きい差（X1-X2）が得られた場合は、width/2を差し引いてショートカット距離を取得します。次に、通常どおり距離を計算します。

于 2010-06-14T22:31:08.570 に答える
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

mod演算子で「abs」関数を使用することはできません。

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