Kolizje dowolnego trójkąta z prostokątem (zaznaczanie trójkątów)
Logowanie
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zapomniałem hasła
» Forum » Programowanie » [C++] Wytwarzanie gier 2D

Kolizje dowolnego trójkąta z prostokątem (zaznaczanie trójkątów)

Ostatnio zmodyfikowano 2024-11-10 17:15
Autor Wiadomość
tBane
Temat założony przez niniejszego użytkownika
Kolizje dowolnego trójkąta z prostokątem (zaznaczanie trójkątów)
» 2024-11-10 14:46:40
Witam.
Piszę sobie grę. Potrzebuję wykrywać kolizje dowolnego trójkąta opisanego przez trzy punkty z prostokątem w celu wybierania obiektów poprzez zaznaczenie. To znaczy chciałbym zaznaczyć pewien obszar i wszystkie trójkątne obiekty wewnątrz tego zaznaczenia.. wybrać. Do tego właśnie potrzebuje algorytmu tej kolizji.
P-181867
DejaVu
» 2024-11-10 14:56:22
Zrób prostokątną otoczkę wokół trójkąta, czyli znajdź min i max dla współrzędnych wierzchołków trójkąta osobno w osi X oraz Y. To będzie prostokąt otaczający. Jeżeli te prostokąty się przecinają, to 'jest' kolizja w rozumieniu 'ten element chcę zaznaczyć'. Natomiast jeżeli chcesz zrobić 'precyzyjne' zaznaczanie, to musisz zaimplementować dodatkowy algorytm, który będzie wywoływany, gdy "prostokąty się przecinają". Wówczas uruchamiasz 'bardziej zaawansowany algorytm'. Takie 'dwuetapowe' wykrywanie kolizji jest popularne i wydaje mi się powszechnie stosowane. Prostokąty bardzo szybko i łatwo się wykrywa, natomiast wykrywanie przecięć linii pod różnymi kątami to już jest nieco więcej zabawy i znacznie więcej kosztuje obliczeniowo.
P-181868
tBane
Temat założony przez niniejszego użytkownika
» 2024-11-10 14:57:55
No dobra. Zrobię kolizję dwuetapową. Ale jak sprawdzić w takim razie przecięcia linii?
P-181869
DejaVu
» 2024-11-10 15:02:46
ChatGPT 4o:
Aby wykryć kolizję dowolnego trójkąta z prostokątem w SFML, możesz zastosować podejście dwuetapowe:

1. **Etap wstępny**: Oblicz prostokątną otoczkę trójkąta (ang. bounding box). Wykorzystaj minimalne i maksymalne wartości współrzędnych wierzchołków trójkąta do utworzenia prostokąta, który go otacza. Następnie sprawdź, czy ten prostokąt przecina się z prostokątem zaznaczenia. Jeśli nie ma przecięcia, odrzuć trójkąt.

2. **Etap dokładniejszy**: Jeśli otoczka prostokątna trójkąta przecina się z zaznaczeniem, wykonaj bardziej szczegółowe sprawdzenie kolizji:
   - Sprawdź, czy dowolny z wierzchołków trójkąta znajduje się wewnątrz prostokąta zaznaczenia.
   - Oblicz przecięcia pomiędzy bokami trójkąta a krawędziami prostokąta zaznaczenia, co wymaga wykorzystania funkcji do sprawdzania przecięć odcinków.

Przykładowa implementacja do sprawdzenia przecięcia dwóch odcinków może wyglądać tak:

```cpp
struct Point {
    float x, y;
};

bool onSegment(Point p, Point q, Point r) {
    return q.x <= std::max(p.x, r.x) && q.x >= std::min(p.x, r.x) &&
           q.y <= std::max(p.y, r.y) && q.y >= std::min(p.y, r.y);
}

int orientation(Point p, Point q, Point r) {
    float val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0; // kolinearne
    return (val > 0) ? 1 : 2; // 1 = zgodnie ze wskazówkami zegara, 2 = przeciwnie
}

bool doIntersect(Point p1, Point q1, Point p2, Point q2) {
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    if (o1 != o2 && o3 != o4) return true;

    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false;
}
```

