Circle to Line Collision - Help needed!

I’ve been updating my Touchline game, getting it ready to submit to the App Store and have hit a snag with my collision detection. I’ve just switched to a new collision detection algorithm for my line to circle collisions, but something’s wrong. Most of the time it’s detecting collisions perfectly, but occasionally I can manage to stick a line straight through a circle and nothing seems to be detected. See the following video for an example:

http://cl.ly/2M3X2P3T2f3w0L2U2G0x

My other issue is that I need to be able to tell how far away a given circle is, and I’m not sure if this algorithm will provide me with that. Any help any of you maths geniuses could provide me would be very much appreciated.

I got the algorithm I’m using from the following Stack Overflow post: http://stackoverflow.com/questions/1073336/circle-line-collision-detection

Code for a simplified test app:

------------------------------------------
-- MAIN
------------------------------------------
    
function setup()
    touches = {}
    enemies = {}
    
    -- generate some random enemies
    for i = 1,5 do
        local x = math.random(0,WIDTH)
        local y = math.random(0,HEIGHT)
        table.insert(enemies, Enemy(x,y))
    end
    
    ship = Ship()
end

function draw()
    background(40, 40, 50)
    
    local startTouch = nil
    local endTouch = nil        
    
    for k,touch in pairs(touches) do
        endTouch = startTouch
        startTouch = touch
    end
    
    if endTouch then
        -- if we have two touches, tell the ship about them
        ship:setPoints(startTouch, endTouch)
        ship:draw()
    end

    for i,v in ipairs(enemies) do
        -- check for collisions and update enemies
        if endTouch then ship:collide(v) end
        v:draw()
    end
end

function touched(touch)
    touches[touch.id] = vec2(touch.x, touch.y)
end

HIT = 4
NOT_HIT = 1


------------------------------------------
-- SHIP
------------------------------------------

Ship = class()

function Ship:init(col)
    self:reset(col)
end

function Ship:reset(col)
    self.startPoint = nil
    self.endPoint = nil
    
    self.lineLength = 0.0
    self.lineWidth = 12
    self.currentWidth = 12
    
    self.lightColor = col or color(184, 248, 24, 255) 
    self.darkColor = col or color(184, 248, 24, 255) 
end

function Ship:setPoints(startp, endp)

    -- keep track of which point is leftmost
    if startp.x < endp.x then
        self.startPoint = startp
        self.endPoint = endp
    else
        self.startPoint = endp
        self.endPoint = startp
    end
end

function Ship:draw()
    self.lineLength = self.startPoint:dist( self.endPoint )
        
        pushStyle()
        
            noSmooth()
            lineCapMode(PROJECT)
            stroke(self.darkColor)
            strokeWidth(self.currentWidth)
            line(self.startPoint.x, self.startPoint.y, self.endPoint.x, self.endPoint.y)
                
            stroke(self.lightColor)
            strokeWidth(self.currentWidth - 4)
            line(self.startPoint.x, self.startPoint.y, self.endPoint.x, self.endPoint.y)
            
        popStyle()
end

function Ship:collide(v)
    -- v is a circle
    local d = self.endPoint - self.startPoint
    local f = self.startPoint - v.position
    local r = v:halfWidth()
    
    local a = d:dot( d ) 
    local b = 2*f:dot( d ) 
    local c = f:dot( f ) - r*r 

    local discriminant = b*b-4*a*c
    if( discriminant < 0 ) then
        -- no intersection
        v:style(NOT_HIT)
    else
      -- ray didn't totally miss sphere,
      -- so there is a solution to
      -- the equation.
    
      discriminant = math.sqrt( discriminant )
      local t1 = (-b + discriminant)/(2*a)
      local t2 = (-b - discriminant)/(2*a)
    
      if( t1 >= 0 and t1 <= 1 ) then
        -- solution on is ON THE RAY.
        v:style(HIT)
      else
        -- solution "out of range" of ray
        v:style(NOT_HIT)
      end
    
      -- use t2 for second point
    end
end

------------------------------------------
-- ENEMY
------------------------------------------

Enemy = class()

function Enemy:init(x,y)
    self.position = vec2(x,y)
    self.size = math.random(20,200)
    self.distance = 0
    self.c = color(255, 0, 0, 255)
end

function Enemy:draw()
    fill(self.c)
    noStroke()
    ellipseMode(CENTER)
    ellipse(self.position.x, self.position.y, self.size)
    
    font("Futura-Medium")
    fontSize(20)
    fill(255, 255, 255, 255)
    text(self.distance, self.position.x, self.position.y)
end

function Enemy:style(num)
    -- restyle the enemy based on how we're colliding
    if num == NOT_HIT then
        self.c = color(255, 0, 0, 255)
    else
        self.distance = "HIT"
        self.c = color(0, 255, 162, 255)
    end
