Formula to determine if a line segment intersects a circle (flat)

views:

284

answers:

Formula to determine if a line segment intersects a circle (flat)

Hi,

Apologies if this is considered a repeat question, but the answers I've seen on here are too complex for my needs.

I simply need to find out if a line segment intersects a circle. I don't need to find the distance to the line from the circle center, I don't need to solve for the points of intersection.

The reason I need something simple is that I have to code this in SQL and am unable to call out to external libraries, and need to write this formula in a WHERE clause... basicaly it has to be done in a single statement that I can plug values in to.

Assuming 2 points A (Ax,Ay) and B (Bx,By) to describe the line segment, and a circle with center point C (Cx,Cy) and radius R, the formula I am currently using is:

( R*R* ( (Ax-Bx)(Ax-Bx) + (Ay-By)(Ay-By) ) ) -( ((Ax-Cx)(By-Cy))-((Bx-Cx)(Ay-Cy)) ) > 0

This formula is taken from link text, and is based on a 0,0 centered circle.

The reason I am posting is that I am getting weird results and I wondered if I did something stupid. :(

Hi Dan,

although this doesn't exactly answer your question: Do you really have to calculate this on the fly on a SQL-Select? This means that the DB-system has to calculate the formula for every single row in the table (or every single row for which the remaining where conditions hold, respectively) which might result in bad performance.

Instead, you might consider creating a separate boolean column and calculate its value in an on-insert/on-update trigger. There, in turn, you wouldn't even need to put the test in a single line formula. Using a separate column has another advantage: You can create an index on that column which allows you to get your set of intersecting/non-intersecting records very fast.

chiccodoro 2010-06-04 14:52:01

Thanks for the suggestion, but unfortunatly I need to do this calculation for many different circles (each time against many thousand line segments), so I can't calculate anything in advance.

Dan 2010-06-04 15:03:14

I see, the circle coordinates are not part of the records at all(?) You might want to specify that in your question.

chiccodoro 2010-06-04 15:17:39

It's probably worth mentioning that I filter out most of the lines before this calculation by checking that:1) at least one of the points A,B has an x value at least (circle center - radius)2) at least one of the points A,B has an x value at most (circle center + radius)3) at least one of the points A,B has a y value at least (circle center - radius)4) at least one of the points A,B has a y value at most (circle center + radius)If these conditions are not all met then the whole line lies outside the cross shape made by extending a square centered on the circle with length 2R.

Dan 2010-06-04 15:35:12

In response to your point about the circles... they are in the database it's just that there are potentially a lot of them, and they all will need to be checked against all lines. This calculation will be done once per database, so your suggestion is more or less what will happen in reality, except I will only store the intersections once calculated instead of storing all the non-intersections too. The whole DB gets wiped frequently and data re-imported and each time the intersects need to be calculated.

Dan 2010-06-04 15:42:12

ansaurus

tags:

views:

answers:

Formula to determine if a line segment intersects a circle (flat)

related questions