0

線分のセットがありAB1, AB2, ... ABnます。それぞれに(Ax, Ay), (Bx, By)座標があります。次に、中心座標 (Cx、Cy) と r (半径) を持つ円があります。

問題: どの線分が円の上にあるか (図中)、またはそうでないかをどのように検出できますか? 図での説明.

私は自分の考えを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()

よろしくお願いいたします。

4

2 に答える 2

2

各線について、円の中心からの距離が最小である線上の点を計算できるはずです。これを行うには、中心の位置ベクトルを線の方向ベクトルに投影します。その最小距離点を P と呼びます。P が円内にあり (つまり、その座標の平方和の平方根が円の半径よりも小さい)、P が線分の端点の間にある場合、線分はサークル。

線の端点自体が円の内側にあるかどうかも確認する必要があります。

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')
于 2014-11-04T00:42:35.290 に答える
0

1つ目: タスク定義のトポロジーを明確にする

用語の定義：

すべての「線分」が与えられます。

各線分は、各端点のデカルト ペアによって定義され[x,y]ます。

トポロジー条件に関する最初の質問文は、次のように述べています。

円の上にある線分 を検出する(図中) またはしない?

著者自身のコメントは次のように追加します。

交差するだけでなく、円内にあるセグメントを見つけます。

質問のタイトルには次のように記載されています。

円の内側または交差する線分をピックアップ

タイトルとコメントで確認されているように、「線分」が「円の上に横たわる」ためのトポロジー条件を満たすには、{ 1 | 2 }端点のいずれかが円の内側にあれば十分です。

このトポロジーの仮定が失敗した場合、jez-posted ベクトル法線距離ソリューションは正しいです。

解決：

明確な用語定義とトポロジー条件に基づいて、定義された制約を満たす「線分」のセットは次のように取得されます。

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

    aBooleanANSWER = ( aCartesianDISTANCE( A, C ) <= r )
                     or
                     ( aCartesianDISTANCE( B, C ) <= r )

    return ( aBooleanANSWER )
于 2014-11-04T16:07:11.957 に答える