# Path: trimesh/grouping.py
# def unique_ordered(data):
#     '''
#     Returns the same as np.unique, but ordered as per the
#     first occurance of the unique value in data.
# 
#     Example
#     ---------
#     In [1]: a = [0, 3, 3, 4, 1, 3, 0, 3, 2, 1]
# 
#     In [2]: np.unique(a)
#     Out[2]: array([0, 1, 2, 3, 4])
# 
#     In [3]: trimesh.grouping.unique_ordered(a)
#     Out[3]: array([0, 3, 4, 1, 2])
#     '''
#     data = np.asanyarray(data)
#     order = np.sort(np.unique(data, return_index=True)[1])
#     result = data[order]
#     return result
# 
# Path: trimesh/util.py
# 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/util.py
# def is_ccw(points):
#     '''
#     Given an (n,2) set of points, return True if they are counterclockwise
#     '''
#     xd = np.diff(points[:, 0])
#     yd = np.sum(np.column_stack((points[:, 1],
#                                  points[:, 1])).reshape(-1)[1:-1].reshape((-1, 2)), axis=1)
#     area = np.sum(xd * yd) * .5
#     ccw = area < 0
# 
#     return ccw


import numpy as np
import networkx as nx
from collections import deque
from ..grouping import unique_ordered
from ..util import unitize
from ..constants import tol_path as tol
from .util import is_ccw
        self._cum_norm = np.cumsum(self._norms)

    def sample(self, distances):
        # return the indices in cum_norm that each sample would
        # need to be inserted at to maintain the sorted property
        positions = np.searchsorted(self._cum_norm, distances)
        positions = np.clip(positions, 0, len(self._unit_vec) - 1)
        offsets = np.append(0, self._cum_norm)[positions]
        # the distance past the reference vertex we need to travel
        projection = distances - offsets
        # find out which dirction we need to project
        direction = self._unit_vec[positions]
        # find out which vertex we're offset from
        origin = self._points[positions]
        # just the parametric equation for a line
        resampled = origin + (direction * projection.reshape((-1, 1)))

        return resampled

    def truncate(self, distance):
        '''
        Return a truncated version of the path.
        Only one vertex (at the endpoint) will be added.
        '''
        position = np.searchsorted(self._cum_norm, distance)
        offset = distance - self._cum_norm[position - 1]

        if offset < tol.merge:
            truncated = self._points[:position + 1]
        else:

# Path: trimesh/grouping.py
# def unique_ordered(data):
#     '''
#     Returns the same as np.unique, but ordered as per the
#     first occurance of the unique value in data.
# 
#     Example
#     ---------
#     In [1]: a = [0, 3, 3, 4, 1, 3, 0, 3, 2, 1]
# 
#     In [2]: np.unique(a)
#     Out[2]: array([0, 1, 2, 3, 4])
# 
#     In [3]: trimesh.grouping.unique_ordered(a)
#     Out[3]: array([0, 3, 4, 1, 2])
#     '''
#     data = np.asanyarray(data)
#     order = np.sort(np.unique(data, return_index=True)[1])
#     result = data[order]
#     return result
# 
# Path: trimesh/util.py
# 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/util.py
# def is_ccw(points):
#     '''
#     Given an (n,2) set of points, return True if they are counterclockwise
#     '''
#     xd = np.diff(points[:, 0])
#     yd = np.sum(np.column_stack((points[:, 1],
#                                  points[:, 1])).reshape(-1)[1:-1].reshape((-1, 2)), axis=1)
#     area = np.sum(xd * yd) * .5
#     ccw = area < 0
# 
#     return ccw


# Path: trimesh/path/traversal.py
import numpy as np
import networkx as nx
from collections import deque
from ..grouping import unique_ordered
from ..util import unitize
from ..constants import tol_path as tol
from .util import is_ccw

        self._cum_norm = np.cumsum(self._norms)

    def sample(self, distances):
        # return the indices in cum_norm that each sample would
        # need to be inserted at to maintain the sorted property
        positions = np.searchsorted(self._cum_norm, distances)
        positions = np.clip(positions, 0, len(self._unit_vec) - 1)
        offsets = np.append(0, self._cum_norm)[positions]
        # the distance past the reference vertex we need to travel
        projection = distances - offsets
        # find out which dirction we need to project
        direction = self._unit_vec[positions]
        # find out which vertex we're offset from
        origin = self._points[positions]
        # just the parametric equation for a line
        resampled = origin + (direction * projection.reshape((-1, 1)))

        return resampled

    def truncate(self, distance):
        '''
        Return a truncated version of the path.
        Only one vertex (at the endpoint) will be added.
        '''
        position = np.searchsorted(self._cum_norm, distance)
        offset = distance - self._cum_norm[position - 1]

        if offset < tol.merge:
            truncated = self._points[:position + 1]
        else:

            vector = unitize(np.diff(self._points[np.arange(2) + position],