Circle-line collision

[1micha.elok]

It's been 2 years since Marcus introduced this polygon - circle line collision, and it still has me wondering. I keep staring at it, trying to figure out what it's actually supposed to be. It's probably just a quick test model again  

Code:

#win32
set window "Collision", 640, 480
set redraw off

'Vertices
v  = []
v.square    = [-50, -50, 50, -50, 50, 50, -50, 50]
v.star      = [0, -100, 25, -25, 100, 0, 25, 25, 0, 100, -25, 25, -100, 0, -25, -25]
v.rectangle = [0, 0, 129, 0, 129, 31, 0, 31]
v.tmp1      = [0, 0, 200, 0, 200, 31, 0, 31]
v.tmp2      = [0, 0, 31, 0, 31, 415, 0, 415]
v.cross = [-19,-59, -19,-19, -59,-19, -59,20, -19,20, -19,60, 20,60, 20,20, 60,20, 60,-19, 20,-19, 20,-59]

visible lines = []
filledPolys = []

'             MakePoly(verts,       x, y,       r, g, b,        lines, renderList)
square      = MakePoly(v.square,    320, 240, 255, 100, 100,    lines, filledPolys)
star        = MakePoly(v.star,      425, 100, 100, 255, 100,    lines, filledPolys)
cross       = MakePoly(v.cross,     175, 125, 100, 100, 255,     lines, filledPolys)
rectangle   = MakePoly(v.rectangle, 110, 300, 100, 255, 255,    lines, filledPolys)
rectangle2  = MakePoly(v.rectangle, 425, 300, 100, 255, 255,    lines, filledPolys)
tmp1        = MakePoly(v.tmp1,       50, 416, 255, 100, 255,    lines, filledPolys)
tmp2        = MakePoly(v.tmp2,       32,  32, 255, 100, 255,    lines, filledPolys)

'Balls
visible objs = []
ballCount = 0
objs[ballCount] = Object(rnd(0,width()), 0, 16)


'-----------
' Main Loop
'-----------
while not keydown(KEY_ESCAPE, true)
    ' Clear screen 
    set color 0, 0, 0; cls

    ' Draw grid
    set color 64, 64, 64
    for gx = 0 to 640 step 64  draw line gx, 0, gx, 480 
    for gy = 0 to 480 step 64  draw line 0, gy, 640, gy 

    ' Rotate obstacles: + = clockwise, - = counter-clockwise
    square.SetAngle(square.Angle() + rad(0.5))
    star.SetAngle(star.Angle() + rad(0.25))
    cross.SetAngle(cross.Angle() - rad(0.5))
    rectangle.SetAngle(rectangle.Angle() - rad(0.25))
    rectangle2.SetAngle(rectangle2.Angle() + rad(0.25))
   
    ' draw obstacles
    foreach polygn in filledPolys  polygn.DrawFilled()

    ' coordinate labels, infobox
    set color 255, 255, 255
    shapes = [square,star,cross,rectangle,rectangle2,tmp1,tmp2]
    for i = 0 to sizeof(shapes)-1   
        DrawCoordLabel(shapes[i])
    next
    set caret width()/2+100, height()-50; center "Press ENTER for more balls"

    ' balls
    foreach ball in objs
        UpdateObject(ball)
        DrawObject(ball)
    next
   
    i = 0
    while i < ballCount - 1
        j = i + 1
        while j < ballCount
            ResolveBallCollision(objs[i], objs[j])
            j = j + 1
        wend
        i = i + 1
    wend
   
    'Drop ball
    if keydown(KEY_RETURN,true) then
        objs[ballCount] = Object(rnd(0,width()), 0, 16)
        ballCount = ballCount + 1
    endif

    redraw
    fwait 60
wend


'------------
' Functions
'------------
function Object(x, y, r)
    return [x: x, y: y, r: r, rsqr: r*r, dx: 0, dy: 0, pdx: 0, pdy: 0]
endfunc

' Draw ball
function DrawObject(obj)
    set color 255, 255, 0
    draw ellipse obj.x, obj.y, obj.r, obj.r, true
endfunc

' Update ball
function UpdateObject(obj)
    obj.dy = obj.dy + 0.1
    if obj.dy > 6 then obj.dy = 6
   
    ' Update position
    obj.x = obj.x + obj.dx
    obj.y = obj.y + obj.dy
   
    ' Collision detection
    PushOut(obj, lines)
endfunc

' ResolveBallCollision
function ResolveBallCollision(b1, b2)
    dx = b2.x - b1.x; dy = b2.y - b1.y
    distSq = dx*dx + dy*dy
    minDist = b1.r + b2.r
    minDistSq = minDist * minDist
   
    ' Early exit if no collision or zero distance
    if distSq >= minDistSq or distSq = 0 then return
   
    dist = sqr(distSq)
           
    ' push apart
    overlap = minDist - dist
    b1.x = b1.x -  overlap; b1.y = b1.y -  overlap
    b2.x = b2.x +  overlap; b2.y = b2.y +  overlap 