Funkcja `doIntersect` sprawdza, czy dwa odcinki (p1, q1) oraz (p2, q2) przecinają się, co pozwala dokładnie określić kolizję.

Natomiast nie jestem przekonany czy to poprawny algorytm do wykrywania przecięć linii, więc będziesz musiał poczytać/poeksperymentować.
P-181870
DejaVu
» 2024-11-10 15:12:52
Nawet działa:
C/C++
#include <SFML/Graphics.hpp>
#include <iostream>
#include <cmath>

struct Point {
    float x, y;
};

bool onSegment( Point p, Point q, Point r ) {
    return q.x <= std::max( p.x, r.x ) && q.x >= std::min( p.x, r.x ) &&
    q.y <= std::max( p.y, r.y ) && q.y >= std::min( p.y, r.y );
}

int orientation( Point p, Point q, Point r ) {
    float val =( q.y - p.y ) *( r.x - q.x ) -( q.x - p.x ) *( r.y - q.y );
    if( val == 0 ) return 0; // kolinearne
   
    return( val > 0 ) ? 1
        : 2; // 1 = zgodnie ze wskazówkami zegara, 2 = przeciwnie
}

bool doIntersect( Point p1, Point q1, Point p2, Point q2 ) {
    int o1 = orientation( p1, q1, p2 );
    int o2 = orientation( p1, q1, q2 );
    int o3 = orientation( p2, q2, p1 );
    int o4 = orientation( p2, q2, q1 );
   
    if( o1 != o2 && o3 != o4 ) return true;
   
    if( o1 == 0 && onSegment( p1, p2, q1 ) ) return true;
   
    if( o2 == 0 && onSegment( p1, q2, q1 ) ) return true;
   
    if( o3 == 0 && onSegment( p2, p1, q2 ) ) return true;
   
    if( o4 == 0 && onSegment( p2, q1, q2 ) ) return true;
   
    return false;
}

// Klasa reprezentująca linię z funkcją obrotu
class Line {
public:
    Line( sf::Vector2f start, float length, float rotationSpeed )
        : startPosition( start )
        , length( length )
        , rotationSpeed( rotationSpeed )
        , angle( 0 )
    {
        vertices[ 0 ] = sf::Vertex( startPosition );
        vertices[ 1 ] = sf::Vertex( sf::Vector2f( startPosition.x + length, startPosition.y ) );
    }
   
    void update() {
        angle += rotationSpeed;
        float cosAngle = std::cos( angle );
        float sinAngle = std::sin( angle );
        vertices[ 1 ].position = sf::Vector2f(
        startPosition.x + length * cosAngle,
        startPosition.y + length * sinAngle
        );
    }
   
    // Zwraca wierzchołki linii do rysowania
    sf::Vertex * getVertices() { return vertices; }
   
    // Zwraca punkty końcowe jako strukturę Point do detekcji kolizji
    Point getStartPoint() const { return { vertices[ 0 ].position.x, vertices[ 0 ].position.y }; }
    Point getEndPoint() const { return { vertices[ 1 ].position.x, vertices[ 1 ].position.y }; }
   
    // Ustawia kolor linii
    void setColor( const sf::Color & color ) {
        vertices[ 0 ].color = color;
        vertices[ 1 ].color = color;
    }
   
private:
    sf::Vector2f startPosition;
    float length;
    float rotationSpeed;
    float angle;
    sf::Vertex vertices[ 2 ];
};

