I need an algorithm to position lines on a set of points in a 2D environment. The algorithm should identify collinear points within a specified tolerance and place lines accordingly. Each resulting line should include its position, orientation, and length as part of the output. Points will be given in a table all being in order one after the other.
The points will be ordered in a sequence one after the other, just like this: Example of points placement & order
Here’s an example of what I’m looking for: Example of desired behavior
You can write the algorithm in any language of your preference.
Currently, I am using the area of the triangle formed by 3 consecutive points to check if it is lower than the tolerance. This works, but it’s not perfect. I need a more robust method. I will show you below some of the results I get, and how they’re problematic.
Errors with this algorithm:
1. The points are almost perfectly colinear, but when there’s a change in direction the algorithm thinks that the next point is still part of the sequence, because of how close they are: Issue 1
2. The first & last point are considered to form a line, but they don’t because of how much space there is between one and the other: Issue 2
// Example input
const points = [
{ id: 1, Position: [-0.5882743, -1.6162703] },
{ id: 2, Position: [-0.256999224, -1.45751464] },
{ id: 3, Position: [0, -1.31999934] },
{ id: 4, Position: [0.215323642, -1.22116101] },
{ id: 5, Position: [0.410423964, -1.12763059] },
{ id: 6, Position: [0.599999726, -1.03922999] },
{ id: 7, Position: [0.758489013, -0.903932035] },
{ id: 8, Position: [0.827327669, -0.694210351] },
{ id: 9, Position: [0.883345604, -0.509999752] },
{ id: 10, Position: [0.939692199, -0.342020005] },
{ id: 11, Position: [1.00450349, -0.177121118] },
{ id: 12, Position: [1.05999959, 0] },
{ id: 13, Position: [1.12268031, 0.197958842] },
{ id: 14, Position: [1.202806, 0.437785536] },
{ id: 15, Position: [1.31635785, 0.759999573] },
{ id: 16, Position: [1.28695393, 1.0798825] },
{ id: 17, Position: [1.14416122, 1.36355829] }
];
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;
}
aziz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.