Bienvenue, Invité. Merci de vous connecter ou de vous inscrire.
Avez-vous perdu votre e-mail d'activation ?

Auteur Sujet: Besoin d'aide pour un calcul d'intersection..  (Lu 8400 fois)

0 Membres et 1 Invité sur ce sujet

Slash94

  • Jr. Member
  • **
  • Messages: 89
    • Voir le profil
Besoin d'aide pour un calcul d'intersection..
« le: Juillet 23, 2017, 01:21:48 pm »
Salut à tous :-)

Je viens vous voir car j'aimerais que vous me donniez la logique qui me permettrait de détecter si un carré est dans un champ de ligne..

Je m'explique, je souhaiterais faire en sorte que lorsque le rayon passe par le carré, que celui-ci devienne rouge et qu'il redevienne blanc lorsque ce n'est plus le cas, cela me semblait d'une simplicité enfantine à mettre en place, d'ailleurs ça doit être le cas sur le plan pratique, mais sur le plan calcul, je suis un peu perdu..

Idée du rendu que j'aimerais obtenir en collision ( mon code ne marche pas, j'ai colorié en rouge sur paint pour vous donner l'idée )



Hors collision :



Voici mon code ( il est dégueulasse et en un seul bloc, c'est juste un code de test à l'arrache pour trouver cet algo, justement !)

#include <iostream>
#include <math.h>
 
#include <SFML/Graphics.hpp>
 
const float PI = 3.14;
 
int main()
{
    sf::RenderWindow renderWindow(sf::VideoMode(800,600,32),"Raycasting Attempt", sf::Style::Titlebar);
    renderWindow.setFramerateLimit(60);
 
    ///COORDONNEES DU TRIANGLE///
    float pic = 15;
 
    ///VITESSE DE DEPLACEMENT///
    float speed = 3;
 
    ///POSITION DU TRIANGLE ET SON DIFFERENTIEL
    sf::Vector2f tPos;
    sf::Vector2i diff;
 
    sf::ConvexShape triangle(3);
 
    triangle.setPoint(0, sf::Vector2f(pic,NULL));
    triangle.setPoint(1, sf::Vector2f(pic*2,pic*2));
    triangle.setPoint(2, sf::Vector2f(NULL,pic*2));
 
    triangle.setOrigin(sf::Vector2f(pic, pic));
 
    ///LA LIGNE DE PROJECTION///
    sf::Vertex lineProjLeft[] =
    {
        sf::Vertex(sf::Vector2f(0,0)),
        sf::Vertex(sf::Vector2f(150,150))
    };
 
    ///LE CARRE DE TEST///
    sf::ConvexShape quad(4);
 
    quad.setPoint(0, sf::Vector2f(0,0));
    quad.setPoint(1, sf::Vector2f(25,0));
    quad.setPoint(2, sf::Vector2f(25,25));
    quad.setPoint(3, sf::Vector2f(0,25));
 
    quad.setPosition(sf::Vector2f(200,200));
 
    while (renderWindow.isOpen())
    {
        sf::Event event;
        while (renderWindow.pollEvent(event))
        {
            switch(event.type)
            {
            case sf::Event::Closed:
                renderWindow.close();
                break;
            case sf::Event::KeyReleased:
                if (event.key.code == sf::Keyboard::Escape)
                    renderWindow.close();
            break;
            }
        }
 
        ///DEPLACEMENT FLECHES///
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Up))
            tPos.y-=speed;
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Down))
            tPos.y+=speed;
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Left))
            tPos.x-=speed;
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Right))
            tPos.x+=speed;
 
        lineProjLeft[0].position.x = tPos.x;
        lineProjLeft[0].position.y = tPos.y;
 
        triangle.setPosition(tPos);
 
        ///CALCUL DU DIFFERENTIEL POUR L'ANGLE///
        diff.x = sf::Mouse::getPosition(renderWindow).x - tPos.x;
        diff.y = sf::Mouse::getPosition(renderWindow).y - tPos.y;
 
        float angle = (atan2(diff.x, diff.y)) * 180 / PI;
 
        triangle.setRotation(-(angle+180));
 
        lineProjLeft[1].position.x = sf::Mouse::getPosition(renderWindow).x;
        lineProjLeft[1].position.y = sf::Mouse::getPosition(renderWindow).y;
 
        if (lineProjLeft[1].position.x > quad.getPosition().x && lineProjLeft[0].position.x < quad.getPosition().x
            && lineProjLeft[1].position.y > quad.getPosition().y && lineProjLeft[0].position.y < quad.getPosition().y +25)
        {
            quad.setFillColor(sf::Color::Red);
        } else {
            quad.setFillColor(sf::Color::White);
        }
 
        renderWindow.clear();
 
        renderWindow.draw(triangle);
        renderWindow.draw(lineProjLeft, 2, sf::Lines);
        renderWindow.draw(quad);
 
        renderWindow.display();
    }
}