int main() {
    sf::RenderWindow window( sf::VideoMode( 800, 600 ), "Line Intersection Test" );
    window.setFramerateLimit( 60 );
   
    // Linie z różnymi punktami początkowymi, długościami i prędkościami obrotu
    Line line1( sf::Vector2f( 400, 300 ), 150, 0.02f );
    Line line2( sf::Vector2f( 450, 350 ), 150, 0.03f );
   
    while( window.isOpen() ) {
        sf::Event event;
        while( window.pollEvent( event ) ) {
            if( event.type == sf::Event::Closed )
                 window.close();
           
        }
       
        // Aktualizacja położenia linii
        line1.update();
        line2.update();
       
        // Sprawdzenie kolizji między liniami
        if( doIntersect( line1.getStartPoint(), line1.getEndPoint(),
        line2.getStartPoint(), line2.getEndPoint() ) ) {
            line1.setColor( sf::Color::Green );
            line2.setColor( sf::Color::Green );
        }
        else {
            line1.setColor( sf::Color::Red );
            line2.setColor( sf::Color::Red );
        }
       
        // Rysowanie
        window.clear();
        window.draw( line1.getVertices(), 2, sf::Lines );
        window.draw( line2.getVertices(), 2, sf::Lines );
        window.display();
    }
   
    return 0;
}
P-181871
tBane
Temat założony przez niniejszego użytkownika
» 2024-11-10 15:58:25
Ok. Dzieki. Spróbuję jeszcze jednej metody tzn wymyśliłem algorytm z wykorzystaniem y=ax+b. Jak moja nie zadziała to skorzystam z tej, którą podałeś. Jak mój algorytm będzie działał to się nim podzielę
P-181872
DejaVu
» 2024-11-10 16:01:34
Spoko, ale ja pamiętam, że dawno temu jak implementowałem algorytm do wykrywania czy odcinki się przecinają, to był on wielokrotnie dłuższy, więc ta implementacja skoro 'o dziwo' działa, to bym jej używał na Twoim miejscu :)

Tu masz bardziej ucywilizowany kod, który 'wydziela' algorytmikę kolizji 'linii' do dedykowanej klasy.
C/C++
class Line {
public:
    sf::Vector2f start;
    sf::Vector2f end;
   
    Line( const sf::Vector2f & _start, const sf::Vector2f & _end )
        : start( _start )
        , end( _end )
    { }
   
    // Funkcja sprawdzająca, czy linia przecina się z inną linią
    bool intersects( const Line & _other ) const {
        // Jeśli jedna z linii jest punktem, zwracamy false
        if( start == end || _other.start == _other.end ) {
            return false;
        }
        return doIntersect( start, end, _other.start, _other.end );
    }
   
private:
    bool onSegment( const sf::Vector2f & _p, const sf::Vector2f & _q, const sf::Vector2f & _r ) const {
        return _q.x <= std::max( _p.x, _r.x ) && _q.x >= std::min( _p.x, _r.x ) &&
        _q.y <= std::max( _p.y, _r.y ) && _q.y >= std::min( _p.y, _r.y );
    }
   
    int orientation( const sf::Vector2f & _p, const sf::Vector2f & _q, const sf::Vector2f & _r ) const {
        float val =( _q.y - _p.y ) *( _r.x - _q.x ) -( _q.x - _p.x ) *( _r.y - _q.y );
        if( val == 0 ) return 0; // kolinearne
       
        return( val > 0 ) ? 1
            : 2; // 1 = zgodnie ze wskazówkami zegara, 2 = przeciwnie
    }
   
    bool doIntersect( const sf::Vector2f & _p1, const sf::Vector2f & _q1, const sf::Vector2f & _p2, const sf::Vector2f & _q2 ) const {
        int o1 = orientation( _p1, _q1, _p2 );
        int o2 = orientation( _p1, _q1, _q2 );
        int o3 = orientation( _p2, _q2, _p1 );
        int o4 = orientation( _p2, _q2, _q1 );
       
        if( o1 != o2 && o3 != o4 ) return true;
       
        if( o1 == 0 && onSegment( _p1, _p2, _q1 ) ) return true;
       
        if( o2 == 0 && onSegment( _p1, _q2, _q1 ) ) return true;
       
        if( o3 == 0 && onSegment( _p2, _p1, _q2 ) ) return true;
       
        if( o4 == 0 && onSegment( _p2, _q1, _q2 ) ) return true;
       
        return false;
    }
};


