Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say I have this circle here.

What would be an algorithm to check if lines like the green or blue lines intersect the edge of the circle, but not the red line.

So lets say

if(amountOfPointsHit(line, circle) > 1) then return true
else return false

enter image description here

I only know the start and finish points of the lines, and not where the line intersects the circle. So the pseudo code would more be like

if(pointBetweenXYHit(x1, y1, x2, y2, circle) > 1) then return true
else return false

Here is the code I came up with based on the answers...

/**
*@param l1  Line point 1, containing latitude and longitude
*@param l2  Line point 2, containing latitude and longitude
*@param c   Center of circle, containing latitude and longitud
*@param r   Radius of the circle
**/
Maps.ui.inCircle = function(l1, l2, c, r){
    var a = l1.lat() - l2.lat()
    var b = l1.lng() = l2.lng()
    var x = Math.sqrt(a*a + b*b)
    return (Math.abs((c.lat() - l1.lat()) * (l2.lng() - l1.lng()) - 
           (c.lng() -  l1.lng()) * (l2.lat() - l1.lat())) / x <= r);
}

pseudo code for that ^^ is

method inCircle (line1point, line2point, center, radius)
    let l1 = line1point
    let l2 = line2point
    let c = center
    let r = radius
    x is length between points line1point and line2point
    return true if ((c.x - l1.x) * (l2.y * l1.y) - (c.y - l1.y) * (l2.x - l2.y)) / x) 
    is less then or eqaul to r
share|improve this question
    
do you have center of circle and radius of circle? –  Santosh Linkha Jan 11 '13 at 0:52
    
Check out the question –  FabianCook Jan 11 '13 at 0:55
    
I dont think your code cares about the end points of line segments. I added code to my answer. –  ryu jin Jan 11 '13 at 1:01
    
Check pseudo code? –  FabianCook Jan 11 '13 at 1:02
    
We only want to know if it intersects it, if any point of the line lays within the circle we want to return true –  FabianCook Jan 11 '13 at 1:48

3 Answers 3

up vote 2 down vote accepted

You can find the shortest distance from a point to a line using the formula $$\operatorname{distance}(ax+by+c=0, (x_0, y_0)) = \frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}. $$ Put $(x_0,y_0)$ = center of circle. If this distance is smaller (or equal) than radius of circle, then your line and circle intersects.

Since you know start point $(x_1,y_1) $ and end point $(x_2, y_2) $, you can get the equation of line using formula $$y - y_1 = \frac{y_2 - y_1}{x_2 - x_1}(x-x_1)$$ Simplifying, we get $$ (x_2 - x_1) y + (y_1 - y_2)x +(x_1-x_2)y_1 + x_1(y_2-y_1) = 0$$ It would be nice to store $a = x_2 - x_1, b = y_1 - y_2, c = (x_1-x_2)y_1 + x_1(y_2-y_1)$

It would be something like

return (Math.abs((l2.lat() - l1.lat())*c.lat() +  c.lng()*(l1.lng() -     
       l2.lng()) + (l1.lat() - l2.lat())*l1.lng() +
       (l1.lng() - l2.lng())*c.lat())/ Math.sqrt((l2.lat() - l1.lat())^2 +
       (l1.lng() - l2.lng())^2) <= r)

something like $$ \frac{\left | (x_2 - x_1)x_0 + (y_1 - y_2)y_0 + (x_1-x_2)y_1 + x_1(y_2-y_1) \right |}{\sqrt{(x_2 - x_1)^2 + (y_1 - y_2)^2}} \le r$$

share|improve this answer

Let $A = (A_x,A_y)$ and $B = (B_x,B_y)$ be the end points of a line segment. Then all points of the line are $A + t (B-A)$ for $0 < t < 1$.

Let $C = (C_x,C_y)$ be the center of the circle and $R$ its radius. Then all points of the circle are $(x,y)$ such that $(x-C_x)^2 + (y-C_y)^2 = R^2$ by Pythagoras theorem.

By moving everything we can have $C = (0,0)$, this makes calculations a bit simpler. The equation of the circle becomes $x^2 + y^2 = R^2$.

As for number of points of intersection: there will be either 0 - no intersection, 1 - it is a tangent line or 2 - it goes right through the circle.

The points of intersection must satisfy both equations simultaneous. $(x,y)$ is a point of intersection if $x^2 + y^2 = R^2$ and $(x,y) = A + t (B-A)$ for some $0 < t < 1$.

We can split $(x,y) = A + t (B-A)$ into components:

  • $x = A_x + t (B_x - A_x)$
  • $y = A_y + t (B_y - A_y)$

and put this into the circle equation

$$(A_x + t (B_x - A_x))^2 + (A_y + t (B_y - A_y))^2 = R^2$$

multiply it out

$$[A_x^2 + A_y^2 - R^2] + 2 [A_x (B_x - A_x) + A_y (B_y - A_y)] t + [(B_x - A_x)^2 + (B_y - A_y)^2] t^2 = 0$$

this is a simple quadratic equation, you can use the discriminant ("$b^2 - 4ac > 0$") to check if there are two real values of $t$, then you must check if they are between 0 and 1.

// parameters: ax ay bx by cx cy r
ax -= cx;
ay -= cy;
bx -= cx;
by -= cy;
a = ax^2 + ay^2 - r^2;
b = 2*(ax*(bx - ax) + ay*(by - ay));
c = (bx - ax)^2 + (by - ay)^2;
disc = b^2 - 4*a*c;
if(disc <= 0) return false;
sqrtdisc = sqrt(disc);
t1 = (-b + sqrtdisc)/(2*a);
t2 = (-b - sqrtdisc)/(2*a);
if(0 < t1 && t1 < 1 && 0 < t2 && t2 < 1) return true;
return false;
share|improve this answer

A line segment intersects the edge of the circle if the distance between the center and the line segment is less than or equal to the radius and at least one end of the line segment is outside the circle.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.