La longueur de la ligne dépend de la position de la souris, si vous avez AUSSI une idée également de comment stopper la longueur de la ligne dés qu'il rencontre le cube, je suis preneur, mais ce n'est pas ma préoccupation première ( celle-ci étant celle que j'ai mentionné au début ! )

Merci à vous pour votre précieuse aide :-)
« Modifié: Août 03, 2017, 09:38:01 pm par Slash94 »

Kernel panik

  • Newbie
  • *
  • Messages: 5
    • Voir le profil
    • E-mail
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #1 le: Juillet 23, 2017, 04:53:46 pm »
Bonjour ^_^

Il existe plusieurs façon de le faire. A mon avis le plus simple est de calculer le point d’intersection entre le rayon et les deux diagonales du carré.

Pour ce faire, tu peux utiliser une fonction qui calcul le point d'intersection entre deux segments A et B définit par leurs points A0, A1 et B0, B1 et retourne true s'il y a intersection ainsi que le point d'intersection dans le paramètre _intersects (pour limiter le tracé du rayon jusqu'à ce point)

bool Intersects (sf::Vector2f _A0, sf::Vector2f _A1, sf::Vector2f _B0, sf::Vector2f _B1, sf::Vector2f* _intersects)    
{
   float Aa = (_A1.y - _A0.y) / (_A1.x - _A0.x);
   float Ab = _A0.y - (Aa * _A0.x);

   float Ba = (_B1.y - _B0.y) / (_B1.x - _B0.x);
   float Bb = _B0.y - (Ba * _B0.x);

   if (Aa == Ba)
      return false;

   float x = (Bb - Ab) / (Aa - Ba);
   if (x < _A0.x || x > _A1.x)
      return false;

   if (x < _B0.x || x > _B1.x)
      return false;

   _intersects->x = x;
   _intersects->y = Aa * x + Ab;

   return true;
}
 

Ensuite, tu n'as plus qu'à faire une fonction qui l’appelle pour chaque diagonale.

bool Intersects(sf::Vector2f _A0, sf::Vector2f _A1, sf::FloatRect _rect, sf::Vector2f* _intersects)    
{
   if (Intersects(_A0, _A1, sf::Vector2f(_rect.left, _rect.top), sf::Vector2f(_rect.left + _rect.width, _rect.top + _rect.height), _intersects))
      return true;

   return Intersects(_A0, _A1, sf::Vector2f(_rect.left, _rect.top + _rect.height), sf::Vector2f(_rect.left + _rect.width, _rect.top), _intersects);
}
 

Tu peux sûrement optimiser ce code pour utiliser directement les variables que tu utilises mais ça te donne une idée.

Laurent

  • Administrator
  • Hero Member
  • *****
  • Messages: 32498
    • Voir le profil
    • SFML's website
    • E-mail
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #2 le: Juillet 23, 2017, 08:42:50 pm »
Citer
c'est juste un code de test à l'arrache pour trouver cet algo
Ce genre d'algorithmes simples ne s'inventent pas, ils se trouvent très facilement avec Google ;)
Laurent Gomila - SFML developer

