How to pick up line segments which is inside or intersect a circle?

Question

I have sets of line segments AB1, AB2, ... ABn. Each one has (Ax, Ay), (Bx, By) coordinates. Then, I have circle with a center coordinate (Cx, Cy) and r (radius).

Problem: How can I detect which line segment lies on a circle (in figure) OR not? .

I tried to formulate my idea in Python:

import numpy as np
import pylab as plt

def detect(A,B, C, r):
    '''
    Returns 'True' if line is inside or intersected the circle, otherwise 'False'.
    Inputs:
       - A - segment line coordinate (Ax, Ay)
       - B - segment line coordinate (Bx, By)
       - C - circle coordinate (Cx, Cy)
       - r - circle radius
    ''' 
    # Do process for detection
    return (boolean)

def plot_detected(An, Bn, C, r):
    '''
    Plots newly detected line segments with red color 
    while the rest remains with blue color 
    '''
    plt.figure(1)
    plt.subplot(111)
    for A, B in zip(An, Bn):
        if detect(A, B, C, r):
              line1, = plt.plot([ A[0], B[0] ], [ A[1], B[1] ], 'ro-')
        else:
              line2, = plt.plot([ A[0], B[0] ], [ A[1], B[1] ], 'bo-')
    pl.legend([line1, line2], ('detected','un-detected'))
    plt.show()

def main():
    C = [18.5, 18.5]
    r = 2.4
    Ax = np.array([16.2, 17.2, 22.2, 18.2, 23.8, 18.8])
    Ay = np.array([22.8, 20.6, 23.8, 18.4, 20.8, 22.8])
    Bx = np.array([21.8, 19.8, 18.2, 19.8, 17.2, 22.8])
    By = np.array([17.8, 17.2, 19.2, 19.2, 16.8, 20.8])
    An = np.vstack([Ax, Ay]).T
    Bn = np.vstack([Bx, By]).T

    plot_detected(An, Bn, C, r)

if __name__ == '__main__':
    main()

Thank you for your help in advance.

Answer 1

For each line, you should be able to compute the point on the line that is minimally distant from the circle centre. To do that, you project the position vector of the centre onto the line's direction vector. Call that minimally-distant point P. If P is within the circle (i.e. the sqrt of the sum of squares of its coordinates is less than the circle radius) and P is also between the line segment's end points, then the line segment intersects the circle.

You also have to check whether the line endpoints themselves are inside the circle.

def detect( A, B, C, r ):

    # First, let's express each vector as a complex number.
    # This simplifies the rest of the code because we can then subtract them
    # from each other in one statement, or find their length with one statement.
    # (Downside: it does not allow us to generalize the code to spheres in 3D.)
    OA = complex( *A )
    OB = complex( *B )
    OC = complex( *C )

    # Now let's translate into a coordinate system where A is the origin
    AB = OB - OA
    AC = OC - OA

    # Before we go further let's cover one special case:  if either A or B is actually in
    # the circle,  then mark it as a detection
    BC = OC - OB
    if abs( BC ) < r or abs( AC ) < r: return True

    # Project C onto the line to find P, the point on the line that is closest to the circle centre
    AB_normalized = AB / abs( AB )
    AP_distance = AC.real * AB_normalized.real  +  AC.imag * AB_normalized.imag    # dot product (scalar result)
    AP = AP_distance * AB_normalized   # actual position of P relative to A (vector result)

    # If AB intersects the circle, and neither A nor B itself is in the circle,
    # then P, the point on the extended line that is closest to the circle centre, must be...

    # (1) ...within the segment AB:
    AP_proportion = AP_distance / abs( AB )   # scalar value: how far along AB is P?
    in_segment =   0 <= AP_proportion <= 1

    # ...and (2) within the circle:
    CP = AP - AC
    in_circle = abs( CP ) < r

    detected = in_circle and in_segment


    #OP = OA + AP
    #plt.plot( [OC.real, OP.real], [OC.imag, OP.imag], {True:'rs--', False:'bs--'}[detected] )

    return detected



def plot_detected(An, Bn, C, r):
    '''
    Plots newly detected line segments with red color 
    while the rest remains with blue color 
    '''
    plt.figure(1)
    plt.clf()
    plt.subplot(111)
    for A, B in zip(An, Bn):
        if detect(A, B, C, r):
              line1, = plt.plot([ A[0], B[0] ], [ A[1], B[1] ], 'ro-')
        else:
              line2, = plt.plot([ A[0], B[0] ], [ A[1], B[1] ], 'bo-')
    plt.legend([line1, line2], ('detected','un-detected'))
    circle = mpatches.Circle( C, r, fc="none", ec='k' )
    plt.gca().add_patch(circle)
    plt.gca().set_aspect('equal')