Fórmula para la intersección de segmentos. ¿Se cruzan las líneas: intersección de segmentos en un plano?

Se dan dos segmentos. El primero está dado por puntos. P 1 (x 1; y 1) Y P2 (x2;y2). El segundo está dado por puntos. P3 (x3;y3) Y P4 (x4;y4).

La posición relativa de los segmentos se puede comprobar mediante productos vectoriales:

Considere el segmento P3 P4 y puntos P 1 Y P2.

Punto P 1 se encuentra a la izquierda de la línea P3 P4, para ella el producto vectorial v 1 > 0, ya que los vectores están orientados positivamente.
Punto P2 ubicado a la derecha de la línea, para ello el producto vectorial v 2< 0 , ya que los vectores están orientados negativamente.

Para hacer el punto P 1 Y P2 se encuentran en lados opuestos de una línea recta P3 P4, es suficiente que se cumpla la condición v 1 v 2< 0 (los productos vectoriales tenían signos opuestos).

Se puede aplicar un razonamiento similar para el segmento P 1 P 2 y puntos P 3 Y P 4.

Así que si v 1 v 2< 0 Y v 3 v 4< 0 , entonces los segmentos se cruzan.

El producto cruzado de dos vectores se calcula mediante la fórmula:

Dónde:
hacha, sí- coordenadas del primer vector,
bx, por- coordenadas del segundo vector.

Ecuación de una recta que pasa por dos puntos diferentes especificados por sus coordenadas.

Sean dos puntos no coincidentes en una recta: P 1 con coordenadas ( x1 ;y1) Y P2 con coordenadas (x2; y2). En consecuencia, un vector con origen en el punto P 1 y terminar en un punto P2 tiene coordenadas (x 2 -x 1 , y 2 -y 1). Si P(x, y) es un punto arbitrario en una recta, entonces las coordenadas del vector P 1 P igual (x - x 1, y – y 1).

