题
假设二维平面中有两个点 (a , b)。给定这两个点,找到线段上与最接近它的每个点等距且距离最小的最大点的最佳方法是什么。
我使用 C#,但任何语言的示例都会有所帮助。
List<'points> FindAllPointsInLine(Point start, Point end, int minDistantApart)
{
// find all points
}
解决方案
将问题解释为:
- 点间
start
- 并点
end
- 之间均匀分布的点的最大数量是多少
minDistanceApart
那么,这相当简单:之间的长度 start
和 end
除以 minDistanceApart
, ,向下舍入负 1。(如果没有负 1,您最终得到的是端点之间的距离数,而不是中间的额外点数)
执行:
List<Point> FindAllPoints(Point start, Point end, int minDistance)
{
double dx = end.x - start.x;
double dy = end.y - start.y;
int numPoints =
Math.Floor(Math.Sqrt(dx * dx + dy * dy) / (double) minDistance) - 1;
List<Point> result = new List<Point>;
double stepx = dx / numPoints;
double stepy = dy / numPoints;
double px = start.x + stepx;
double py = start.y + stepy;
for (int ix = 0; ix < numPoints; ix++)
{
result.Add(new Point(px, py));
px += stepx;
py += stepy;
}
return result;
}
如果您想要所有点,包括起点和终点,那么您必须调整 for 循环,并在“start.x”和“start.y”处开始“px”和“py”。请注意,如果端点的准确性至关重要,您可能需要直接根据比率“ix / numPoints”执行“px”和“py”计算。
其他提示
我不确定我是否理解你的问题,但是你想像这样划分线段吗?
前:
A +--------------------+ B
后:
A +--|--|--|--|--|--|--+ B
“两条破折号”是您的最小距离吗?如果是这样,那么将有无数组满足该条件的点,除非您的最小距离可以精确地除以线段的长度。然而,可以通过如下方式获得这样的一组:
- 求直线的矢量参数方程
- 求总点数 (floor(length / minDistance) + 1)
- 从 0 到 n 循环 i,找到沿线的每个点(如果参数方程采用 t 从 0 到 1,则 t = ((float)i)/n)
编辑]在看到Jerryjvl的答复后,我认为您想要的代码就是这样:(用 Java 语言执行此操作)
List<Point> FindAllPointsInLine(Point start, Point end, float distance)
{
float length = Math.hypot(start.x - end.x, start.y - end.y);
int n = (int)Math.floor(length / distance);
List<Point> result = new ArrayList<Point>(n);
for (int i=0; i<=n; i++) { // Note that I use <=, not <
float t = ((float)i)/n;
result.add(interpolate(start, end, t));
}
return result;
}
Point interpolate(Point a, Point b, float t)
{
float u = 1-t;
float x = a.x*u + b.x*t;
float y = a.y*u + b.y*t;
return new Point(x,y);
}
[警告:代码尚未测试]
查找,将适合上线的点的数量。计算X和Y坐标的步骤和生成点。像这样:
lineLength = sqrt(pow(end.X - start.X,2) + pow(end.Y - start.Y, 2))
numberOfPoints = floor(lineLength/minDistantApart)
stepX = (end.X - start.X)/numberOfPoints
stepY = (end.Y - start.Y)/numberOfPoints
for (i = 1; i < numberOfPoints; i++) {
yield Point(start.X + stepX*i, start.Y + stepY*i)
}
不隶属于 StackOverflow