Kompletny przykład:

C/C++
#include <SFML/Graphics.hpp>
#include <cmath>
#include <algorithm>

class Line {
public:
    sf::Vector2f start;
    sf::Vector2f end;
   
    Line( const sf::Vector2f & _start, const sf::Vector2f & _end )
        : start( _start )
        , end( _end )
    { }
   
    // Funkcja sprawdzająca, czy linia przecina się z inną linią
    bool intersects( const Line & _other ) const {
        // Jeśli jedna z linii jest punktem, zwracamy false
        if( start == end || _other.start == _other.end ) {
            return false;
        }
        return doIntersect( start, end, _other.start, _other.end );
    }
   
private:
    bool onSegment( const sf::Vector2f & _p, const sf::Vector2f & _q, const sf::Vector2f & _r ) const {
        return _q.x <= std::max( _p.x, _r.x ) && _q.x >= std::min( _p.x, _r.x ) &&
        _q.y <= std::max( _p.y, _r.y ) && _q.y >= std::min( _p.y, _r.y );
    }
   
    int orientation( const sf::Vector2f & _p, const sf::Vector2f & _q, const sf::Vector2f & _r ) const {
        float val =( _q.y - _p.y ) *( _r.x - _q.x ) -( _q.x - _p.x ) *( _r.y - _q.y );
        if( val == 0 ) return 0; // kolinearne
       
        return( val > 0 ) ? 1
            : 2; // 1 = zgodnie ze wskazówkami zegara, 2 = przeciwnie
    }
   
    bool doIntersect( const sf::Vector2f & _p1, const sf::Vector2f & _q1, const sf::Vector2f & _p2, const sf::Vector2f & _q2 ) const {
        int o1 = orientation( _p1, _q1, _p2 );
        int o2 = orientation( _p1, _q1, _q2 );
        int o3 = orientation( _p2, _q2, _p1 );
        int o4 = orientation( _p2, _q2, _q1 );
       
        if( o1 != o2 && o3 != o4 ) return true;
       
        if( o1 == 0 && onSegment( _p1, _p2, _q1 ) ) return true;
       
        if( o2 == 0 && onSegment( _p1, _q2, _q1 ) ) return true;
       
        if( o3 == 0 && onSegment( _p2, _p1, _q2 ) ) return true;
       
        if( o4 == 0 && onSegment( _p2, _q1, _q2 ) ) return true;
       
        return false;
    }
};

// Klasa do rysowania linii i zarządzania kolorem, opakowująca obiekt Line
class DrawableLine {
public:
    DrawableLine( const sf::Vector2f & _start, const sf::Vector2f & _end, float _rotationSpeed )
        : line( _start, _end )
        , rotationSpeed( _rotationSpeed )
        , angle( 0 )
        , color( sf::Color::Red )
    { }
   
    void update() {
        // Obrót końca linii wokół punktu startowego
        angle += rotationSpeed;
        float cosAngle = std::cos( angle );
        float sinAngle = std::sin( angle );
       
        line.end = sf::Vector2f(
        line.start.x + length() * cosAngle,
        line.start.y + length() * sinAngle
        );
    }
   
    // Sprawdza przecięcie z inną linią
    bool intersects( const DrawableLine & _other ) const {
        return line.intersects( _other.line );
    }
   
    // Ustawia kolor linii
    void setColor( const sf::Color & _color ) {
        color = _color;
    }
   
    // Zwraca wierzchołki do rysowania
    sf::Vertex * getVertices() {
        vertices[ 0 ] = sf::Vertex( line.start, color );
        vertices[ 1 ] = sf::Vertex( line.end, color );
        return vertices;
    }
   
private:
    Line line; // Instancja klasy Line do przechowywania punktów linii i detekcji kolizji
    float rotationSpeed;
    float angle;
    sf::Color color;
    sf::Vertex vertices[ 2 ];
   