Slash94

  • Jr. Member
  • **
  • Messages: 89
    • Voir le profil
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #3 le: Juillet 23, 2017, 09:20:02 pm »
Merci énormément Kernel Panik, je vais étudier ton code tout de suite !

Laurent > Salut à toi, quel type de mot-clefs pourrais-je taper sur Google pour avoir un résultat me rapprochant de ce que je désire faire ?

Laurent

  • Administrator
  • Hero Member
  • *****
  • Messages: 32498
    • Voir le profil
    • SFML's website
    • E-mail
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #4 le: Juillet 24, 2017, 07:56:22 am »
"ray rectangle intersection 2d" par exemple.
Laurent Gomila - SFML developer

Slash94

  • Jr. Member
  • **
  • Messages: 89
    • Voir le profil
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #5 le: Juillet 24, 2017, 01:27:11 pm »
Kernel Panik > j'ai essayé de passer en revue le code que tu as proposé à plusieurs reprises et je dois admettre que j'ai du mal à comprendre son fonctionnement, j'aimerais d'ores & déjà comprendre le fonctionnement d'une fonction avant de l'utiliser car je déteste copier-coller bêtement du code tout fait, j'ai pas le sentiment d'être capable de le refaire seul et je trouve ça frustrant.

J'ai trouvé exactement le principe que j'aimerais mettre en place ici :



Mais je trouve aucun cours de mathématiques qui vulgariserait au plus haut point ce type de calcul de manière à enseigner des non-initiés comme moi...

Kernel panik

  • Newbie
  • *
  • Messages: 5
    • Voir le profil
    • E-mail
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #6 le: Juillet 24, 2017, 04:48:48 pm »
En faite on ne fait pas une recherche d'intersection entre un rectangle et une droite mais entre deux segments.
Pour l'étendre à un rectangle, tu peux le faire sur les quatre fois (une fois pour chaque côté du rectangle) ou uniquement sur les diagonale pour gagner du temps de calcul. Ce qui peut être intéressant si tu as beaucoup de rectangles à tester
Cependant, en faisant le calcul sur les diagonales tu perds un peu en précision. La détection ne se fera pas dans certains cas particuliers où le rayon entre dans le rectangle mais s’arrête avant d'atteindre une diagonale. Ce qui n'est pas un problème dans le cas où le rayon à une portée « illimitée ».
De plus le point d'intersection retourné se trouve à l'intérieur du rectangle et non sur l'un des bords. Cela peut être gênant suivant l'ordre d'affichage.
A toi de voir ce que tu souhaites privilégier en fonction de tes besoins.

Pour ce qui est du calcul de l'intersection en lui même c'est juste un peu de maths ^_^
Il faut commencer par calculer les paramètres des équations des droites dont les segments font partie.
Donc j'ai un segment [A0 A1] qui fait partie de la droite d'équation y = Aa * x + Ab, et le segment [B0 B1] qui fait partie de la droite d'équation y = Ba * x + Bb. Tu peux adapter cette partie là si tu utilises des coordonnées polaires pour définir ton rayon à la place de deux points.
   float Aa = (_A1.y - _A0.y) / (_A1.x - _A0.x);
   float Ab = _A0.y - (Aa * _A0.x);

   float Ba = (_B1.y - _B0.y) / (_B1.x - _B0.x);
   float Bb = _B0.y - (Ba * _B0.x);

Ensuite on teste si la pente des droites ne sont pas les mêmes, si c'est le cas les droites sont parallèles il n'y aura donc pas d'intersection.
   if (Aa == Ba)
      return false;

Pour trouver l'intersection, il reste juste à résoudre un système de 2 équations 2 inconnues :
y = Aa * x + Ab
y = Ba * x + Bb
La solution étant :
   float x = (Bb - Ab) / (Aa - Ba);

Il reste alors à vérifier que le x trouvé pour le point d'intersection se trouve bien sur le segment et pas sur une le reste des droites. Dans le cas où tu aurais un rayon avec une portée illimitée il ne faudra faire ce test que pour le segment correspondant au rectangle.
   if (x < _A0.x || x > _A1.x)
      return false;

   if (x < _B0.x || x > _B1.x)
      return false;

