Collinearity of points


  • admin

    This is an attempt at determining collinearity of a series of points. Rather than compare tangents, one stackoverflower suggested calculating areas of triangles. Other strategies?

    def polygon_area(points):  
        area = 0
        q = points[-1]
        for p in points:  
            area += p[0] * q[1] - p[1] * q[0]
            q = p
        return area / 2
        
    def plot(points):
        if len(points) < 3:
            return None
        a = 0
        for pi, p in enumerate(points[:-2]):
            npt = points[pi+1]
            nnpt = points[pi+2]
            a += abs(polygon_area([points[pi], npt, nnpt]))
        return a
            
    pts = [
        (725,417),
        (548, 440),
        (414, 458),
        (261, 479)
        ]
    
    # tolerance for error
    margin = 200
    
    v = plot(pts)
    
    print("plotted area", v)
    fontSize(100)
    if -.5*margin < v < .5*margin:
        text("colinear",(100,100))
    else:
        text("not colinear",(100,100))
    
    # draw the dots
    fill(0,0,1)
    stroke(1,0,0)
    translate(100,100)
    newPath()
    moveTo(pts[0])
    for p in pts[1:]:
        lineTo(p)
    drawPath()
    
    ds = 10
    fill(0,0,1)
    stroke(None)
    for p in pts:
        oval(p[0]-.5*ds, p[1]-.5*ds, ds, ds)
    


  • what would be 'compare tangents'?
    ā€”
    comparing angles is probably more expensive?

    def get_angle(p1, p2): return atan2((p2[1] - p1[1]), (p2[0] - p1[0]))
            
    pts = [
        (725,417),
        (548, 440),
        (414, 458),
        (261, 479)
        ]
    
    angles = [ get_angle(point, pts[p+1]) for p, point in enumerate(pts[:-1])]
    angle = get_angle(pts[0], pts[-1])
    
    
    # tolerance for error
    margin = pi/180
    
    fontSize(100)
    if all(abs(a - angle) < margin for a in angles):
        text("colinear",(100,100))
    else:
        text("not colinear",(100,100))
    
    # draw the dots
    fill(0,0,1)
    stroke(1,0,0)
    translate(100,100)
    newPath()
    moveTo(pts[0])
    for p in pts[1:]:
        lineTo(p)
    drawPath()
    
    ds = 10
    fill(0,0,1)
    stroke(None)
    for p in pts:
        oval(p[0]-.5*ds, p[1]-.5*ds, ds, ds)
    


  • That animation of the KABK crown I did: was looking into this question so as to avoid having to define the collinear = invalid segments explicitly ā€” having the code test the combinations is a more elegant solution.
    https://twitter.com/MauriceMeilleur/status/973090865882296325