Intersecção de entidades geométricas

5

Eu estava tentando projetar uma pequena API geométrica C ++ para fins de aprendizado, mas me deparei com um problema ao lidar com interseções de entidades geométricas. Por exemplo, a interseção de uma linha e uma esfera pode ter três tipos diferentes: um par de pontos, um ponto ou nada. Eu encontrei várias maneiras de lidar com esse problema, mas não sei qual delas parece ser a melhor:

CGAL Object tipo de retorno

Primeiro tentei ver o que foi feito em outras bibliotecas geométricas. O mais completo que encontrei foi o CGAL. No CGAL, as funções de interseção retornam um Object , que é um tipo genérico que pode conter qualquer coisa (como boost::any ). Em seguida, você tenta atribuir o Object a um valor de outro tipo, aqui está um exemplo:

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 propósito, a função assign usa dynamic_cast para verificar se as duas variáveis são designáveis (todo mundo adora o RTTI).

Tipo de retorno da união

Uma união também pode ser usada como um tipo de retorno, mas significa usar um id para cada tipo geométrico e ter algum tipo de tipo de variante para cobrir todos os problemas.

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

Evitando o problema "sem interseção"

Para dividir o caso "sem interseção" do problema principal, algumas bibliotecas exigiam que o usuário verificasse se havia uma interseção antes de tentar descobrir qual era o tipo de retorno da interseção. Ficou assim:

Line line;
Sphere sphere;

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

Outra maneira de dividir o caso "sem interseção" do resto do problema seria usar um tipo optional :

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

Usando exceções para controlar o tipo "retorno"

Eu já posso ver alguns de vocês chorando.

No entanto, outra maneira de lidar com esse problema de ter diferentes tipos de retorno seria throw dos resultados, em vez de retorná-los. O retorno "sem interseção" ainda pode usar uma das técnicas do parágrafo anterior:

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?)

Ter um tipo de retorno "principal", jogando os outros

Outra forma seria ter um tipo de retorno "principal" para a interseção, digamos std::pair<Point, Point> e considerando os outros tipos de retorno como "excepcionais"; Isso dá mais significado ao uso de exceções, enquanto isso ainda não é uma boa gestão de erros. Por outro lado, pode parecer estranho lidar com um tipo "main" diferente dos outros ...

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.
    // ...
}

Eu propositalmente deixei a gestão de erros e o caso "sem interseção" fora deste último exemplo, já que muitas técnicas já descritas poderiam ser usadas para lidar com isso e eu não quero que o número de exemplos seja exponencial. Aqui está um deles:

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

Como os casos em que o resultado é lançado são excepcionais, ele não deve adicionar nenhuma sobrecarga de tempo de execução ao programa se o sistema subjacente usar exceções de custo zero em vez do antigo sistema de exceções SJLJ.

A pergunta atual

Bem, essa foi uma introdução bem longa, então aqui está a pergunta: existe uma solução idiomática para o problema nesses exemplos? E se não, há pelo menos alguns dos exemplos que poderiam ser banidos sem um segundo pensamento (bem, você poderia dar um segundo pensamento para os exemplos de exceção embora ...)?

Nota: algo parecia evidente para mim, mas aparentemente não é: a entidade retornada pela interseção entre duas entidades geométricas não está limitada a um nada, um ponto ou um conjunto de pontos. Uma interseção pode praticamente retornar qualquer entidade geométrica. Portanto, usar um contêiner para manter os valores não parece uma boa ideia.

Nota 2: nota da máquina do tempo, acontece. Depois de ter pensado nisso, eu baniria exceções (como a maioria das pessoas faria), não porque as exceções são inerentemente ruins ou não projetadas para isso, mas porque faz com que a expressão intersection(...) == SomeShape lance uma exceção mesmo quando os dois operandos deveriam ser igual, o que não é elegante. Eu acho que eu usaria um filho bastardo de uma variante.

    
por Morwenn 22.11.2013 / 16:23
fonte

3 respostas

4

Como você está trabalhando em uma API geométrica, eu acho que você não é apenas interessado na interseção de linhas e esferas, mas também tem mais projetos interessantes.

Uma abordagem natural para resolver seu problema de representar valores para interseção seria definir um tipo de figuras geométricas para que você pode representar:

  • Pontos
  • Linhas
  • Esferas
  • Interseções que você não pode computar (tipo de interseção simbólica)
  • União de números

Depois de ter feito isso, seu algoritmo de interseção pode engolir dois figuras e retornar uma figura, calculada usando

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

onde eu denoto a união por + e a interseção por . e onde A, B, C, D e os pontos podem ser um ponto, uma esfera, uma linha ou um interseção que você não pode calcular.

Até certo ponto, esta abordagem dá resultados satisfatórios e pode dar a sensação de que é a solução certa para o problema.

Existem, no entanto, muitos problemas com esta abordagem, que você deve estar ciente de:

  1. Intersecção que você não pode computar tende a absorver tudo, isto é, cruzando qualquer coisa com uma interseção que você não pode produz uma interseção que você não pode computar.

  2. Se você cruzar duas esferas, produz um círculo, que você não pode calcular, não porque você não pode encontrar o círculo que é, mas porque você não pode representar círculos. Se você optar por adicionar círculos para o seu vocabulário, você tem que descobrir como calcular interseções com todas as outras figuras que você possa ter. Então se você tem n valores base que você deve lidar com n ^ 2 tipo de interseções. Então, escolhendo um rico vocabulário de figuras sem confiar em '' interseções que você não pode computar '' não é uma opção.

  3. Mesmo se você restringir-se ao reino rassuring de algébrico figuras (definidas por equações polinomiais), computando interseções está longe de ser trivial. O que você está tentando fazer é computar conjunto mínimo de geradores do ideal reduzido definido pelo seu interseção, por isso não espere ser capaz de fazer isso em mais de um alguns exemplos. Você deve considerar qualquer coisa que seja capaz de calcular um acidente de sorte.

por 22.11.2013 / 17:30
fonte
2

as soluções que eu usaria ou teria visto são:

  1. use um container para retornar os pontos de interseção

    mais expansível para outras entidades geométricas que podem ter mais interseções, mas tem mais sobrecarga

  2. retorna pontos inválidos quando não há interseção

    você precisa ter um conceito de validade para o tipo de dados ou ter um optional type

  3. use uma função de retorno de chamada que é chamada toda vez que uma interseção é encontrada

    este permite o processamento específico sem a necessidade de recolher todos os pontos

os que eu proibiria BAN são aqueles que usam exceções, o tratamento de exceção é lento e muitas pessoas o crucificam por fazer isso

    
por 22.11.2013 / 16:42
fonte
1

Você listou muitas alternativas válidas, mas a mais direta está faltando:

Basta retornar a contagem de interseções e retornar os pontos por meio de um argumento de matriz. O argumento da matriz, é claro, tem um tamanho para ajustar a contagem máxima de interseções. Algo parecido com isto:

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

Isso é tão seguro ou inseguro quanto a abordagem union ou a que retorna pontos ilegais. No entanto, tem uma vantagem clara: você não força o código do usuário a diferenciar os três casos. I. e., Em vez de ter uma escada if-else ao longo das linhas

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

o site chamador pode optar por dizer

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

Isso não é possível se a contagem de interseções estiver de alguma forma codificada no tipo de retorno da função.

E, sim, eu também descartaria qualquer coisa com exceções sem pensar duas vezes. Eles são brutalmente lentos, a menos que sejam otimizados. E para otimização você precisaria divulgar o código de cálculo de interseção para o site de chamada.

    
por 06.05.2015 / 17:25
fonte