Q&A
ある線分m1->m2からある点m3がどれくらい離れているかは、多分m1-m2の距離(sqrt((x1-x2)^2+(y1-y2)^2)と原点と他2点で構成される三角形の面積(|x1y2-x2y1|/2)から計算できると思うので、その距離が所定の距離以内であることを全線分と点で順繰り順繰り確認すればいいのでは？(思いつき)
問題と実現したいこと
2次元XY平面座標上に、始点から終点まで複数の線分をつなげた道(Path)がある。
道は一本道で、途中で枝分かれはしないが交差することはありえる。
この道を、始点から終点まで人が逆走することなく移動する。
いま道が２本あり、それぞれ別の道にいる２人が手をつないで始点から終点まで移動するものとする。
このとき、２人の間の距離が一定以下のまま（手をつないだまま）移動できるかを判定したい。
すなわち「２本の道のかたち、軌跡が（ほぼ）同じか？」を判定したい。
この具体的な判定方法（アルゴリズム）、あるいはコードがあれば知りたい。
入力データと期待する結果例
Python
1# max_dist : つないだ手の長さ（移動する点間の最大距離） 2def is_same_path(path1, path2, max_dist=0): 3 ret = True 4 # 判定処理 5 return ret 6 7# 道は、連結された各線分の開始、終了位置座標のリストで構成される。 8 9# 線分の数や途中の線分の接続位置が異なっていてもOK 10p1 = [(0,0),(1,1),(3,3),(4,4)] 11p2 = [(0,0),(2,2),(4,4)] 12is_same_path(p1, p2) # True 13 14# 2本は重なっているが、終点が離れているのでNG 15p1 = [(0,0),(2,2)] 16p2 = [(0,0),(1,1)] 17is_same_path(p1, p2) # False 18 19# 2本は完全に重なっているが、1が逆走しないと離れてしまうのでNG 20p1 = [(0,0),(1,1),(2,2)] 21p2 = [(0,0),(1,1),(0,0),(2,2)] 22is_same_path(p1, p2) # False
たとえば以下は「（投影された）かたち」はほぼ同じだが軌跡が違うので違う道としたい
補足・制限
- 座標、距離は実数値
- 線分を構成する座標範囲は-10e8～+10e8程度
- 道を構成する線分数は最大でも10000程度
調べたこと、その他
線分と線分の距離など、１線分のみや線分と点の距離を測る方法はみつかるが、複数線分で構成されたものについては見つからなかった。
また、一般的なアルゴリズム、あるいは競技プログラミングの問題としてとりあげられていそうだが、問題を表すキーワードがうまく表現できず見つけることができなかった。
考えるきっかけとなった問題：高速に精度指定で図形に差分があるか判定する方法を見つけたい
折れ線AとBがあるとき，
「A側の全頂点について，折れ線Bまでの最短距離を調べて閾値を超過していたらアウト」
「B側の〃，折れ線Aまで〃」
という判定だけだとダメなパターンがある…という話かな？
一番離れる可能性が高いのは頂点だと思います。
ある頂点においてもう一方の道の各線分との距離を求め、その最小値を求めます。
これを両方の道の全ての頂点に行い、全ての最小値が範囲内にあれば二つの道は近いと言えるんじゃないでしょうか。
書いているうちにすれ違いましたが、fana さんと同じ考えだと思います。
ああ，例として
> # 2本は完全に重なっているが、1が逆走しないと離れてしまうのでNG
というのがあるので，やっぱりこんな話だとダメということですね．
（一方の側が現在位置から次の頂点まで行くことは可能か？ それが可能なとき，他方の側は最低どこまで進むのか？ みたいなのをスタート地点からやっていくような感じのことをする必要があるのかな？）
dameoさん、Zuishinさん、fanaさんコメントありがとうございます。
道として、軌跡（たどった経路）も同じものと判定したいので「順繰り順繰り」的な判定が必要になってくると思います。
どうもコードに落とし込めなくて、いっそ既存の考えなりコードがないものかと探しています。
「２人の間の距離が一定以下のまま（手をつないだまま）移動できるか」が
「２本の道のかたち、軌跡が（ほぼ）同じか？」と同じことなのかはわかりませんが、前者について考えると、
二人の移動速度が同一であることを前提として、同一長さの２線分において最大距離になるのは開始の頂点間か終了の頂点間どちらかになるかと思います。
初回はp1[0]とp2[0]の距離をmax_distと比較
次回からは
p1[0]p1[1]とp2[0]p2[2]で線分が短い方の長さをLとする。仮にp1[0]p1[1]が短いとする。
p2[0]p2[1]の線上でp2[0]から長さLの位置をp2[0]Lとする。
p1[1]とp2[0]Lの距離をmax_distと比較
以降 p1[1]p1[2]とp2[0]L P2[1]間の距離で短い方を判断・・・の繰り返し
(軌跡の比較としてありえるかわかりませんが)仮にどちらかのトータル長さが短く、一方が終点で止まったままのようなケースがある場合は、終点と一方の線分の残りの頂点との比較になるでしょうか。
愚直な方法ですが上記で実現できないですかね。
すみません、先の線分と点の距離の話で、線分を超えた部分の距離の計算が正しくなかったですね。線分と点で構成する3角形が90度以上になる場合(内積で簡単に分かる)は、点と点により近い方の線分の頂点間で距離を計算してください(線分と点の距離の公式があるならそれ使えばいい)。
順繰りと言ってた理由は素早く異なる経路判定できるようにという意図でした。逆走は順繰りやっていけば簡単に判定できると思いますし、何が出来ないという話なのかイマイチ分かりません。
> # 2本は完全に重なっているが、1が逆走しないと離れてしまうのでNG
> p1 = [(0,0),(1,1),(2,2)]
> p2 = [(0,0),(1,1),(0,0),(2,2)]
> is_same_path(p1, p2) # False
is_same_path(p1, p2, 0.8) は True ですか？
kazuma-sさん。はい。深く考えていなかったのですが、Trueになります。
1の人が、2の人が逆走することを見越して(0.5,0.5)の位置にとどまることで
max_distがルート(0.5**2+0.5**2)=約0.7 までならTrueとなります。
dameoさん、線分と点の距離について了解しました。
また、私が「順繰り順繰り」というご指摘に合点がいった点は、逆走せずに進む（通過済みの線分はもう考慮しなくてよい）という理解したからです。
「何が出来ないという話」については申し訳ありません。
率直にいって質問した時点ではそもそも「何をしたらいいのか（どのような考えで処理するか）」から分からなかったのですが、頂いたコメントからおおまかな流れが考えられそうに思えてきました。
Crimson_Tideさん、そうですね。
線分の長いほうの人が、短いほうの人が来るのをp2[0]Lの地点で待って進んでいくイメージでしょうか。
コメントありがとうございます。
is_same_path(p1, p2, 0.8)をTrueとすると
>たとえば以下は「（投影された）かたち」はほぼ同じだが軌跡が違うので違う道としたい
を否定することにならないでしょうか？
つまるところ「２人の間の距離が一定以下のまま移動できるか」だけでは、軌跡の類似性を担保できないと思うのですがいかがですか。
（「２人の間の距離が一定以下のまま移動できれば軌跡が類似しているとする」、と定義した上での問題だとするのであればそれはそれでよいですが、「（投影された）かたち」はほぼ同じだが軌跡が違うので違う道としたい」は守られないことになるかと思います。）
実際に判定する際の距離閾値というのは，軌跡の規模に対して相応に小さい，という話なのではないでしょうか．
例として微妙だけど【２人で並んで同じ道を歩いているときに，一方だけが途中で「あ，１０円みっけ！」って拾うために数歩戻った】みたいな．
Crimson_Tideさん
今回の質問では「軌跡の類似性」とは何か？それはどのように定義できるか？をいろいろ考えた末
とりあえず「２人の間の距離が一定以下のまま移動できれば軌跡が類似しているとする」という定義上での問題となります。
そしてfanaさんのコメントでのご指摘のとおり、閾値であるmax_distは道の総長と比較して小さい値を想定しています。
閾値が0だと完全にかたちも軌跡も一致する、という判定となりますが、これが0よりおおきな場合は、これが「ほぼ類似」の尺度となります。このような尺度が妥当、あるいは理解しやすいかといわれると正直微妙ですが。
ただ、このような問題（尺度）は既存の考えがありそうに思っており、それが知りたいところではあります…
p1=[(0,0),(1,0)]
p2=[(0,0),(0.9,0),(0.1,0),(1,0)]
max_dist=0 として
is_same_path(p1, p2, max_dist) は逆走を角度だけで判定しない場合、線分と点の距離方式だとTrueになってしまう気がしますね。
p1は線分1個しかないので、p2の各点が線分p1との距離を計算すれば全部0になるからです。
10円拾うだけでも逆走＝角度だけなら内積で判定できるけど…
dameoさん、コメントありがとうございます。
挙げていただいた具体例をどう判定すべきか考えてみたのですが
判定処理では、最終的には「線分と線分」や「線分と点」というより「点と点」の距離を判定基準にしなければならないように思えてきました。
道の上を逆走せずに滑らかに動く人（点）の間の距離を一定以下に保ったまま、終点まで移動できるか？と考えるとこの例ではFalseとなるべきです。
ただ難しいのは、その人（点）が動きつづけることと、とちゅうで相手の逆走を見越して「進みすぎないようにする」必要もありそうなことでしょうか。
点と点になるなら、path内の点間距離に制限が付きそうな気がするし、高速化という観点で逆向きな気もするので個人的にはちょっとお付き合いできかねます。要件次第ですが、自分で仕様を決められるなら線分内の逆走は気にしません。
dameoさん、もろもろ明確になっていない質問に対してご意見いだだきありがとうございました。
あまり事前に考えすぎないで、単純にできるところからはじめるべきかとも思いはじめています。
> 折れ線AとBがあるとき，
> 「A側の全頂点について，折れ線Bまでの最短距離を調べて閾値を超過していたらアウト」
> 「B側の〃，折れ線Aまで〃」
っていうのをちょっと変えて（「最短距離」というのをやめて）……
A側の全頂点について，距離閾値内にある折れ線Bの「範囲」を調べる，ということを考えたらどうだろうか．
ここで「範囲」を，折れ線上の位置を示す媒介変数 t（：スタート地点では0でありゴールに向かうほど増える） で表すとしたら，
A側の頂点の並び順序と，そいつらに対して計算した当該範囲の並び順というか前後関係みたいなの とを照らし合わせることで判定が行えないかなぁ…とか．
（AとBの立場を変えた側でもチェックする必要がある）
（１個の頂点に対して「範囲」が複数個になることもあり得るので，そこはちょっと考えなきゃだめかな？）
１個目の頂点での範囲 t1s～t1e と
２個目の頂点での範囲 t2s～t2e との間に
「こうなったらダメ」っていう関係性があるんじゃないかな，と．
Aの隣接する頂点間で
・範囲に重複がある状態はセーフ（その重複範囲内にBが留まった状態でAが動ける）と思う．
・範囲に重複が無い場合，上記の例で言えば t2e < t1s みたいになってたらアウト？
回答4件
0
効率はともかく，以下のような話でいけませんかね？
２人を｛A,B｝と呼ぶことにする．
両者がスタート地点から出発するとき，どちらが先に次の頂点に到達するだろうか？
Aが先か，それともBが先か？
それは現時点ではわからない
→ じゃあここで探索木を枝分かれさせよう．深さ優先なり幅優先なりで探索すればいい．OK.
ここではAの側が先に次の頂点に着くという側の仮説について考える．
Aがその頂点（位置を Pa としよう）に到達した時刻において，B側は最低でもどこまで進んでいなければならないのか？という位置（こちらを Pb としよう）は簡単に求めることができる．
Pa を中心として半径が距離閾値である円とB側の折れ線との交点群のうち，もっともBのスタート地点に（道のり的な意味で）近い点だ．
※ただし，例外として，Bのスタート地点が円の内側にある場合はスタート地点だ．
これで，全体の問題を２つの小問題に分割できた．
- 「Aのスタート地点から Pa までの経路」 vs 「Bのスタート地点から Pb までの経路」
- 「Pa からAのゴールまでの経路」 vs 「Pb からBのゴールまでの経路」
の２つだ．
この話を図で示す．
青い折れ線がA側，赤いのがB側．スタート地点を丸印で示している．
そしたら，これら２つの問題をまた同じように扱っていけばいい．
もちろん，どこまで問題を分割すればいいのか？ は，「小問題が解ける状態になるまで」である．
例えば「線分 vs 線分」な状態にまでなれば true か false か判断できるハズ．
投稿2022/11/29 13:11
編集2022/11/30 07:27総合スコア11954
問題を２つの小問題に分割していけば，各小問題には「過去に歩いた部分」が含まれない形になる
…と考えた．
時刻0の側から「ここまでなら確定的に２人とも進める」部分を少しずつ削り取っていくイメージ，とでもいうか．
で，二人の間の進み具合の関係性みたいなところは探索木で力技で扱う，っていう．
※特にこの手の話題の場合，こういう「どうかな感」みたいな回答が付いた場合，何かしらの応答，例えば，
「その話だと，こういう入力のときにアウトなのではなかろうか」だとか
「一見，それで解けるように思えるけども，背景事情的にそういう探索ぎみた方法だと処理速度の観点で採用できなさそうだから，別の方法が欲しい」とか
何かそういう所感みたいなのでもとにかく書いてしまった方が，他の人がそれを鑑みた話を考えたり書いたりするきっかけになり得るのではないかな，とか思ったりします．
（なんというか，変に中途半端な個数のリアクションが付いた良いとも悪いとも知れない回答の存在が，他者からの新規の回答を抑止してしまっているように思える．申し訳ない気分というか．）
回答ありがとうございます。
じつは回答いただいてから何回も回答を読んでいるのですが、どうしても理解ができておらず
コメントどうしようかと思っていました（笑
おもに理解できないところは分割の結果の「小問題」がどのような問題なのか？
それはどのようにして解けるのか？
といった点です。
そこでお願いなのですが、
質問に挙げた簡単なデータ例において、具体的な問題分割と小問題の解決手順を示していだだけるとありがたいです。（思い切り「丸投げ」で申し訳ありません）
データ例でやるのはとても大変なので，とりあえず分ける話の絵を描いてみました．
A側の折れ線を Pa を境にして２つに切る，B側も Pb を境にして２つに切る．
（AがPaに到達する時刻を境にして，過去側と未来側に問題をわける）
小問題１と２が共にtrueと判定できるならば元の問題もtrueである，という話です．
この絵ではどちらの小問題もまだ判定が難しいので，またこいつらを同様に分割していくことになります（ここでまた探索木が枝分かれする）．
この例では，小問題１については，さらに分割するとしたら「B（赤い側）が先にスタート地点の次の頂点に到達する」側の仮説しかないです．
（A側が先な仮説の側は同じ問題のままになっちゃうので）
分割した結果の２つの問題は，どちらの問題も「線分vs線分」になります．
ここまでくれば true か false か判定できるハズ．
これ，探索木の中では同じ問題を扱う部分がでてきそうですね．
図の「元の問題」で「B が先に次の頂点に着く」側の仮説を探索するとき，そこで「元の問題」を２つに分割した結果できる２つの小問題のうちの過去側の問題が，上記コメントでの小問題１を分割した結果の過去側と一致する．
> A側の折れ線を Pa を境にして２つに切る，B側も Pb を境にして２つに切る．
> （AがPaに到達する時刻を境にして，過去側と未来側に問題をわける）
>
> 小問題１と２が共にtrueと判定できるならば元の問題もtrueである，という話です．
伝わる説明になってるかな？
AとBがある長さの紐で繋がっているとして
もしも
Aが最初の（＝スタート地点の次の）頂点位置 Pa まで
「特定のレールに沿ってしか動けないB」を引きずって歩くような形で移動すること
ができるのだとしたら，
そのときBはPbの位置まで引きずられているハズである．
↓
そもそも，この「もしも」の話自体が可能なのか否か？（これが過去側の小問題）
可能なのであれば，残された問題は，この地点よりも先の話（未来側の小問題）になる．
※もちろん，Pb自体が存在しないなら「もしも」の話自体は不可能と判定される．
実際には途中で適宜 先導して引きずる側 と 引きずられる側 を入れ替えても良いが，とにかく両者が Pa,Pb まで到達することが可能なのか？
というのが過去側の問題の正確な意味，かな．
で，途中で役割を入れ替えてみること＝問題をさらに分割すること かな．
---
…とすると，別に「次の頂点まで」という話じゃなくても良い気がするな．
（「次の頂点」とすれば，過去側での一方の側が必ず線分になるから何か扱いやすいかな？と思ったんだけど）
話としては「残りの経路上のどこかまで」としてもいいわけだ．
（例えば，残りの経路長のうちの半分の位置 とかを選ぶと効率が良くなったりするのかも？？）
図入りでの回答の追記ありがとうございます。
まだ理解できていませんが、時間をかけて読みます。
とりあえず最後の（これ以上分割できない）小問題（「線分vs線分」）は
「お互いの終点から半径が閾値である円との交点が見つかるか？」という理解でよいでしょうか？
線分同士であって，両者の始点間の距離が閾値(以下)であることのチェックは事前に済んでいる状況であるから…終点間の距離だけ見ればいいのかな？
---
（※こういう，回答者の説明がイマイチで困る場合に，「もしもこの回答を読んで話がわかった人がいたならばその人の言葉で説明してもらえると助かる！」みたいな，そういう機能(?) が欲しいかも）
説明は分かりやすく、内容の理解は出来ているのですが、分散処理したいのなら有効かもしれない考え方だとだけ思いました。ただ効果は懐疑的というのが個人的な見解です。理由は分割にかかる時間の方が長そうだから。現状最終的に何がしたいのか(要件が)分からないので、有効な可能性がないわけでもなく、コメントしていませんでした。
内容の価値（：実際問題として 使える/使えない）以前に，まず書いた内容が読み手に伝わらないと意味がないので，そのような状況と見える場合には，補足説明等していただけると助かります．
これ以上何か言うことはないですよ。具体的にしたほうが分かりやすくなるけど、するほど遅くなるので説明しにくい。
問題を分割するところまでは大筋ではなんとなく理解できたと思いますが
それを分岐させ小問題にする部分、そして最終的な小問題を具体的に解くところが私には理解（コードに落とし込む）ができませんでした。私の理解力不足で申し訳ないです。
しかし回答いただきありがとうございました。
0
自己解決
line segments, path, curve, similar, distanceといった単語で検索した結果、「Fréchet distance（フレシェ距離）」を見つけました。
Fréchet distance
Fréchet距離の計算アルゴリズム
基本的には質問と同じ考えで、２曲線のとおる順番とかたちの類似性を測る尺度（距離）となっています。
この距離をじっさいに解く方法はFast Discrete Fréchet Distanceといった記事にも記載あるようにいろいろあるようなのですが、曲線を離散的な複数の線分として捉えた場合、Dynamic Time Warpingという手法で解けるようです。
今回はこの「Fréchet distance（フレシェ距離）」という考えが得られたことで、回答をクローズします。
コメント、回答いただいた皆様ありがとうございました。
投稿2022/12/01 07:34
編集2022/12/04 08:08総合スコア38339
これで解決に至るか？()は少し疑問の余地が残っていますが、逆走を含み、処理手順に依らない厳密に一意な距離の定義というのが良いと思いました。射影した自由空間内で(0,0)から(1,1)に単調増加で到達可能なことで真とする、という明快な解とし、その特性を利用して分解能を上げることによる効率化を図るという方法論までは分かるのですが、実装に落としこむにはまだいろいろと考えることがある点、それをしたとしてどこまで速いのか？は難しいところですね。
私の回答はここまで厳密な解ではないので、精度上劣るだろうし、例えばある距離以下、ではなく距離を計算するような探索をかける場合不向きです。また線分内の逆走(これが問題になるのは現実だとレアケースだと思うけど)についても誤った結果を出すでしょう。ようは厳密な汎用ライブラリレベルの実装をするなら使えません。逆に論文の方法は速度的にはちょっと想像もつかない時間がかかりそうですが、厳密に正確な解を出すことができ、速度的に改善する余地があり、またクラスタリングや経路の単純化など汎用な用途に適用できそうです。なので、回答として正解としていいのか分からないのですが、グッドだけ送らせてもらいました。
コメントありがとうございます。
ご指摘の通り、真正面な解法だと空間が大きいとメモリ的にも相当厳しそうですが、
いろいろな最適化手法はあるようです。
ただ正直内容を理解するのは私にはほぼ無理なので「こういったものがある」というところまでで回答をクローズしました。
(理解する上でも一旦)先に進めるの大事なので、まずは進んでみてください。上手くいくことをお祈りしてます。
個人的にはメモリよりも精度と速度が心配です。
0
回答ではありません。
とりあえず要件を満たしていない線分と点の距離で書いたpythonコードです。分かりやすいわけでもないです。あと何となくnumpyを使ってるけど、なくてもそんな手間ではありません。デバッグもしてないのでバグもあるかと思います。
python
1import numpy as np 2 3def get_distance(line_start: np.ndarray, line_end: np.ndarray, point: np.ndarray) -> float: 4 """line_startからline_endまでの線分とpointの距離を返す 5 6 Args: 7 line_start (np.ndarray): 線分の始点 8 line_end (np.ndarray): 線分の終点 9 point (np.ndarray): 点 10 11 Returns: 12 float: line_startからline_endまでの線分とpointの距離 13 """ 14 v1 = line_end - line_start 15 v2 = point - line_start 16 p = np.dot(v1, v2) # 内積 17 if p < 0: 18 return np.linalg.norm(v2) # 始点よりも前側の点なので、始点と点の距離を返す 19 v1 = -v1 20 v2 = point - line_end 21 p = np.dot(v1, v2) # 内積 22 if p < 0: 23 return np.linalg.norm(v2) # 終点よりも先側の点なので、終点と点の距離を返す 24 return np.absolute(np.cross(v1, v2)) / np.linalg.norm(v1) # 線分と点の距離(外積の絶対値を線分の長さで割ると距離が出る)を返す 25 26def is_same_path(path1: np.ndarray, path2: np.ndarray, max_dist: float =0, debug: bool = False) -> bool: 27 """path1とpath2の経路が同じかどうかを返す 28 29 Args: 30 path1 (np.ndarray): 経路を表すリスト 31 path2 (np.ndarray): 経路を表すリスト 32 max_dist (float, optional): 各経路が同一であるために満たすべき距離. Defaults to 0. 33 debug (bool, optional): デバッグ時にTrue. Defaults to False. 34 35 Returns: 36 bool: 同じのときTrue 37 """ 38 if len(path1) == 0 or len(path2) == 0: 39 return False 40 if np.linalg.norm(path1[0] - path2[0]) > max_dist: 41 return False 42 if len(path1) + len(path2) == 2: 43 return True 44 if np.linalg.norm(path1[len(path1)-1] - path2[len(path2)-1]) > max_dist: 45 return False 46 47 linePath = path1 # 線分として処理している経路 48 lineIndex = 1 # 線分終端のインデックス 49 pointPath = path2 # 点として処理している経路 50 pointIndex = 0 # 点のインデックス 51 52 switch = 0 # 現行ターゲット(上4つの変数)での試行回数(線分/点で2回まで) 53 passed = True # 現行ターゲット(上4つの変数)でのsame判定成功時True 54 while switch < 2: 55 if passed and pointIndex + 1 < len(pointPath): 56 pointIndex += 1 57 passed = False 58 switch = 0 59 else: 60 switch += 1 61 if switch >= 2: 62 break 63 if switch > 0: 64 linePath, lineIndex, pointPath, pointIndex = pointPath, pointIndex, linePath, lineIndex 65 if passed: 66 continue 67 r = get_distance(linePath[lineIndex - 1], linePath[lineIndex], pointPath[pointIndex]) 68 if debug: 69 if linePath is path1: 70 line = 'path1' 71 point = 'path2' 72 else: 73 line = 'path2' 74 point = 'path1' 75 print(f'{line}({lineIndex-1}-{lineIndex}) to {point}({pointIndex}): {r}') 76 if r <= max_dist: 77 passed = True 78 return pointIndex + 1 == len(pointPath) and lineIndex + 1 == len(linePath) and passed 79 80path1 = np.array([ 81 [25.00, 115.50], 82 [132.50, 21.00], 83 [250.00, 62.50], 84 [278.50, 194.00], 85 [410.00, 212.50], 86 [459.50, 105.50], 87]) 88 89path2 = np.array([ 90 [38.50, 119.50], 91 [78.00, 55.50], 92 [154.50, 21.50], 93 [203.50, 60.50], 94 [265.50, 75.50], 95 [287.00, 190.00], 96 [399.00, 226.00], 97 [426.00, 155.50], 98 [463.50, 118.00], 99]) 100 101if is_same_path(path1, path2, 15, debug = True): 102 print('same!!!') 103else: 104 print('not same')
実行結果
path1(0-1) to path2(1): 10.071189382978861 path1(0-1) to path2(2): 22.005681084665387 path2(1-2) to path1(1): 9.391952027485976 path2(1-2) to path1(2): 103.92906234542868 path1(1-2) to path2(2): 6.855201648737006 path1(1-2) to path2(3): 13.600062035934494 path1(1-2) to path2(4): 20.22992832414391 path2(3-4) to path1(2): 8.990618659910627 path2(3-4) to path1(3): 119.21094748386156 path1(2-3) to path2(4): 12.394747436271063 path1(2-3) to path2(5): 9.154387740744644 path1(2-3) to path2(6): 124.67658160215976 path2(5-6) to path1(3): 9.394147114027968 path2(5-6) to path1(4): 17.414074767267998 path1(3-4) to path2(6): 14.900792007655637 path1(3-4) to path2(7): 59.20304046246274 path2(6-7) to path1(4): 5.444186169462745 path2(6-7) to path1(5): 60.18513105410671 path1(4-5) to path2(7): 9.41091006968288 path1(4-5) to path2(8): 8.878657156773821 same!!!
使用データ
質問の絵を元になんとなく作りました。他で使えるように貼っておきます。
svg
1<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 20010904//EN" 3 "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd"> 4 5<svg xmlns="http://www.w3.org/2000/svg" 6 viewBox="0 0 496 271"> 7 <path fill="none" stroke="red" stroke-width="15" 8 d="M 925.00,115.50 10132.50,21.00 11250.00,62.50 12278.50,194.00 13410.00,212.50 14459.50,105.50 15 " /> 16 <path fill="none" stroke="blue" stroke-width="15" 17 d="M 1838.50,119.50 1978.00,55.50 20154.50,21.50 21203.50,60.50 22265.50,75.50 23287.00,190.00 24399.00,226.00 25426.00,155.50 26463.50,118.00 27 " /> 28</svg>
投稿2022/11/30 11:26
編集2022/11/30 11:30退会済みユーザー
総合スコア0
1と2について「線分と(終)点の距離」を必要におうじて入れ替えて判定し先に進めていく流れと理解しました。
逆走ケースでは質問と異なる結果となりますが、シンプルで計算量も少なく素晴らしいと思います。
回答（ではないとありますが）ありがとうございます。
0
こんなんでいいかしら?
C++
1#include <vector> 2#include <utility> 3#include <algorithm> 4 5typedef std::pair<double,double> point; // 座標 6 7// 2点間の距離 8double distance(const point& p0, const point& p1) { 9 return sqrt((p0.first-p1.first)*(p0.first-p1.first) + (p0.second-p1.second)*(p0.second-p1.second)); 10} 11 12bool is_same_path(const std::vector<point>& path1, const std::vector<point>& path2, double max_dist) { 13 if ( path1.size() != path2.size() ) return false; // pathの長さは同じであるべし 14 // 両pathの各point間の距離が一定距離より近いならtrue 15 return std::equal(path1.begin(), path1.end(), path2.begin(), 16 [=](const point& p1, const point& p2) { return distance(p1, p2) < max_dist; }); 17}
投稿2022/11/29 08:40
総合スコア16612
回答ありがとうございます。
ですが残念ながら期待例での「線分の数～が異なっていてもOK」という条件が満たせていないです。
少ない方は終点で足踏みするんですか? それともほかのなにか?
はい。足踏みします。
二人の移動速度は独立しており（逆走しないかぎり）自由です。
二人はそれぞれの道を道なりに、最初から最後まで手をつないだまま移動できるか？
といった制約になります。
ならば「短い方は数が揃うまで終点座標を追加して同じ長さに」すればいいのかしら。
はい。
線分が長いほうに終点を追加することで、おおむねいけそうな気がします。
この話で…
> # 線分の数や途中の線分の接続位置が異なっていてもOK
> p1 = [(0,0),(1,1),(3,3),(4,4)]
> p2 = [(0,0),(2,2),(4,4)]
コレを扱えるのでしょうか？
（２個目の頂点の時点で false と判定されませんか？）
> (２個目の頂点の時点で false と判定されませんか？）
この例だとp2に(1,1)を終点を挿入してあげて進めることができると理解しています。
max_dist の値が 0 だとしたら
（ distance(p1, p2) <= max_dist として = が必要な気もするけど）
p1[0] と p2[0] が同一か？
p1[1] と p2[1] が同一か？
p1[2] と p2[2] が同一か？
…
というのが全部trueになるか？ というのが std::equal なのだと思うので，そしたら
p1[1]=(1,1) と p2[1]=(2,2) の時点で false になると見えるのですが，もうこの時点で読み間違っていますか？
（この場合，p2側のどこに(1,1)を挿入してもtrueにできないように見える）
p1 = [(0,0),(1,1),(3,3),(4,4)]
p2 = [(0,0),(2,2),(4,4)]
においてp1[1]=(1,1)とp2[1]=(2,2)ではp2のほうが長いからp2に(1,1)を挿入…
といった感じに先頭から順に処理していき、最終的には
p1 = [(0,0),(1,1),(2,2),(3,3),(4,4)]
p2 = [(0,0),(1,1),(2,2),(3,3),(4,4)]
となって一致するように判定されると私は理解しましたがいかがでしょうか？
あなたの回答
tips
プレビュー