Usando el producto vectorial, la condición para la colinealidad de los vectores. P 1 P Y P 1 P 2 se puede escribir así:
|P 1 P ,P 1 P 2 |=0, es decir. (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
o
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

La última ecuación se reescribe de la siguiente manera:
hacha + por + c = 0, (1)
Dónde
a = (y 2 -y 1),
segundo = (x 1 -x 2),
c = x 1 (y 1 -y 2) + y 1 (x 2 -x 1)

Entonces, la línea recta se puede especificar mediante una ecuación de la forma (1).

¿Cómo encontrar el punto de intersección de líneas?
La solución obvia es resolver el sistema de ecuaciones lineales:

hacha 1 +por 1 =-c 1
hacha 2 +por 2 =-c 2 (2)

Introduzca símbolos:

Aquí D es el determinante del sistema, y Dx, Dy- determinantes resultantes de sustituir la columna de coeficientes de la correspondiente incógnita por una columna de términos libres. Si re ≠ 0, entonces el sistema (2) es definido, es decir, tiene solución única. Esta solución se puede encontrar usando las siguientes fórmulas: x 1 =D x /D, y 1 =D y /D, que se denominan fórmulas de Cramer. Un recordatorio rápido de cómo se calcula el determinante de segundo orden. El determinante distingue dos diagonales: la principal y la secundaria. La diagonal principal consta de elementos tomados en la dirección desde la esquina superior izquierda del determinante hasta la esquina inferior derecha. Diagonal lateral: desde la parte superior derecha hasta la parte inferior izquierda. El determinante de segundo orden es igual al producto de los elementos de la diagonal principal menos el producto de los elementos de la diagonal secundaria.

Punto de intersección

Se nos dan dos rectas, definidas por sus coeficientes y . Necesitas encontrar su punto de intersección o descubrir que las líneas son paralelas.

Solución

Si dos rectas no son paralelas, entonces se cortan. Para encontrar el punto de intersección, basta con crear un sistema de dos ecuaciones lineales y resolverlo:

Usando la fórmula de Cramer, inmediatamente encontramos una solución al sistema, que será la deseada punto de intersección:

Si el denominador es cero, es decir

entonces el sistema no tiene soluciones (directas paralelo y no coinciden) o tiene infinitos (directos fósforo). Si es necesario distinguir entre estos dos casos, hay que comprobar que los coeficientes de las rectas sean proporcionales con el mismo coeficiente de proporcionalidad que los coeficientes y , para lo cual basta con calcular los dos determinantes si ambos lo son; igual a cero, entonces las líneas coinciden:

Implementación

estructura pt(doble x, y;); línea de estructura (doble a, b, c;); EPS doble constante =1e-9; doble det (doble a, doble b, doble c, doble d)(retorno a * d - b * c;) bool intersección (línea m, línea n, pt y res)(doble zn = det (m.a, m.b, n.a , n.b);si(abs(zn)< EPS)returnfalse; res.x=- det (m.c, m.b, n.c, n.b)/ zn; res.y=- det (m.a, m.c, n.a, n.c)/ zn;returntrue;} bool parallel (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS;} bool equivalent (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS &&abs(det (m.a, m.c, n.a, n.c))< EPS &&abs(det (m.b, m.c, n.b, n.c))< EPS;}

Lección de la serie “ Algoritmos geométricos»

Hola querido lector.

Consejo 1: Cómo encontrar las coordenadas del punto de intersección de dos líneas.

Escribamos tres funciones nuevas más.

La función LinesCross() determinará si intersecarse si dos segmento. En él, la posición relativa de los segmentos se determina mediante productos vectoriales. Para calcular productos vectoriales, escribiremos una función: VektorMulti().

La función RealLess() se utilizará para implementar la operación de comparación "<” (строго меньше) для вещественных чисел.

Tarea 1. Dos segmentos están dados por sus coordenadas. Escribe un programa que determine ¿Se cruzan estos segmentos? sin encontrar el punto de intersección.

Solución
. El segundo está dado por puntos.

Considere el segmento y los puntos y .

El punto se encuentra a la izquierda de la recta, para ello el producto vectorial > 0, ya que los vectores están orientados positivamente.

El punto está ubicado a la derecha de la línea, para la cual el producto vectorial es < 0, так как векторы отрицательно ориентированы.

Para que los puntos y se encuentren en lados opuestos de la recta, es suficiente que se cumpla la condición< 0 (векторные произведения имели противоположные знаки).

Se puede realizar un razonamiento similar para el segmento y los puntos y .

Así que si , entonces los segmentos se cruzan.

Para comprobar esta condición se utiliza la función LinesCross() y para calcular productos vectoriales se utiliza la función VektorMulti().

ax, ay – coordenadas del primer vector,

bx, by – coordenadas del segundo vector.

Programa geometr4; (¿Se cruzan 2 segmentos?) Const _Eps: Real=1e-4; (precisión del cálculo) var x1,y1,x2,y2,x3,y3,x4,y4: real; var v1,v2,v3,v4: real;función RealLess(Const a, b: Real): booleano; (Estrictamente menos) comenzar RealLess:= b-a> _Eps end; Función (RealLess)VektorMulti(ax,ay,bx,by:real): real; (ax,ay - coordenadas a bx,by - coordenadas b) comenzar vektormulti:= ax*by-bx*ay; fin; Líneas de función Cruz (x1, y1, x2, y2, x3, y3, x4, y4: real): booleano; (¿Se cruzan los segmentos?) start v1:=vektormulti(x4-x3,y4-y3,x1-x3,y1-y3); v2:=vectormulti(x4-x3,y4-y3,x2-x3,y2-y3); v3:=vectormulti(x2-x1,y2-y1,x3-x1,y3-y1); v4:=vectormulti(x2-x1,y2-y1,x4-x1,y4-y1); si RealLess(v1*v2,0) y RealLess(v3*v4,0) (v1v2<0 и v3v4<0, отрезки пересекаются} then LinesCross:= true else LinesCross:= false end; {LinesCross}begin {main} writeln(‘Введите координаты отрезков: x1,y1,x2,y2,x3,y3,x4,y4’); readln(x1,y1,x2,y2,x3,y3,x4,y4); if LinesCross(x1,y1,x2,y2,x3,y3,x4,y4) then writeln (‘Да’) else writeln (‘Нет’) end.

Resultados de la ejecución del programa:

Ingrese las coordenadas de los segmentos: -1 1 2 2.52 2 1 -1 3
Sí.

Escribimos un programa que determina si los segmentos especificados por sus coordenadas se cruzan.

En la próxima lección crearemos un algoritmo que se puede utilizar para determinar si un punto se encuentra dentro de un triángulo.

Querido lector.

Ya se ha familiarizado con varias lecciones de la serie Algoritmos geométricos. ¿Está todo escrito de forma accesible? Estaré muy agradecido si deja comentarios sobre estas lecciones. Quizás todavía sea necesario mejorar algo.

Atentamente, Vera Gospodarets.

Se dan dos segmentos. El primero está dado por puntos. P 1 (x 1; y 1) Y P2 (x2;y2). El segundo está dado por puntos. P3 (x3;y3) Y P4 (x4;y4).

La posición relativa de los segmentos se puede comprobar mediante productos vectoriales:

Considere el segmento P3 P4 y puntos P 1 Y P2.

Punto P 1 se encuentra a la izquierda de la línea P3 P4, para ella el producto vectorial v 1 > 0, ya que los vectores están orientados positivamente.
Punto P2 ubicado a la derecha de la línea, para ello el producto vectorial v 2< 0 , ya que los vectores están orientados negativamente.

Para hacer el punto P 1 Y P2 se encuentran en lados opuestos de una línea recta P3 P4, es suficiente que se cumpla la condición v 1 v 2< 0 (los productos vectoriales tenían signos opuestos).

Se puede aplicar un razonamiento similar para el segmento P 1 P 2 y puntos P 3 Y P 4.

Así que si v 1 v 2< 0 Y v 3 v 4< 0 , entonces los segmentos se cruzan.

El producto cruzado de dos vectores se calcula mediante la fórmula:

Dónde:
hacha, sí— coordenadas del primer vector,
bx, por— coordenadas del segundo vector.

Ecuación de una recta que pasa por dos puntos diferentes especificados por sus coordenadas.

Sean dos puntos no coincidentes en una recta: P 1 con coordenadas ( x1 ;y1) Y P2 con coordenadas (x2; y2).

Intersección de líneas

En consecuencia, un vector con origen en el punto P 1 y terminar en un punto P2 tiene coordenadas (x 2 -x 1 , y 2 -y 1). Si P(x, y) es un punto arbitrario en una recta, entonces las coordenadas del vector P 1 P igual (x - x 1, y - y 1).

Usando el producto vectorial, la condición para la colinealidad de los vectores. P 1 P Y P 1 P 2 se puede escribir así:
|P 1 P,P 1 P 2 |=0, es decir. (x-x 1)(y 2 -y 1)-(y-y 1)(x 2 -x 1)=0
o
(y 2 -y 1)x + (x 1 -x 2)y + x 1 (y 1 -y 2) + y 1 (x 2 -x 1) = 0

La última ecuación se reescribe de la siguiente manera:
hacha + por + c = 0, (1)
Dónde
a = (y 2 -y 1),
segundo = (x 1 -x 2),
c = x 1 (y 1 -y 2) + y 1 (x 2 -x 1)

Entonces, la línea recta se puede especificar mediante una ecuación de la forma (1).

¿Cómo encontrar el punto de intersección de líneas?
La solución obvia es resolver el sistema de ecuaciones lineales:

hacha 1 +por 1 =-c 1
hacha 2 +por 2 =-c 2 (2)

Introduzca símbolos:

Aquí D es el determinante del sistema, y Dx, Dy— determinantes resultantes de sustituir la columna de coeficientes con la correspondiente incógnita por una columna de términos libres. Si re ≠ 0, entonces el sistema (2) es definido, es decir, tiene solución única. Esta solución se puede encontrar usando las siguientes fórmulas: x 1 =D x /D, y 1 =D y /D, que se denominan fórmulas de Cramer. Un recordatorio rápido de cómo se calcula el determinante de segundo orden. El determinante distingue dos diagonales: la principal y la secundaria. La diagonal principal consta de elementos tomados en la dirección desde la esquina superior izquierda del determinante hasta la esquina inferior derecha. Diagonal lateral: desde la parte superior derecha hasta la parte inferior izquierda. El determinante de segundo orden es igual al producto de los elementos de la diagonal principal menos el producto de los elementos de la diagonal secundaria.