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;
}