exploring splitting triangles in Processing Python mode

helpers.py

from __future__ import division

def point_inside_poly(x, y, points):
    # ray-casting algorithm based on
    # https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html
    inside = False
    for i, p in enumerate(points):
        pp = points[i - 1]
        xi, yi = p
        xj, yj = pp
        intersect = ((yi > y) != (yj > y)) and (
            x < (xj - xi) * (y - yi) / (yj - yi) + xi)
        if intersect:
            inside = not inside
    return inside

def line_intersect(*args, **kwargs):
    """
    Adapted from Bernardo Fontes https://github.com/berinhard/sketches/
    2020-11-14 Does not assume Line objects anymore, and works with 4 points or 8 coords.
    2021_09_26 Adding intersection outside the segments. Also fixing bug when calling with 8 coords as arguments.
    2021_09_26 Removed line_a & line_b variables, rewrote ZeroDivision exception catching as a conditional check.
    """
    as_PVector = kwargs.get('as_PVector', False)
    in_segment = kwargs.get('in_segment', True)
    
    if len(args) == 2:  # expecting 2 Line objects or 2 tuples of 2 point tuples.
        (x1, y1), (x2, y2) = args[0]
        (x3, y3), (x4, y4) = args[1]
    elif len(args) == 4:
        (x1, y1), (x2, y2) = args[:2]
        (x3, y3), (x4, y4) = args[2:]
    elif len(args) == 8:
        x1, y1, x2, y2, x3, y3, x4, y4 = args
    else:
        raise ValueError, "line_intersect requires 2 lines, 4 points or 8 coords."
            
    divisor = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1)
    if divisor:
        uA = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / float(divisor)
        uB = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / float(divisor)
    else:
        return None
    if not in_segment or 0 <= uA <= 1 and 0 <= uB <= 1:
        x = x1 + uA * (x2 - x1)
        y = y1 + uA * (y2 - y1)
        return PVector(x, y) if as_PVector else (x, y)
    else:
        return None
    
def ccw(*args):
    """Returns True if the points are arranged counter-clockwise in the plane"""
    if len(args) == 1:
        a, b, c = args[0]
    else:
        a, b, c = args
    return (b[0] - a[0]) * (c[1] - a[1]) > (b[1] - a[1]) * (c[0] - a[0])

def edges_as_sets(poly_points, frozen=True):
    """
    Return a (frozen)set of poly edges as frozensets of 2 points.
    """
    if frozen:
        return frozenset(frozenset(edge) for edge in poly_edges(poly_points))
    else:
        return set(frozenset(edge) for edge in poly_edges(poly_points))

def poly_edges(poly_points):
    """
    Return a list of edges (tuples containing pairs of points)
    for a list of points that represent a closed polygon
    """
    return pairwise(poly_points) + [(poly_points[-1], poly_points[0])]


def pairwise(iterable):
    from itertools import tee
    "s -> (s0, s1), (s1, s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

split_triangles_v2.pyde

from __future__ import division
from helpers import line_intersect, point_inside_poly, ccw

def setup():
    size(500, 500)
    noCursor()
    
def draw():
    background(200)
    scale(2)
    noFill()
    stroke(0)
    t1 = [(100, 100), (200, 100), (150, 150)] ; draw_t(t1)
    t2 = [(mouseX, mouseY), (mouseX +50, mouseY), (mouseX + 25, mouseY + 100)]; draw_t(t2)
    edges1 = t_edges(t1)
    edges2 = t_edges(t2)
    split_edges1 = []
    for edge in edges1:    
        split_edges1 += split_edges(edge, edges2)               
    split_edges2 = []
    for edge in edges2:    
        split_edges2 += split_edges(edge, edges1)               
    stroke(255, 0, 0)     
    edges1_in_t2 = [edge for edge in split_edges1 if edge_in_poly(edge, t2)]
    draw_edges(edges1_in_t2)
    # draw_edges(split_edges1)   
    stroke(0, 0, 200)
    edges2_in_t1 = [edge for edge in split_edges2 if edge_in_poly(edge, t1)]
    draw_edges(edges2_in_t1)
    # draw_edges(split_edges2)   
    
def split_edges(edge, edges):
    points = []
    for other in edges:
        ip = line_intersect(edge, other)
        if ip:
            points.append(ip)
            circle(ip[0], ip[1], 5)
    if not points:
        return  [edge]
    else:
        return split_single_edge(edge, points)

def split_single_edge(edge, points):
    if len(points) == 1:
        return [(edge[0], points[0]), (points[0], edge[1])]
    elif sq_dist(edge[0], points[0]) < sq_dist(edge[0], points[1]):
        return [(edge[0], points[0]), (points[0], points[1]), (points[1], edge[1])]         
    else:
        return [(edge[0], points[1]), (points[1], points[0]), (points[0], edge[1])]         
            
def sq_dist(a, b):
    (xa, ya), (xb, yb) = a, b
    return (xa - xb) * (xa - xb) + (ya - yb) * (ya - yb)
            
def draw_edges(edges):
    push()
    translate(2, 2)
    for (xa, ya), (xb, yb) in edges:
        line(xa, ya, xb, yb)
    pop()

def edge_in_poly(edge, poly):
    x, y = midpoint(edge)
    return point_inside_poly(x, y, poly)

def midpoint(edge):
    (xa, ya), (xb, yb) = edge
    return (xa + xb) / 2.0, (ya + yb) / 2.0
    
def draw_t(t):
    triangle(*(t[0] + t[1] + t[2]))

def t_edges(t):
    a, b, c = t if not ccw(t) else t[::-1]
    return [(a, b), (b, c), (c, a)]