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)
set(m) & set(c)
para obtener los valores repetidos, aunque eso no te permitirá hallar los índices.