melt日記

.NETすらまともに扱えないへたれのページ

ホーム 連絡をする 同期する ( RSS 2.0 ) Login
投稿数  111  : 記事  3  : コメント  8254  : トラックバック  41

ニュース

わんくま同盟

わんくま同盟

C# と VB.NET の質問掲示板

iKnow!


Dictation



書庫

どうも、脳内で Template Metaprogramming が流行っている melt です。こんばんは。


といいつつも今日は Template Metaprogramming は全く関係なくて、凸包判定についてのお話です。

自分は最近ゲームプログラミングのためのリアルタイム衝突判定という本を読み進めています。

当然内容なんてほとんど分かっていないのですが、ちょっとだけ理解できる部分に面白いことが書いてありました。

多角形が凸かどうかを判定する方法をネット上で調べてみると、各線分ベクトルの外積の符号が全て同じ(内角が180度未満)であれば凸多角形として判断している場合が多いのだけれども、この判断だけだと十分ではない、ということが書かれていました。

五芒星なんか考えると分かりやすいと思います。

http://melt.wankuma.com/gobousei.jpg

確かに内角が全て180度未満ですが、明らかに凸多角形では無いです。


で、これはどうやって解決すればいいのかなぁと思って続きを読んでみたのですが、この本、参考文献だけ示してソースが載ってないのです。

どうしようかなと思ってとりあえず参考文献の情報を調べてみると、どうやらホームページ上でソースコードが公開されているとのこと。

ここから辿れる中の、convex_opt.cというのがそれに当たるようです。

英語読めない人なのでどういう仕組みなのかあまり理解出来ていないのですが、とりあえずこれを C# 用に書き直してテストしてみると、五芒星はちゃんと NotConvex になりました。


他にも点が同じ場所にあるような場合とか複数の点が同一直線上にあるようなケースも試してみましたが、ちゃんと正常に判断されていました。テラスゴス。


以下 C# 用に書き直したコード

public struct Point
{
    public Point(double x, double y)
    {
        X = x;
        Y = y;
    }
    public double X;
    public double Y;
}


public enum ConvexType
{
    NotConvex = -2, // 凸包ではない
    NotConvexDegenerate = -1, // 凸包ではなく、縮退している
    ConvexDegenerate = 0, // 凸包であるが、縮退している
    ConvexCCW = 1, // 反時計回りの凸包
    ConvexCW = 2, // 時計回りの凸包
}

public static ConvexType IsConvex(Point[] points)
{
    int nvert = points.Length;

    if (nvert < 3)
    {
        return ConvexType.ConvexDegenerate;
    }
    int second;
    Point dprev;
    int iread = 1;
    while (true)
    {
        second = iread++;
        dprev = new Point(
            points[second].X - points[0].X,
            points[second].Y - points[0].Y);
        if (dprev.X != 0 || dprev.Y != 0)
        {
            break;
        }
        if (iread >= nvert)
        {
            return ConvexType.ConvexDegenerate;
        }
    }

    int saveSecond = second;

    int curDir =
        (dprev.X < 0.0) ? -1 :
        (dprev.X > 0.0) ? 1 :
        (dprev.Y < 0.0) ? -1 :
        (dprev.Y > 0.0) ? 1 : 0;

    int dirChanges = 0;
    int angleSign = 0;

    while (true)
    {
        if (iread >= nvert)
        {
            iread = 0;
        }
        int third = iread++;

        Point dcur = new Point(
            points[third].X - points[second].X,
            points[third].Y - points[second].Y);
        if (dcur.X == 0.0 && dcur.Y == 0.0)
        {
            continue;
        }

        int thisDir =
            (dcur.X < 0.0) ? -1 :
            (dcur.X > 0.0) ? 1 :
            (dcur.Y < 0.0) ? -1 :
            (dcur.Y > 0.0) ? 1 : 0;
        if (thisDir == -curDir)
        {
            ++dirChanges;
        }
        curDir = thisDir;

        double cross = dprev.Y * dcur.X - dprev.X * dcur.Y;
        if (cross > 0)
        {
            if (angleSign == -1)
            {
                return ConvexType.NotConvex;
            }
            angleSign = 1;
        }
        else if (cross < 0)
        {
            if (angleSign == 1)
            {
                return ConvexType.NotConvex;
            }
            angleSign = -1;
        }
        second = third;
        dprev = dcur;

        if (saveSecond == second)
        {
            break;
        }
    }

    if (dirChanges > 2)
    {
        if (angleSign == 0)
        {
            return ConvexType.NotConvexDegenerate;
        }
        else

        {
            return ConvexType.NotConvex;
        }
    }
    if (angleSign > 0)
    {
        return ConvexType.ConvexCCW;
    }
    if (angleSign < 0)
    {
        return ConvexType.ConvexCW;
    }
    return ConvexType.ConvexDegenerate;
}

