Intersezione di entità geometriche

5

Stavo provando a progettare una piccola API geometrica C ++ per scopi di apprendimento, ma ho riscontrato un problema quando si trattava di intersezioni di entità geometriche. Ad esempio, l'intersezione di una linea e di una sfera può avere tre diversi tipi: un paio di punti, un punto o niente. Ho trovato diversi modi per affrontare questo problema, ma non so quale di essi sembra essere il migliore:

CGAL Object tipo di ritorno

Prima ho provato a vedere cosa è stato fatto in altre librerie geometriche. Il più completo che ho trovato è stato CGAL. In CGAL, le funzioni di intersezione restituiscono un Object che è un tipo generico che può contenere qualsiasi cosa (come boost::any ). Quindi, provi ad assegnare Object a un valore di un altro tipo, ecco un esempio:

void foo(CGAL::Segment_2<Kernel> seg, CGAL::Line_2<Kernel> line)
{
    CGAL::Object result;
    CGAL::Point_2<Kernel> ipoint;
    CGAL::Segment_2<Kernel> iseg;

    result = CGAL::intersection(seg, line);
    if (CGAL::assign(ipoint, result)) {

        // handle the point intersection case.

    } else if (CGAL::assign(iseg, result)) {

        // handle the segment intersection case.

    } else {

       // handle the no intersection case.
    }
}

A proposito, la funzione assign usa dynamic_cast per verificare se le due variabili sono assegnabili (tutti amano RTTI).

Tipo di ritorno Unione

Un'unione può anche essere usata come un tipo di ritorno, ma significa usare un id per ogni tipo geometrico e avere una sorta di tipo di variante per coprire tutti i problemi.

struct Variant
{
    int id;
    union
    {
        Point point;
        std::pair<Point, Point> pair;
    };
};

int main()
{
    Point point;
    std::pair<Point, Point> pair;

    Variant v = intersection(Line{}, Sphere{});
    if (v.id == ID_POINT)
    {
        point = v.point;
        // Do something with point
    }
    else if (v.id == ID_VARIANT)
    {
        pair = v.pair;
        // Do something with pair
    }
    else
    {
        // No intersection
    }
}

Evitare il problema "nessuna intersezione"

Per dividere il caso "nessuna intersezione" dal problema principale, alcune librerie richiedevano che l'utente verificasse se c'era un'intersezione prima di cercare di trovare quale fosse il tipo di ritorno dell'intersezione. Sembrava questo:

Line line;
Sphere sphere;

if (intersects(line, sphere))
{
    auto ret = intersection(line, sphere);
    // Do something with ret
}

Un altro modo per dividere il caso "nessuna intersezione" dal resto del problema sarebbe utilizzare un tipo optional :

std::optional<...> ret = intersection(Line{}, Sphere{});
if (ret)
{
    // Do something with ret
}

Utilizzo delle eccezioni per controllare il tipo di "ritorno"

Posso già vedere alcuni di voi piangere.

Ancora un altro modo per gestire il problema di avere diversi tipi di ritorno sarebbe di throw dei risultati invece di restituirli. Il ritorno "nessuna intersezione" potrebbe ancora utilizzare una delle tecniche del paragrafo precedente:

try
{
    intersection(Line{}, Sphere{});
}
catch (const Point& point)
{
    // Do something with point
}
catch (const std::pair<Point, Point>& pair)
{
    // Do something with pair
}
// Can still catch errors (or "no intersection" special type?)

Avere un tipo di ritorno "principale", lanciando gli altri

Un altro modo sarebbe avere un tipo di ritorno "principale" per l'intersezione, diciamo std::pair<Point, Point> e considerando gli altri tipi di ritorno come "eccezionali"; dà più significato all'utilizzo delle eccezioni, mentre questa non è ancora una gestione dell'errore. D'altra parte, potrebbe sembrare strano gestire un tipo "principale" in modo diverso rispetto agli altri ...

try
{
    auto pair = intersection(Line{}, Sphere{});
    // Do something with pair
}
catch (const Point& point)
{
    // The chances for a sphere and a line to meet at
    // a single point are so small that the case can
    // already be considered exceptional.
    // ...
}

Ho lasciato intenzionalmente la gestione degli errori e il caso di "nessuna intersezione" da quest'ultimo esempio poiché molte tecniche già descritte potrebbero essere utilizzate per gestirlo e non voglio che il numero di esempi sia esponenziale. Eccone uno però:

try
{
    // res is optional<pair<Point, Point>>
    if (auto res = intersection(Line{}, Sphere{}))
    {
        std::cout << "intersection: two points" << '\n'
                  << std::get<0>(*res).x() << " "
                  << std::get<0>(*res).y() << '\n'
                  << std::get<1>(*res).x() << " "
                  << std::get<1>(*res).y() << '\n';
    }
    else
    {
        std::cout << "no intersection" << '\n';
    }
}
catch (const Point& point)
{
    // Exceptional case
    std::cout << "intersection: one point" << '\n'
              << point.x() << " "
              << point.y() << '\n';
}

Poiché i casi in cui viene generato il risultato sono eccezionali, non dovrebbe aggiungere alcun sovraccarico di runtime al programma se il sistema sottostante utilizza eccezioni a costo zero invece del vecchio sistema di eccezioni SJLJ.

La domanda effettiva

Beh, questa è stata un'introduzione piuttosto lunga, quindi ecco la domanda: c'è una soluzione idiomatica al problema in questi esempi? E se no, ci sono almeno alcuni degli esempi che potrebbero essere vietati senza ripensamenti (beh, potresti dare un secondo pensiero agli esempi di eccezioni anche se ...)?