Si c'est le cas tu peux alors calculer ton y et affecter le résultat au pointeur passé en paramètre
   _intersects->x = x;
   _intersects->y = Aa * x + Ab;


Voila, j'espère que ça répond à tes questions ^_^
« Modifié: Juillet 24, 2017, 04:57:16 pm par Kernel panik »

kimci86

  • Full Member
  • ***
  • Messages: 128
    • Voir le profil
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #7 le: Juillet 24, 2017, 08:39:17 pm »
@Kernel panik, attention aux divisions par zéro!

Pour le calcul d'intersection entre deux droites, il me semble plus lisible d'utiliser le déterminant.
J'avais fait comme ça dans un prototype en python. Il ne devrait pas être trop compliqué de l'adapter en C++.
def det(A, B):
    return A.x * B.y - A.y * B.x

def line_line_intersection(line0, line1):
    A, B = line0
    C, D = line1

    AB = B - A
    CD = D - C
    AC = C - A

    return A + det(AC, CD) / det(AB, CD) * AB

Il y a une explication ici : https://stackoverflow.com/a/565282

Comme il y a une division, il faut vérifier au préalable que det(AB, CD) est non nul, c'est à dire que les droites ne sont pas parallèles.

En partant de ça, tu peux tester l'intersection du rayon avec chaque côté du rectangle.

Slash94

  • Jr. Member
  • **
  • Messages: 89
    • Voir le profil
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #8 le: Juillet 25, 2017, 11:05:55 pm »
Bonsoir à toi Kernel, merci beaucoup pour ton obstination :-)

Je saisi d'ores & déjà davantage le concept, mais à quoi sert le Vector2f _intersects ? d'où vient-il ?

kimci86 > ta méthode à l'air plus archaïque ( et elle a le mérite de moins piquer les yeux :-P ) mais pourrais-tu me décrire davantage le fonctionnement de ton code ?
J'ai toujours été une daube en maths, j'ai une folle envie de m'y perfectionner mais j'ai beau multiplier les recherches sur Google ou Youtube, je ne tombe que sur des résolutions d'équations à base de

droite d1 : y = 2x-6
droite d2 : y = -5x+1


etc.. rien à voir avec mes repères à moi qui sont plutôt les suivants :

line1.x1 = 20
line1.y1 = 20
line1.x2 = 138
line1.y2 = 169

line2.x1 = 100
line2.y1 = 60
line2.x2 = 80
line2.y2 = 140

Je ne vois pas à quoi servent leurs " x " à tout bout de champs dans leurs explications...

Merci beaucoup à vous en tout cas les gars, j'attends avec impatience vos éclaircissements :-)

kimci86

  • Full Member
  • ***
  • Messages: 128
    • Voir le profil
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #9 le: Juillet 26, 2017, 01:44:10 am »
Je ne vois pas à quoi servent leurs " x " à tout bout de champs dans leurs explications...

C'est souvent la notation anglo-saxonne pour le produit vectoriel. Dans le post de Stack Overflow que j'ai cité, c'est défini au début comme la longueur (algébrique) de ce produit vectoriel, ce qui n'est autre que le déterminant de deux vecteurs dans le plan (cf. Wikipédia).

Voici plus d'explications sur mon code :
On a deux paires de points qui définissent les droites (A,B) et (C,D). On suppose donc A différent de B et C différent de D.
On suppose aussi que les droites se coupent en un point P (ie. les droites ne sont pas parallèles).
Le point P est sur la droite (AB) donc il existe un nombre réel alpha tel que
        P = A + alpha AB
Il suffit de calculer la valeur de alpha pour connaître P. Pour cela, il nous faut une équation : on va exploiter le fait que P est sur la droite (CD).
C'est là qu'intervient le déterminant. On exprime que le vecteur CP est colinéaire au vecteur CD par
        det(CP, CD) = 0
Pour faire apparaître alpha dans l'équation, on commence par faire apparaître AP en remplaçant CP dans l'expression par AP - AC.
        det(AP - AC, CD) = 0
