Dados los puntos A y B correspondientes a la línea AB y los puntos P y Q correspondientes a la línea PQ, encuentre el punto de intersección de estas líneas. Los puntos se dan en Plano 2D con sus Coordenadas X e Y. Ejemplos:
Input : A = (1, 1), B = (4, 4)
C = (1, 8), D = (2, 4)
Output : The intersection of the given lines
AB and CD is: (2.4, 2.4)
Input : A = (0, 1), B = (0, 4)
C = (1, 8), D = (1, 4)
Output : The given lines AB and CD are parallel.
En primer lugar, supongamos que tenemos dos puntos (x 1 , y 1 ) y (x 2 , y 2 ). Ahora, encontramos la ecuación de la línea formada por estos puntos. Sean las líneas dadas:
- un 1 x + segundo 1 y = do 1
- un 2 x + segundo 2 y = do 2
Ahora tenemos que resolver estas 2 ecuaciones para encontrar el punto de intersección. Para resolver, multiplicamos 1. por b 2 y 2 por b 1 Esto nos da, a 1 b 2 x + b 1 b 2 y = c 1 b 2 a 2 b 1 x + b 2 b 1 y = c 2 b 1 Restando estos obtenemos, (a 1 b 2 – a 2 b 1 ) x = c 1 b 2 – c 2 b 1Esto nos da el valor de x. Del mismo modo, podemos encontrar el valor de y. (x, y) nos da el punto de intersección. Nota: Esto da el punto de intersección de dos líneas, pero si nos dan segmentos de línea en lugar de líneas, también debemos volver a verificar que el punto así calculado realmente se encuentre en ambos segmentos de línea. Si el segmento de línea está especificado por los puntos (x 1 , y 1 ) y (x 2 , y 2 ), entonces para verificar si (x, y) está en el segmento, solo tenemos que verificar que
- mín (x 1 , x 2 ) <= x <= máx (x 1 , x 2 )
- mín (y 1 , y 2 ) <= y <= máx (y 1 , y 2 )
El pseudocódigo para la implementación anterior:
determinant = a1 b2 - a2 b1
if (determinant == 0)
{
// Lines are parallel
}
else
{
x = (c1b2 - c2b1)/determinant
y = (a1c2 - a2c1)/determinant
}
Estos se pueden derivar obteniendo primero la pendiente directamente y luego encontrando la intersección de la línea.
C++
// C++ Implementation. To find the point of
// intersection of two lines
#include <bits/stdc++.h>
using namespace std;
// This pair is used to store the X and Y
// coordinates of a point respectively
#define pdd pair<double, double>
// Function used to display X and Y coordinates
// of a point
void displayPoint(pdd P)
{
cout << "(" << P.first << ", " << P.second
<< ")" << endl;
}
pdd lineLineIntersection(pdd A, pdd B, pdd C, pdd D)
{
// Line AB represented as a1x + b1y = c1
double a1 = B.second - A.second;
double b1 = A.first - B.first;
double c1 = a1*(A.first) + b1*(A.second);
// Line CD represented as a2x + b2y = c2
double a2 = D.second - C.second;
double b2 = C.first - D.first;
double c2 = a2*(C.first)+ b2*(C.second);
double determinant = a1*b2 - a2*b1;
if (determinant == 0)
{
// The lines are parallel. This is simplified
// by returning a pair of FLT_MAX
return make_pair(FLT_MAX, FLT_MAX);
}
else
{
double x = (b2*c1 - b1*c2)/determinant;
double y = (a1*c2 - a2*c1)/determinant;
return make_pair(x, y);
}
}
// Driver code
int main()
{
pdd A = make_pair(1, 1);
pdd B = make_pair(4, 4);
pdd C = make_pair(1, 8);
pdd D = make_pair(2, 4);
pdd intersection = lineLineIntersection(A, B, C, D);
if (intersection.first == FLT_MAX &&
intersection.second==FLT_MAX)
{
cout << "The given lines AB and CD are parallel.\n";
}
else
{
// NOTE: Further check can be applied in case
// of line segments. Here, we have considered AB
// and CD as lines
cout << "The intersection of the given lines AB "
"and CD is: ";
displayPoint(intersection);
}
return 0;
}
Java
// Java Implementation. To find the point of
// intersection of two lines
// Class used to used to store the X and Y
// coordinates of a point respectively
class Point
{
double x,y;
public Point(double x, double y)
{
this.x = x;
this.y = y;
}
// Method used to display X and Y coordinates
// of a point
static void displayPoint(Point p)
{
System.out.println("(" + p.x + ", " + p.y + ")");
}
}
class Test
{
static Point lineLineIntersection(Point A, Point B, Point C, Point D)
{
// Line AB represented as a1x + b1y = c1
double a1 = B.y - A.y;
double b1 = A.x - B.x;
double c1 = a1*(A.x) + b1*(A.y);
// Line CD represented as a2x + b2y = c2
double a2 = D.y - C.y;
double b2 = C.x - D.x;
double c2 = a2*(C.x)+ b2*(C.y);
double determinant = a1*b2 - a2*b1;
if (determinant == 0)
{
// The lines are parallel. This is simplified
// by returning a pair of FLT_MAX
return new Point(Double.MAX_VALUE, Double.MAX_VALUE);
}
else
{
double x = (b2*c1 - b1*c2)/determinant;
double y = (a1*c2 - a2*c1)/determinant;
return new Point(x, y);
}
}
// Driver method
public static void main(String args[])
{
Point A = new Point(1, 1);
Point B = new Point(4, 4);
Point C = new Point(1, 8);
Point D = new Point(2, 4);
Point intersection = lineLineIntersection(A, B, C, D);
if (intersection.x == Double.MAX_VALUE &&
intersection.y == Double.MAX_VALUE)
{
System.out.println("The given lines AB and CD are parallel.");
}
else
{
// NOTE: Further check can be applied in case
// of line segments. Here, we have considered AB
// and CD as lines
System.out.print("The intersection of the given lines AB " +
"and CD is: ");
Point.displayPoint(intersection);
}
}
}
Python3
# Python program to find the point of
# intersection of two lines
# Class used to used to store the X and Y
# coordinates of a point respectively
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
# Method used to display X and Y coordinates
# of a point
def displayPoint(self, p):
print(f"({p.x}, {p.y})")
def lineLineIntersection(A, B, C, D):
# Line AB represented as a1x + b1y = c1
a1 = B.y - A.y
b1 = A.x - B.x
c1 = a1*(A.x) + b1*(A.y)
# Line CD represented as a2x + b2y = c2
a2 = D.y - C.y
b2 = C.x - D.x
c2 = a2*(C.x) + b2*(C.y)
determinant = a1*b2 - a2*b1
if (determinant == 0):
# The lines are parallel. This is simplified
# by returning a pair of FLT_MAX
return Point(10**9, 10**9)
else:
x = (b2*c1 - b1*c2)/determinant
y = (a1*c2 - a2*c1)/determinant
return Point(x, y)
# Driver code
A = Point(1, 1)
B = Point(4, 4)
C = Point(1, 8)
D = Point(2, 4)
intersection = lineLineIntersection(A, B, C, D)
if (intersection.x == 10**9 and intersection.y == 10**9):
print("The given lines AB and CD are parallel.")
else:
# NOTE: Further check can be applied in case
# of line segments. Here, we have considered AB
# and CD as lines
print("The intersection of the given lines AB " + "and CD is: ")
intersection.displayPoint(intersection)
# This code is contributed by Saurabh Jaiswal
C#
using System;
// C# Implementation. To find the point of
// intersection of two lines
// Class used to used to store the X and Y
// coordinates of a point respectively
public class Point
{
public double x, y;
public Point(double x, double y)
{
this.x = x;
this.y = y;
}
// Method used to display X and Y coordinates
// of a point
public static void displayPoint(Point p)
{
Console.WriteLine("(" + p.x + ", " + p.y + ")");
}
}
public class Test
{
public static Point lineLineIntersection(Point A, Point B, Point C, Point D)
{
// Line AB represented as a1x + b1y = c1
double a1 = B.y - A.y;
double b1 = A.x - B.x;
double c1 = a1 * (A.x) + b1 * (A.y);
// Line CD represented as a2x + b2y = c2
double a2 = D.y - C.y;
double b2 = C.x - D.x;
double c2 = a2 * (C.x) + b2 * (C.y);
double determinant = a1 * b2 - a2 * b1;
if (determinant == 0)
{
// The lines are parallel. This is simplified
// by returning a pair of FLT_MAX
return new Point(double.MaxValue, double.MaxValue);
}
else
{
double x = (b2 * c1 - b1 * c2) / determinant;
double y = (a1 * c2 - a2 * c1) / determinant;
return new Point(x, y);
}
}
// Driver method
public static void Main(string[] args)
{
Point A = new Point(1, 1);
Point B = new Point(4, 4);
Point C = new Point(1, 8);
Point D = new Point(2, 4);
Point intersection = lineLineIntersection(A, B, C, D);
if (intersection.x == double.MaxValue && intersection.y == double.MaxValue)
{
Console.WriteLine("The given lines AB and CD are parallel.");
}
else
{
// NOTE: Further check can be applied in case
// of line segments. Here, we have considered AB
// and CD as lines
Console.Write("The intersection of the given lines AB " + "and CD is: ");
Point.displayPoint(intersection);
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to find the point of
// intersection of two lines
// Class used to used to store the X and Y
// coordinates of a point respectively
class Point
{
constructor(x, y)
{
this.x = x;
this.y = y;
}
// Method used to display X and Y coordinates
// of a point
displayPoint(p){
document.write("(" + p.x + ", " + p.y + ")");
}
}
function lineLineIntersection(A,B,C,D){
// Line AB represented as a1x + b1y = c1
var a1 = B.y - A.y;
var b1 = A.x - B.x;
var c1 = a1*(A.x) + b1*(A.y);
// Line CD represented as a2x + b2y = c2
var a2 = D.y - C.y;
var b2 = C.x - D.x;
var c2 = a2*(C.x)+ b2*(C.y);
var determinant = a1*b2 - a2*b1;
if (determinant == 0)
{
// The lines are parallel. This is simplified
// by returning a pair of FLT_MAX
return new Point(Number.MAX_VALUE, Number.MAX_VALUE);
}
else
{
var x = (b2*c1 - b1*c2)/determinant;
var y = (a1*c2 - a2*c1)/determinant;
return new Point(x, y);
}
}
// Driver code
let A = new Point(1, 1);
let B = new Point(4, 4);
let C = new Point(1, 8);
let D = new Point(2, 4);
var intersection = lineLineIntersection(A, B, C, D);
if (intersection.x == Number.MAX_VALUE && intersection.y == Number.MAX_VALUE){
document.write("The given lines AB and CD are parallel.");
}else{
// NOTE: Further check can be applied in case
// of line segments. Here, we have considered AB
// and CD as lines
document.write("The intersection of the given lines AB " + "and CD is: ");
intersection.displayPoint(intersection);
}
// This code is contributed by shruti456rawal
</script>
Producción:
The intersection of the given lines AB and CD is: (2.4, 2.4)
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Aanya Jindal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA