def xsect_spline(sp_a, sp_b, _hubs, precision):
    pt_a_prev = pt_b_prev = None
    EPS_SPLINE = min(sp_a.length, sp_b.length) / precision
    pt_a_prev = sp_a.points[0]
    for a, pt_a in enumerate(sp_a.points[1:]):
        pt_b_prev = sp_b.points[0]
        for b, pt_b in enumerate(sp_b.points[1:]):

            # Now we have 2 edges
            # print(pt_a, pt_a_prev, pt_b, pt_b_prev)
            xsect = intersect_line_line(pt_a, pt_a_prev, pt_b, pt_b_prev)
            if xsect is not None:
                if (xsect[0] - xsect[1]).length <= EPS_SPLINE:
                    f = intersect_point_line(xsect[1], pt_a, pt_a_prev)[1]
                    # if f >= 0.0-EPS_SPLINE and f <= 1.0+EPS_SPLINE:
                        # for some reason doesnt work so well, same below
                    if f >= 0.0 and f <= 1.0:
                        f = intersect_point_line(xsect[0], pt_b, pt_b_prev)[1]
                        # if f >= 0.0-EPS_SPLINE and f <= 1.0+EPS_SPLINE:
                        if f >= 0.0 and f <= 1.0:
                            # This wont happen often
                            co = xsect[0].lerp(xsect[1], 0.5)
                            hub = get_hub(co, _hubs, EPS_SPLINE)

                            sp_a.hubs.append((a, hub))
                            sp_b.hubs.append((b, hub))

            pt_b_prev = pt_b

        pt_a_prev = pt_a

    def slide_update(self,context,eventd,settings):
        x,y = eventd['mouse']
        region = context.region
        region = eventd['region']
        r3d = eventd['r3d']
        hit = common_utilities.ray_cast_region2d_bvh(region, r3d, (x,y), self.trg_bvh, self.trg_mx, settings)[1]
        if hit[2] is None: return

        pt = invert_matrix(self.trg_mx) * hit[0]
        def dist(v_index):
            v = self.trg_bme.verts[v_index]
            l = (self.trg_mx * v.co) - pt
            return l.length

        v_ind = min(self.loopslide.vert_loop_vs, key = dist)  #<  The closest edgeloop point to the mouse
        n = self.loopslide.vert_loop_vs.index(v_ind)
        v_pt = self.trg_bme.verts[v_ind].co
        
        p_right, pct_right = intersect_point_line(pt, v_pt, v_pt + self.loopslide.edge_loop_right[n])
        p_left, pct_left = intersect_point_line(pt, v_pt, v_pt + self.loopslide.edge_loop_left[n])

        if pct_right > 0:
            self.loopslide.pct = min(1, pct_right)
            self.loopslide.right = True
        else:
            self.loopslide.right = False
            self.loopslide.pct = min(1, pct_left)

        self.loopslide.calc_snaps(self.trg_bme, snap = False)

    def hover_non_man(self,context,x,y):
        region = context.region
        rv3d = context.region_data
        coord = x, y
        self.mouse = Vector((x, y))
        
        loc3d_reg2D = view3d_utils.location_3d_to_region_2d
        
        view_vector = view3d_utils.region_2d_to_vector_3d(region, rv3d, coord)
        ray_origin = view3d_utils.region_2d_to_origin_3d(region, rv3d, coord)
        ray_target = ray_origin + (view_vector * 1000)
        mx = self.cut_ob.matrix_world
        imx = mx.inverted()
        loc, no, face_ind = self.cut_ob.ray_cast(imx * ray_origin, imx * ray_target)
        
        if len(self.non_man_points):
            co3d, index, dist = self.kd.find(mx * loc)

            #get the actual non man vert from original list
            close_bmvert = self.bme.verts[self.non_man_bmverts[index]] #stupid mapping, unreadable, terrible, fix this, because can't keep a list of actual bmverts
            close_eds = [ed for ed in close_bmvert.link_edges if not ed.is_manifold]
            if len(close_eds) == 2:
                bm0 = close_eds[0].other_vert(close_bmvert)
                bm1 = close_eds[1].other_vert(close_bmvert)
            
                a0 = bm0.co
                b   = close_bmvert.co
                a1  = bm1.co 
                
                inter_0, d0 = intersect_point_line(loc, a0, b)
                inter_1, d1 = intersect_point_line(loc, a1, b)
                
                screen_0 = loc3d_reg2D(region, rv3d, mx * inter_0)
                screen_1 = loc3d_reg2D(region, rv3d, mx * inter_1)
                screen_v = loc3d_reg2D(region, rv3d, mx * b)
                
                screen_d0 = (self.mouse - screen_0).length
                screen_d1 = (self.mouse - screen_1).length
                screen_dv = (self.mouse - screen_v).length
                
                if 0 < d0 <= 1 and screen_d0 < 30:
                    self.hovered = ['NON_MAN_ED', (close_eds[0], mx*inter_0)]
                    return
                elif 0 < d1 <= 1 and screen_d1 < 30:
                    self.hovered = ['NON_MAN_ED', (close_eds[1], mx*inter_1)]
                    return
                elif screen_dv < 30:
                    if abs(d0) < abs(d1):
                        self.hovered = ['NON_MAN_VERT', (close_eds[0], mx*b)]
                        return
                    else:
                        self.hovered = ['NON_MAN_VERT', (close_eds[1], mx*b)]
                        return

def f_1(me, list_0, arg, context, ob_act):

    cb = context.scene.pt_custom_props.b
    cen1 = context.scene.pt_custom_props.en1

    dict_0 = {}
    dict_1 = {}

    if arg == 'x':
        lp1 = Vector((0, 0, 0))
        lp2 = Vector((1, 0, 0))
    elif arg == 'y':
        lp1 = Vector((0, 0, 0))
        lp2 = Vector((0, 1, 0))
    elif arg == 'z':
        lp1 = Vector((0, 0, 0))
        lp2 = Vector((0, 0, 1))

    if cb == False:
        for vi in list_0:
            v = (me.vertices[vi].co).copy()
            if cen1 == 'opt0':
                p3 = intersect_point_line( v, lp1, lp2)[0]
            elif cen1 == 'opt1':
                p1 = ob_act.matrix_world * v
                p2 = intersect_point_line( p1, lp1, lp2)[0]
                p3 = (ob_act.matrix_world).inverted() * p2

            dict_0[vi] = p3

        for j in dict_0:
            me.vertices[j].co = dict_0[j]

    elif cb == True:
        for vi in list_0:
            v = (me.vertices[vi].co).copy()
            if cen1 == 'opt0':
                p3 = intersect_point_line( v, lp1, lp2)[0]
            elif cen1 == 'opt1':
                p1 = ob_act.matrix_world * v
                p2 = intersect_point_line( p1, lp1, lp2)[0]
                p3 = (ob_act.matrix_world).inverted() * p2

            me.vertices.add(1)
            me.vertices[-1].co = p3
            me.vertices[-1].select = False
            dict_1[vi] = me.vertices[-1].index

        edge_copy_(me, dict_1)
        faces_copy_(me, dict_1)

def intersect(pt,bone) :
    intersection = intersect_point_line(pt,bone['head'],bone['tail'])

    point_on_line = (pt-intersection[0]).length < 0.001

    #print('point_on_line',point_on_line)
    #distance = True
    is_in_range = False
    if intersection[1]<=0.5 :
        distance = (pt-bone['head']).length
        #print(distance)
        if intersection[1]>=0 :
            is_in_range = True
        else :
            is_in_range = distance > -1.5

    elif intersection[1]>0.5 :
        distance = (pt-bone['tail']).length

        #print(distance)
        if intersection[1]<=1 :
            is_in_range = True
        else :
            is_in_range = distance < 2.5

    #print('is_in_range',is_in_range)
    #print(bone)
    #print('intersection',intersection)
    #print('point_on_line',point_on_line)

    #print('is_in_range',is_in_range)


    if point_on_line and is_in_range:
        return intersection[1]