Par linéarité du déterminant, det(AP - AC, CD) = det(AP, CD) - det(AC, CD), donc on obtient
        det(AP, CD) = det(AC, CD)
En remplaçant AP par alpha AB, on trouve
        alpha det(AB, CD) = det(AC, CD)
On a supposé que les droites (AB) et (CD) ne sont pas parallèles donc le déterminant det(AB, CD) est non nul.
        alpha = det(AC, CD) / det(AB, CD)
On a donc trouvé l'expression de P.
        P = A + det(AC, CD) / det(AB, CD) * AB

J'espère que ça t'aide.

Slash94

  • Jr. Member
  • **
  • Messages: 89
    • Voir le profil
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #10 le: Août 01, 2017, 09:30:10 am »
Salut à vous les gars ! Désolé de ne pas m'être manifesté plus tôt..!

Je vous remercie énormément pour vos contributions, je vais de ce pas étudier ça DE SUITE ! :-]



EDIT :

Alors voilà, pour simplifier le tout afin d'apprendre bien doucement, j'ai remplacé le carré par un autre segment, le but étant de trouver le point d'intersection entre le segment que je déplace moi-même avec la souris et le clavier et le second qui est placé par défaut pour le test.

J'ai tenté d'appliquer ton algo mais manifestement ça ne semble pas fonctionner correctement... l'intersection est détectée uniquement lorsque je suis dans une position précise :

Dans ces deux cas de figure, il ne se passe rien... ( voir consoles )



Ou encore



Mais quand je me place là, j'ai quelque chose ( voir console )



Voici mon code :

#include <iostream>
#include <math.h>

#include <SFML/Graphics.hpp>

const float PI = 3.14;

bool intersects(sf::Vector2f L1P1, sf::Vector2f L1P2, sf::Vector2f L2P1, sf::Vector2f L2P2,
                sf::Vector2f &coords);

int main()
{
    sf::RenderWindow renderWindow(sf::VideoMode(800,600,32),"Raycasting Attempt", sf::Style::Titlebar);
    renderWindow.setFramerateLimit(60);

    sf::Vector2f m_coords = sf::Vector2f(0,0);

    ///COORDONNEES DU TRIANGLE///
    float pic = 15;

    ///VITESSE DE DEPLACEMENT///
    float speed = 3;

    ///POSITION DU TRIANGLE ET SON DIFFERENTIEL
    sf::Vector2f tPos;
    sf::Vector2i diff;

    sf::ConvexShape triangle(3);

    triangle.setPoint(0, sf::Vector2f(pic,NULL));
    triangle.setPoint(1, sf::Vector2f(pic*2,pic*2));
    triangle.setPoint(2, sf::Vector2f(NULL,pic*2));

    triangle.setOrigin(sf::Vector2f(pic, pic));

    ///LA LIGNE DE PROJECTION///
    sf::Vertex lineProjLeft[] =
    {
        sf::Vertex(sf::Vector2f(0,0)),
        sf::Vertex(sf::Vector2f(150,150))
    };

    ///LA LIGNE DE TEST///

    sf::Vertex lineTest[] =
    {
        sf::Vertex(sf::Vector2f(100,180)),
        sf::Vertex(sf::Vector2f(220,120))
    };

    while (renderWindow.isOpen())
    {
        sf::Event event;
        while (renderWindow.pollEvent(event))
        {
            switch(event.type)
            {
            case sf::Event::Closed:
                renderWindow.close();
                break;
            case sf::Event::KeyReleased:
                if (event.key.code == sf::Keyboard::Escape)
                    renderWindow.close();
            break;
            }
        }

        ///DEPLACEMENT FLECHES///
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Up))
            tPos.y-=speed;
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Down))
            tPos.y+=speed;
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Left))
            tPos.x-=speed;
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Right))
            tPos.x+=speed;

        lineProjLeft[0].position.x = tPos.x;
        lineProjLeft[0].position.y = tPos.y;

        triangle.setPosition(tPos);

        ///CALCUL DU DIFFERENTIEL POUR L'ANGLE///
        diff.x = sf::Mouse::getPosition(renderWindow).x - tPos.x;
        diff.y = sf::Mouse::getPosition(renderWindow).y - tPos.y;

        float angle = (atan2(diff.x, diff.y)) * 180 / PI;

        triangle.setRotation(-(angle+180));

        lineProjLeft[1].position.x = sf::Mouse::getPosition(renderWindow).x;
        lineProjLeft[1].position.y = sf::Mouse::getPosition(renderWindow).y;

        if (intersects(lineProjLeft[0].position, lineProjLeft[1].position,
                       lineTest[0].position, lineTest[1].position, m_coords))
        {
            std::cout << " x : " << m_coords.x << std::endl;
            std::cout << " y : " << m_coords.y << std::endl;
        }

        renderWindow.clear();

        renderWindow.draw(triangle);
        renderWindow.draw(lineProjLeft, 2, sf::Lines);
        renderWindow.draw(lineTest, 2, sf::Lines);

        renderWindow.display();
    }
}