end

-- register the current distance from the line to this enemy
function Enemy:skim(distance)
    self.distance = distance
end

function Enemy:miss()
    self.distance = 0
end 

function Enemy:halfWidth()
    return self.size * 0.5
end

As a guy who always turns first to brute force, I’d solve this by first filtering both lines and circles by a bounding boxes, then pulling the end points of the line as it intersects the circle’s box, then test the center point of that segment against the center and diameter of the circle. Not elegant, but should be straightforward and more or less foolproof.


------------------------------------------
-- MAIN
------------------------------------------
    
function setup()
    touches = {}
    enemies = {}
    
    -- generate some random enemies
    for i = 1,5 do
        local x = math.random(0,WIDTH)
        local y = math.random(0,HEIGHT)
        table.insert(enemies, Enemy(x,y))
    end
    
    ship = Ship()
end

function draw()
    background(40, 40, 50)
    
    local startTouch = nil
    local endTouch = nil        
    
    for k,touch in pairs(touches) do
        endTouch = startTouch
        startTouch = touch
    end
    
    if endTouch then
        -- if we have two touches, tell the ship about them
        ship:setPoints(startTouch, endTouch)
        ship:draw()
    end

    for i,v in ipairs(enemies) do
        -- check for collisions and update enemies
        if endTouch then ship:collide(v) end
        v:draw()
    end
end

function touched(touch)
    touches[touch.id] = vec2(touch.x, touch.y)
end

HIT = 4
NOT_HIT = 1


------------------------------------------
-- SHIP
------------------------------------------

Ship = class()

function Ship:init(col)
    self:reset(col)
end

function Ship:reset(col)
    self.startPoint = nil
    self.endPoint = nil
    
    self.lineLength = 0.0
    self.lineWidth = 12
    self.currentWidth = 12
    
    self.lightColor = col or color(184, 248, 24, 255) 
    self.darkColor = col or color(184, 248, 24, 255) 
end

function Ship:setPoints(startp, endp)

    -- keep track of which point is leftmost
    if startp.x < endp.x then
        self.startPoint = startp
        self.endPoint = endp
    else
        self.startPoint = endp
        self.endPoint = startp
    end
end

function Ship:draw()
    self.lineLength = self.startPoint:dist( self.endPoint )
        
        pushStyle()
        
            noSmooth()
            lineCapMode(PROJECT)
            stroke(self.darkColor)
            strokeWidth(self.currentWidth)
            line(self.startPoint.x, self.startPoint.y, self.endPoint.x, self.endPoint.y)
                
            stroke(self.lightColor)
            strokeWidth(self.currentWidth - 4)
            line(self.startPoint.x, self.startPoint.y, self.endPoint.x, self.endPoint.y)
            
        popStyle()
end

function Ship:collide(v)
    -- v is a circle
    local d = self.endPoint - self.startPoint
    local f = self.startPoint - v.position
    local r = v:halfWidth()
    
    local a = d:dot( d ) 
    local b = 2*f:dot( d ) 
    local c = f:dot( f ) - r*r 

    local discriminant = b*b-4*a*c
    if( discriminant < 0 ) then
        -- no intersection
        v:style(NOT_HIT)
    else
      -- ray didn't totally miss sphere,
      -- so there is a solution to
      -- the equation.
    
      discriminant = math.sqrt( discriminant )
      local t1 = (-b + discriminant)/(2*a)
      local t2 = (-b - discriminant)/(2*a)
    
      if( t1 >= 0 and t1 <= 1 ) or ( t2 >= 0 and t2 <= 1 )  then
        -- solution on is ON THE RAY.
        v:style(HIT)
      else
        -- solution "out of range" of ray
        v:style(NOT_HIT)
      end
    end
end

------------------------------------------
-- ENEMY
------------------------------------------

Enemy = class()

function Enemy:init(x,y)
    self.position = vec2(x,y)
    self.size = math.random(20,200)
    self.distance = 0
    self.c = color(255, 0, 0, 255)
end

function Enemy:draw()
    fill(self.c)
    noStroke()
    ellipseMode(CENTER)
    ellipse(self.position.x, self.position.y, self.size)
    
    font("Futura-Medium")
    fontSize(20)
    fill(255, 255, 255, 255)
    text(self.distance, self.position.x, self.position.y)
end

function Enemy:style(num)
    -- restyle the enemy based on how we're colliding
    if num == NOT_HIT then
        self.c = color(255, 0, 0, 255)
    elseif num == NOT_QUITE_HIT then
        self.c = color(0, 62, 255, 255)
    else
        self.distance = "HIT"
        self.c = color(0, 255, 162, 255)
    end
end

-- register the current distance from the line to this enemy
function Enemy:skim(distance)
    self.distance = distance
end

