Pythonで点と線の距離を計算したい

Question

Pythonを使用して点と線の距離を計算したいのですが、方法がわかりません。

こちらのサイトを拝見し、距離を計算するための公式を知ることはできました。

私は現在、地図上に目標とする座標を打ち、その点々でできた線を実際に歩いてみてGPSの座標を取得しています。
ですので、目標とする座標でできた線と、実際に歩いてできた座標のデータがあります。

上でリンクを貼ったサイトの図を流用して説明すると、点aと点bが目標とする座標で、それらの間に実際の座標の点cがたくさんあるような感じです。

また、目標の線も実際の座標も一方向だけに向かって進んでいるのではなく、途中で折り返す部分があったりして、どうやって処理すればいいか思い浮かびません。

今のところ、目標地点の座標が入っているリストをforループで回して、その中でさらに実際の座標が入っているリストをforループで回してます。二つ目のforループの中で、リンク先の公式を使い距離を求めています。
ですが、思っているような動きになりませんでした。

import numpy as np

target_list = [(,), ..., (,)] # 座標のタプルのリストになっている
actual_list = [(,),....,(,)]　# 座標のタプルのリストになっている
block = 0
length = 0

for a in range(len(target_list) - 1):
    for point in actual_list:                                                          　　　
        u = np.array([target_list[block+1][0] - target_list[block][0], target_list[block+1][1] - target_list[block][1]])
        v = np.array([point[0] - target_list[block][0], point[1] - target_list[block][1]])

        distance = abs(np.cross(u, v) / np.linalg.norm(u))
        if length < distance:
            length = distance
        # if文で条件分岐してblockをインクリメントする？

以上のような流れになるように思ったのですが、blockを進めていくためのインクリメントの方法もよくわかりません。
ループの回し方がおかしいのだと思うのですが、どのように考えればいいのでしょうか？

Comments

[y_waiwai]

思っていたような動きにならないとはどうなるんでしょうか。ソースコードもなし、その結果も省略されてるでは回答しようがありませんが。

[okmokm]

目標の線は点からできているので、二つの点（a,b）で線分をとり、その線分の範囲の中にある実際の点との距離を計算していき、実際の点が線分の範囲を超えたら次の線分に移って同様に計算していく、というような動きを考えていました。ですが、結果としては、実際の点の一点目だけで処理が回っていき、終わっているような状態です。

[tiitoi]

ある点からある直線への距離というならわかりますが、複数の線分がある場合、ある点から線分の距離といった場合、どのように定義するのでしょうか？質問の目的が2つの軌道がどれくらいかけ離れているかを示す指標を計算したいという動機であれば、他の方法もあるかと思います。

[okmokm]

計算の目的は仰っているように、二つの軌道がどれくらい離れているかを計算したいということです。しかし、これ以外に方法が思いつきませんでした。ほかにどのような方法が考えられるのでしょうか？

[tiitoi]

2つの軌道の差を計算するというのは SLAM という分野で出てくる話なので「Trajectory similarity」等で検索すると、計測方法について記載がある論文が出てきます。「点と線分の距離の差の合計」という計測方法ではどの線分との距離を計算するのかなど問題があり、軌道の誤差を計算するあまりいい指標にはならない気がします。

[okmokm]

SLAMという分野があるんですね、ありがとうございます。Trajectory Simiralityも調べたいと思います。「点と線分の距離の差の合計」というよりも、それぞれの実際の点と線分の距離を求め、それらの中で最も大きい値を最大の誤差とするような処理を考えていました。どちらにしても点と線分の距離を求めるのは難しいということですね。

[tiitoi]

点と線分の距離自体を求めるのは難しくないです。https://teratail.com/questions/155180 の回答にやり方を書いてあります。 ただ、そのやり方で目的である軌道のずれの計算につかえるかはわからないので、軌道の類似性を計測する他の手段も探してみてはという意味で書きました。

[okmokm]

もちろんtiitoiさんのコメントのご主旨は理解しています。言葉足らずですみませんでした。「軌道の類似性を計測する」という考え方が今まで思い浮かびませんでした。単純な計算ではできなさそうな感じですね…。ありがとうございます。

Answer 1

端的に云えば

if length < distance:

が、やりたいこととは逆の判定になっていると思われます。またblock変数については特にいじる必要はありません。
できるだけ提示されたコードを維持しつつ変数名の修正、コメント追加したコード例を示します。

import numpy as np
import sys

target_list = [(0,0),(1,1),(2,4)]               # 歩いた点群
actual_list = [(0.1,0.2),(1.1,1.2),(2.1,4,1)]   # 目標座標を結ぶ各線分を構成する点群
min_lens = sys.float_info.max  # 最近線分から最も近い歩いた点の距離。最大値をセット
max_lens =-sys.float_info.max  # 〃             遠い〃       距離。最小値をセット
for actual_pt in actual_list: # 各歩いた点について

    print('歩いた座標:{:.2f},{:.2f}'.format(actual_pt[0],actual_pt[1]))

    # まず、最も距離の近い線分を特定する
    min_len = sys.float_info.max  # 距離。最大値をセット

    for cur_idx in range(len(target_list) - 1): # 各線分について
        u = np.array([target_list[cur_idx+1][0] - target_list[cur_idx][0], target_list[cur_idx+1][1] - target_list[cur_idx][1]])
        v = np.array([actual_pt[0] - target_list[cur_idx][0], actual_pt[1] - target_list[cur_idx][1]])
        cur_len = abs(np.cross(u, v) / np.linalg.norm(u))

        # 現在の距離の方が小さい→最小値を更新
        if cur_len <= min_len:
            min_len = cur_len

    # 最近線分からの最も近い点、遠い点の距離を記憶する
    print('最近線分までの距離:{:.2f}'.format(min_len))
    if min_len <= min_lens:
        min_lens = min_len
    elif min_len >= max_lens:
        max_lens = min_len

print('最近線分からの最近距離:{:.2f}, 最遠距離:{:.2f}'.format(min_lens,max_lens))

Comments

[okmokm]

詳細な例までお示しいただきありがとうございます。
こちらのコードは折り返し地点でも関係なく計算可能なのでしょうか？
また、最も離れている座標、つまりどの実際の点が最も誤差があったのかを取得したい場合は、min_lenをどのように変更するのでしょうか？

[8524ba23]

まずは最も近い線分を求めるので
・折り返し地点でも問題ありません。
> また、最も離れている座標、つまりどの実際の点が最も誤差があったのか
最近と最遠の点の距離を最後に出力するように回答修正しました。

[okmokm]

sys.float_info.maxで最も近い線分を求めることができている、ということでしょうか？なぜこれだけのコードで最も近い線分を求めることができるのか、まだ理解できていないので、可能でしたらご説明いただきたいです。
また、このコードをリストの中身が千個以上あるようなデータで実行してみたところ、2分ほど時間がかかるのですが、どのようにすれば処理の時間を短くすることができるのでしょうか？

[8524ba23]

最近（小）値を求めるための初期値として、とても大きな数値を初期値としてセットしています。
この初期値をセットすることによって、必ず走査先頭のデータで最小値がセットされることが保証されます。
なお、根本的な考えは、コードコメントおよび簡単なデータ例値で動作を確認しつつ理解してみてください。
さらに処理時間を短くするにはforループではなくNumPyだけで行列演算すると可能ですが、まずは現在のコードの動きを理解をするのが先決かと思います。

[okmokm]

二つ目のforでの処理が、実際の点と最も近い線分を求める処理ということになると理解しています。
また、何度も恐縮なんですが、まれに明らかに最も誤差が大きい点を取れない場合があるのですが、どのような原因が考えられますか？

[8524ba23]

その誤差とはGPSの計測誤差ではありませんか？
であれば処理側では異常値を弾く必要があります。

[okmokm]

言葉が不足していてすみません。誤差とは実際の点と目標の軌道とが最も離れているときの実際の点のことです。
データ自体に異常値がある可能性があるということですね。