No.7ベストアンサー
- 回答日時:
線分と直線の違いは数学的には結構本質.
(0,0)と(1,0)を両端とする線分Lとx軸と
点A(2,0)を考える.
さて,AからLまでの距離,Aからx軸までの距離
どう考えます?
線分を相手にするときには「直線相手の公式」は使えないから
もっと根本にもどって,AからL上の点まで「距離」の中から
最小の値をとる点を探すことになります.
(a,b),(c,d)を両端とする線分上の任意の点(x,y)は
(x,y)=(1-t)(a,b)+t(c,d) (0<=t<=1)で表せる.
今点(A,B)をとって(A,B)からその線分の点までの距離d(t)を考えると
d(t)^2 = ((1-t)a+tc-A)^2 + ((1-t)b+td-B)^2だから
これの最小値を求めればよい.
ただし「0<=t<=1」で.これがめんどくさい.
#数学的には高校一年生程度の問題だが計算が面倒
じゃどうするか.今度は
(a,b),(c,d)を両端とする「直線」を相手にして
一度,その直線まで(A,B)から垂線を下ろし,その垂線の足をHとする.
Hが線分上にあれば(A,B)とHまでの距離が線分までの距離
Hが線分上になければ,
・Hを(1-t)(a,b)+t(c,d)の表記で書いたときに t>1であれば(A,B)と(c,d)の距離が求める距離
・t<0であれば(A,B)と(a,b)の距離が求める距離
くらいの手数になるか.
>その点が移動するたびに最短距離を計算しなければならない場合に、再計算の大半が無駄な計算をしているような気がしたということです。
さて。。なぜ無駄と思います?
点を移動したら当然値が変わるのだから再計算は必要です.
どこまで「正確さ」を求めるか,計算コストなどとの
トレードオフも当然あります.
その移動量や線分の形態などいろいろな条件があります.
もちろんいくつかの「節約方法」はあります.
・「解像度」を粗く考える方法
本来ならば1ピクセル単位で考えるのを例えば,16x16ピクセル
(これはわざと大きくしてますよ,念のため)を
一点だと思って,その範囲でのマウス移動は無視する
・各点ごとの結果をキャッシュしておく.
同じ点の値を複数回計算しないように
一度計算したらその値を保存しておき,
二回目以降は同じ計算をしない
折れ線も変化するならば折れ線の情報も考慮しないと当然だめ
・折れ線を構成する各線分の位置関係を考慮しておき,
ある点からの距離が分かり,
移動した後の点がそれほど離れていないならば
遠くの線分を再計算対象には含めない
これくらいの工夫は考慮すべきでしょう.
この回答への補足
回答有難うございます。
>・折れ線を構成する各線分の位置関係を考慮しておき,...
この最後の点の具体的方法を知りたい、というのが質問の趣旨でした。
こだわっている方がいらっしゃるようなので念のため、線分ABと点Cとの距離を求めるアルゴリズムは自分としては以下のように実装しました。
1) 直線ABへCから下ろした垂線との交点をDとすると、ベクトルADは
ベクトルABのスカラー倍となるからこの倍数をαとする。
2) 0<α<1の場合、最短距離はCとDとの距離
3) それ以外の場合、線分ABの両端点とCとの距離をそれぞれに求めて近い方 を最短距離とする。
No.6
- 回答日時:
> 再計算の大半が無駄な計算をしているような気がしたということです。
それは、おそらく気のせいでありましょう。
ところで、「距離」の定義に関する質問にはお答えいただけないのでしょうか?
No.5
- 回答日時:
念のため「距離」の定義を確認します。
折れ線を構成する線分のひとつが
(0, 0)と(1, 0)とを結ぶものであるとします。
また、距離を求めたい点の座標を(2, 1)とします。
この場合の距離はいくらですか?
この回答への補足
少し言葉が足りなくて申し訳ありませんでした。距離を求める計算が無駄というのではなく、点がそれほど遠くへ一気に移動しないことが多い(マウスポインタのように)ケースで、その点が移動するたびに最短距離を計算しなければならない場合に、再計算の大半が無駄な計算をしているような気がしたということです。
よろしくお願いします。
No.4
- 回答日時:
> 線分との距離をひとつひとつ処理すればできるのは分かっているですが、
> 線分の数が多い場合にその計算の大半が無駄なような気がしまして、
距離をすべて求めなければ、どれが最短距離かはわからないですよね。
ムダな計算は一つもないと思います。
たまたま、計算結果の中から一つだけを選んでいるに過ぎないのです。
No.1
- 回答日時:
折れ線ということは、複数の直線群ですね。
1点目と2点目とで1本目の直線、
2点目と3点目とで2本目の直線、以下同様
のような。
まずは、点と1本の直線との距離を求めるところから
始めてみてはいかがでしょうか。
それができたら、2本目、3本目、...に拡張して、
最小値を求めれば、問題が解決すると思います。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 地図・道路 バイク 右折時に中央線に寄るタイミング 2 2022/08/28 10:27
- 事故 私にも落ち度がありますが1車線の道路で 前の車が遅くて詰まってしまって 車間距離近いまま走りました 5 2022/10/02 13:21
- その他(プログラミング・Web制作) 2点間の距離(dx,dy)を求めるプログラムを作っています。空白の赤線に何を入れたらいいか教えて欲し 1 2022/05/06 18:33
- 数学 ベクトル方程式(ヘッセの標準形)についての質問 2 2022/04/23 18:00
- 事故 前方でウーバーの配達員みたいでアプリスマホ見ながら運転のノロノロ原付がゆっくり迷った運転していて自分 6 2022/08/02 08:00
- バス・高速バス・夜行バス 東京都内の私鉄で超短距離利用者が減っているのは或るパスですか? 1 2023/05/28 13:52
- 物理学 無限に長い導体円筒の問題です。 (1)この導体円筒の単位あたりの静電容量を求めよ。 (2)内外の導体 1 2023/05/30 23:49
- 数学 数学ベクトルに関しての質問 3 2022/05/25 23:21
- 数学 数B 2直線のなす角 ベクトル(-1,√3)に垂直で、原点Oからの距離が4である直線の方程式を求めよ 2 2022/06/30 01:05
- 高校 数Ⅱの軌跡という単元について質問です。 問題の最後に、逆に、この~上の全ての点は条件を満たすとかく場 3 2023/03/21 16:38
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語の課題で、1年の秒数を計...
-
65536は2の何乗なのでしょうか?
-
Excel VBAにてFFT
-
matlab計算での進捗状況を知りたい
-
入射角反射角
-
CRC8を教えてください
-
VBとVBAの違い
-
変化させるセルが変化しない
-
matlabで計算終了
-
2進数の乗算をc言語で計算した...
-
FORTRANで>>
-
骨折リスク評価のFRAXについて...
-
fortran πについて
-
VBAでの勤務時間計算
-
for文である数の倍数になるまで...
-
[急募]Pythonについてです。
-
VB6で正確なミリ秒を計測したい...
-
C言語についてです。 再帰を使...
-
CとFORTRANの計算速度はどちら...
-
ファイルサイズの単位 BYTE,MB...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
VBAの再計算が反映されない件に...
-
排他的論理和 BCC(水平パリテ...
-
EXCELなどで「返す」という表現
-
バッチファイルでウインドウを...
-
モジュラス103の計算とは何でし...
-
傾いた四角形内の範囲の条件式
-
Visual C++でdebugとreleaseで...
-
変化させるセルが変化しない
-
骨折リスク評価のFRAXについて...
-
C# 計算処理中に実行中ウィン...
-
VBAでの勤務時間計算
-
べき乗の計算が遅い理由
-
C言語についてです。 再帰を使...
-
Excel VBAにてFFT
-
数値計算の高速化 (cos, sin, exp)
-
VBとVBAの違い
-
VB6で正確なミリ秒を計測したい...
-
スレッド処理からダイアログを...
-
matlabで計算終了
おすすめ情報