def e_no_(bme, indx, p, p1):
    tmp1 = (bme.verts[indx].co).copy()
    tmp1[0] += 0.1
    tmp1[1] += 0.1
    tmp1[2] += 0.1
    ip1 = intersect_point_line(tmp1, p, p1)[0]
    return tmp1 - ip1

    def active_element(self, context, x, y):
        active_head = self.head.mouse_over(x, y)
        active_tail = self.tail.mouse_over(x, y)

        mouse_loc = Vector((x, y, 0))
        head_loc = Vector((self.head.x, self.head.y, 0))
        tail_loc = Vector((self.tail.x, self.tail.y, 0))
        intersect = intersect_point_line(mouse_loc, head_loc, tail_loc)

        dist = (intersect[0] - mouse_loc).length_squared
        bound = intersect[1]
        active_self = (dist < 100) and (bound < 1) and (bound > 0)  # TODO:  make this a sensitivity setting

        if active_head and active_tail and active_self:  # they are all clustered together
            print("returning head but tail too")
            return self.head

        elif active_tail:
            print("returning tail")
            return self.tail

        elif active_head:
            print("returning head")
            return self.head

        elif active_self:
            print("returning line")
            return self

        else:
            print("returning None")
            return None

 def distance_point_edge(pt, edge):
     line_p1 = edge.verts[0].co
     line_p2 = edge.verts[1].co
     ret = intersect_point_line(pt, line_p1, line_p2)
     closest_point_on_line = ret[0]
     distance_vector = closest_point_on_line - pt
     return distance_vector.length

def get_closest_edge(bm, point, dist):
    r_edge = None
    for edge in bm.edges:
        v1 = edge.verts[0].co
        v2 = edge.verts[1].co
        # Test the BVH (AABB) first
        for i in range(3):
            if v1[i] <= v2[i]:
                isect = v1[i] - dist <= point[i] <= v2[i] + dist
            else:
                isect = v2[i] - dist <= point[i] <= v1[i] + dist

            if not isect:
                break
        else:
            ret = intersect_point_line(point, v1, v2)

            if ret[1] < 0.0:
                tmp = v1
            elif ret[1] > 1.0:
                tmp = v2
            else:
                tmp = ret[0]

            new_dist = (point - tmp).length
            if new_dist <= dist:
                dist = new_dist
                r_edge = edge

    return r_edge

    def active_element(self,context,x,y):
        active_head = self.head.mouse_over(x, y)
        active_tail = self.tail.mouse_over(x, y)
        active_tan = self.plane_tan.mouse_over(x, y)
        
        mouse_loc = Vector((x,y,0))
        head_loc = Vector((self.head.x, self.head.y, 0))
        tail_loc = Vector((self.tail.x, self.tail.y, 0))
        intersect = intersect_point_line(mouse_loc, head_loc, tail_loc)
        
        dist = (intersect[0] - mouse_loc).length_squared
        bound = intersect[1]
        active_self = (dist < 100) and (bound < 1) and (bound > 0) #TODO:  make this a sensitivity setting
        
        if active_head and active_tail and active_self: #they are all clustered together
            #print('returning head but tail too')
            return self.head
        
        elif active_tail:
            #print('returning tail')
            return self.tail
        
        elif active_head:
            #print('returning head')
            return self.head
        
        elif active_tan:
            return self.plane_tan
        
        elif active_self:
            #print('returning line')
            return self
        
        else:
            #print('returning None')
            return None
#cut line, a user interactive 2d line which represents a plane in 3d splace
    #head (type conrol point)
    #tail (type control points)
    #target mesh
    #view_direction (crossed with line to make plane normal for slicing)
    
    #draw method
    
    #new control point project method
    
    #mouse hover line calc
    
    
