構造体COORDの名前をPOSITIONという別の名前に置換しております。No.28に書かせていたいた、私のアルゴリズムですが、>2.すべての座標について、ひとつずつ、以下の手順に従ってルート探索するこの部分で非常に処理コストがかかってしまうことが分かり、断念しました。(私の環境でですが20本程度の線分で40秒以上かかってしまいました)それに比べ、みけCATさんのやり方ですと、非常に高速でしたので、これを使わせていただこうと思います。線分を座標圧縮する(座標の値が0~1000くらいなら必要ない)座標圧縮という言葉を今回初めて知りましたので、ネットで調べてみました。(Google検索で3~4件程度しかヒットできず、その実態がなんなのか理解に苦しんでいるのですが、何やらプログラミング技術者のアルゴリズム試験かなにかで有名な設問であるかのような印象をうけました。誤って解析している場合がありますので、ご指摘くだされば幸いです。座標の幅は大きい(-10^9~10^9など)がオブジェクトの数は少ない(数100~10000程度)時に有効なテクニックです。座標の幅をオブジェクトの数の定数倍にでき、空間に対する走査がしやすくなります。適当な例を考えてみると、実質的に意味のない空白が消え、考えないといけない面積が小さくなることがわかります。座標をソートするのは、元の座標に対する圧縮後の座標を素早く求めるためです。今回のアルゴリズムで使用する幅優先探索の対象の面積はだいたい1,000,000になり、1秒程度で処理できるということがわかります。矩形を見つける処理もO(x座標の最大値×y座標の最大値×log(x座標の最大値)×log(y座標の最大値))くらいなので、座標の最大値が1000くらいなら座標圧縮をしなくても実用的な速度で解が求まるということがわかります。「必要ない」であって、「やっても意味がない」「やらないべき」ではないことに注意してください。6年前>みけCATさんご教授くださりありがとうございます。座標圧縮というのは、内部のオブジェクト同士の比率をたもったまま、全体の空間自体を縮小するイメージなのですね。その結果、等倍で探索するよりも処理が高速になると。おかげさまで、理解できました。分かりやすいご説明を図まで用意して教えてくださり、ありがとうございました。>「必要ない」であって、「やっても意味がない」「やらないべき」ではないことに注意してください。座標圧縮する甲斐があるかないかは、座標圧縮してみないことにはわからないということですね。ご忠告くださりありがとうございます。みけCATさんのご提示くださったアルゴリズムの理解ができましたので、あとは(これまたみけCATさんがご提示くださった)プログラムを見ながら、コーディングのテクニック的な部分を学ばせていただくだけですので、このスレッドは解決とさせていただきます。この度は、私の不注意と不勉強から皆様を混乱させてしまいすみませんでした。私のミスを適切にご指摘をしてくださったusaoさんに感謝いたします。ありがとうございました。今回の質問は、私にとって大変勉強になりました。この場をお借りして、このスレッドをご覧いただいた皆様にもお礼申し上げます。座標圧縮というのは、内部のオブジェクト同士の比率をたもったまま、全体の空間自体を縮小するイメージなのですね。その結果、等倍で探索するよりも処理が高速になると。「比率」ではなく「位置関係」をたもちます。6年前>みけCATさんご指摘くださりありがとうございます。・・・オブジェクト同士の「位置関係」をたもつ、ですか。以下の私の認識があっておりますでしょうか?お手すきの際でけっこうですので、ご覧になられたらご回答くださると幸いです。>「比率」ではなく「位置関係」をたもちます。比率という表現だと、位置関係まで指し示せていないから、私が使う言葉を間違えているよ、ということですね。比率をたもつ、と表現してしまいました。>「比率」ではなく「位置関係」をたもちます。比率という表現だと、位置関係まで指し示せていないから、私が使う言葉を間違えているよ、ということですね。