    // Oblicza długość linii
    float length() const {
        return std::sqrt( std::pow( line.end.x - line.start.x, 2 ) + std::pow( line.end.y - line.start.y, 2 ) );
    }
};

int main() {
    sf::RenderWindow window( sf::VideoMode( 800, 600 ), "Line Intersection Test" );
    window.setFramerateLimit( 60 );
   
    // Linie do rysowania z różnymi punktami początkowymi, długościami i prędkościami obrotu
    DrawableLine line1( sf::Vector2f( 400, 300 ), sf::Vector2f( 550, 300 ), 0.02f );
    DrawableLine line2( sf::Vector2f( 450, 350 ), sf::Vector2f( 600, 350 ), 0.03f );
   
    while( window.isOpen() ) {
        sf::Event event;
        while( window.pollEvent( event ) ) {
            if( event.type == sf::Event::Closed )
                 window.close();
           
        }
       
        // Aktualizacja pozycji linii
        line1.update();
        line2.update();
       
        // Sprawdzenie kolizji między liniami
        if( line1.intersects( line2 ) ) {
            line1.setColor( sf::Color::Green );
            line2.setColor( sf::Color::Green );
        }
        else {
            line1.setColor( sf::Color::Red );
            line2.setColor( sf::Color::Red );
        }
       
        // Rysowanie linii
        window.clear();
        window.draw( line1.getVertices(), 2, sf::Lines );
        window.draw( line2.getVertices(), 2, sf::Lines );
        window.display();
    }
   
    return 0;
}
P-181873
DejaVu
» 2024-11-10 16:53:12
Jeszcze 'bonus' - ten kod umożliwi Ci weryfikację 'wzrokową' czy istnieją przypadki, w których wykrywanie przecięć 'linii' działa źle, bo 'przecinają' się np. pod jakimś specyficznym kątem. Przyda Ci się to, jeżeli planujesz implementować 'własną' wersję algorytmu.
C/C++
#include <SFML/Graphics.hpp>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime>

class Line {
public:
    sf::Vector2f start;
    sf::Vector2f end;
   
    Line( const sf::Vector2f & _start, const sf::Vector2f & _end )
        : start( _start )
        , end( _end )
    { }
   
    // Funkcja sprawdzająca, czy linia przecina się z inną linią
    bool intersects( const Line & _other ) const {
        if( start == end || _other.start == _other.end ) {
            return false;
        }
        return doIntersect( start, end, _other.start, _other.end );
    }
   
private:
    bool onSegment( const sf::Vector2f & _p, const sf::Vector2f & _q, const sf::Vector2f & _r ) const {
        return _q.x <= std::max( _p.x, _r.x ) && _q.x >= std::min( _p.x, _r.x ) &&
        _q.y <= std::max( _p.y, _r.y ) && _q.y >= std::min( _p.y, _r.y );
    }
   
    int orientation( const sf::Vector2f & _p, const sf::Vector2f & _q, const sf::Vector2f & _r ) const {
        float val =( _q.y - _p.y ) *( _r.x - _q.x ) -( _q.x - _p.x ) *( _r.y - _q.y );
        if( val == 0 ) return 0; // kolinearne
       
        return( val > 0 ) ? 1
            : 2; // 1 = zgodnie ze wskazówkami zegara, 2 = przeciwnie
    }
   
