Pregunta Usar la geometría de impulso para verificar si dos líneas tienen una intersección


¿Es posible usar boost :: geometry para verificar si dos segmentos de línea (cada uno dado por dos puntos en 2D) se cruzan entre sí? Si esto es posible, ¿boost :: geometry permite verificar también casos especiales como que solo un punto es (numéricamente) en la otra línea, o que ambas líneas son iguales?


5
2017-11-08 19:41


origen


Respuestas:


Si está hablando específicamente sobre Boost.Geometry API, es, por supuesto, posible.

Tu código debería verse más o menos así

#include <boost/geometry/geometries/segment.hpp> 
#include <boost/geometry/algorithms/intersection.hpp>

typedef boost::geometry::model::segment<Point> Segment;
Segment AB( Point(x1,y1), Point(x2,y2) );
Segment CD; //similar code

bool result = boost::geometry::intersects(AB, CD);

Si necesita puntos de intersección:

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

Ahora la salida tendrá 0, 1 o 2 puntos, dependiendo de las ubicaciones.

Por supuesto, su tipo de punto debe ser "compatible" con los conceptos de Boost.Geometry. El siguiente código hará que QPointF sea compatible:

#include <boost/geometry/geometries/register/point.hpp>
BOOST_GEOMETRY_REGISTER_POINT_2D_GET_SET(QPointF, qreal, cs::cartesian, x, y, setX, setY);

8
2017-11-08 22:11



Usted pregunta si dos líneas se cruzan. Dos líneas siempre se cruzan a menos que sean paralelas.

El siguiente algoritmo le ayuda a calcular si un segmento cruza una línea. Funciona de la siguiente manera: teniendo las coordenadas de 3 puntos calcula el determinante de

x1 y1 1
x2 y2 1
x3 y3 1

Donde (x1; y1) y (x2; y2) son el punto que representa su línea y (x3; y3) representan su 3er punto (uno de los extremos de su segmento). Si el determinante es positivo, (x3; y3) está a la derecha del vector orientado desde (x1; y1) a (x2; y2); si es negativo, está a la derecha. Y si el determinante es 0, entonces el punto está en la línea.

Lo que tienes que hacer es aplicar este algoritmo dos veces una vez para un extremo del segmento y una vez para el otro, si el producto de los determinantes es negativo, se cruza, si no, no lo hace.

Puede ir más allá y calcular si dos segmentos se cruzan. Todo lo que tiene que hacer es aplicar la misma idea dos veces, solo que la segunda vez que su (x1; y1) y (x2; y2) serán los valores que usó para (x3; y3) y su nuevo (x3; y3) su viejo (x1; y1) y (x2; y2).

Aprendí este algoritmo en "Algoritmo de Sarrus", así que quizás buscar en Google podría dar una mejor explicación.


1
2017-11-08 19:55



Puedes intentar usar el algoritmo de intersección. Si las líneas se cruzan, el la salida no estará vacía.


0
2017-11-08 19:45



ejemplo para principiantes sin el uso de BOOST_GEOMETRY_REGISTER_POINT_2D_GET_SET

namespace bg = boost::geometry;

typedef bg::model::point<double, 2, bg::cs::cartesian> point_t;
typedef bg::model::segment<point_t> 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);

0
2018-01-06 19:50