# Path: trimesh/util.py
# def three_dimensionalize(points, return_2D=True):
#     '''
#     Given a set of (n,2) or (n,3) points, return them as (n,3) points
# 
#     Arguments
#     ----------
#     points:    (n, 2) or (n,3) points
#     return_2D: boolean flag
# 
#     Returns
#     ----------
#     if return_2D:
#         is_2D: boolean, True if points were (n,2)
#         points: (n,3) set of points
#     else:
#         points: (n,3) set of points
#     '''
#     points = np.asanyarray(points)
#     shape = points.shape
# 
#     if len(shape) != 2:
#         raise ValueError('Points must be 2D array!')
# 
#     if shape[1] == 2:
#         points = np.column_stack((points, np.zeros(len(points))))
#         is_2D = True
#     elif shape[1] == 3:
#         is_2D = False
#     else:
#         raise ValueError('Points must be (n,2) or (n,3)!')
# 
#     if return_2D:
#         return is_2D, points
#     return points
# 
# def unitize(points, check_valid=False):
#     '''
#     Turn a list of vectors into a list of unit vectors.
# 
#     Arguments
#     ---------
#     points:       (n,m) or (j) input array of vectors.
#                   For 1D arrays, points is treated as a single vector
#                   For 2D arrays, each row is treated as a vector
#     check_valid:  boolean, if True enables valid output and checking
# 
#     Returns
#     ---------
#     unit_vectors: (n,m) or (j) length array of unit vectors
# 
#     valid:        (n) boolean array, output only if check_valid.
#                    True for all valid (nonzero length) vectors, thus m=sum(valid)
#     '''
#     points = np.asanyarray(points)
#     axis = len(points.shape) - 1
#     length = np.sum(points ** 2, axis=axis) ** .5
# 
#     if is_sequence(length):
#         length[np.isnan(length)] = 0.0
# 
#     if check_valid:
#         valid = np.greater(length, _TOL_ZERO)
#         if axis == 1:
#             unit_vectors = (points[valid].T / length[valid]).T
#         elif len(points.shape) == 1 and valid:
#             unit_vectors = points / length
#         else:
#             unit_vectors = np.array([])
#         return unit_vectors, valid
#     else:
#         unit_vectors = (points.T / length).T
#     return unit_vectors
# 
# Path: trimesh/constants.py
# class NumericalToleranceMesh(object):
# class NumericalResolutionMesh(object):
# class NumericalTolerancePath(object):
# class NumericalResolutionPath(object):
# class MeshError(Exception):
# class TransformError(Exception):
#     def __init__(self, **kwargs):
#     def __init__(self, **kwargs):
#     def __init__(self, **kwargs):
#     def __init__(self, **kwargs):
# def _log_time(method):
#     def timed(*args, **kwargs):


import numpy as np
from ..util import three_dimensionalize, unitize
from ..constants import tol_path as tol



def line_line(origins, directions):
    '''
    Find the intersection between two lines.
    Uses terminology from:
    http://geomalgorithms.com/a05-_intersect-1.html

    line 1:    P(s) = p_0 + sU
    line 2:    Q(t) = q_0 + tV

    Arguments
    ---------
    origins:    (2,d) list of points on lines (d in [2,3])
    directions: (2,d) list of direction vectors

    Returns
    ---------
    intersects:   boolean, whether the lines intersect.
                  In 2D, false if the lines are parallel
                  In 3D, false if lines are not coplanar
    intersection: if intersects: (d) length point of intersection
                  else:          None
    '''

    is_2D, origins = three_dimensionalize(origins)

# Path: trimesh/util.py
# def three_dimensionalize(points, return_2D=True):
#     '''
#     Given a set of (n,2) or (n,3) points, return them as (n,3) points
# 
#     Arguments
#     ----------
#     points:    (n, 2) or (n,3) points
#     return_2D: boolean flag
# 
#     Returns
#     ----------
#     if return_2D:
#         is_2D: boolean, True if points were (n,2)
#         points: (n,3) set of points
#     else:
#         points: (n,3) set of points
#     '''
#     points = np.asanyarray(points)
#     shape = points.shape
# 
#     if len(shape) != 2:
#         raise ValueError('Points must be 2D array!')
# 
#     if shape[1] == 2:
#         points = np.column_stack((points, np.zeros(len(points))))
#         is_2D = True
#     elif shape[1] == 3:
#         is_2D = False
#     else:
#         raise ValueError('Points must be (n,2) or (n,3)!')
# 
#     if return_2D:
#         return is_2D, points
#     return points
# 
# def unitize(points, check_valid=False):
#     '''
#     Turn a list of vectors into a list of unit vectors.
# 
#     Arguments
#     ---------
#     points:       (n,m) or (j) input array of vectors.
#                   For 1D arrays, points is treated as a single vector
#                   For 2D arrays, each row is treated as a vector
#     check_valid:  boolean, if True enables valid output and checking
# 
#     Returns
#     ---------
#     unit_vectors: (n,m) or (j) length array of unit vectors
# 
#     valid:        (n) boolean array, output only if check_valid.
#                    True for all valid (nonzero length) vectors, thus m=sum(valid)
#     '''
#     points = np.asanyarray(points)
#     axis = len(points.shape) - 1
#     length = np.sum(points ** 2, axis=axis) ** .5
# 
#     if is_sequence(length):
#         length[np.isnan(length)] = 0.0
# 
#     if check_valid:
#         valid = np.greater(length, _TOL_ZERO)
#         if axis == 1:
#             unit_vectors = (points[valid].T / length[valid]).T
#         elif len(points.shape) == 1 and valid:
#             unit_vectors = points / length
#         else:
#             unit_vectors = np.array([])
#         return unit_vectors, valid
#     else:
#         unit_vectors = (points.T / length).T
#     return unit_vectors
# 
# Path: trimesh/constants.py
# class NumericalToleranceMesh(object):
# class NumericalResolutionMesh(object):
# class NumericalTolerancePath(object):
# class NumericalResolutionPath(object):
# class MeshError(Exception):
# class TransformError(Exception):
#     def __init__(self, **kwargs):
#     def __init__(self, **kwargs):
#     def __init__(self, **kwargs):
#     def __init__(self, **kwargs):
# def _log_time(method):
#     def timed(*args, **kwargs):


# Path: trimesh/path/intersections.py
import numpy as np
from ..util import three_dimensionalize, unitize
from ..constants import tol_path as tol




def line_line(origins, directions):
    '''
    Find the intersection between two lines.
    Uses terminology from:
    http://geomalgorithms.com/a05-_intersect-1.html

    line 1:    P(s) = p_0 + sU
    line 2:    Q(t) = q_0 + tV

    Arguments
    ---------
    origins:    (2,d) list of points on lines (d in [2,3])
    directions: (2,d) list of direction vectors

    Returns
    ---------
    intersects:   boolean, whether the lines intersect.
                  In 2D, false if the lines are parallel
                  In 3D, false if lines are not coplanar
    intersection: if intersects: (d) length point of intersection
                  else:          None
    '''

    is_2D, origins = three_dimensionalize(origins)

    is_2D, directions = three_dimensionalize(directions)