function Enemy:miss()
    self.distance = 0
end 

function Enemy:halfWidth()
    return self.size * 0.5
end

When you check if the intersection point is on the line, you need to check both intersection points. You’re only checking one of them with your code so if that is the one off the line then you get a false negative.

Aha! Thanks so much, Andrew - I knew I must’ve missed something simple! :slight_smile:

Can you tell whether I can easily determine the actual distance between the spheres and the line? I’m thinking it’s something to do with the dot product of f, but I’m getting a far bigger number that would be correct.

lol - when I first saw your post, I thought “What you need here is a mathematician”.

Then I saw Andrew had posted and thought “whew”.

:slight_smile:

That was what I was hoping for :smiley:

I was going to ask: precisely what information do you want to know about the circle and the line?

From the code looks like frosty has the center of the circle, C, and the start and end points of the line segment, A and B. Assuming it’s a full line, not just a line segment, then you need to solve these equations

(C - A) + x = (B - A) * lambda
x * (B - A) = 0

x is the vector from the center of the circle, perpendicular to the line. So calc this

lambda = (C-A) dot (B-A) / (B-A) dot (B-A)

and once you know lambda, find x from the first equation. The distance from the line to the circle will be x - radius.

function Ship:collide(v)
    -- v is a circle
    -- rebase to one end of line
    local w = self.endPoint - self.startPoint
    local u = v.position - self.startPoint
    local r = v:halfWidth()
    
    -- projection of centre along line (not normalised)
    local a = u:dot(w)
    local d
    if a <= 0 then
        -- circle is closest to start of line
        d = u:lenSqr()
    else
        local b = w:lenSqr()
        if a >= b then
            -- circle is closest to end of line
            d = u:distSqr(w)
        else
            -- circle is closest to a point along the line
            d = u:lenSqr() - a*a/b
        end
    end
    if d > r*r then
        -- no intersection
        v:style(NOT_HIT)
    else
      -- intersection
        v:style(HIT)
    end
    return d
end

This computes the square of the distance from the point to the line segment. There are three possible cases: the point is over the line or is off to one side or the other. To figure out which, we compute the dot product of the vector from one end to the circle with the vector along the line. If this is negative, the circle is closest to the start point. If it is bigger than the square of the line length, then the circle is closest to the endpoint. Otherwise, it’s closet to some point in the middle and we can use Pythagoras to get the distance.

If you’re only interested in the distance if it is under a certain threshold then there’s an optimisation step to eliminate obvious cases (along the lines of Mark’s suggestion). Is this the case?

Yep, so all I need to know are two things:

  1. Has the line collided with a circle? If so, game over.
  2. How close to the line is a given circle? (circles change their colour as a warning the closer to the line they get).

So it doesn’t matter which part of the line it’s colliding with, just whether it’s collided at all, and if not how far away it is from the line.

As in the example code I posted, the line in question has a finite length.

Okay, so the routine I just posted works out the distance to the centre and then sets the style if the distance is less than the radius. It also returns the distance for later processing (could be done in the routine, of course).

(Actually, we always work with the squares to avoid square roots)

function Ship:collide(v,th)
    -- v is a circle
    -- th is a threshold factor 
    th = th or 1
    -- rebase to one end of line
    local w = self.endPoint - self.startPoint
    local u = v.position - self.startPoint
    local r = v:halfWidth()
    -- detection zone
    th = th*(.00625*r + 2.875)*r
    
    -- Set l = length of line
    -- then vector along line is w,
    -- let w# be the unit vector along line, so w = l * w#
    -- vector from start of line to centre of circle is u
    -- let w% be the unit normal to the line
    -- then u = s * w% + t * w# for some s and t
    -- s is the distance of u from the (infinite) line
    -- t is the parameter of the closest point to u along the line
    -- then s = u . w% = u x w# and t = u . w#
    -- if 0 < t < l then the distance is s
    -- if t < 0 it is the length of u
    -- if t > l it is the length of u - w
    
    -- th is our "threshold": we want to do a quick check to see if
    -- we're outside this value.  If so, we don't need to examine
    -- the situation too closely.
    -- So if |s| > th we exit, as we're further than th from the
    -- infinite line
    -- If t < - th we exit, as we're beyond the start by th 
    -- If t > l + th we exit, as we're beyond the end by th
    
    -- In fact, we work with squared quantities and don't normalise
    
    local a = u:dot(w) -- a = u . w = t * l
    local b = w:lenSqr() -- |w|^2 = l * l
    local c = math.abs(u:cross(w)) -- |u x w| = |s| * l
    local tth = th*th*b
    r = r*r
    c = c*c -- s*s*l*l
    -- |s| > th <=> s*s*l*l > th*th*l*l 
    -- t < -th <=> t*l *|t*l| < - th*th*l*l
    -- t > l + th <=> (t*l - l*l)|(t*l - l*l)| > th*th*l*l
    local ab = a - b
    if c > tth or a*math.abs(a) < - tth or ab*math.abs(ab) > tth then
        v:style(NOT_HIT,0)
        return
    end
    -- no bailout, need to compute actual distance (squared)
    local d,h,cl
    -- t < 0 <=> t*l < 0
    if a <= 0 then
        -- circle is closest to start of line
        d = u:lenSqr()
        if d > r then
            h = NOT_HIT
            cl = 1 - (d-r)/(th*th)
        else
            h = HIT
        end
    else
        -- t > l <=> t*l > l*l
        if a >= b then
            -- circle is closest to end of line
            d = u:distSqr(w)
            if d > r then
                h = NOT_HIT
                cl = 1 - (d-r)/(th*th)
            else
                h = HIT
            end
        else
            -- circle is closest to a point along the line
            d = c
            if d > r*b then
                h = NOT_HIT
                cl = 1 - (d-r*b)/tth
            else
                h = HIT
            end
        end
    end
    v:style(h,cl)
