直線と線分の交差判定について高速なアルゴリズム

タイトルの通りなのですが、
まさにその部分をプログラムで作っている最中です。

直線 : ax+by+c=0　で言うところの a,b,c のパラメータと
線分の2端点 ( x1 , y1 ) , ( x2 , y2 )　がわかっています。

その情報を使って今は
　( ax1 + by1 + c ) * ( ax2 + by2 +c ) < 0
のときに交差している。

という風に処理しているんですが、 どうにもこの部分の処理で時間がかかっているみたいで、
なんとか高速化したいんですが、直線と線分の交差判定について触れてあるサイトが少なかったり、
今使っているアルゴリズムのサイトだったりしか見かけないので、どうにもこうにもなりません。

もしこれが最速のアルゴリズムならしかたないんですが、もし皆さんご存知でしたらお力添えをお願いします。

No.3 ベストアンサー 回答者： episteme 回答日時： 2010/12/20 21:43

そんだけ大量の演算を高速にやりたいなら、OpenCLとかによるGPGPUの利用を考えてはいかがでしょう。

参考URL：http://codezine.jp/article/detail/5439

この回答へのお礼

やっぱGPUにするっきゃないっすかね。

お礼日時：2010/12/21 00:34

No.2 回答者： Tacosan 回答日時： 2010/12/20 16:06

ちなみにその「画像」はどのくらいの画素数なんでしょうか?

No.1 回答者： kmee 回答日時： 2010/12/19 22:23

> どうにもこの部分の処理で時間がかかっている

本当にそうですか?
5回のかけ算と4回の足し算が「時間がかかる」だとすれば、プログラムの他の部分は「ほとんどなにもしていない」って位でないと。(例えば、printf使ってたら、その方が何倍(下手すれば何十、何百、何万倍)も時間かかります)

実行環境によっては確かに遅いケースもあります(CPUが遅く、浮動小数点演算専用回路が付いていないマイコン等)
しかし、最近の普通のコンピュータなら、億単位の四則演算しても数秒もかかりません。

○本当はどこで時間かかっているのか、確認しましょう

○他の部分のアルゴリズムの見直しましょう
例えば、n個の点から、直線を交差する組み合わせを探す、というものだったら

「全ての組み合わせを選ぶ→判定式を計算」
としたら
「9(1回あたりの計算) * n(n-1)/2(組合せの数)」
回計算することになりますが

「全点の aX+bY+c を計算→全組み合わせで 左の値を使って判定式を計算」
とすれば
「4(1点あたりの計算) * n (点の数) + 1(組み合わせ1つあたりの計算) * n(n-1)/2」
と大幅に削減できます。(もっとも、点の数が万単位でもなければ実感できないですが)

この回答への補足

すみません。情報をだいぶはしょっていたので誤解を与えたかもしれません。

この直線の交差判定はかなり繰り返し計算するのでちょっとでも処理を軽くしたいという旨の相談です。

だいたい700～900個の点（画像中にある物体の輪郭を抽出した点）のうち隣接する点同士と直線の成分で交差判定をします。
それを、256*256回のループに加えてカメラ台数分の6回繰り返す処理なので
270000000回位です。億単位で繰り返し処理をします。


確かに点の位置には関係性があるのでその辺のアルゴリズムも考えてみます。

補足日時：2010/12/19 23:42