由點定義的兩條任意線之間的中線（即-賽道的中線）。

假設我有兩個閉合的環路，在二維x、y空間中代表一個賽道的邊界。每個環路的起點如果用一條線連接，將代表起點/終點線，這條線的中點將代表賽道的中心線。

從起跑線向外移動，每個回圈都由線段組成，這些線段的長度是隨機的，變化相對較小。每個環路的線段數量較多，約為20-40K。

考慮到這一點，我試圖解決的問題是找到一個代表其他兩個回圈的中線的封閉回圈（即--軌道的中心線）。

起初我認為，鑒于每條小線段的長度相對接近，我可以采取一個長度為一段的步驟，該步驟是兩個環路中較小的一段，這個較短的長度被用來通知沿長線段的一個點，然后在兩個長度相等的步驟之間找到一個中點。沿著每條線的新位置被更新，并且這個程序重復進行，有效地在具有較短步驟的活動回圈之間來回切換。

我正在 python 中進行這項作業，我有一個包含兩個回圈的 X 和 Y 位置（x = *.PositionX 和 y = *.PositionZ）的 csv 檔案。以下是我試圖使用的內容，供參考

import traceback
import pandas as pd
import numpy as np
from matplotlib import pyplot as plt    

fDict = {"Bernese Alps":{"fName":"2021-09-12202910_FM7_DASH"，"left"。 4,"right":6},
         "Maple Valley":{"fName":"2021-08-30171416_FM7_DASH", "left": 4,"right":1},}

track = "Maple Valley"。

df = pd.read_csv(fDict[track]["fName"/span>] ".csv")

#對應于賽道左右極限的圈數。
lapRight = fDict[track]["right"]
lapLeft = fDict[track]["left"]

#Position from history for right and left>
rightPos = df.loc[df.LapNumber==lapRight,['PositionX','PositionZ']]
leftPos = df.loc[df.LapNumber==lapLeft,['PositionX','PositionZ']]

#Vector difference from one position to the next both right and left]。
rightDiff = rightPos.diff()
rightDiff.iloc[0] = rightPos.iloc[0] -rightPos.iloc[-1]
leftDiff = leftPos.diff()
leftDiff.iloc[0] = leftPos.iloc[0]-leftPos.iloc[-1]