bool intersects(sf::Vector2f L1P1, sf::Vector2f L1P2, sf::Vector2f L2P1, sf::Vector2f L2P2,
                sf::Vector2f &coords)
{
    float P1 = (L1P2.x - L1P1.x) / (L1P2.y - L1P1.y);
    float PP1 = L1P1.y - (P1*L1P1.x);

    float P2 = (L2P2.x - L2P1.x) / (L2P2.y - L2P1.y);
    float PP2 = L2P1.y - (P1*L2P1.x);

    if (P1 == P2)
        return false;

    float x = (PP2 - PP1) / (P1 - P2);

    if (x<L1P1.x || x>L1P2.x)
        return false;

    if (x<L2P1.x || x>L2P2.x)
        return false;

    coords.x = x;
    coords.y = (P1 * x) + PP1;

    return true;
}
 

Merci encore de bien vouloir m'aider :-)
« Modifié: Août 01, 2017, 10:33:04 am par Slash94 »

kimci86

  • Full Member
  • ***
  • Messages: 128
    • Voir le profil
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #11 le: Août 01, 2017, 08:06:13 pm »
Si tu veux utiliser la méthode avec les pentes des droites, tu devras gérer le cas particulier de droites verticales. Je t'encourage à utiliser le déterminant, c'est moins bancal.

Sinon, il y a une erreur dans le calcul de PP2. (Trop de copier-coller !)

Slash94

  • Jr. Member
  • **
  • Messages: 89
    • Voir le profil
Re: Besoin d'aide pour un calcul de trajectoire...
« Réponse #12 le: Août 03, 2017, 09:37:43 pm »
Salut à toi Kimci,

J'ai beau avoir retourné Google, des forums francophones comme anglophones, des vidéos sur YouTube dans toutes les langues imaginables, je n'ai absolument RIEN trouvé de convaincant sur la manière dont effectuer un tel calcul avec des coordonnées de vecteurs tel que :
d1.x1, d1.y1, d1.x2, d1.y2 et d2.x1, d2.y1, d2.x2, d2.y2

J'aimerais réellement avoir une explication CLAIRE & NET ( si possible en français ) sur le FONCTIONNEMENT d'un tel calcul avec vraiment toutes les explications possibles sans théorie inutile & lourde..

La plupart des vidéos que je peux voir sur le net sont des résolutions d'équation scolaires qui n'ont aucun rapport avec le type de coordonnées que je veux utiliser moi...

kimci86

  • Full Member
  • ***
  • Messages: 128
    • Voir le profil
Re: Besoin d'aide pour un calcul d'intersection..
« Réponse #13 le: Août 04, 2017, 09:48:07 pm »
Je ne sais pas si tu veux plus d'explications sur comment faire ou pourquoi ça marche, mais dans la cas où tu demandes comment faire concrètement, j'ai bidouillé un programme d'exemple pour afficher le point d'intersection de deux segments et déplacer les extrémités des segments à la souris.

#include <SFML/Graphics.hpp>
#include <algorithm>

