0

Okay, I want to be able to calculate whether a line crosses a circle(at least a part of the line inside the circle). I found several answers to this, but I thought they were too complicated so I came up with this. I'm no math guy, so I'm kinda stuck now. When the line is aligned vertically the "radius >= Math.sqrt(len * len + len * len - o);" becomes true( with 45° angles it becomes 0). I have no clue why this happens. Thanks :)

function lineInCircle(sx, sy, x, y, cx, cy, radius) {
    cx -= sx; x -= sx; //sx is the first point's x position
    cy -= sy; y -= sy;//sy is the first point's y position
    len = Math.sqrt((cy * cy) + (cx * cx))//hypotenuse of circle (cy, cx) to (0, 0) (with offset)
    atanx = Math.atan(y / x); //angle of  (0, 0) to (x, y) in radians
    atany = atanx - Math.atan(cy / cx); //to center
    var o = 2 * len * len * Math.cos(atany);
    var o = o < 0 ? -o:o//Had to do this, at some point the value can become inverted
    return radius >= Math.sqrt(len * len + len * len - o);
}

Edit:

function lineInCircle(sx, sy, x, y, cx, cy, radius) {
    cx -= sx; x -= sx; //sx is the first point's x position
    cy -= sy; y -= sy;//sy is the first point's y position
    ctp = Math.sin(Math.atan(y / x) - Math.atan(cy / cx)) * Math.sqrt((cy * cy) + (cx * cx));
    return radius >= ctp && ctp >= -radius;
}

Works pretty much the same but is faster. The problem is that it calculates an infinite line. How would I fix that?

Edit 2:

function lineInCircle(sx, sy, x, y, cx, cy, radius) {
    cx -= sx; x -= sx;
    cy -= sy; y -= sy;
    var h = Math.sqrt(cy * cy + cx * cx)
    ctp = Math.sin(Math.atan(y / x) - Math.atan(cy / cx)) * h;
    sideb = Math.sqrt(h * h - ctp * ctp);
    line = Math.sqrt(x * x + y * y)
    if (sideb - radius > line) {return false}
    return radius >= ctp && ctp >= -radius;
}

Partial fix, doesn't go on to infinity for one direction from the line(line end)

Edit 3: A bit longer but more than twice as fast, back to square one

function lineInCircle2(sx, sy, x, y, cx, cy, radius) {
    var ysy = y - sy
    var xsx = x - sx
    var k = ((y-sy) * (cx-sx) - (x-sx) * (cy-sy)) / (ysy * ysy + xsx * xsx)
    var ncx = cx - k * (y-sy)
    var ncy = cy + k * (x-sx)
    ncx -= cx
    ncy -= cy
    var ctp = Math.sqrt(ncx * ncx + ncy * ncy)
    return radius >= ctp && ctp >= -radius;
}

Edit 4: Success!

function lineInCircle(sx, sy, x, y, cx, cy, radius) {
    if (sx > cx + radius && x > cx + radius || x < cx - radius && sx < cx - radius) {return false;}
    if (sy > cy + radius && y > cy + radius || y < cy - radius && sy < cy - radius) {return false;}
    var k = ((y - sy) * (cx - sx) - (x - sx) * (cy - sy)) / ((y - sy) * (y - sy) + (x - sx) * (x - sx))
    var ncx = k * (y - sy)
    var ncy = k * (x - sx)
    return radius >= Math.sqrt(ncx * ncx + ncy * ncy);
}

Does exactly what I want, I optimized it down to 4.5 - 4.6 seconds for 100000000 iterations compared for 10+ secs for the first version and still is much more accurate(meaning no more weird behavior in certain angles). I'm satisfied :D

thabubble
  • 640
  • 1
  • 8
  • 17
  • Your question currently just consists of a bunch of code. What is the logic behind this code? Perhaps posting a diagram would help. – Oliver Charlesworth Jun 01 '12 at 20:17
  • 3
    Perhaps this question can help: http://stackoverflow.com/questions/1073336/circle-line-collision-detection – Fernando Jun 01 '12 at 20:27
  • I'm making a "game" which consists of 9 dots, you know the "think outside of the box" game. This was to try and see what you can do with a html5 canvas. And for one to complete it, you have to get all those 4 line to cover all the dots. – thabubble Jun 01 '12 at 21:09
  • @Fernando. Yeah, I've read that. I don't know why but I have no clue what to do with it. I can't wrap my head around it. – thabubble Jun 01 '12 at 21:10

2 Answers2

0

Too much work. Find the normal that passes through the center, and see if the intersection is closer than the radius.

Ignacio Vazquez-Abrams
  • 776,304
  • 153
  • 1,341
  • 1,358
0
function lineInCircle(sx, sy, x, y, cx, cy, radius) {
    if (sx > cx + radius && x > cx + radius || x < cx - radius && sx < cx - radius) {return false;}
    if (sy > cy + radius && y > cy + radius || y < cy - radius && sy < cy - radius) {return false;}
    var k = ((y - sy) * (cx - sx) - (x - sx) * (cy - sy)) / ((y - sy) * (y - sy) + (x - sx) * (x - sx))
    var ncx = k * (y - sy)
    var ncy = k * (x - sx)
    return radius >= Math.sqrt(ncx * ncx + ncy * ncy);
}

Takes about 4.5 - 4.6 seconds for 100000000 iterations to finish on my machine.

thabubble
  • 640
  • 1
  • 8
  • 17