PolylineとPolylineの交差する座標の取得について

Question

現在、Canvasに含まれるPolylineと引数で指定したPolylineの交差する座標の取得をしたいと思っています。
しかし、明らかに交差してないときにも座標値が複数取得されてしまいます。
アルゴリズムは線分の交差のアルゴリズムを使っています。
コードはこれでよいのでしょうか？やはりスクリーン座標からデカルト座標への変換が必要なのでしょうか？数学に疎いので難航しております。
ちなみにコードは下の通りです。

List<Point> Intersect(Canvas canvas, Polyline eraser)
{
            List<Point> intersections = new List<Point>();

            foreach (Polyline target in canvas.Children)
            {
                for (int i = 0; i < target.Points.Count - 1; i++)
                {
                    for (int j = 0; j < eraser.Points.Count - 1; j++)
                    {
                        Point p1, p2, p3, p4;
                        p1 = target.Points[i];
                        p2 = target.Points[i + 1];
                        p3 = eraser.Points[j];
                        p4 = eraser.Points[j + 1];

                        double d = (p2.X - p1.X) * (p4.Y - p3.Y) - (p2.Y - p1.Y) * (p4.X - p3.X);

                        //2つの線分が平行
                        if (d == 0)
                            continue;

                        double r = ((p4.Y - p3.Y) * (p3.X - p1.X) - (p4.X - p3.X) * (p3.Y - p1.Y) )/ d;

                        double s = ((p2.Y - p1.Y) * (p3.X - p1.X) - (p2.X - p1.X) * (p3.Y - p1.Y)) / d;

                        if (r < 0.0 || r > 1.0)
                            continue;
                        if (s < 0.0 || s > 1.0)
                            continue;

                        double x, y;

                        x = p1.X + r * (p2.X - p1.X);
                        y = p1.Y + r * (p2.Y - p1.Y);

                        intersections.Add(new Point(x, y));
                    }
                }
            }
            return intersections;
}

Answer 1

Intersectメソッドの引数eraserは、canvasには含まれていないのですよね。もし含まれていたら、eraserの中で線分が交差していると、その座標を取得してしまいます。

eraserはcanvasの外にあるとして、簡単なプログラムを作ってそのままコピペして試してみましたが、Intersectメソッド自体は問題はないようです。正しく交点を検出できていますし、交差していない場合は未検出（Count == 0）で返ってきています。

やはりスクリーン座標からデカルト座標への変換が必要なのでしょうか？

私も数学には疎いので「デカルト座標って何？」と思って調べてみましたが、直交座標系のことですね。スクリーン座標は変換するまでもなく元々デカルト座標系です。

考えられることとしては、canvasオブジェクトの座標系とeraserオブジェクトが想定する座標系が異なる場合は、期待通りに動かないかもしれません。

canvasに追加したPolylineオブジェクトに添付プロパティ(Left/Top/Right/Bottom)でオフセットを設定していると、Pointsリストに設定されている座標と実際の表示位置がずれるので、計算する際はその分を調整する必要があります。

あるいは、RenderTransformプロパティに何か設定していると描画の座標系と表示の座標系は一致しないので、その場合も、canvasオブジェクトとeraserオブジェクトの座標系を合わせる必要があります。

検出した交点座標に何か印を表示させて、期待通りの結果が返ってきているかどうかを視覚的に確認できるようにしておくと、デバッグしやすいと思います。

Comments

[dylan]

回答ありがとうございます。
うっかりeraserがCanvasに含まれていました。
お手数かけました。

Answer 2

誤動作する理由そのものは、catsforepawさんのおっしゃるとおり座標系の不一致ではというのに一票です。

ただ、そこを正したとしても残る問題があって、それは接触と交差を区別できない点です。お示しのコードでは接触した場合も交差と判定しています。そういう意図ならそれでいいのですが、接触しただけなら交差扱いにはしたくないという場合、このアルゴリズムでは無理です。特に、肘同士が当たっているような接触を判定できません。接触と交差を区別するためには、各点の多角形包含判定をしないといけません。

Comments

[dylan]

回答ありがとうございます。
ためになる話で勉強になります。