在 space 上绘制环形环绕的线段

Question

我有一个 2D space 的角度 [0, 2pi] x [0, 2pi] 环绕，具有类似环形的拓扑结构（水平边缘彼此对应，垂直边缘也是如此）。我在这个space中有两点，我想在这两点之间画一条线段。

在某些情况下，这条线段是明显的线段，从一点到另一点。在其他情况下，线段应该 "go around the edge" 而不是 "the long way, through the middle":

+--------+
|        |
|  A--B  |
|        |
+--------+

+--------+
|        |
|-A    B-|
|        |
+--------+

虽然这些情况比较容易处理，但有一种情况对我来说真的很麻烦，而且我的代码目前无法正确处理：

+-----------+
|        /  |
|       B   |
|           |
|  A       /|
| /       / |
+-----------+

即如果这条线环绕两个方向，它有时会环绕对角。我不确定是否还有更多这些棘手的案例。

到目前为止，我想出的唯一可靠的算法是计算中点为 (A + B) / 2，同时适当使用模运算，在该位置画一个点，然后递归细分左右间隔类似，直到点之间的距离小于单个像素。显然，这不会很快。

我的另一种方法是检测（分别用于 x 和 y）短距离是直接的还是围绕边缘的，然后绘制一条或两条线段。这不能正确处理第三种情况，除非线被一分为二并且中点位于示例图像右下角的线段上。我不确定如何有效地检测到这一点，或者如何计算中点的位置，因为只是一半的点并不总是有效，它可能会与端点之一一起在边缘结束，如果它们各自与边缘的距离不相等。

有没有更好的算法？有没有我没有看到的明显解决方案？我什至不确定如何 google 解决这个问题。我不想实现我自己的线光栅化算法，我只想将这个问题分解为欧几里得直线并使用 OpenGL 或 GDI 或其他任何方式绘制它们。

到目前为止我的代码是：

void Draw_WrappedSegment(float f_x0, float f_y0, float f_x1, float f_y1)
{
    const float s = 2 * f_pi;
    f_x0 = fmod(fmod(f_x0, s) + s, s);
    f_y0 = fmod(fmod(f_y0, s) + s, s);
    f_x1 = fmod(fmod(f_x1, s) + s, s);
    f_y1 = fmod(fmod(f_y1, s) + s, s);
    // make sure the coordinates end up being positive and modulo 2pi

    float f_ydist0 = fabs(f_y0 - f_y1);
    float f_ydist1 = fabs(fmod(f_y0 + s - f_y1, s));
    float f_ydist2 = fabs(fmod(f_y1 - f_y0 + s, s));
    float f_xdist0 = fabs(f_x0 - f_x1);
    float f_xdist1 = fabs(fmod(f_x0 + s - f_x1, s));
    float f_xdist2 = fabs(fmod(f_x1 - f_x0 + s, s));
    //     0                        2pi                       4pi
    //p1'' |     p0             p1   |     p0'            p1'  |
    //            <---f_dist0--->
    //                           <-f_dist1->
    // <-f_dist2->

    const float f_epsilon = 1e-3f; // sometimes the modulo causes an error and even though the díst 0 and dist 2 should equal, dist 2 is slightly smaller
    if(f_xdist0 <= f_xdist1 + f_epsilon && f_xdist0 <= f_xdist2 + f_epsilon) {
        if(f_ydist0 <= f_ydist1 + f_epsilon && f_ydist0 <= f_ydist2 + f_epsilon) {
            MoveTo(f_x0, f_y0);
            LineTo(f_x1, f_y1); // the "short" way in both directions
        } else {
            float f_sign = (f_y0 < f_y1)? 1 : -1; // swap the lower and upper edge if the points are not sorted by y
            MoveTo(f_x0, f_y0);
            LineTo(f_x1, f_y1 - f_sign * s); // from point 0 to the lower edge
            MoveTo(f_x1, f_y1);
            LineTo(f_x0, f_y0 + f_sign * s); // from point 1 to the upper edge
        }
    } else {
        if(f_ydist0 <= f_ydist1 + f_epsilon && f_ydist0 <= f_ydist2 + f_epsilon) {
            float f_sign = (f_x0 < f_x1)? 1 : -1; // swap the left and right edge if the points are not sorted by x
            MoveTo(f_x0, f_y0);
            LineTo(f_x1 - f_sign * s, f_y1); // from point 0 to the left edge
            MoveTo(f_x1, f_y1);
            LineTo(f_x0 + f_sign * s, f_y0); // from point 1 to the right edge
        } else {
            float f_sign_x = (f_x0 < f_x1)? 1 : -1; // swap the left and right edge if the points are not sorted by x
            float f_sign_y = (f_y0 < f_y1)? 1 : -1; // swap the lower and upper edge if the points are not sorted by y
            MoveTo(f_x0, f_y0);
            LineTo(f_x1 - f_sign_x * s, f_y1 - f_sign_y * s); // from point 0 to one edge
            MoveTo(f_x1, f_y1);
            LineTo(f_x0 + f_sign_x * s, f_y0 + f_sign_y * s); // from point 1 to the other edge
        }
    }
}

Answer 1

与其只使用正方形 [0, 2pi] x [0, 2pi]，不如尝试将 space [-2pi,4pi] x [-2pi,4pi] 与该正方形的九个副本（如井字棋盘）平铺在一起。将 A 放在中心方格中，然后将 B 的副本（根据需要将坐标平移 ±2pi）放在九个方格中的每一个方格中。选择最靠近 A 的 B 副本，然后从 A 到 B 的那个副本画一条线。这条线在穿过方块时可能有多条线段。只需 "untranslate" 这些部分回到中心广场，您就会得到想要的图表。

在 space 上绘制环形环绕的线段

Drawing a line segment on a space that wraps toroidally

2d

line

distance

modulo