CGAL users discussion list

[Malcolm Ryan <>]

On 29/01/2007, at 3:09 PM, Malcolm Ryan wrote:

> As far as I can see, the Do_intersect test should be reasonably  
> simple:
>
> Consider the distance d from the centre of the circle to the line  
> defined by the segment.
>      If (d > radius) return 0 solutions
>
> if (distance(centre, source) < radius) then
>    if (distance(centre, target) < radius) return 0 solutions;
>    else return 1 solution;
> else if (distance(centre, target) < radius) then
>    return 1 solution;
> else
>    construct a line perpendicular to the segment, passing through  
> the centre of the circle
>    if (source and target are on the same side of this line) return  
> 0 solutions
>    else if (d == radius) return 1
>    else return 2 solutions.
>
> This should all be doable with existing predicates in the 2d  
> kernel, except for the construction of the perpendicular line in  
> the fourth line from the bottom. I can't see any easy way to avoid  
> that, without resorting to algebra.

Aha. It can be replaced with an angle() test which sees if the angle  
given by (source, target, centre) is obtuse (no solutions) or acute  
(1 or 2 solutions).

Malcolm

           "Cleanliness is not next to godliness nowadays,
                for cleanliness is made an essential
              and godliness is regarded as an offence.
                                    - G.K.Chesterton, On Lying in Bed