ある領域と直線の交点を求めたい

質問

白い背景の中に不規則な形をした黒いエリアがあったとします。
白いエリア内のある点から黒いエリア内のある点に向けて直線を引いた時、
その直線と色の境目にできる交点の座標を調べるにはどのようにすればいいのでしょうか？

色情報は取得済みで、関数に座標 x と y を渡すと 0(白) か 1(黒) が返ります。

交点の座標は整数で、色の切り替え部分の白側の座標とします。
黒いエリアはひとつのまとまりで、ドーナツ状に穴が空くことはありません。

言語はC#を予定していますが概念がわかれば良いので他の言語でも構いません。
宜しくお願い致します。

回答No.4

f272 · ベストアンサー

http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AC%E3%82%BC%E3%83%B3%E3%83%8F%E3%83%A0%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
やりたいのはこういうことか？

お礼

最終的にこちらのアルゴリズムを使って直線が通る座標を取得し、
色の境界を検出する方式にしました。
ありがとうございます。

回答No.3

maiko0318

そう、そこがプログラミングの腕ってやつです。

そういう場合は個別に判断して1/(xの係数)ずつ増やすとか、
縦棒(x=1)というようにyが出てこない場合(xの係数が0)はどうするとか考えるのです。
(1,5)から(1,10)ならxを1にし、yを1ずつ増やすことで解決します。

プログラムを組んでいると例外条件が山ほど出てきます。
プログラム＝例外の山って感じでプログラムは例外処理のほうがはるかに多いですよ。

回答No.2

maiko0318

＞始点から終点に向かって1ピクセルずつ線を伸ばしていく雰囲気が近いかもしれません。

だから、関数がわかっているんだからxを始点から終点に１ずつ増やしていき
（始点のx>終点のxなら１ずつ引いていく)、yを求める。
で、その位置が白か黒かって判断するんだよ。

補足

仮にy=10xほどの関数だった場合、xを1ずつ増やしていくと交点のyは10の倍数しか得られません。あるいはxが同じ縦一直線の場合などはどのように判断すればいいのでしょうか。

回答No.1

maiko0318

それは数学の世界ですね。

直線の開始位置と終点位置がわかっているのですから、
直線の関数を割り出し、その上の点が白か黒か判断すればいいことになりますね。

あと、その直線と色の境目にできる交点というのは何百、何千という数になることもお忘れなく。

補足

求める座標は整数ピクセルですので近似値ということになるかと思います。
白黒二値のビットマップ画像上の座標を想定しています。
始点から終点に向かって1ピクセルずつ線を伸ばしていく雰囲気が近いかもしれません。