21
$\begingroup$

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

just image with three lines and one circle

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 - l1.x)) / x) 
    is less then or eqaul to r
$\endgroup$
5
  • $\begingroup$ do you have center of circle and radius of circle? $\endgroup$
    – S L
    Jan 11, 2013 at 0:52
  • $\begingroup$ Check out the question $\endgroup$
    – FabianCook
    Jan 11, 2013 at 0:55
  • $\begingroup$ I dont think your code cares about the end points of line segments. I added code to my answer. $\endgroup$
    – ryu jin
    Jan 11, 2013 at 1:01
  • $\begingroup$ Check pseudo code? $\endgroup$
    – FabianCook
    Jan 11, 2013 at 1:02
  • $\begingroup$ We only want to know if it intersects it, if any point of the line lays within the circle we want to return true $\endgroup$
    – FabianCook
    Jan 11, 2013 at 1:48

4 Answers 4

11
$\begingroup$

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 = y_1 - y_2, b = x_2 - x_1, 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.lng() +  c.lat()*(l1.lng() -     
       l2.lng()) + (l1.lat() - l2.lat())*l1.lng() +
       (l1.lng() - l2.lng())*l1.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$$

$\endgroup$
2
  • $\begingroup$ Not sure what I am doing wrong but I have a straight line with two points (a & b) of a line segment and if extended would intercept the exact center of a 100 radius circle at Point c, and yet it fails to show a number less than 100 or even 0 as it seems it should. My C# code static double target (Point a, Point b, Point c){ return Math.Abs((b.Y-a.Y)*c.X + (a.X-b.X)*c.Y + (a.Y-b.Y)*a.X + (a.X-b.X)*a.Y) / Math.Sqrt( Math.Pow((b.Y-a.Y),2) + Math.Pow((a.X-b.X),2) );} Test numbers: Point a = new Point(677,211);Point b = new Point(764,261);Point c = new Point(2912,1500); $\endgroup$
    – Edward
    May 8, 2017 at 22:28
  • 3
    $\begingroup$ this doesn't work for line segments, if you are after a solution for a finite line, check ryu jin's answer $\endgroup$ Nov 3, 2017 at 22:04
11
$\begingroup$

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 = (bx - ax)^2 + (by - ay)^2;
b = 2*(ax*(bx - ax) + ay*(by - ay));
c = ax^2 + ay^2 - r^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;
$\endgroup$
5
  • $\begingroup$ I think in your pseudo code a and c are swapped. I mean considering (at^2 + bt + c) = 0, a would be (bx - ax)^2 + (by - ay)^2, not c. $\endgroup$ Apr 22, 2018 at 15:06
  • $\begingroup$ Has the code been fixed? $\endgroup$
    – sammosummo
    Jan 13, 2019 at 13:07
  • $\begingroup$ Can confirm! a and c need to be switched. As of October 19 that is not corrected in the code. Just to make sure everybody has the right ones: a = (bx - ax)^2 + (by - ay)^2; and c = ax^2 + ay^2 - r^2; are the correct ones. $\endgroup$
    – macskay
    Oct 5, 2019 at 16:02
  • $\begingroup$ Note to future people: This has been fixed by Filip $\endgroup$ Apr 6, 2021 at 7:19
  • $\begingroup$ Confusion with coordinates is why the math should be done with vectors first and then converted to coordinates later. See my answer. $\endgroup$
    – qwr
    Jun 18, 2021 at 6:01
3
$\begingroup$

$\newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand\inner[2]{\langle #1, #2 \rangle}$ Frequently in computer graphics, if you work through the math in terms of vectors instead of coordinates, it makes the math simpler and works for any dimension. Say $v_1$ and $v_2$ are the endpoints of the line segment. Let $v = v_2 - v_1$ be a vector and WLOG let $C$ be a circle (or sphere in higher dimensions) centered at the origin with radius $r$. Then points on the line segment are given by $x = v_1 + t v$ for $0 \le t \le 1$.

We know points on the sphere are given by $\norm{x} = r$. Now we can simply solve $\norm{v_1 + tv}^2 = r^2$ and if there are real solutions we can check the values of $t$ to see if the intersections are within the line segment.

This gives us the quadratic equation in $t$ $$\norm{v}^2 t^2 + 2 \inner{v_1}{v} t + (\norm{v_1}^2 - r^2) = 0$$

We get real solutions for $t$ if discriminant $\Delta = 4 \inner{v_1}{v}^2 - 4\norm{v}^2 (\norm{v_1}^2 - r^2) \ge 0$, and the line is tangent if $\Delta = 0$. We can check if the intersections happen within the line segment by checking if $$ t = \frac{-2 \inner{v_1}{v} \pm \sqrt \Delta} {2 \norm{v}^2} = \frac{- \inner{v_1}{v} \pm \sqrt {\Delta/4}}{\norm{v}^2} $$ is between $0$ and $1$. These can be simplified in terms of coordinates for special cases of 2D and 3D and should be simplified in code for computational efficiency. For example, to just check if there are intersections for an infinite line, we only need to check if $r^2 ((x_2 - x_1)^2 + (y_2 - y_1)^2) \ge x_1 y_2 - x_2 y_1$. No division or squareroots in this computation!

$\endgroup$
3
  • $\begingroup$ Note this seems to be for infinite lines not line segments as the question shows. $\endgroup$
    – WDUK
    Jun 18, 2021 at 4:25
  • 1
    $\begingroup$ @WDUK I've cleaned up this old answer and added the line segment case $\endgroup$
    – qwr
    Jun 18, 2021 at 5:15
  • 1
    $\begingroup$ @WDUK I actually rewrote the answer again in a method that is coordinate free so works in 3D also $\endgroup$
    – qwr
    Jun 18, 2021 at 5:52
2
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .