1

Tengo 2 listas con distintos puntos de un grafico. Lo que necesito es saber el primer punto de interseccion entre ambas listas e imprimirlo.

introducir la descripción de la imagen aquí

m = [1.35, 2.35, 3.35, 4.35, 5.35, 6.35, 7.35]

c = [3, 5, 8, 14, 4, 10, 7.35]
for item in m:
    for item2 in c:
        Si el item esta entre item2-1 y item2:
            print(calculo de intersecion)
1
  • 1
    Puedes usar intersección de conjuntos: set(m) & set(c) para obtener los valores repetidos, aunque eso no te permitirá hallar los índices.
    – abulafia
    el 22 jul. 2019 a las 20:12

2 respuestas 2

1

Suponiendo que cuando dices "se intersectan", te refieres al lugar donde se cruzan las líneas en el grafico. Si es así, cada segmento de recta se compone de puntos:

L1_ini = x1, y1
L1_fin = x2, y2
L2_ini = x1, y3
L2_fin = x2, y4

Los puntos x de un segmento c son iguales a los del otro segmento m Para saber si un segmento se traslapa con otro, se puede comparar la diferencia entre sus inicios y sus finales. Si ambas dan del mismo signo, entonces no se cruzan, si una diferencia es tiene signo diferente es porque se ha cruzado.

dif1 = L1_ini(y1) - L2_ini(y2)
dif2 = L1_fin(y3) - L2_fin(y4)

Si la multiplacación dif1 * dif2 da signo negativo (-) entonces se han cruzado las líneas

Finalmente el punto de intersección, se puede calcular usando el método empleado en esta respuesta de StackOverflow (en Inglés)

How do I compute the intersection point of two lines?

Adaptando el código para el requerimiento, quedaría así:

def line(p1, p2):
    A = (p1[1] - p2[1])
    B = (p2[0] - p1[0])
    C = (p1[0]*p2[1] - p2[0]*p1[1])
    return A, B, -C

def intersection(L1, L2):
    D  = L1[0] * L2[1] - L1[1] * L2[0]
    Dx = L1[2] * L2[1] - L1[1] * L2[2]
    Dy = L1[0] * L2[2] - L1[2] * L2[0]
    x = Dx / D
    y = Dy / D
    return x,y

# ##########
m = [1.35, 2.35, 3.35, 4.35, 5.35, 6.35, 7.35]
c = [3, 5, 8, 14, 4, 10, 7.35]

num_data = len(m)
for x in range(num_data - 1):
    dif1 = c[x] - m[x]
    dif2 = c[x + 1] - m[x + 1]
    if(dif1 * dif2) <= 0:
        # Se interceptan las dos rectas.
        L1 = line([x, m[x]], [x+1, m[x+1]])
        L2 = line([x, c[x]], [x+1, c[x+1]])
        result = intersection(L1, L2)
        print("El punto [y] de interseccion es:", round(result[1], 4))

Salida

El punto [y] de interseccion es: 5.2273
El punto [y] de interseccion es: 5.62
El punto [y] de interseccion es: 7.35

Si solo requieres el primer valor, pues le pones un break al final del if.

3
  • Gracias por tu respuesta aunque mirando el grafico la primer interseccion me dá menor a 5. puede ser? el 23 jul. 2019 a las 12:24
  • 1
    Lo que pasa es que el punto de intersección tiene coordenadas [X] e [Y], en mi código solo te estoy dando el punto [Y] (para que corresponda a los valores de las listas que estas dando). Efectivamente el primer punto de intersección tiene coordenada X=4.877, pero Y=5.227. En el código, la variable result tiene ambas coordenadas. Si quieres la [X], pues restult[0] y la [Y] result[1]. Observa la respuesta que da @PatricioMoracho donde el resultado es el mismo.
    – aeportugal
    el 23 jul. 2019 a las 16:19
  • Muchas gracias! el 23 jul. 2019 a las 16:27
1

Tu pregunta no es nada trivial, el problema más general, es un problema de geometría, la idea es poder encontrar un punto de intersección entre dos segmentos. En tu caso tienes dos líneas, que en algún momento se intersectan, la idea es encontrar estos puntos de intersección. En este caso, como son líneas de tendencia, los valores de x de cada punto se corresponde con un entero que se incrementa de a 1. La idea sería ir iterar para comparar segmentos dados por los puntos x y x + 1 y su respectivos valores de y.

Hay muchas implementaciones para determinar el punto de intersección de dos rectas, sin embargo en este caso, el problema es más particular: 1) hay que considerar segmentos y no rectas, (usando rectas, todos los segmentos en algún momento se intersectan, a menos que sean segmentos paralelos) 2) Habría que considerar condiciones de colinearidad, dos segmentos iguales (cuya solución sería infinitos puntos).

Tomando lo anterior como base, me ha gustado mucho esta implementación que contempla los dos puntos anteriores. Veamos:

from __future__ import division 
from collections import namedtuple

Point = namedtuple('Point', 'x y')
Segment = namedtuple('Segment', 'ep1 ep2')

def find_slope(segment):
    """
    Return the slope of the line segment, if it is defined. If it is
    undefined, return None.
    """
    p1, p2 = segment.ep1, segment.ep2
    if p2.x - p1.x == 0.0:
        return None
    else:
        return (p2.y-p1.y) / (p2.x-p1.x)

def find_y_intercept(slope, point):
    """
    Return the y-intercept of an infinite line with slope equal to slope that
    passes through point. If slope does not exist, return None.
    """
    if slope is None:
        return None
    else:
        return point.y - slope*point.x

def order_segment(segment):
    """
    Order endpoints in segment primarily by x position, and secondarily by y
    position.
    """
    ep1, ep2 = segment.ep1, segment.ep2
    if (ep1.x > ep2.x or ep1.x == ep2.x and ep1.y > ep2.y):
        segment.ep1, segment.ep2 = segment.ep2, segment.ep1

def order_segments(segments):
    """
    Order segments by each segment's first endpoint. Similar to order_segment,
    order primarily by first endpoint's x position, and secondarily by first
    endpoint's y position.
    """
    seg1, seg2 = segments
    if (seg1.ep1.x > seg2.ep1.x or seg1.ep1.x == seg2.ep1.x
            and seg1.ep1.y > seg2.ep1.y):
        segments[0], segments[1] = segments[1], segments[0]

def on(point, segment):
    """
    Return True if point lies on segment. Otherwise, return False.
    """
    return (within(segment.ep1.x, point.x, segment.ep2.x) and
            within(segment.ep1.y, point.y, segment.ep2.y))

def within(p, q, r):
    """
    Return True if q is between p and r. Otherwise, return False.
    """
    return p <= q <= r or r <= q <= p

def find_intersection(segment1, segment2):
    """
    Return an intersection point of segment1 and segment2, if one exists. If
    multiple points of intersection exist, randomly return one of those
    intersection points. If no intersection exists, return None.
    """
    [s1, s2] = [find_slope(l) for l in [segment1, segment2]]
    [k1, k2] = [find_y_intercept(s, l[0])
                for s, l in [(s1, segment1), (s2, segment2)]]

    if s1 == s2:
        if k1 != k2:
            return None
        #  at this point, the two line segments are known to lie on the same
        #  infinite line (i.e. all of the endpoints are collinear)
        segments = [segment1, segment2]
        for segment in segments:
            order_segment(segment)
        order_segments(segments)
        intersection = segments[1].ep1
    else:
        #  assume segment 1 has slope and segment 2 doesn't
        s, x, k = s1, segment2.ep1.x, k1
        #  assumption wrong, segment 1 doesn't have a slope, but segment 2 does
        if s1 is None:
            s, x, k = s2, segment1.ep1.x, k2
        #  assumption wrong, segments 1 and 2 both have slopes
        elif s2 is not None:
            x = (k2-k1) / (s1-s2)
        y = s*x + k
        intersection = Point(x, y)

    if on(intersection, segment1) and on(intersection, segment2):
        return intersection
    else:
        return None

Y si implementamos el código anterior con tu ejemplo, haríamos algo así:

m = [1.35, 2.35, 3.35, 4.35, 5.35, 6.35, 7.35]
c = [3, 5, 8, 14, 4, 10, 7.35]
for x in range(1, len(m)):

  s1 = Segment(Point(x, m[x-1]), Point(x+1, m[x]))
  s2 = Segment(Point(x, c[x-1]), Point(x+1, c[x]))

  print("Intersección para x entre {0} y {1}: {2}".format(x, x+1, find_intersection(s1, s2)))

La Salida:

Intersección para x entre 1 y 2: None
Intersección para x entre 2 y 3: None
Intersección para x entre 3 y 4: None
Intersección para x entre 4 y 5: Point(x=4.877272727272727, y=5.227272727272727)
Intersección para x entre 5 y 6: Point(x=5.2700000000000005, y=5.62)
Intersección para x entre 6 y 7: None

Notese que se detectaron solo dos puntos que coinciden visualmente con la gráfica, Asimismo, el último punto x=7, podríamos considerarlo como una intersección, el problema que que estamos comparando segmentos que van de x-1 a x, la solución sería, agregar un nuevo punto en las dos listas idéntico al último, por ejemplo:

m.append(m[-1])
c.append(c[-1])
for x in range(1, len(m)):
    ....

Y ahora sí:

Intersección para x entre 1 y 2: None
Intersección para x entre 2 y 3: None
Intersección para x entre 3 y 4: None
Intersección para x entre 4 y 5: Point(x=4.877272727272727, y=5.227272727272727)
Intersección para x entre 5 y 6: Point(x=5.2700000000000005, y=5.62)
Intersección para x entre 6 y 7: None
Intersección para x entre 7 y 8: Point(x=7, y=7.35)
1
  • Muchisimas Gracias Patricio!!! el 23 jul. 2019 a las 16:26

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.