#retopo object, surface
    #colelction of cut lines
    #collection of countours to loft
    
    #n rings (crosses borrowed from looptools)
    #n follows (borrowed from looptools and or bsurfaces)
    
    #method contours from cutlines
    
    #method bridge contours

 def MatchPairByPerpendicular(self, context, sObj, sID, dObj, dID):
     #当互相垂直角度不为90度时，使用这个
     #我们现在已有一条公共边与两个可能与垂直与公共边的面异面的点，如果两点到公共边上的最小距离坐标很近，说明两个三角形是镜像关系；
     #这是MatchPair的升级版，但是最好先用MatchPair得到公共边，容易理解
     
     #通过RotateO的判断，我们已经将三对[0-1-2]的[1-2]进行了公共边处理，所以，0是可能是与垂直与公共边的面异面的点。
     #所以，几乎可以忽视部分传入参数,eg : ID
     
     if len(sID) != 3 or len(dID) != 3:
         self.report( {'WARNING'}, 'Perpendicular Error in MatchPairByPerpendicular Function!!!' )
         return
         
     #两点
     wm = sObj.matrix_world.copy()
     sP0 = wm * (sObj.data.vertices[self.vts[0][sID[0]]].co.copy())
     wm = dObj.matrix_world.copy()
     dP0 = wm * (dObj.data.vertices[self.vts[self.objs.index(dObj)][dID[0]]].co.copy())
     
     #两点是否重合
     if (dP0 - sP0).magnitude < 0.000001:
         return
     
     #公共边
     wm = sObj.matrix_world.copy()
     sP1 = wm * (sObj.data.vertices[self.vts[0][sID[1]]].co.copy())
     sP2 = wm * (sObj.data.vertices[self.vts[0][sID[2]]].co.copy())
     
     #映射点，求矢量-角度
     from mathutils import geometry
     sP4 = geometry.intersect_point_line(sP0, sP1, sP2)[0]
     dP4 = geometry.intersect_point_line(dP0, sP1, sP2)[0]
     v1, v2 = (sP4 - sP0).normalized(), (dP4 - dP0).normalized()
     
     #角度相关
     angle = v1.angle(v2)
     if angle < 0.000001:
         return
         
     cross = v1.cross(v2)
     
     if self.BoolRotate1Flip == True:
         angle += pi
     angle *= -1
         
     bpy.ops.transform.rotate(value=angle, axis=cross)
     return

def compute_distance(point, line, line_end, tolerance):
    '''call to the mathuutils function'''
    inter_p = intersect_point_line(point, line, line_end)
    dist = (inter_p[0] - point).length
    segment_percent = inter_p[1]
    is_in_line = dist < tolerance
    closest_in_segment = 0 <= segment_percent <= 1
    is_in_segment = is_in_line and closest_in_segment
    return dist, is_in_segment, is_in_line, list(inter_p[0]), closest_in_segment

def distance_point_segment(point, v1, v2):
    '''Compute distance of a point from a line segment.'''
    x, d = geometry.intersect_point_line(point, v1, v2)
    if d <= 0:
        return v1, (point - v1).magnitude
    elif d >= 1.0:
        return v2, (point - v2).magnitude
    else:
        return x, (point - x).magnitude

