我想找到一条线(由起点和终点给出(与网格线(x=0,1,2,3...或y=0,1,2,3,...(的交叉。因此，交叉点的x还是y是整数。
我提出了以下代码，用于查找5.5,3.5和10.5,20.5点与网格(平行于x和y轴的线(的交点。
#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,%fn", 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,%fn", 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,%dn", (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,%dn", (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(的顺序找到的。
以下是您的问题的完整解决方案。假设我们当前处于坐标(x,y)，然后计算下一个整数与x, y的偏移量，并将其称为dx, dy。现在，下一个最近的点将是两个可能的点：
- (
x+dx，与Y相对应(或 - (SomeX，
y+dx(
现在我们的挑战是找到最接近的一个。斜率(Dy/Dx(实际上会帮助我们找到直线上下一个最近的斜率。
如果dx偏移给出了直线上下一个最近的点，则y坐标的相应偏移dy可以由dy = minv * dx计算。相反，如果dy是最接近的偏移，那么我们可以用dx = m * dy来计算dx。因此，我们实际上写了一个if语句，以找出两个可能的替代方案中哪一个是最接近的。就是这样。一旦我们找到下一个最近的点，我们就重复同样的过程，直到到达终点。但是，请注意以下浮点计算的局限性。当Dx或Dy几乎等于0时，则有效点的数目将变为无穷大。因此，您需要定义要计算的最大点的上限。因此，我没有在下面的代码中处理这些情况(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, %fn", 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, %fn", 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);
}
}
}