最接近点を持つ線を特定

質問

お世話になります。
宜しくお願いします。

現在、swingとawtを駆使して、線や図形の描画を行うアプリを作成しています。
その中で、次の様な事をする場合の処理で躓いております。助けてください。

よろしければ添付の図をご参照下さい。
ほぼ中央にサイコロの「1」の目の様な正方形があり、
その中心に赤い円(中心点)があります。
図示上ではわかりやすいように赤い円で示しましたが、実際には1pixelの点です。
そして、4本のラインがまとわり付いていると思います。
これらのラインの内、「中心点との最接近点を持つ線」を特定したいです。
各座標同士の頂点情報は、図形の親要素(TextPane)の0,0からの相対頂点情報として、
いつでも参照可能なスコープの変数に保持していますので、
後は特定する為の計算式にあてはめるだけと考えておりますが、難航しております。
どうかお助け下さい。よろしくおねがいします。

＜他＞
・全ての頂点座標は必ず0,0以上の値となります。
・中心点は必ず正方形の中心に描画されます。ただし、正方形自体の描画位置は無作為です。
・ラインは図示上では4本ですが、実際にはn本です
・ラインは図示上では適度に分散していますが、頂点情報は再描画の度、完全に無作為に設定されます。
・図形をTextPaneの中に書く所までは問題なくできています。

回答No.1

Tacosan · ベストアンサー

中心点とそれぞれの直線なり線分なりとの距離を全部計算すればいいだけじゃないの?

お礼

私の早合点により貴重な助言を流してしまい申し訳ありません。
その方法で良かったようです。
公式を突き止める所まではいけましたので、
ここから先は数学カテゴリに持ち込もうと思います。
ありがとうございました。

補足

＞直線なり線分なりとの距離を全部計算
線を形成する座標1点ずつですか？

回答No.4

ngsvx

横から失礼します。

質問者さんと回答者さんとの間で、行き違いがあるように感じました。

＃1の回答は、

「任意の1点と直線の距離を求める公式」というものがあるから、その公式を使って
それぞれの直線毎に距離を計算すればいい

と言っています。(つまり計算の回数は、直線の数だけということ)

質問者さんはこれの意味を取り違えているように思えますがいかがでしょうか？

公式で計算した結果は、厳密には1～2ピクセル程度誤差がでるかもしれませんが、
恐らく問題にはならないと思います。

ちなみにですが、私は昔お絵かきソフトのようなものを作ったことがありました。
そこでは、描画済みの図形をマウスでクリックし属性（太さ等）を変更できるのですが、
その際には、描画済みの各図形に対し、マウスでクリックされたかどうかの判定をするのに、
今回のような計算を行いました。

先ほどの誤差はまったく問題にならなかったです。

速度的にも、問題はありませんでした。
（ペンティアム133MHzくらいのマシンでのことです）

ですので、今回も公式を使った方法で問題ないかと思います。

補足

私の思い込みで話をややこしくしていたようですね。(学が無いもので、お恥ずかしい)
調べてみた所よくわからない記号満載の公式にぶつかったので、
ここから先は数学カテゴリに持ち込もうと思います。
ありがとうございます。
真意に気づいたのはnvsgxさんの助言をいただいてからですが、
回答者は最初から正しい意見を出してくださっていたようですので、
BAは最初の回答者とさせていただきます。申し訳ありません。

回答No.3

Tacosan

ん～, そうなると若干面倒だなぁ.

イメージだけでいくと, 各直線に対し
1. 中心点からその直線に下した垂線の足の座標を求める
2. その「前後」のピクセルを見つけてそいつらとの距離を計算する
という処理で中心点から各直線までの距離が求まるはずです. もちろん直線でなくて線分なら「実は端点が最も近い」とか「2 で『前後』のピクセルを見つけるときに一方が線分の外に出る」という可能性も考慮する必要があります.

面倒ではありますが直線ないし線分の本数に比例する時間でできるはずです.

回答No.2

Tacosan

え? 「中心点との最接近点を持つ線」の「最接近点」って, ひょっとして
「その線を描画したときのピクセルのうち『中心点』と最も近いところ」
って意味?

だとしたら, 「線をどのように描画するか」という情報がないと無理だよ.

補足

＞「その線を描画したときのピクセルのうち『中心点』と最も近いところ」
その通りなのです。

＞「線をどのように描画するか」という情報
線は全て直線です。そしてdrawLineの引数となる始点終点の座標情報はアプリ全体で参照可能なスコープの変数に保持してあります。
それを使って判定はできないでしょうか？
計算の為の情報に不足があればご指摘下さい。

一応、昨日出していただいた案で線の始点～終点間の連続する座標を算出し、
(この時点でdrawLineの書き出す線とは微妙にずれた値が出ていると思いますが、そこは最終的にすり合わせますので気にしないで下さい)
各座標と中心座標とでピタゴラスイッチして距離を求めてラインごとのminを保持し、
最終的に全体ラインのminと、それを保持するラインを取得する簡単なロジックを書いてみましたが、
ちょっと時間がかかりすぎてました。(100本で平均して20秒ぐらい)
現在の表示範囲(600,600)で100本の場合、最大で約84,852点、
実際にはそのおおよそ半分ぐらいの所の回数座標計算を行わなければいけないのでしょうが、
関数呼び出しのオーバーヘッドを抑える為にMathは使わずベタ書きし、
また距離も比較に用いるだけなのでルート計算は省いていますので、
1点当たりの計算自体は精々数クロックで済んでいる筈なのですが、それでこの負荷は少し異常です。
ひとまずロジックがタコってる疑いが大なのでそれを改善すれば速度的な向上は見込めると思っていますが、
そもそもの考え方がベタすぎるので、もっと良い方法があれば、できればそちらを取りたいです。
よろしければ引き続きお力添えをいただければ幸いです。