def get_selection_radius():

	ob = bpy.context.active_object

	radius = 0.0
	
	# no use continueing if nothing is selected
	if contains_selected_item(ob.data.polygons):
	
		# Find the center of the selection
		cent = mathutils.Vector()
		nr = 0
		nonVerts = []
		selVerts = []
		for p in ob.data.polygons:
			if p.select:
				for v in p.vertices:
					nr += 1
					cent += v.co
			else:
				nonVerts.extend(p.vertices)
				
		cent /= nr
		
		chk = 0
		
		# Now that we know the center.. we can figure out how close the nearest point on an outer edge is
		for e in get_selected_edges():
		
			nonSection = [v for v in e.vertices if v in nonVerts]
			if len(nonSection):
			
				v0 = ob.data.vertices[e.vertices[0]].co
				v1 = ob.data.vertices[e.vertices[1]].co
				
				# If there's more than 1 vert of this edge on the outside... we need the edge length to be long enough too!
				if len(nonSection) > 1:
					edge = v0 - v1
					edgeRad = edge.length * 0.5
					
					if edgeRad < radius or not chk:
						radius = edgeRad
						chk += 1
				
				int = geometry.intersect_point_line(cent, v0, v1)
				
				rad = cent - int[0]
				l = rad.length
				
				if l < radius or not chk:
					radius = l
					chk += 1
					
	return radius

    def grad_f_ed(ed, p, last_face):

        # walk around non manifold edges
        if len(ed.link_faces) == 1:
            minv = min(ed.verts, key=geos.get)
            return minv.co, minv, None

        f = [fc for fc in ed.link_faces if fc != last_face][0]
        g = gradient_face(f, geos)
        L = f.calc_perimeter()

        # test for vert intersection
        for v in f.verts:
            v_inter, pct = intersect_point_line(v.co, p, p - L * g)

            delta = v.co - v_inter
            if delta.length < epsilon:
                print("intersect vert")
                return v.co, v, None

        tests = [e for e in f.edges if e != ed]

        for e in tests:

            v0, v1 = intersect_line_line(e.verts[0].co, e.verts[1].co, p, p - L * g)

            V = v0 - e.verts[0].co
            edV = e.verts[1].co - e.verts[0].co
            Vi = v0 - p

            if V.length - edV.length > epsilon:
                # print('intersects outside segment')
                continue
            elif V.dot(edV) < 0:
                # print('intersects behind')
                continue

            elif Vi.dot(g) > 0:  # remember we watnt to travel DOWN the gradient

                # print('shoots out the face, not across the face')
                continue

            else:

                # print('regular face edge crossing')
                return v0, e, f

        # we didn't intersect across an edge, or on a vert,
        # therefore, we should travel ALONG the edge

        vret = min(ed.verts, key=geos.get)
        return vret.co, vret, None

def region_2d_to_location_3d(region, rv3d, coord, depth_location):
    """
    Return a 3d location from the region relative 2d coords, aligned with
    *depth_location*.

    :arg region: region of the 3D viewport, typically bpy.context.region.
    :type region: :class:`bpy.types.Region`
    :arg rv3d: 3D region data, typically bpy.context.space_data.region_3d.
    :type rv3d: :class:`bpy.types.RegionView3D`
    :arg coord: 2d coordinates relative to the region;
       (event.mouse_region_x, event.mouse_region_y) for example.
    :type coord: 2d vector
    :arg depth_location: the returned vectors depth is aligned with this since
       there is no defined depth with a 2d region input.
    :type depth_location: 3d vector
    :return: normalized 3d vector.
    :rtype: :class:`mathutils.Vector`
    """
    from mathutils import Vector
    from mathutils.geometry import intersect_point_line

    persmat = rv3d.perspective_matrix.copy()
    viewinv = rv3d.view_matrix.inverted()
    coord_vec = region_2d_to_vector_3d(region, rv3d, coord)
    depth_location = Vector(depth_location)

    if rv3d.is_perspective:
        from mathutils.geometry import intersect_line_plane

        origin_start = viewinv.translation.copy()
        origin_end = origin_start + coord_vec
        view_vec = viewinv.col[2].copy()
        return intersect_line_plane(origin_start,
                                    origin_end,
                                    depth_location,
                                    view_vec, 1,
                                    )
    else:
        dx = (2.0 * coord[0] / region.width) - 1.0
        dy = (2.0 * coord[1] / region.height) - 1.0
        persinv = persmat.inverted()
        viewinv = rv3d.view_matrix.inverted()
        origin_start = ((persinv.col[0].xyz * dx) +
                        (persinv.col[1].xyz * dy) +
                         viewinv.translation)
        origin_end = origin_start + coord_vec
        return intersect_point_line(depth_location,
                                    origin_start,
                                    origin_end,
                                    )[0]

        def bezier_error(self, error_max=-1.0, test_count=8):
            from mathutils.geometry import interpolate_bezier

            test_points = interpolate_bezier(self.points[0].co,
                                             self.handle_left,
                                             self.handle_right,
                                             self.points[-1].co,
                                             test_count,
                                             )

            from mathutils.geometry import intersect_point_line

            error = 0.0

            # this is a rough method measuring the error but should be ok
            # TODO. dont test against every single point.
            for co in test_points:
                # initial values
                co_best = self.points[0].co

                length_best = (co - co_best).length
                for p in self.points[1:]:
                    # dist to point
                    length = (co - p.co).length
                    if length < length_best:
                        length_best = length
                        co_best = p.co

                    p_ix, fac = intersect_point_line(co, p.co, p.prev.co)
                    p_ix = p_ix
                    if fac >= 0.0 and fac <= 1.0:
                        length = (co - p_ix).length
                        if length < length_best:
                            length_best = length
                            co_best = p_ix

                error += length_best / test_count

                if error_max != -1.0 and error > error_max:
                    return True

            if error_max != -1.0:
                return False
            else:
                return error

    def hover(self,context,x,y):
        '''
        hovering happens in screen space, 20 pixels thresh for points, 30 for edges
        '''
        self.mouse = Vector((x, y))
        if len(self.pts) == 0:
            return

        def dist(v):
            diff = v - Vector((x,y))
            return diff.length
        
        loc3d_reg2D = view3d_utils.location_3d_to_region_2d
        screen_pts =  [loc3d_reg2D(context.region, context.space_data.region_3d, pt) for pt in self.pts]
        closest_point = min(screen_pts, key = dist)
        
        if (closest_point - Vector((x,y))).length  < 20:
            self.hovered = ['POINT',screen_pts.index(closest_point)]
            return

        if len(self.pts) < 2: 
            self.hovered = [None, -1]
            return
                    
        for i in range(0,len(self.pts)):   
            a  = loc3d_reg2D(context.region, context.space_data.region_3d,self.pts[i])
            next = (i + 1) % len(self.pts)
            b = loc3d_reg2D(context.region, context.space_data.region_3d,self.pts[next])
            
            if b == 0 and not self.cyclic:
                self.hovered = [None, -1]
                return
            
            if a and b:
                intersect = intersect_point_line(Vector((x,y)).to_3d(), a.to_3d(),b.to_3d()) 
                if intersect:
                    dist = (intersect[0].to_2d() - Vector((x,y))).length_squared
                    bound = intersect[1]
                    if (dist < 900) and (bound < 1) and (bound > 0):
                        self.hovered = ['EDGE',i]
                        return
                    
        self.hovered = [None, -1]

