Source

geoalg / geoalg / line.py

Full commit
#!/usr/bin/env python
#coding:utf-8
# Author:  mozman
# Purpose: line
# Created: 31.03.2010

from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals
from __future__ import absolute_import

from geoalg import Ray2D, ParallelRaysError

__all__ = ['Line2D', 'ccw', 'do_intersect']

class Line2D(object):
    def __init__(self, start, end):
        if start > end:
            start, end = end, start
        self.start = start
        self.end = end
        self.ray = Ray2D(start, end)

    def length(self):
        return ((self.start[0] - self.end[0])**2 + \
                (self.start[1] - self.end[1])**2)**0.5

    def midpoint(self):
        return ((self.start[0] + self.end[0])*.5,
                (self.start[1] + self.end[1])*.5)

    def is_in_range(self, point):
        if not self.ray.is_vertical:
            return self.start[0] <= point[0] <= self.end[0]
        else:
            return self.start[1] <= point[1] <= self.end[1]

    def intersect(self, other_line):
        try:
            point = self.ray.intersect(other_line.ray)
            if self.is_in_range(point) and \
               other_line.is_in_range(point):
                return point
            else:
                return None
        except ParallelRaysError:
            return None

def ccw(point0, point1, point2):
    dx1 = point1[0] - point0[0]
    dy1 = point1[1] - point0[1]
    dx2 = point2[0] - point0[0]
    dy2 = point2[1] - point0[1]
    if dx1*dy2 > dy1*dx2:
        return +1
    elif dx1*dy2 < dy1*dx2:
        return -1
    elif (dx1*dx2 < 0) or (dy1*dy2<0):
        return -1
    elif (dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2):
        return +1
    return 0

def do_intersect(line1, line2):
    return ((ccw(line1[0], line1[1], line2[0]) * \
             ccw(line1[0], line1[1], line2[1]) <=0) and \
            ((ccw(line2[0], line2[1], line1[0]) * \
              ccw(line2[0], line2[1], line1[1])) <=0))