Nota: qualcosa mi è apparso evidente ma apparentemente non lo è: l'entità restituita dall'intersezione tra due entità geometriche non è limitata a un nulla, a un punto oa un insieme di punti. Un'intersezione può praticamente restituire qualsiasi entità geometrica. Pertanto, usare un contenitore per contenere i valori non sembra una buona idea.

Nota 2: time machine note, succede. Dopo aver riflettuto, vieterei le eccezioni (come farebbe la maggior parte delle persone), non perché le eccezioni siano intrinsecamente cattive o non progettate per questo, ma perché rendono l'espressione intersection(...) == SomeShape un'eccezione anche quando entrambi gli operandi dovrebbero essere uguale, che non è elegante. Suppongo che invece utilizzerei un figlio bastardo di una variante.

    
posta Morwenn 22.11.2013 - 16:23
fonte

3 risposte

4

Dato che stai lavorando su un'API geometrica, immagino che non sei solo interessato all'intersezione di linee e sfere, ma ne ha anche di più progetti entusiasmanti.

Un approccio naturale per risolvere il tuo problema di rappresentare i valori per l'intersezione sarebbe quella di definire un tipo per figure geometriche in modo che puoi rappresentare:

  • Punti
  • Righe
  • Spheres
  • Intersezioni che non puoi calcolare (tipo di intersezione simbolica)
  • Unione di figure

Dopo averlo fatto, il tuo algoritmo di intersezione può trarne due figure e restituisce una figura, calcolata usando

(A + B + ...). (C + D + ...) = A.C + A.D + B.C + B.D + ...

dove indico l'unione di + e l'intersezione di . e dove A, B, C, D e i punti possono essere un punto, una sfera, una linea o un punto intersezione che non puoi calcolare.

In un certo senso, questo approccio dà risultati soddisfacenti e può dare la sensazione che sia la soluzione giusta al problema.

Ci sono tuttavia molti problemi con questo approccio, che tu dovrebbe essere a conoscenza di:

  1. L'intersezione che non puoi calcolare tende ad assorbire tutto, intersecando qualsiasi cosa con un'intersezione che non puoi produce un incrocio che non puoi calcolare.

  2. Se intersechi due sfere, produce un cerchio, che non puoi calcola, non perché non riesci a trovare il cerchio che è, ma perché non puoi rappresentare cerchi. Se scegli di aggiungere cerchi al tuo vocabolario, devi capire come calcolare intersezioni con tutte le altre figure che potresti avere. Quindi se lo hai n figure di base che dovresti trattare con n ^ 2 tipo di intersezioni. Quindi, scegliendo un ricco vocabolario di figure senza affidarsi a "intersezioni che non è possibile calcolare" non è un'opzione.

  3. Anche se ti limiti al rassicurante regno dell'algebrico figure (definite da equazioni polinomiali), intersezioni di calcolo è tutt'altro che banale. Quello che stai cercando di fare è calcolare a insieme minimo di generatori dell'ideale ridotto definito dal tuo intersezione, quindi non aspettatevi di essere in grado di farlo su più di un alcuni esempi Dovresti considerare tutto ciò che sei in grado di calcolare come un fortunato incidente.

risposta data 22.11.2013 - 17:30
fonte
2

le soluzioni che vorrei utilizzare o che ho visto usate sono:

  1. usa un contenitore per restituire i punti di intersezione

    più espandibile per altre entità geometriche che potrebbero avere più intersezioni ma avere un sovraccarico in più

  2. restituisce punti non validi quando non ci sono intersezioni

    devi avere un concetto di validità per il tipo di dati o avere un optional type

  3. usa una funzione di callback che viene chiamata ogni volta che viene trovata un'intersezione

    questo consente un'elaborazione specifica senza la necessità di raccogliere tutti i punti

quelli che vorrei BAN inavvertitamente sono quelli che usano le eccezioni, la gestione delle eccezioni è lenta e molte persone con crocifiggere te per farlo

    
risposta data 22.11.2013 - 16:42
fonte
1

Hai elencato molte alternative valide, tuttavia manca quella lineare:

Basta restituire il conteggio delle intersezioni e restituire i punti tramite un argomento array. L'argomento dell'array, ovviamente, ha una dimensione adatta al conteggio massimo delle intersezioni. Qualcosa del genere:

size_t getIntersections(const Sphere& sphere, const Ray& ray, std::array<Point, 2>* intersections);

Questo è sicuro o pericoloso come l'approccio union o quello che restituisce punti illegali. Tuttavia, ha un chiaro vantaggio: non forzare il codice utente a distinguere tra i tre casi. I. e., Invece di avere una scala if-else lungo le linee

auto result = intersections(...);
if(/*no intersection*/) {
    ...
} else if(/*one intersection*/) {
    ...
} else /*two intersections*/ {
    ...
}

il sito chiamante può scegliere di dire

arrays<Point, 2> points;
for(size_t i = getIntersections(..., &points); i--; ) {
    /*code to handle points[i]*/
}

Questo non è possibile se il conteggio delle intersezioni è in qualche modo codificato nel tipo di ritorno della funzione.

E, sì, vorrei anche scartare qualsiasi cosa con eccezioni senza pensarci due volte. Sono brutalmente lenti a meno che non siano ottimizzati. E per l'ottimizzazione avresti bisogno di rivelare il codice di calcolo dell'intersezione al sito chiamante.

    
risposta data 06.05.2015 - 17:25
fonte

Leggi altre domande sui tag