    bool doIntersect( const sf::Vector2f & _p1, const sf::Vector2f & _q1, const sf::Vector2f & _p2, const sf::Vector2f & _q2 ) const {
        int o1 = orientation( _p1, _q1, _p2 );
        int o2 = orientation( _p1, _q1, _q2 );
        int o3 = orientation( _p2, _q2, _p1 );
        int o4 = orientation( _p2, _q2, _q1 );
       
        if( o1 != o2 && o3 != o4 ) return true;
       
        if( o1 == 0 && onSegment( _p1, _p2, _q1 ) ) return true;
       
        if( o2 == 0 && onSegment( _p1, _q2, _q1 ) ) return true;
       
        if( o3 == 0 && onSegment( _p2, _p1, _q2 ) ) return true;
       
        if( o4 == 0 && onSegment( _p2, _q1, _q2 ) ) return true;
       
        return false;
    }
};

// Klasa do rysowania linii i zarządzania kolorem, opakowująca obiekt Line
class DrawableLine {
public:
    DrawableLine( const sf::Vector2f & _start, const sf::Vector2f & _end, float _rotationSpeed )
        : line( _start, _end )
        , rotationSpeed( _rotationSpeed )
        , angle( 0 )
        , color( sf::Color::Red )
    { }
   
    void update() {
        angle += rotationSpeed;
        float cosAngle = std::cos( angle );
        float sinAngle = std::sin( angle );
       
        line.end = sf::Vector2f(
        line.start.x + length() * cosAngle,
        line.start.y + length() * sinAngle
        );
    }
   
    bool intersects( const DrawableLine & _other ) const {
        return line.intersects( _other.line );
    }
   
    void setColor( const sf::Color & _color ) {
        color = _color;
    }
   
    sf::Vertex * getVertices() {
        vertices[ 0 ] = sf::Vertex( line.start, color );
        vertices[ 1 ] = sf::Vertex( line.end, color );
        return vertices;
    }
   
private:
    Line line;
    float rotationSpeed;
    float angle;
    sf::Color color;
    sf::Vertex vertices[ 2 ];
   
    float length() const {
        return std::sqrt( std::pow( line.end.x - line.start.x, 2 ) + std::pow( line.end.y - line.start.y, 2 ) );
    }
};

int main() {
    std::srand( static_cast < unsigned >( std::time( 0 ) ) );
   
    sf::RenderWindow window( sf::VideoMode( 800, 600 ), "Line Intersection Test" );
    window.setFramerateLimit( 60 );
   
    std::vector < DrawableLine > lines;
    for( int i = 0; i < 100; ++i ) {
        // Losowe pozycje początkowe linii
        sf::Vector2f start( static_cast < float >( std::rand() % 800 ), static_cast < float >( std::rand() % 600 ) );
        sf::Vector2f end( start.x + 100.0f, start.y ); // Stała długość, początkowo pozioma
        float rotationSpeed =( std::rand() % 101 - 50 ) / 5000.0f; // Losowa prędkość obrotu
       
        // Dodajemy nową linię do wektora
        lines.emplace_back( start, end, rotationSpeed );
    }
   
    while( window.isOpen() ) {
        sf::Event event;
        while( window.pollEvent( event ) ) {
            if( event.type == sf::Event::Closed )
                 window.close();
           
        }
       
        // Aktualizacja i reset koloru każdej linii
        for( auto & line: lines ) {
            line.update();
            line.setColor( sf::Color::Red ); // Domyślnie ustawiamy kolor na czerwony
        }
       
        // Sprawdzanie kolizji każdy z każdym
        for( std::size_t i = 0; i < lines.size(); ++i ) {
            for( std::size_t j = i + 1; j < lines.size(); ++j ) {
                if( lines[ i ].intersects( lines[ j ] ) ) {
                    lines[ i ].setColor( sf::Color::Green );
                    lines[ j ].setColor( sf::Color::Green );
                }
            }
        }
       
        // Rysowanie wszystkich linii
        window.clear();
        for( auto & line: lines ) {
            window.draw( line.getVertices(), 2, sf::Lines );
        }
        window.display();
    }
   
    return 0;
}
P-181875
« 1 » 2
  Strona 1 z 2 Następna strona
» Forum » Programowanie » [C++] Wytwarzanie gier 2D
© Wszelkie prawa zastrzeżone 2005-2024