在环绕的空间上绘制一条线段

Question

我有一个角度为[0, 2pi] x [0, 2pi]的二维空间，它环绕着环形拓扑结构（水平边缘与垂直边缘相对应）。我在这个空间有两点，我想在这两点之间划一条线。

在某些情况下，该线段是从一点到另一点的明显线段。在其他情况下，该线段应该“去周围的边缘”，而不是去“很长的路要走，通过中间的”：

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

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

虽然这些案件是适度宽松的处理，有一个情况真的很烦我，而我的代码到目前为止处理不正确：

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

iee如果线路绕过两个方向，则有时会缠绕在对面的角落。我不完全确定这些棘手的案件是否还有更多。

到目前为止，我唯一能够可靠工作的算法是计算中点为(A + B)/2，同时适当使用模运算，在此位置绘制一个点，然后递归地细分左右区间，直到点之间的距离小于单个像素。显然，这不会很快。

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

有更好的算法吗？有没有明显的解决方案，我没有看到？我甚至不知道如何谷歌这个问题。我不想实现我自己的线栅格化算法，我只想将这个问题分解成欧几里德直线，并使用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]工作的，试着用这个广场（如井字棋板）的9份平铺空间[-2pi,4pi] x [-2pi,4pi]。将A放在中心的正方形中，然后放置B的副本（根据需要将坐标转换为+2π的坐标）到九个方格的每一个中。选择与A最接近的B的副本，然后从A画出该行到该B的副本。此行可能有多个片段在它们穿过方块时行进。只需将这些片段“翻译”回中央广场，就可以得到您想要的图表。