我需要一种算法来在 2D 环境中将线定位在一组点上。该算法应识别指定公差范围内的共线点并相应地放置线。每条生成的线都应包括其位置、方向和长度作为输出的一部分。点将按顺序一个接一个地列在表中。
这些点将按顺序一个接一个地排列，就像这样：点放置和顺序的示例
// Example input for testing
const table = [
{ Position: [0.849999487, -1.47224224] },
{ Position: [0.848479152, -1.01117814] },
{ Position: [0.842648506, -0.707066119] },
{ Position: [0.848704576, -0.489999771] },
{ Position: [0.845723033, -0.307818025] },
{ Position: [0.846934378, -0.149337426] },
{ Position: [0.859999716, 0] },
{ Position: [0.846934378, 0.149337381] },
{ Position: [0.845723033, 0.307817996] },
{ Position: [0.848704517, 0.489999801] },
{ Position: [0.842648506, 0.707066059] },
{ Position: [0.848479271, 1.01117814] },
{ Position: [0.599999666, 1.03923011] },
{ Position: [0.376222014, 1.03366148] },
{ Position: [0.184067041, 1.04389584] },
{ Position: [0, 1.0399996] },
{ Position: [-0.184066996, 1.04389584] },
{ Position: [-0.376221985, 1.03366148] },
{ Position: [-0.599999726, 1.03922999] },
{ Position: [-0.874190629, 1.04181993] },
{ Position: [-1.24099123, 1.04131532] }
];
以下是我所寻找的示例：期望行为的示例
您可以使用您喜欢的任何语言编写算法。
目前，我正在使用由 3 个连续点形成的三角形的面积来检查它是否低于公差。这有效，但并不完美。我需要一种更强大的方法。我将在下面向您展示我得到的一些结果，以及它们存在的问题。
该算法的错误：
1. 这些点几乎完全共线，但当方向发生变化时，算法认为下一个点仍然是序列的一部分，因为它们非常接近：问题 1
2. 第一个点和最后一个点被视为形成一条线，但由于它们之间有很大空间，所以它们并不构成一条线：问题 2
function getBoundaryWalls2(points) {
const COLLINEAR_TOLERANCE = 0.05; // How strict the line detection is
const MIN_LINE_LENGTH = 1; // Minimum length for a valid line
const walls = [];
// Checks if 3 points form a nearly straight line by calculating triangle area
function areCollinear(p1, p2, p3) {
const x1 = p1.position.x, y1 = p1.position.y;
const x2 = p2.position.x, y2 = p2.position.y;
const x3 = p3.position.x, y3 = p3.position.y;
// If area of triangle is near 0, points are almost collinear
const area = Math.abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2);
return area < COLLINEAR_TOLERANCE;
}
// Gets angle between two points in degreesS
function getAngle(p1, p2) {
const dx = p2.position.x - p1.position.x;
const dy = p2.position.y - p1.position.y;
return (Math.atan2(dy, dx) * 180 / Math.PI);
}
// Gets distance between two points
function getDistance(p1, p2) {
const dx = p2.position.x - p1.position.x;
const dy = p2.position.y - p1.position.y;
return Math.sqrt(dx * dx + dy * dy);
}
let i = 1;
while (i < points.length - 1) {
// Start a new potential line with two points
const currentLine = {
startPoint: points[i],
endPoint: points[i + 1],
points: [points[i], points[i + 1]]
};
// Try to extend the line by adding more collinear points
let j = i + 2;
while (j < points.length) {
if (areCollinear(currentLine.startPoint, currentLine.endPoint, points[j])) {
currentLine.endPoint = points[j];
currentLine.points.push(points[j]);
j++;
} else {
break;
}
}
// If line is long enough, create a wall
const length = getDistance(currentLine.startPoint, currentLine.endPoint);
if (length >= MIN_LINE_LENGTH) {
// Calculate wall center
const centerX = (currentLine.startPoint.position.x + currentLine.endPoint.position.x) / 2;
const centerY = (currentLine.startPoint.position.y + currentLine.endPoint.position.y) / 2;
// Get wall orientation
const orientation = getAngle(currentLine.startPoint, currentLine.endPoint);
// Create wall object
const wall = {
position: { x: centerX, y: centerY },
orientation: orientation,
length: length,
points: currentLine.points
};
walls.push(wall);
}
// Skip to next unprocessed point
i += currentLine.points.length - 1;
}
return walls;
}
这是我的 C++ 代码，用于检查一条线上的三个点
这是我使用此方法在点之间查找线的代码
这是从样本点产生的输出
完整的应用程序代码
完整的 VSCODE 项目位于https://github.com/JamesBremner/linify