例えば、ベジエ曲線が四角形の中に入っていることを確かめるにはどうすればよいだろうか。

四角形内に点があるか、辺との交点があればベジエ曲線が含まれる。

そこで、交点を求めたい。

Bezier Clipping

最近のアルゴリズムらしい Bezier Clipping というものが有る。

http://nis-lab.is.s.u-tokyo.ac.jp/nis/bezclip.html

を、必死に読んでみた。

まず、曲線と直線の式がある。

これを使って、次のような式にする

* は、曲線の制御点の座標

この式に対して、次のように処理する。参考にしたのはこちらのページhttp://www-ui.is.s.u-tokyo.ac.jp/~kenshi/assignment/cg07/bezierclip.html

1. 凸包を得る
2. 各辺のうち、f(t)=0 を通る辺の、f(t) = 0 での t を求め、min, max とする
3. そのような辺がなければこの部分には解がない
4. min, max の範囲が、もともとの半分以上なら、解が複数あるとみて、曲線を半分に分割する。その両方の曲線を再帰し、両方の結果を戻す
5. そうでない場合、収束しているか調べ、していれば値を返す
6. していなければmin, max の範囲で曲線を切り出し、再帰し、結果を戻す。

自分の場合、切り取った曲線の t の変域は 0 <= t <= 1 だったので、 再帰した処理が戻ってくるとき、(max – min)倍に縮めて最小値を加算する処理を付け加えた。

        //このオブジェクトをベジエクリッピングする
        public float[] bezierclipping() {
            //Pointf にする t は項数で均等に分けたもの
            PointF[] pts = new PointF[points.Length];
            PointF[] convex;
            for (int i = 0; i < points.Length; i++) {
                pts[i].X = (1.0f / (points.Length-1)) * i;
                pts[i].Y = points[i];
            }

            //凸包を得る
            convex = mymath.convex_hull(pts);

            //凸包のうち、ゼロを通る辺を最小・最大値とする
           float min = float.MinValue, max = float.MaxValue;
           for (int i = 0; i < convex.Length; i++)
           {
               int j = (i + 1) % convex.Length;
               if (convex[i].Y * convex[j].Y < 0)
               {
                   if (min == float.MinValue)
                   {
                       min = (convex[i].X * (float)Math.Abs(convex[j].Y)
                           + convex[j].X * (float)Math.Abs(convex[i].Y))
                           / ((float)Math.Abs(convex[i].Y) + (float)Math.Abs(convex[j].Y));

                   }
                   else if (max == float.MaxValue)
                   {
                       max = (convex[i].X * (float)Math.Abs(convex[j].Y)
                           + convex[j].X * (float)Math.Abs(convex[i].Y))
                           / ((float)Math.Abs(convex[i].Y) + (float)Math.Abs(convex[j].Y));
                       break;
                   }
               }
               else if (convex[i].Y == 0) {
                   if (min == float.MinValue) min = convex[i].X;
                   else if (max == float.MaxValue) { max = convex[i].X; break; }
               }
           }
            if (min == float.MinValue || max == float.MaxValue)
                return new float[] { };

            if(min > max){
                float tmp;
                tmp = min; min = max; max = tmp;
            }
            if (max - min < (float)Math.Abs(pts[pts.Length - 1].X - pts[0].X) * 0.5f)
            {
                //0.5以下に小さくなるのならば、解はひとつ
                if (max - min < 0.0001) //収束判別
                {
                    return new float[] { (max - min) / 2 };
                }

                //もう一度縮めたい
                float[] tmp = cut(min, max).bezierclipping();
                for (int cnt = 0; cnt < tmp.Length; cnt++) {
                    tmp[cnt] *= (max - min)/1;
                    tmp[cnt] += min;
                }
                return tmp;
            }
            else
            {
                //0.5以上ならば解が複数ある
                bezierfunc[] cut_half = cut(0.5f);
                float[] a, b, c;
                a = cut_half[0].bezierclipping();
                b = cut_half[1].bezierclipping();

                c = new float[a.Length + b.Length];
                for (int i = 0; i < c.Length; i++) {
                    c[i] = (i < a.Length) ? a[i]/2 : (b[i - a.Length]/2 + 0.5f);
                }
                return c;
            }
        }