endfunc

' PushOut: collision resolution
function PushOut(obj, lines)
    for i = 1 to 4
        col = false
        foreach ln in lines
            dp = max(0, min(ln[6], (obj.x - ln[0])*ln[4] + (obj.y - ln[1])*ln[5]))
            px = ln[0] + dp*ln[4]; py = ln[1] + dp*ln[5]
            dx = obj.x - px; dy = obj.y - py
            d = dx*dx + dy*dy
           
            if d < obj.rsqr
                k = 1/sqr(d)
               
                obj.x = px + dx*k*obj.r
                obj.y = py + dy*k*obj.r
               
                obj.dx = obj.dx + 0.5 * dx*k
                obj.dy = obj.dy + 0.5 * dy*k
                col = true
            endif
        next
        if not col break
    next
endfunc

' Polygon
function Polygon(points, x, y, r, g, b)
    p = [trans: unset, org: [], verts: [], x: x, y: y, a: 0, cx: 0, cy: 0, r: r, g: g, b: b]
    pcount = sizeof(points)/2
   
    ' Store original vertices
    for i = 0 to pcount - 1
        p.verts[sizeof(p.verts)] = points[i*2]
        p.verts[sizeof(p.verts)] = points[i*2 + 1]
    next
   
    ' collision lines
    n = pcount - 1
   
    for i = 0 to n
        j = (i + 1)%pcount
        p.org[sizeof(p.org)] = Line(
                points[i*2], points[i*2 + 1],
                points[j*2], points[j*2 + 1])
    next
   
    for i = 0 to pcount - 1
        p.cx = p.cx + points[i*2]; p.cy = p.cy + points[i*2 + 1]
    next
    p.cx = p.cx/pcount; p.cy = p.cy/pcount
    p.trans = copy(p.org)
   
    p.AddTo = function(lines)
        foreach ln in .trans  lines[sizeof(lines)] = ln
    endfunc

    p.X = function(); return .x ;endfunc
    p.Y = function(); return .y ;endfunc
    p.Angle = function(); return .a ;endfunc
   
    p.SetTransform = function(x, y, angle)
        .x = x; .y = y; .a = angle; .Transform()
    endfunc
    p.SetPosition = function(x, y)
        .x = x; .y = y; .Transform()
    endfunc
    p.SetAngle = function(angle)
        .a = angle; .Transform()
    endfunc
   
    p.Transform = function()
        RotateLines(.org, .trans, .cx, .cy, .a)
        foreach ln in .trans
            ln[0] = ln[0] + .x; ln[1] = ln[1] + .y
            ln[2] = ln[2] + .x; ln[3] = ln[3] + .y
            ln[4] = (ln[2] - ln[0])/ln[6]; ln[5] = (ln[3] - ln[1])/ln[6]
        next
    endfunc
   
    p.DrawFilled = function()
        set color .r, .g, .b
        vcount = sizeof(.verts)/2
        polyArgs = []
        for i = 0 to vcount - 1
            vx = .verts[i*2] - .cx; vy = .verts[i*2 + 1] - .cy
            ' Apply rotation
            rx = vx*cos(.a) - vy*sin(.a)
            ry = vx*sin(.a) + vy*cos(.a)
            polyArgs[sizeof(polyArgs)] = rx + .cx + .x
            polyArgs[sizeof(polyArgs)] = ry + .cy + .y
        next
        draw poly polyArgs, true
    endfunc
   
    p.Transform()
    return p
   
    function RotateLines(srcLines, dstLines, aroundX, aroundY, angle)
        c = cos(angle); s = sin(angle)
        for i = 0 to sizeof(srcLines) - 1
            srcLn = srcLines[i]; dstLn = dstLines[i]
            x = srcLn[0] - aroundX; y = srcLn[1] - aroundY
            dstLn[0] = aroundX + x*c - y*s; dstLn[1] = aroundY + y*c + x*s
            x = srcLn[2] - aroundX; y = srcLn[3] - aroundY
            dstLn[2] = aroundX + x*c - y*s; dstLn[3] = aroundY + y*c + x*s
        next
    endfunc   
endfunc

function Line(x0, y0, x1, y1)
    ln = [x0, y0, x1, y1]
    dx = ln[2] - ln[0]; dy = ln[3] - ln[1]
    ln[6] = sqr(dx*dx + dy*dy)
    ln[4] = dx/ln[6]
    ln[5] = dy/ln[6]
    return ln
endfunc

function MakePoly(verts, x, y, r, g, b, lines, renderList)
    p = Polygon(verts, x, y, r, g, b)
    p.AddTo(lines)
    renderList[sizeof(renderList)] = p
    return p
endfunc

function DrawCoordLabel(p)
    set caret p.X(), p.Y()
    wln "X"
    wln (int(p.X())) + "," + (int(p.Y()))
endfunc