C 版の classifyPolygon2 と比べて無駄に比較している部分があるので少しだけ遅くなってしまっていますが、許容範囲かなぁという感じです。


あと↑のコードは 0.0 と比較していますが、ほんとはある程度小さい値(Epsilon)より小さければ 0 として考える方がいいと思うんですけどどうなんでしょう。

投稿日時 : 2007年11月15日 2:20

コメント

# re: [C#]多角形の正確な凸包判定 2007/11/15 11:50 とっちゃん
3点は必ず凸多角形ですよw

0丸めをするかどうかは...利用先次第のような気がします。
衝突判定なら、整数演算で行けるだろうしw

専門外だからさっぱり~ですけどねw

# re: [C#]多角形の正確な凸包判定 2007/11/15 12:07 melt
>3点は必ず凸多角形ですよw
まあそうなんですけど、この関数は、その三角形が時計回りの三角形なのか反時計回りの三角形なのか、それとも縮退した三角形なのか、というのを調べるのにも使えそうですね。

0 丸めは頑健性についてもうちょっと勉強してから考えることにします。

# re: [C#]多角形の正確な凸包判定 2007/11/15 12:12 Zee
凸を判断するなら両側に凹みがあるか判定すれば凸ということになるんじゃ?

凹みになる前の座標を取得して2つ後の座標と直線で結ぶ
2番目に来る点と織りなす角度のSINが+か-か判断して+なら凹みとする。

判定が+、-、+となれば凸となるように判断してはどうですか?

# re: [C#]多角形の正確な凸包判定 2007/11/15 13:33 凪瀬
結局、「各線分ベクトルの外積の符号が全て同じ」では不十分だけど、
そこに何を加えることで正しく判定できるようになるんでしょうか?
ソースを読め?

五芒星みたいなのは内角の総和で判定するとかすれば対処できそうだけど。


# re: [C#]多角形の正確な凸包判定 2007/11/15 15:00 melt
>Zee さん
数学苦手なのでよく分からないですごめんなさい。
直前の線分から見て90度未満で折れ曲がってたら凹みってことですか?

>凪瀬さん
>そこに何を加えることで正しく判定できるようになるんでしょうか?
ソースを読む限りだと、方向の変化と複数の点が同じ場所にあるときの対応を加えれば良さそうな感じですね。

>ソースを読め?
リンク先のソースのコメントを読めば分かるかもしれません。

>五芒星みたいなのは内角の総和で判定するとかすれば対処できそうだけど。
自己交差を含む多角形の内角の総和は、必ず凸包の多角形の内角の総和と一致しない、というのが証明できればいけそうですね。

# re: [C#]多角形の正確な凸包判定 2007/11/15 15:40 凪瀬
なんか問題提起しておいて、解決できたよ!っていってるけどその方策は秘密(はぁと
みたいな感じのエントリになっててじれったかったものでw

仕組みはよくわからんがソースを移植したら判別できたってことなのかw

# re: [C#]多角形の正確な凸包判定 2007/11/15 15:57 melt
ですです。
ソースを見ればやっていることは大体分かって、確かにこれならいけそうな気はするなぁとは思うんですが、なぜこれで十分なのかということに関しては Graphics Gems IV(参考文献として挙げられていた本)等を読まないと分からなさそうです。

このエントリは「仕組みはどうでもいいからとにかく凸包の判定が出来る C# のソースが欲しい」って感じで検索してきた方のために書いたつもりです。

# re: [C#]多角形の正確な凸包判定 2007/11/15 16:17 Zee
>直前の線分から見て90度未満で折れ曲がってたら凹みってことですか?
もうちょっとわかりやすく・・・

1.1点目座標と3点座標を結んで直線を引く
2.2点目がその線を引いた右か左か判定
3.次の点で同じ事をする

四角形ABCDの場合
・この理論だとACに線を引くことになる。
・対角線に対しBは左にくる(右回りの時計回りなら)
・Bに移る
・BとDを結ぶ
・Cは左にくる
・Cに移る
・CとAを結ぶ
・Dは左にくる
・Dに移る
・DとBを結ぶ
・Aは左にくる

判定結果:左、左、左、左 ・・・ 凸形状じゃない


凸形状の場合ABCDEFGHと点名を付番する。
・ACを結ぶ
・Bは右
・BDを結ぶ
・Cは左
・CEを結ぶ
・Dは左
・DFを結ぶ
・Eは右
・・・・・・・・・
あとは左

結果: 右、左、左、右、左 左、左、左

なので右~右を挟む所が凸になっている。


☆形状
結果だけ・・・
右、左、右、左、右、左、右、左、右、左
なので、
右左右の組み合わせが5つある。
(最後のものは最初のものに挟まれる:図形は必ず閉合するので)
なので凸部分が5つあると分かる。

ってな具合に考えたんですけども。


# re: [C#]多角形の正確な凸包判定 2007/11/15 16:47 melt
>1.1点目座標と3点座標を結んで直線を引く
>2.2点目がその線を引いた右か左か判定
>3.次の点で同じ事をする
多分それは外積の符号をみる方法と同じだと思います。

>☆形状
絵が悪かったですね……この五芒星は直線五本で描いた形です。
  1
4   3
 2 5
という順番で線を結んでいくと、上記の方法だと右・右・右・右・右、と判断されて、凸包の多角形(凸のない多角形)と判断されてしまうのです。

# re: [C#]多角形の正確な凸包判定 2007/11/16 9:24 Zee
>>☆形状
>絵が悪かったですね……この五芒星は直線五本で描いた形です。
>  1
>4   3
< 2 5
>という順番で線を結んでいくと、上記の方法だと右・右・右・右・右、と判断さ>れて、凸包の多角形(凸のない多角形)と判断されてしまうのです。

自分の中では、構成する直線は重なり合わないという前提なので、
話がかみ合っていませんでしたね^^;(失礼いたしました)

# sHsLCOTezBRTUjQNy 2011/12/26 23:38 http://www.discreetpharmacist.com/ger/index.asp
Extremely easy by words but in reality?, a lot of things don`t correspond. Not everything is so rosy..!

# AeAuzHWYrkBgGeLvhSl 2011/12/27 0:22 http://www.discreetpharmacist.com/ger/index.asp
Well, actually, a lot of what you write is not quite true !... well, okay, it does not matter:D

# NiMhDDskWuJJiPfb 2011/12/27 6:33 http://www.67wine.com/
Heartfelt thanks..!

# VtyBtWhyOOHxcQ 2012/01/06 22:27 http://www.luckyvitamin.com/c-1154-vitamin-k-formu
Read, of course, far from my topic. But still, we can work together. How do you feel about trust management?!...

# ugg sale 2012/10/26 12:30 http://www.topsuggsonsale.com
He struck his attacker on the ear.Be careful!Do l have toYou can never turn the clock back.What's wrong with you? Do you think you can come?Do you think you can come?Thanks for your flattering me.Well£¬it depends.There isn't any water in the bottle.
ugg sale http://www.topsuggsonsale.com

# Burberry Sale 2012/10/27 2:19 http://burberry.2096909555.com
She was injured badly in the accident.He won an election.I caught the last bus.We need to cooperate perfectly to win the game.Of course!I have two cats.I have two cats.You mustn't aim too high.Let me see.I would rather stay at home alone.
Burberry Sale http://burberry.2096909555.com

# maillot football pas cher 2013/01/13 4:13 http://www.maillotdefootpascher2013.info/
à 700 $ pour une table qui peut accueillir quatre personnes , en battant les San Jose Earthquakes 1-0 le 26 Juin, Nous avons donné une bonne réaction dans les 25 dernières minutes nouveau maillot foot, il a été juste essayer dobtenir dans la zone entre les deux défenseurs centraux, cest une autre équipe qui nous attend dans la file dattente maillot equipe de france mariniere. évadez-vous avec Sounders match nul 2-2 contre les Whitecaps Seattle Sounders lutte contre Columbus Crew Seattle Sounders Impossible Snap séquence sans victoire contre Chivas USA Seattle Sounders Avance à lUS Open Quarts de finale de la Coupe Seattle Sounders lutte contre lImpact de Montréal . Backe na pas maché ses mots lors de la discussion ennuis de dommages de son équipe et 1-3-2 record depuis dévidant cinq victoires consécutives! Le club lui a demandé de renégocier son contrat .
maillot football pas cher http://www.maillotdefootpascher2013.info/

# maillot de foot pas cher 2013/01/13 4:13 http://www.maillotfootpascher1314.com/
Rosales flottait personnalis maillot de foot , e réellement contr?lé le ballon maillot de foot barca, Si Chelsea obtenir ce stade et qui tourne , Les Sounders ont riposté peu de temps après . Fernandez était sur son chemin à Chicago et Tiffert était le plus récent ajout à la liste Sounders maillot de foot 2013 real, Royaume eu les meilleures occasions de la seconde moitié .
maillot de foot pas cher http://www.maillotfootpascher1314.com/

# fgiGHPTEJvWE 2015/04/19 14:51 sally
iQM9gJ http://www.FyLitCl7Pf7kjQdDUOLQOuaxTXbj5iNG.com

Post Feedback

タイトル
名前
Url:
コメント