Struttura dei dati da utilizzare per il controllo della griglia rispetto al tempo ottimizzato?

Question

Struttura dei dati da utilizzare per il controllo della griglia rispetto al tempo ottimizzato?

#1 da (2 voti)

1

Mi sto chiedendo qui perché ritengo che questa domanda possa essere archiviata nella categoria "Algoritmo e concetti di struttura dei dati".

Sfondo: Mi è stato recentemente assegnato l'incarico di progettare e sviluppare un nuovo programma. Le specifiche sono ancora in fase di discussione e posso dire la mia, data la mia esperienza andrò per C ++ o C, anche a seconda dei requisiti hardware e legali (certificazione).

Uno dei problemi principali che devo risolvere in questo programma è controllare le collisioni tra una linea (2D o 3D) e una (nuovamente 2D o 3D). Sto cercando suggerimenti su quale tipo di strutture dati sarebbe ottimale (runtime saggio) per eseguire tali controlli e / o se c'è una panoramica dei possibili algoritmi con un confronto dei vari costi e benefici ad essi connessi?

Modifica Per indirizzare il commento Inutile, la griglia è un quadrato regolare ( x % 0.5 == 0 , uguale per y) e i segmenti sono diritti tra due punti noti (x_0, y_0) e (x_1,y_1) . Nel caso 3D dovrei aggiungere la coordinata z , ma queste proprietà rimarrebbero invariate. Il risultato dell'algorthm sarebbe l'elenco dei quadrati della griglia attraversati dalla linea.

Da quando ho fatto questa domanda, ho scoperto l'algoritmo Bresenham . L'output sarebbe quello che cerco, ma è ottimale o ci sono approcci migliori?

c++ c architecture

posta Federico 06.10.2015 - 13:55

fonte

1 risposta

Leggi altre domande sui tag c++ c architecture

Il DTO dovrebbe avere i validatori? Perché alcuni compilatori non sintetizzano le operazioni di spostamento per questo paragrafo in C ++ Primer 5th?

score 2 · Accepted Answer

L'algoritmo standard è 2D-DDA e 3D-DDA. Ciò restituisce ogni cella intersecata in una griglia 2D o 3D. L'algoritmo di Bresenham è più per il rendering di linee.

Pseudo-codice approssimativo per un raggio (per una linea basta fermarsi alla fine impostando minBoundary e maxBoundary come casella di delimitazione della linea.Questo fermerà sia dalla griglia che dalla fine):

var rayPosition = { x: 25, y: 25 };
var rayDirection = { x: 1, y: 1 };

var cellSize = 50;

var cell = { x: Math.floor(rayPosition.x / cellSize), y: Math.floor(rayPosition.y / cellSize) };

var step = { x: Math.sign(rayDirection.x), y: Math.sign(rayDirection.y) }; // sign returns -1, 0, or 1

var offsetFromAxis =
{
    x: step.x > 0 ? cellSize - (rayPosition.x - Math.floor(rayPosition.x / cellSize) * cellSize) : (rayPosition.x - Math.floor(rayPosition.x / cellSize) * cellSize),
    y: step.y > 0 ? cellSize - (rayPosition.y - Math.floor(rayPosition.y / cellSize) * cellSize) : (rayPosition.y - Math.floor(rayPosition.y / cellSize) * cellSize)
};
var tMax = { x: offsetFromAxis.x / Math.abs(rayDirection.x), y: offsetFromAxis.y / Math.abs(rayDirection.y) };
var tDelta = { x: cellSize / Math.abs(rayDirection.x), y: cellSize / Math.abs(rayDirection.y) };
var minBoundary = { x: -1, y: -1 }; // for a line just do something like (might be off by one):
/* var minBoundary =
{
    x: Math.max(0, Math.min(Math.floor(lineStart.x / cellSize), Math.floor(lineEnd.x / cellSize)) - 1,
    y: Math.max(0, Math.min(Math.floor(lineStart.y / cellSize), Math.floor(lineEnd.y / cellSize)) - 1
}
*/
var maxBoundary = { x: width + 1, y: height + 1 }; // for a line just do something like (might be off by one):
/* var maxBoundary =
{
    x: Math.min(width, Math.max(Math.floor(lineStart.x / cellSize), Math.floor(lineEnd.x / cellSize)) + 1,
    y: Math.min(height, Math.max(Math.floor(lineStart.y / cellSize), Math.floor(lineEnd.y / cellSize)) + 1
}
*/
var boundary = { x: step.x > 0 ? maxBoundary.x : minBoundary.x, y: step.y > 0 ? maxBoundary.y : minBoundary.y };
var cells = [];
do
{
    cells.push({ x: cell.x, y: cell.y });
    if (tMax.x < tMax.y)
    {
        cell.x += step.x;
        if (cell.x == boundary.x)
        {
            break;
        }
        tMax.x += tDelta.x;
    }
    else
    {
        cell.y += step.y;
        if (cell.y == boundary.y)
        {
            break;
        }
        tMax.y += tDelta.y;
    }
} while (true);

Il 3D-DDA è quasi identico aggiungendo un asse z. (Puoi trovare esempi anche online). L'unico grande cambiamento è l'istruzione if:

if (tMax.x < tMax.y)
{
    if (tMax.x < tMax.z)
    {
        // x
    }
    else
    {
        // z
    }
}
else
{
    if (tMax.y < tMax.z)
    {
        // y
    }
    else
    {
        // z
    }
}

Per quanto riguarda le strutture dati, puoi semplicemente usare una matrice 1D e indicizzarla con qualcosa di simile:

index = z * xDimensione * yDimensione + y * xDimensione + x;

Non sei sicuro di quale sia la tua applicazione esatta, ma dovrebbe essere sufficiente.