Geometria Computacional

A geometria computacional é o nome dado à matéria de geometria abordada por dispositivos eletrônicos como o computador. Diversos algoritmos englobam a geometria computacional como intersecção de linhas, polígono, computação do fecho convexo dentre outros.

Pesquisadores

Joseph O'Rourke -> http://maven.smith.edu/~orourke/

Algoritmos

Código Base

Este codigo servira como base para algum dos algoritmos mais a frente

template <typename T>
struct Point{
    T x;
    T y;
 
    bool operator <(const Point &p2) const
    {
        return x < p2.x || (x == p2.x && y < p2.y);
    }
 
    Point<T> operator - (const Point &p) const
    {
        return { x - p.x, y - p.y };
    }
 
    Point<T> operator + (const Point &p) const
    {
        return { x + p.x, y + p.y };
    }
 
    float dot (const Point &p2) const
    {
        return p2.x * x + p2.y * y;
    }
 
    float length() const
    {
        return std::sqrt(x * x + y * y);
    }
};
 
template <typename T>
struct Rect {
    Point<T> p1;
    Point<T> p2;
 
    bool operator <(const Rect &r2) const
    {
        return p1 < r2.p1;
    }
 
    bool isInside(const Point<T> p) const
    {
        return p1.x <= p.x && p.x <= p2.x &&
                p1.y <= p.y && p.y <= p2.y;
    }
 
    bool contains(const Rect &r2) {
        return p1.x <= r2.p1.x && r2.p1.y <= p1.y &&
                p2.x >= r2.p2.x && p2.y >= r2.p2.y;
    }
 
    bool intersects( Rect<T> targetRect )
    {
        if( targetRect.p2.x < p1.x ) return false;
        if( targetRect.p2.y < p1.y ) return false;
 
        if( targetRect.p1.x > p2.x ) return false;
        if( targetRect.p1.y > p2.y ) return false;
 
        return true;
    }
};
 
template <typename T>
struct Triangle {
    Point<T> p1;
    Point<T> p2;
    Point<T> p3;
 
    bool isInside(const Point<T> p) const
    {
        using Vec = Point<T>;
        // Compute vectors
        Vec v0 = p2 - p1;
        Vec v1 = p3 - p1;
        Vec v2 = p - p1;
 
        // Compute dot products
        auto dot00 = v0.dot(v0);
        auto dot01 = v0.dot(v1);
        auto dot02 = v0.dot(v2);
        auto dot11 = v1.dot(v1);
        auto dot12 = v1.dot(v2);
 
        // Compute barycentric coordinates
        auto invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
        auto u = (dot11 * dot02 - dot01 * dot12) * invDenom;
        auto v = (dot00 * dot12 - dot01 * dot02) * invDenom;
 
        // Check if point is in triangle
        return (u >= 0) && (v >= 0) && (u + v <=1);
    }
};

Intersecções

TODO: colocar código

Bibliotecas

CGAL

Biblioteca com doversos algoritmos de geometria computacional
Link: https://www.cgal.org/

Lib2Geom

Biblioteca que nasceu da base de código do Inkscape
Link: https://github.com/inkscape/lib2geom

Links

http://blackpawn.com/texts/pointinpoly/ LInk explicando como verificar se um ponto está em um polígono