在循环中遍历一条线

Question

我想找到一条线（由起点和终点给出）与网格线（x=0,1,2,3... 或 y=0,1,2,3,...）的交叉点。因此，交叉点的x或y是否为整数。

我想出了以下代码，用于查找 5.5,3.5 和 10.5,20.5 给出的线与网格的交点（平行于 x 和 [=15 的线=] 轴）。

#include <stdio.h>
#include <math.h>

float ax[2] = {5.0, 10.5}; // x coordinates of start and end points
float ay[2] = {3.5, 20.5}; // y coordinates of start and end points
int l, k = 0;

int main()
{
    if (ax[k] < ax[k + 1])
    {
        for (l = ceil(ax[k]); l < ax[k + 1]; l++)
        {
            printf("%d,%f\n", l, (ay[k + 1] - ay[k]) / (ax[k + 1] - ax[k]) * l + ay[k] - (ay[k + 1] - ay[k]) / (ax[k + 1] - ax[k]) * ax[k]);
        }
    }

    if (ax[k] > ax[k + 1])
    {
        for (l = ceil(ax[k + 1]); l < ax[k]; l++)
        {
            printf("%d,%f\n", l, (ay[k + 1] - ay[k]) / (ax[k + 1] - ax[k]) * l + ay[k] - (ay[k + 1] - ay[k]) / (ax[k + 1] - ax[k]) * ax[k]);
        }
    }

    if (ay[k] < ay[k + 1])
    {
        for (l = ceil(ay[k]); l < ay[k + 1]; l++)
        {
            printf("%f,%d\n", (ax[k + 1] - ax[k]) / (ay[k + 1] - ay[k]) * l + ax[k] - (ax[k + 1] - ax[k]) / (ay[k + 1] - ay[k]) * ay[k], l);
        }
    }

    if (ay[k] > ay[k + 1])
    {
        for (l = ceil(ay[k]); l < ay[k + 1]; l++)
        {
            printf("%f,%d\n", (ax[k + 1] - ax[k]) / (ay[k + 1] - ay[k]) * l + ax[k] - (ax[k + 1] - ax[k]) / (ay[k + 1] - ay[k]) * ay[k], l);
        }
    }

    return 0;
}

但我需要按顺序打叉（从行首扫描到行尾）。我可以对找到的十字进行排序，但我认为在一个循环中执行此操作会更容易。

预期输出为

5,3.499999
5.161765,4
5.485294,5
5.808824,6
6,6.590909
6.132353,7
6.455883,8
6.779412,9
7,9.681819
7.102942,10
7.426471,11
7.750000,12
8,12.772727
8.073530,13
8.397058,14
8.720589,15
9,15.863635
9.044118,16
9.367647,17
9.691177,18
10,18.954544
10.014706,19
10.338236,20

如您所见，交叉点已经按照距离起点(5.0,3.5)的距离顺序找到了。

Answer 1

这是您问题的完整解决方案。假设我们当前位于坐标 (x,y)，然后我们计算下一个整数与 x, y 的偏移量，并将它们称为 dx, dy。现在，下一个最近的点将是两个可能的点：

(x+dx,某-对应-Y)或
(SomeX, y+dx)

现在我们的挑战是找到最近的哪一个。斜率（Dy/Dx）实际上会帮助我们找到下一个最近的直线。

如果dxoffset给出直线上的下一个最近点，则y坐标对应的偏移dy可以通过dy = minv * dx计算得到。反之，如果dy是最接近的偏移量，那么我们可以用dx = m * dy来计算dx。所以，我们实际上写了一个 if 语句来找出两个可能的备选方案中哪一个是最接近的。而已。一旦我们找到下一个最近的点，我们重复相同的过程，直到我们到达终点。但是，请注意以下浮点计算的局限性。当Dx或Dy几乎等于0时，那么no.of有效点将变为无限。因此，您需要为要计算的最大点数定义一个上限。所以，我没有在下面的代码中处理这些情况（Dx ~ 0 或 Dy ~ 0）。

#include <math.h>
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <float.h>

float ax[2] = {5.0, 10.5}; // x coordinates of start and end points
float ay[2] = {3.5, 20.5}; // y coordinates of start and end points

double add(double x, double dx)
{
    return x + dx;
}

double sub(double x, double dx)
{
    return x - dx;
}

typedef double (*nextint) (double);
typedef double (*next) (double, double);

int main()
{
    double x, x1, x2, dx, Dx;
    double y, y1, y2, dy, Dy;
    double m = 0, minv = 0;

    bool dirX, dirY;

    nextint nextintx, nextinty;
    next nextx, nexty;

    x1 = ax[0];
    x2 = ax[1];
    y1 = ay[0];
    y2 = ay[1];

    dirX = x2 > x1;
    dirY = y2 > y1;

    // Tries to find the next integer of x/y
    // depending on their direction
    nextintx = dirX ? ceil : floor;
    nextinty = dirY ? ceil : floor;

    Dx = fabs(x2 - x1);
    Dy = fabs(y2 - y1);
    
    if (Dx == 0 && Dy == 0) {
    //Only a single point. Not a line segment
            if (ceil(x1) == x1 || ceil(y1) == y1)
                    printf("%f, %f\n", x1, y1);
            return 0;
    }

    if (Dx && Dy) {
            m = Dy/Dx; // slope
            minv = Dx/Dy; // Inverse of slope
    }

    // Tries to find the next point on x/y depending
    // on their direction (+ve or -ve)
    nextx = dirX ? add : sub;
    nexty = dirY ? add : sub;

    x = x1;
    y = y1;

#define morex(x)  (dirX ? (x <= x2) : (x >= x2))
#define morey(y)  (dirY ? (y <= y2) : (y >= y2))
#define more(x,y) (morex(x)) && (morey(y))

    while (more(x,y)) {
        // dx, dy values track the offsets from
        // current (x, y) coordinates respectively where
        // one of the two (x+dx, m*(x+dx)) or (minv*(y+dy), y+dy)
        // can be the desired coordinates(with integeral x/y)
        dx = fabs(nextintx(x) - x);
        dy = fabs(nextinty(y) - y);

        // We found the required (x,y) pair
        // and update their
        if (dx == 0 || dy == 0) {
            // Print the coordinates
            printf("%f, %f\n", x, y);

            // Possible offset for x/y to get integers
            dx = (dx == 0) ? 1 : dx;
            dy = (dy == 0) ? 1 : dy;
        } 

        // This is the main logic of this program.
        // The next possible pair can occur at either (x+dx, someY)
        // or (someX, y+dy). The below condition essentially checks
        // which is the closest one to the current (x,y) cooridnate.
        if (dx * Dy <= dy * Dx) {
            x  = nextx(x, dx);
            dy = dx * m;
            y = nexty(y, dy);
        } else {
            y = nexty(y, dy);
            dx = dy * minv;
            x = nextx(x, dx);
        }
    }
}

在循环中遍历一条线

Traversing through a line in a loop

c

loops

for-loop

geometry

computational-geometry