Utilisation de la géomésortinge accélérée pour vérifier si deux lignes ont une intersection

Est-il possible d’utiliser boost :: geometry pour vérifier si deux segments de droite (chacun donné par deux points en 2D) se coupent? Si cela est possible, boost :: geometry permet-il de vérifier également les cas spéciaux tels que seul un point est (numériquement) sur l’autre ligne ou que les deux lignes sont égales?

Si vous parlez spécifiquement de Boost.Geometry, l’API est bien entendu possible.

Votre code devrait ressembler à ceci

#include  #include  typedef boost::geometry::model::segment Segment; Segment AB( Point(x1,y1), Point(x2,y2) ); Segment CD; //similar code bool result = boost::geometry::intersects(AB, CD); 

Si vous avez besoin de points d’intersection:

 std::vector output; boost::geometry::intersection(AB, CD, output); 

Maintenant, la sortie aura 0, 1 ou 2 points, selon les emplacements.

Bien entendu, votre type de point doit être “conforme” aux concepts de Boost.Geometry. Le code suivant rend QPointF conforme:

 #include  BOOST_GEOMETRY_REGISTER_POINT_2D_GET_SET(QPointF, qreal, cs::cartesian, x, y, setX, setY); 

Vous demandez si deux lignes se croisent. Deux lignes se croisent toujours sauf si elles sont parallèles.

L’algorithme suivant vous aide à calculer si un segment coupe une ligne. Cela fonctionne comme suit: ayant les coordonnées de 3 points vous calculez le déterminant de

 x1 y1 1 x2 y2 1 x3 y3 1 

Où (x1; y1) et (x2; y2) sont le point représentant votre ligne et (x3; y3) représentent votre 3ème point (l’un des extrêmes de votre segment). Si le déterminant est positif, alors (x3; y3) est à droite du vecteur orienté de (x1; y1) à (x2; y2), s’il est négatif, il est à droite. Et si le déterminant est 0, le point est sur la ligne.

Ce que vous devez faire est d’appliquer cet algorithme deux fois, une fois pour une extrémité du segment et une fois pour l’autre. Si le produit des déterminants est négatif, il se croise, sinon il ne le fait pas.

Vous pouvez aller plus loin et calculer si deux segments se croisent. Il suffit d’appliquer deux fois la même idée, mais la deuxième fois, vos (x1; y1) et (x2; y2) seront les valeurs que vous avez utilisées pour (x3; y3) et votre nouvelle (x3; y3) votre old (x1; y1) et (x2; y2).

J’ai appris cet algorithme sous “algorithme de Sarrus”, alors peut-être googler pourrait-il donner une meilleure explication.

Vous pouvez essayer d’utiliser l’algorithme d’intersection . Si les lignes se croisent, la sortie sera non vide.

exemple pour les débutants sans l’utilisation de BOOST_GEOMETRY_REGISTER_POINT_2D_GET_SET

 namespace bg = boost::geometry; typedef bg::model::point point_t; typedef bg::model::segment segment_t; segment_t seg1(point_t(0.0, 0.0), point_t(5.0, 5.0)); segment_t seg2(point_t(10.0, 5.0), point_t(5.0, 0.0)); bool result = boost::geometry::intersects(seg1, seg2);