def f_4(me, list_e, list_0):

    dict_1 = {vi: [] for vi in list_0}

    for i in list_e:
        lp1 = (me.vertices[i[0]].co).copy()
        lp2 = (me.vertices[i[1]].co).copy()
        for vi in list_0:
            v = (me.vertices[vi].co).copy()
        
            p1 = intersect_point_line( v, lp1, lp2)[0]
        
            me.vertices.add(1)
            me.vertices[-1].co = p1
            me.vertices[-1].select = False
            dict_1[vi].append(me.vertices[-1].index)

    n = len(list_e)
    edge_copy_1(me, dict_1, n)
    faces_copy_1(me, dict_1, n)

    def start_grad_f(f, p):

        g = gradient_face(f, geos)
        L = f.calc_perimeter()

        # test for vert intersection
        for v in f.verts:
            v_inter, pct = intersect_point_line(v.co, p, p - L * g)

            delta = v.co - v_inter
            if delta.length < epsilon:
                print("intersects vert")
                return v, v.co, None

        for e in f.edges:

            v0, v1 = intersect_line_line(e.verts[0].co, e.verts[1].co, p, p - L * g)

            V = v0 - e.verts[0].co
            edV = e.verts[1].co - e.verts[0].co
            Vi = v0 - p

            if V.length - edV.length > epsilon:
                # print('intersects outside segment')
                continue
            elif V.dot(edV) < 0:
                # print('intersects behind')
                continue

            elif Vi.dot(g) > 0:  # remember we watnt to travel DOWN the gradient
                # print('shoots out the face, not across the face')
                continue
            else:
                # print('regular face edge crossing')
                return v0, e, f

        # we didn't intersect across an edge, or on a vert,
        # therefore, we should travel ALONG the edge

        vret = min(f.verts, key=geos.get)
        return vret.co, vret, None