aziz's questions

Preciso de um algoritmo para posicionar linhas em um conjunto de pontos em um ambiente 2D. O algoritmo deve identificar pontos colineares dentro de uma tolerância especificada e posicionar as linhas adequadamente. Cada linha resultante deve incluir sua posição, orientação e comprimento como parte da saída. Os pontos serão fornecidos em uma tabela, todos em ordem um após o outro.

Os pontos serão ordenados em sequência um após o outro, assim: Exemplo de posicionamento e ordem dos pontos

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

Aqui está um exemplo do que estou procurando: Exemplo de comportamento desejado

Você pode escrever o algoritmo em qualquer linguagem de sua preferência.

Atualmente, estou usando a área do triângulo formado por 3 pontos consecutivos para verificar se ela é menor que a tolerância. Isso funciona, mas não é perfeito. Preciso de um método mais robusto. Mostrarei abaixo alguns dos resultados que obtive e como eles são problemáticos.

Erros com este algoritmo:
1. Os pontos são quase perfeitamente colineares, mas quando há uma mudança de direção o algoritmo pensa que o próximo ponto ainda faz parte da sequência, devido à proximidade deles: Problema 1

2. O primeiro e o último ponto são considerados como formando uma linha, mas não o fazem devido ao espaço que há entre um e outro: Edição 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;
}