Find the intersection of two lines: Difference between revisions

Content added Content deleted
m (→‎{{header|Python}}: Updated one primitive)
Line 1,356: Line 1,356:


=={{header|Python}}==
=={{header|Python}}==
Find the intersection procedurally, with no imports.
Find the intersection without importing third-party libraries.
<lang python>def line_intersect(Ax1, Ay1, Ax2, Ay2, Bx1, By1, Bx2, By2):
<lang python>def line_intersect(Ax1, Ay1, Ax2, Ay2, Bx1, By1, Bx2, By2):
""" returns a (x, y) tuple or None if there is no intersection """
""" returns a (x, y) tuple or None if there is no intersection """
Line 1,386: Line 1,386:
{{Works with|Python|3.7}}
{{Works with|Python|3.7}}
<lang python>'''The intersection of two lines.'''
<lang python>'''The intersection of two lines.'''

from functools import (reduce)
from itertools import (product)


# intersection :: Line -> Line -> Either String Point
# intersection :: Line -> Line -> Either String Point
def intersection(ab):
def intersection(ab):
Line 1,397: Line 1,397:
def delta(f):
def delta(f):
return lambda x: f(fst(x)) - f(snd(x))
return lambda x: f(fst(x)) - f(snd(x))

def prodDiff(abcd):
def prodDiff(abcd):
[a, b, c, d] = abcd
[a, b, c, d] = abcd
return (a * d) - (b * c)
return (a * d) - (b * c)

def go(pq):
def go(pq):
[abDX, pqDX, abDY, pqDY] = ap(
[abDX, pqDX, abDY, pqDY] = apList(
[delta(fst), delta(snd)]
[delta(fst), delta(snd)]
)([ab, pq])
)([ab, pq])
determinant = prodDiff([abDX, abDY, pqDX, pqDY])
determinant = prodDiff([abDX, abDY, pqDX, pqDY])

def point():
def point():
[abD, pqD] = map(
[abD, pqD] = map(
lambda xy: prodDiff(
lambda xy: prodDiff(
ap([fst, snd])([fst(xy), snd(xy)])
apList([fst, snd])([fst(xy), snd(xy)])
), [ab, pq]
), [ab, pq]
)
)
return ap(
return apList(
[lambda abpq: prodDiff(
[lambda abpq: prodDiff(
[abD, fst(abpq), pqD, snd(abpq)]) / determinant]
[abD, fst(abpq), pqD, snd(abpq)]) / determinant]
Line 1,423: Line 1,423:
'( Parallel lines - no intersection )'
'( Parallel lines - no intersection )'
)
)

return lambda pq: bindLR(go(pq))(
return lambda pq: bindLR(go(pq))(
lambda xs: Right((fst(xs), snd(xs)))
lambda xs: Right((fst(xs), snd(xs)))
)
)


# TEST ----------------------------------------------------
# --------------------------TEST---------------------------
# main :: IO()
# main :: IO()
def main():
def main():
'''Test'''
'''Test'''

# Left(message - no intersection) or Right(point)
# Left(message - no intersection) or Right(point)
# lrPoint :: Either String Point
# lrPoint :: Either String Point
Line 1,444: Line 1,444:
lrPoint['Left'] or lrPoint['Right']
lrPoint['Left'] or lrPoint['Right']
)
)


# GENERIC FUNCTIONS ---------------------------------------
# --------------------GENERIC FUNCTIONS--------------------

# Left :: a -> Either a b
# Left :: a -> Either a b
def Left(x):
def Left(x):
Line 1,453: Line 1,453:
with an associated string.'''
with an associated string.'''
return {'type': 'Either', 'Right': None, 'Left': x}
return {'type': 'Either', 'Right': None, 'Left': x}


# Right :: b -> Either a b
# Right :: b -> Either a b
def Right(x):
def Right(x):
'''Constructor for a populated Either (option type) value'''
'''Constructor for a populated Either (option type) value'''
return {'type': 'Either', 'Left': None, 'Right': x}
return {'type': 'Either', 'Left': None, 'Right': x}


# ap (<*>) :: [(a -> b)] -> [a] -> [b]
# apList (<*>) :: [(a -> b)] -> [a] -> [b]
def ap(fs):
def apList(fs):
'''The application of each of a list of functions,
'''The application of each of a list of functions,
to each of a list of values.'''
to each of a list of values.
⚫
'''
⚫
return lambda xs: reduce(
def go(fx):
lambda a, f: a + reduce(
lambda a, x: a + [f(x)], xs, []
f, x = fx
), fs, []
return f(x)
⚫
return lambda xs: [
⚫
)
go(x) for x
in product(fs, xs)
]


# bindLR (>>=) :: Either a -> (a -> Either b) -> Either b
# bindLR (>>=) :: Either a -> (a -> Either b) -> Either b
def bindLR(m):
def bindLR(m):
Line 1,481: Line 1,484:
mf(m.get('Right')) if None is m.get('Left') else m
mf(m.get('Right')) if None is m.get('Left') else m
)
)


# fst :: (a, b) -> a
# fst :: (a, b) -> a
def fst(tpl):
def fst(tpl):
'''First member of a pair.'''
'''First member of a pair.'''
return tpl[0]
return tpl[0]


# snd :: (a, b) -> b
# snd :: (a, b) -> b
def snd(tpl):
def snd(tpl):
'''Second member of a pair.'''
'''Second member of a pair.'''
return tpl[1]
return tpl[1]


# MAIN ---
# MAIN ---
if __name__ == '__main__':
if __name__ == '__main__':
Retrieved from "https://rosettacode.org/wiki/Find_the_intersection_of_two_lines"