#Vector difference magnitudes one position to the next both right and left[/span
rightDiffMag = (rightDiff.PositionX.copy()*0 np.linalg.norm(rightDiff,axis=1)。 rename({'PositionX':'PositionMag'})
leftDiffMag = (leftDiff.PositionX.copy()*0 np.linalg.norm(leftDiff,axis=1) 。) rename({'PositionX':'PositionMag'})

#Normalized vectors to project to
rightDiffNormed = rightDiff.div(rightDiffMag,'index')
leftDiffNormed = leftDiff.div(leftDiffMag,'index')

#Methods to find center point尋找中心點的方法
#(原本使用x和y的平均值，但為了確認我沒有做錯而改變)。
def right_to_left(rightX, rightZ, leftX, leftZ)。
    rtl_diff = np.array([leftX-rightX,leftZ-rightZ])
    rtl_mag = np.sqrt(sum(rtl_diff**2)
    rtl_dir = rtl_diff/rtl_mag
    return rtl_dir,rtl_mag

def midPoint(rightX,rightZ, leftX, leftZ)。
    rtl_dir, rtl_mag = right_to_left(rightX,rightZ,leftX,leftZ)
    mid_vec = rtl_dir*rtl_mag*.5。
    return rightX mid_vec[0], rightZ mid_vec[1]

#創建新的右、左和中線容器。
rights = [[rightPos.iloc[0].values[0]], [rightPos.iloc[0].values[1] ]
lefts = [[leftPos.iloc[0].values[0]], [leftPos.iloc[0].values[1] ]]
midP = midPoint(rights[0][0],rights[1][0] 。 lefts[0][0],lefts[1][0] )
mids = [[midP[0]],[midP[1] ]

#Initialize which size is longer].

#Initialize partial remainders from prior step
partials = {'left':0.0，'right':0.0}。
#Initialize indicie tracking for each side。
indicies = {'left':1,'right':1}。

print(len（leftPos）,len（rightPos）)
key = input("PAUSED - 'Y' TO CONTINUE 'N' TO ABORT: ")
if key.lower() == 'y':
    Done = False: 完成 = False.
    try:
        while not Done。
            rightIdx = rightPos.index[indicies['right']]
            leftIdx = leftPos.index[indicies['left']]

            #向前推演一個點。
            rightIdx_fwd = rightPos. index[0] if indicies['right'] > =len(rightPos)-1 else rightPos. index[indicies['right'] 1]
            leftIdx_fwd = rightPos. index[0] if indicies['left']> =len(leftPos)-1 else leftPos。 index[indicies['left'/span>] 1]



            #If remaining left side is longer]。
            if leftDiffMag.loc[leftIdx]-partials['left'/span>] >= rightDiffMag.loc[rightIdx]-partials['right'/span>] 。
                active_side = 'left'#Step magnitude is full right step。
                mag = rightDiffMag.loc[rightIdx]-partials['right']
                if not mag partials['left'] >= leftDiffMag.loc[leftIdx_fwd] 。
                    partials['left'] = mag
                else:
                    partials['left']=0.0。
                    indicies['left'] =1。

                引數['right']=0.0
                indicies['right'] =1
            else:
                #Step magnitude is full right step。
                active_side = 'right''left']

                if not mag partials['right'] >= rightDiffMag.loc[rightIdx_fwd] 。
                    partials['right'] = mag
                else:
                    partials['right']=0.0。
                    indicies['right'] =1。

                引數['left']=0.0
                indicies['left'] =1。

            rightUpdate = rightPos.loc[rightIdx] mag*rightDiffNormed.loc[rightIdx_fwd] 。
            leftUpdate = leftPos.loc[leftIdx] mag*leftDiffNormed.loc[leftIdx_fwd] 。
            midP = midPoint(*rightUpdate.value,*leftUpdate.value)

            rights[0].append(rightUpdate.PositionX)
            rights[1].append(rightUpdate.PositionZ)
            lefts[0].append(leftUpdate.PositionX)
            lefts[1].append(leftUpdate.PositionZ)
            mids[0].append(midP[0])
            mids[1].append(midP[1])

            #print(active_side,indicies['left'],leftIdx,indicies['right'],rightIdx,Mag) 

            if indicies['right'/span>]> =len(rightPos)-1 and indicies['left'] > =len（leftPos）-1。
                Done=True：

    except 例外 as err:
        traceback.print_exception(None, err, err.__traceback__)

        print(len(rights[0]) 。 len(lefts[0]),len(mids[0))


        axi = plt.subplot()
        axi.plot(*rights,ls='-'/span>,marker='.'/span>,c='r')
        axi.plot(*lefts,ls='-',marker='。',c='b')
        axi.plot(*mids,ls='-',marker='。',c='k')
        axi.set_aspect('equal')

        fig,axes = plt.subplots(2)
        for i in range（2）。
            axes[i].plot(rights[i],c='r'/span>)
            axes[i].plot(lefts[i],c='b')
            axes[i].plot(mids[i],c='k')

        #fig,axi = plt.subplots()。
        #for rX,rZ,lX,lZ,mX,mZ in zip（*rights,*lefts,*mids）:
            #axi.plot([rX,mX,lX],[rZ,mZ,lZ], c='k')
    最后。
        plt.show()

else:
    print("處理被中止！")

這比我預期的要好，但是：

這比我預期的要好。

• 它很慢，并且
• 取決于曲率/曲率差異（我假設這是驅動誤差的原因），在一個特定的轉彎中，兩個回圈之間的曲率/曲率差異導致將中線拉向一側或另一側。
• 此外，我不確定這是否是一個實施問題或簡化了粗略方法的工件，但對中心線的更新是有噪音/鋸齒的（見下面的評論，我相信這是實施中的一個錯誤）
。

我正在尋找任何能夠找到中心線的方法。如果它能很好地獲得中心線的法線矢量（及其反面--旋轉180度），以及該法線與任何一個邊界環的相應交點（即--代表軌道上任何一點的中線與起點的距離的線），則可加分。如果中心線的步長被歸一化，則可進一步加分。

考慮到我知道行進方向和兩個環路起點的中心點，我在想一個解決方案，那就是為中心線定義一個步長，然后用這個步長代表一個半徑等于步長的半圓，然后求解與這個圓相切的最短直線，該直線以兩個外環路的交點為界。我在下面粗略地說明了這一點。我不確定是否有一種有效/優雅的方法來使用這種方法進行求解。

感謝您提供的任何反饋/指導。我認為可能有一個已知的解決方案來解決這種型別的問題，而我只是使用了錯誤的搜索條件來尋找例子。

PS - 更加仔細地觀察，似乎外環的更新存在畸變，這可能有助于解釋中線的鋸齒狀更新。無論如何，我認為中線向一側傾斜仍然是該方法的一個缺陷，而不是一個實施問題。

更新。

更新。 這似乎是GIS領域中經常出現的問題，在這個領域中，多段線被用來代表河流的邊界，而河流的中線是需要的。

顯然，一個解決方案是生成一個Voronoi圖。這樣做將自然產生代表中線的多角頂點和邊。

舉例說明。

現在我只需要檢測那些位于兩個外部邊界內的Voronoi多邊形頂點。

另外需要注意的是，正如你所期望的那樣，該方法很難處理自相交的軌道，因此我可能需要檢測這種情況，或者通過將軌道切割成多個部分然后再縫合起來來手動防止它。

在起點/終點線上也產生了一些假象。

uj5u.com熱心網友回復：

最終，scipy Voronoi和matplotlib path.contains_points的組合能夠找到中線。我還沒有解決自相交的問題，而且在起點和終點的非中線點上還存在一些小問題，但這些問題是相當小的。

下面是作業解決方案的完整代碼：

而這里是一個輸出的例子：

開始檢查，尋找多邊形內的Voronoi頂點......

檢查164,650個點中哪些位于94,514個點的多邊形內 點中的哪一個位于多邊形的94,514個點內，需要143.72秒才能完成。

。

PS - 使用matplotlib path.contains_points來尋找中線，主要是為了方便使用。正如所指出的那樣，這種方法可能需要一兩分鐘才能從一個由大約10萬個點組成的多邊形中的15萬多個頂點中找到中線。對于這種規模的多邊形和點串列，可能有更有效的解決方案，但這個方法符合我的需求，而且很容易使用。如果你對更快的東西感興趣，請看。在python中檢查一個點是否在一個多邊形內的最快方法是什么

uj5u.com熱心網友回復：

暫時假設在一個特定的位置，外面是兩條相當長的線段。中心線將由與它們的正交投影訃為每條線的距離相等的點組成。我強烈懷疑，如果你的線段以黑森法線形式表示，即ax by c=0，a2 b2=1，那么只要將這兩個方程相加，就可以得到作為角平分線的中心線的方程，即平行線段的相應概括。請確保這些線的法線具有相匹配的方向，例如，從沿中心線行駛的車輛的方向看，所有的線都是向左行駛。

由于你在每一側有多條線段，你需要考慮到它們之間的變化。在任何一邊，你都可能有一個凸面或凹面的頂點，也就是說，在一個（輕微的）角落里，邊界會向外或向內彎曲。如果它向外彎曲，那么就有一個點，中心線與在該角相遇的兩個線段的距離相等。在這一點上，你就用其中一條來定義中心線，而開始用另一條來代替。一個不同的觀點是，兩個連續的線段中的每一個都與對面的線段一起定義自己的中心線，而兩個中心線相交的點就是你從一個線段轉換到另一個線段的地方。你最終又變成了線段。

如果一個角向內彎曲，那么對于中心線上的某些點，該邊界上最近的點將不是線段的正交投影，而是那個角。與一個點和一條線距離相等的所有點的集合是一個拋物線，點是它的焦點，線是它的直角。正交投影將落在那一邊的兩個線段之外。線和線段之間的交叉點將是正交投影與每個線段的終點重合的地方，即在通過其端點的垂直于該線段的線上。你是否準備在你的輸出中處理中心線的拋物線，或者你是否需要以某種方式近似這些？

如果您的兩邊都有相近的角，所有這些都會變得更加復雜。你可能會遇到這樣的情況：中心線的拋物線被直角段的變化所打斷，以及類似的情況。獲得一個完整的解決方案，保證對所有的輸入都做正確的事情，聽起來是一個重大的努力。在大多數典型的使用情況下，能夠合理地作業的東西應該是可以做到的。

到目前為止，這一直是一個相當數學化的答案。為了使我們的演算法更加合理，假設您目前正在查看一對相對的線段以及它們之間的中心線。你的代碼應該確定每條邊上的下一個角，以及該角之后的線段。有了這些資訊，它就可以確定當前的直線中心線將結束于那個角的位置。取兩個變化中較近的一個，以適當的方式將中心線段縫合在一起（可能使用拋物線片），然后用其中一個段交換其后續段。注意那些終點在起點之前的中心線段，那是事情變得混亂的地方。我沒有一個現成的解決方案來處理它們，但可以在測驗資料上檢查它們，以決定在實踐中它們有多大的可能性和多壞。

標籤：

上一篇：TinyMCE編輯器不顯示在JQueryUI對話框內

下一篇：檢查例外型別而不考慮TC#