float det(const sf::Vector2f& v1, const sf::Vector2f& v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

float dot(const sf::Vector2f& v1, const sf::Vector2f& v2)
{
    return v1.x * v2.x + v1.y * v2.y;
}

float squaredLength(const sf::Vector2f& v)
{
    return dot(v, v);
}

float squaredDistance(const sf::Vector2f& v1, const sf::Vector2f& v2)
{
    return squaredLength(v2 - v1);
}

bool lineLine(const sf::Vector2f& A, const sf::Vector2f& B, const sf::Vector2f& C, const sf::Vector2f& D, sf::Vector2f& intersection)
{
    sf::Vector2f AB = B - A,
                 CD = D - C,
                 AC = C - A;

    float d = det(AB, CD);
    if(d)
    {
        intersection = A + det(AC, CD) / d * AB;
        return true;
    }
    else
        return false;
}

bool segmentSegment(const sf::Vector2f& A, const sf::Vector2f& B, const sf::Vector2f& C, const sf::Vector2f& D, sf::Vector2f& intersection)
{
    if(lineLine(A, B, C, D, intersection))
    {
        float u = dot(intersection - A, B - A),
              v = dot(intersection - C, D - C);
        return 0.f <= u && u <= squaredDistance(A, B) &&
               0.f <= v && v <= squaredDistance(C, D);
    }
    else
        return false;
}

int main()
{
    sf::CircleShape interCircle(16.f);
    interCircle.setOrigin(interCircle.getRadius(), interCircle.getRadius());
    interCircle.setFillColor(sf::Color::Transparent);
    interCircle.setOutlineColor(sf::Color::Red);
    interCircle.setOutlineThickness(1.f);

    sf::CircleShape draggedCircle = interCircle;
    draggedCircle.setOutlineColor(sf::Color::Green);
    sf::Vector2f* dragged = nullptr;

    // segments
    sf::VertexArray va(sf::Lines, 4);
    sf::Vector2f& A = va[0].position,
                & B = va[1].position,
                & C = va[2].position,
                & D = va[3].position;
    A = {100, 100};
    B = {700, 300};
    C = {200, 500};
    D = {600, 200};

    sf::RenderWindow window(sf::VideoMode(800, 600), "SFML window");
    window.setFramerateLimit(60.f);

    while(window.isOpen())
    {
        sf::Event event;
        while(window.pollEvent(event))
        {
            if(event.type == sf::Event::Closed)
                window.close();
            else if(event.type == sf::Event::MouseMoved)
            {
                sf::Vector2f mouse = window.mapPixelToCoords(sf::Vector2i(event.mouseMove.x, event.mouseMove.y));

                if(sf::Mouse::isButtonPressed(sf::Mouse::Left) && dragged)
                {
                    *dragged = mouse;
                    draggedCircle.setPosition(*dragged);
                }
                else
                {
                    sf::Vector2f* closest = std::min({&A, &B, &C, &D},
                    [&mouse](const sf::Vector2f* v1, const sf::Vector2f* v2)
                    {
                        return squaredDistance(*v1, mouse) < squaredDistance(*v2, mouse);
                    });

                    if(squaredDistance(mouse, *closest) <= draggedCircle.getRadius() * draggedCircle.getRadius())
                    {
                        dragged = closest;
                        draggedCircle.setPosition(*dragged);
                    }
                    else
                        dragged = nullptr;
                }
            }
        }

        sf::Vector2f intersection;
        bool found = segmentSegment(A, B, C, D, intersection);
        if(found)
            interCircle.setPosition(intersection);

        window.clear();
        window.draw(va);
        if(dragged)
            window.draw(draggedCircle);
        if(found)
            window.draw(interCircle);
        window.display();
    }

    return EXIT_SUCCESS;
}
 

Slash94

  • Jr. Member
  • **
  • Messages: 89
    • Voir le profil
Re: Besoin d'aide pour un calcul d'intersection..
« Réponse #14 le: Août 04, 2017, 11:18:18 pm »
Waaw..
Ton code est absolument SPLENDIDE !!!!! Merci infiniment !