end

and

function Enemy:style(num,dist)
    -- restyle the enemy based on how we're colliding
    dist = dist or 0
    if num == NOT_HIT then
        self.c = color(255, 0, 255*dist, 255)
    else
        self.distance = "HIT"
        self.c = color(0, 255, 162, 255)
    end
end

What’s the main difference with this method of doing things? The threshold means you can avoid doing unnecessary calculations, and you get a non-squared distance value?

I’m not sure if anyone already said this, but you can just find the nearest point on the line and calf for that.

If it is a line segment, the way I would do that is by finding the equation of the line, then applying that to the circle. Then, rather than ending up with calc-ING for a slope and a circle you can calc for a horizontal line on the x axis and a circle.

The first step would be to see if the circles absolute Y position is grater than its radius- if so there is no intersection and you can skip the next parts.

If it is , then you can next check to see if it’s x is both >= 0 and <= the length of the line, n which case there is a collision and you can skip the next bit.

If the x position of the circle is less than zero, go to A, if grater, go to B

A- if the distance between the circles center and 0,0 is less than or equal to its radius there is a collision

B -if the distance between the circles center and (the length of the line),0 is less than or equal to its radius there is a collision

@frosty: With the latest code, the colour of the circle changes when you are near it. The change is gradual, depending on the distance. If the line segment is more than a certain distance away then there is no colour change, so the first thing we do is to see if the line segment is obviously more than that distance away. This is the first part, up to the -- no bailout line (I just noticed that the function should return at that point). Basically, this draws a rectangle around the line and checks to see if the centre of the circle is outside this rectangle. If so, it can’t be near enough for us to bother about so we don’t try to work out the actual distance.

If we’re inside that rectangle, we need to work out the actual distance. The algorithm is pretty much as KMEB says, except that we don’t do an actual transformation - the “X” and “Y” coordinates that KMEB refers to are the “s” and “t” in the comments in my code.

The threshold is to allow you to customise - a bit - what the critical distance is. The critical distance depends on the radius of the circle that we’re testing so that for a small radius then it is proportionally larger than for a large radius. I’d probably go for something a bit more complicated than this at the end, but then it would be reasonable to save the threshold as a property of the circle.

can I use this code to determine if a touch on the screen was within, say, 5 or 10 pixels of a line that is drawn on screen?

@matkatmusic That’s a lot of code to go thru. Heres an example for some code. Slide your finger around the screen to see the distance change.

-- distance of point to line segment

function setup()
    s1=vec2(200,400)  -- line point
    s2=vec2(300,600)  -- line point
    p=vec2(300,100)  -- point position
end

function draw()
    background(40, 40, 50)
    fill(255)
    stroke(255)
    strokeWidth(2)
    line(s1.x,s1.y,s2.x,s2.y)
    ellipse(p.x,p.y,5)
    distPointToLineSeg(p,s1,s2)
    text(d1,WIDTH/2,HEIGHT-100)
end

function touched(t)
    if t.state==BEGAN or t.state==MOVING then
        p=vec2(t.x,t.y)
        distPointToLineSeg(p,s1,s2)
    end
end

function distPointToLineSeg(p,s1,s2)
    local v = s2 - s1
    local w = p - s1

    c1 = w:dot(v)
    if c1 <= 0 then
        d1=p:dist(s1)  -- distance
        return
    end

    c2 = v:dot(v)
    if c2 <= c1 then
        d1=p:dist(s2)  -- distance
        return
    end

    b = c1 / c2;
    pb = s1 + b * v;
    d1=p:dist(pb)  -- distance
end

@matkatmusic - please don’t resurrect three year old threads because it’s confusing. Rather start a new one and link to the old one.