【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※マルチポスト(多重投稿)は謹んで!

 詳しくはこちら



 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.19604

点の包含判定
投稿者---花鳥(2005/01/27 23:57:26)


平面上に、三角形ABCと点Pが与えられています。この点が、三角形のなかに含まれているか判定するプログラムが作りたい。誰か教えてください。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:点の包含判定 19614 YuO 2005/01/28 01:49:08
<子記事> Re:点の包含判定 19629 かずま 2005/01/28 13:38:23


No.19614

Re:点の包含判定
投稿者---YuO(2005/01/28 01:49:08)


>平面上に、三角形ABCと点Pが与えられています。この点が、三角形のなかに含まれているか判定するプログラムが作りたい。誰か教えてください。

「何を」教えて欲しいのですか?
#点と直線の距離を出すだけだと思うのですが……。


この投稿にコメントする

削除パスワード

No.19699

Re:点の包含判定
投稿者---かずま(2005/02/02 03:10:34)


>> 平面上に、三角形ABCと点Pが与えられています。この点が、三角形のなかに
>> 含まれているか判定するプログラムが作りたい。誰か教えてください。

>「何を」教えて欲しいのですか?
> #点と直線の距離を出すだけだと思うのですが……。

点と直線の距離を出すだけで、その点が三角形の内部かどうかを判定する方法を
私は思いつきません。興味があるので具体的にご説明をお願いします。


この投稿にコメントする

削除パスワード

No.19700

Re:点の包含判定
投稿者---たいちう(2005/02/02 11:18:46)


YuOさんの方法とは違うかもしれませんが、ちょっと考えてみました。
前提として点と直線の距離の絶対値だけでなく向きも必要です。

△ABCと点Pについて、辺BCを基準に点Aの高さを考えると、
Pが三角形の内部にあるためには、PとBCの距離は、
この高さ以下である必要があります。
但し、BCを挟んでAと反対側にあってはいけないので、
Aの向きを正として符号付で距離を求めるのが良いでしょう。

辺CA、辺ABについても同様に判定すると必要十分条件になります。

# 決してスマートでないな。絶対値だけの場合も私には無理そう。
# ベクトルAB、ベクトルACで、ベクトルAPを表し、
# 係数の範囲で判定っていうのが数学的には定石だと思いますが
# プログラムでも同じでしょうか?
# いずれセジウィックやクヌースの本で勉強したいなぁ。


この投稿にコメントする

削除パスワード

No.19707

Re:点の包含判定
投稿者---かずま(2005/02/03 01:08:24)


> YuOさんの方法とは違うかもしれませんが、ちょっと考えてみました。
> 前提として点と直線の距離の絶対値だけでなく向きも必要です。

距離だけではだめだということですね。


> △ABCと点Pについて、辺BCを基準に点Aの高さを考えると、
> Pが三角形の内部にあるためには、PとBCの距離は、
> この高さ以下である必要があります。
> 但し、BCを挟んでAと反対側にあってはいけないので、
> Aの向きを正として符号付で距離を求めるのが良いでしょう。

そうですが、直線BC によって分割される 2つの領域において、P が A と同じ
側にあることが重要なのであって、距離は不要です。なぜなら、

辺CA についても、P は B と同じ側、
辺AB についても、P は C と同じ側、

という条件と合わせることで、P が △ABC の内部だと判定できるからです。

No.19629 のプログラムはそれをコーディングしたものです。

直線 AB を表す方程式は、

(ay - by) * (x - bx) - (ax - bx) * (y - by) = 0

点(x, y) が直線AB上であれば = 0 ですが、2つの領域のどちらにあるかに
よって、> 0 または < 0 になりますから、それを判定に使えばよいでしょう。


この投稿にコメントする

削除パスワード

No.19708

Re:点の包含判定
投稿者---mon(2005/02/03 09:11:42)


>> YuOさんの方法とは違うかもしれませんが、ちょっと考えてみました。
>> 前提として点と直線の距離の絶対値だけでなく向きも必要です。
>
>距離だけではだめだということですね。

Sabcは点a,b,cからなる面積だとして、
SPAB + SPBC + SPCA = SABC
が成り立てば内部の点。

距離がわかれば、面積が判るので…
というのはちょっと強引!?


この投稿にコメントする

削除パスワード

No.19709

Re:点の包含判定
投稿者---たいちう(2005/02/03 10:05:44)


> そうですが、直線BC によって分割される 2つの領域において、P が A と同じ
> 側にあることが重要なのであって、距離は不要です。なぜなら、

あ、本当だ。

> Sabcは点a,b,cからなる面積だとして、
> SPAB + SPBC + SPCA = SABC
> が成り立てば内部の点。
>
> 距離がわかれば、面積が判るので…
> というのはちょっと強引!?

これも思いつきませんでした。
かずまさん、monさん、勉強になりました。


この投稿にコメントする

削除パスワード

No.19710

Re:点の包含判定
投稿者---mon(2005/02/03 12:38:24)


PAとPBのなす角
PBとPCのなす角
PCとPAのなす角
の合計が360でもいけるのかな?
すいません、検証してる時間がない。


この投稿にコメントする

削除パスワード

No.19726

Re:点の包含判定
投稿者---かずま(2005/02/04 00:59:04)


> PAとPBのなす角
> PBとPCのなす角
> PCとPAのなす角
> の合計が360でもいけるのかな?

3頂点の座標から 3辺の長さを出し、余弦定理で 3つの角を求めればできると
思いますが、三角関数まで入ってくるので、誤差の問題が大きくなりそうです。
double length(const Point *a, const Point *b)
{
    double x = a->x - b->x,  y = a->y - b->y;
    return sqrt(x*x + y*y);
}

double angle(double a, double b, double c)
{
    double t = (a && c) ? (a*a + c*c - b*b) / (2*a*c) : 0;
    if (t < -1) t = -1; else if (t > 1) t = 1;
    return acos(t);
}

int is_inside(const Point *a, const Point *b, const Point *c, const Point *p)
{
    double bc = length(b, c),  ca = length(c, a),  ab = length(a, b);
    double pa = length(p, a),  pb = length(p, b),  pc = length(p, c);
    double t = angle(pb, bc, pc) + angle(pa, ab, pb) + angle(pc, ca, pa);
    return fabs(t - 2*3.141592653589793238) < 1e-10;
}



この投稿にコメントする

削除パスワード

No.19725

Re:点の包含判定
投稿者---かずま(2005/02/04 00:34:08)


> Sabcは点a,b,cからなる面積だとして、
> SPAB + SPBC + SPCA = SABC
> が成り立てば内部の点。
>
> 距離がわかれば、面積が判るので…
> というのはちょっと強引!?
なるほど、面積を使うという手がありますね。でも、距離は不要です。
3辺の長さが分かっている場合、へロンの公式で三角形の面積が求められるのは
有名ですが、3頂点の座標が分かっている場合も面積は簡単に求められます。

#include <math.h>

typedef struct { double x, y; } Point;

double area(const Point *a, const Point *b, const Point *c)
{
    return fabs((a->x - c->x)*b->y + (b->x - a->x)*c->y + (c->x - b->x)*a->y) / 2;
}

int is_inside(const Point *a, const Point *b, const Point *c, const Point *p)
{
    return area(p, b, c) + area(p, c, a) + area(p, a, b) == area(a, b, c);
}


ただし、これだと、三角形の内部だけでなく、辺上の点も含まれてしまいます。

それ以上に問題なのが、点P が三角形の内部にあっても、浮動小数点演算の精度
の問題により、等式が成り立たない場合があることです。そこで、次のように
書いたほうがよいかもしれません。

int is_inside(const Point *a, const Point *b, const Point *c, const Point *p)
{
    double t = area(p, b, c) + area(p, c, a) + area(p, a, b);
    return fabs(area(a, b, c) - t) < 1e-10 * t;
}



この投稿にコメントする

削除パスワード

No.19754

Re:点の包含判定
投稿者---monkey(2005/02/05 17:22:01)


いろいろな方法が考えられるものですね。
次のようなのはいかがでしょうか。

typedef struct { double x, y; } Point;

int under( const Point* a, const Point* b, const Point* p )
{
    return ( a->x <= p->x && p->x < b->x || b->x < p->x && p->x <= a->x )
           && p->y < a->y + ( p->x - a->x ) * ( b->y - a->y ) / ( b->x - a->x ) ? 1 : 0;
}

int is_inside( const Point* a, const Point* b, const Point* c, const Point* p )
{
    return under( a, b, p ) + under( b, c, p ) + under( c, a, p ) == 1;
}

under関数は、y軸方向を上下としたとき、点pが線分abの下側にあれば1、そうでなければ0を返します。
各辺についてのunder関数の判定結果の合計が1(点pは1辺だけの下側にある)ならば、pは三角形の内
部にあると判定できます.
平面図形と任意の点の関係について、当該点から任意の方向に引いた半直線が図形の周を横切る回数が
奇数回ならば、当該点は図形の内部にあるという原理に基づいています。



この投稿にコメントする

削除パスワード

No.19756

Re:点の包含判定
投稿者---かずま(2005/02/06 02:00:00)


> 次のようなのはいかがでしょうか。

A(0,0), B(4,0), C(3,3) の場合、P(0,-1) や P(4,-5) は明らかに
△ABC の外部ですが、そのプログラムでは内部になってしまいますよ。


この投稿にコメントする

削除パスワード

No.19757

Re:点の包含判定
投稿者---monkey(2005/02/06 02:49:08)


>> 次のようなのはいかがでしょうか。
>
>A(0,0), B(4,0), C(3,3) の場合、P(0,-1) や P(4,-5) は明らかに
>△ABC の外部ですが、そのプログラムでは内部になってしまいますよ。

本当だ^^;
pのx座標値がいずれかの頂点のx座標値と同じ場合に正しく判定できないことがありました。
ご指摘ありがとうございました。

前回書いた原理を生かすなら、pのx座標値と頂点のx座標値が等しい場合の特別な判定処理が必要ですね。
次のように改めます。

typedef struct { double x, y; } Point;

int in_range( double x1, double x2, double t )
{
    return x1 < t && t < x2 || x2 < t && t < x1;
}

int under( const Point* a, const Point* b, const Point* p )
{
    return in_range( a->x, b->x, p->x ) && p->y < a->y + ( p->x - a->x ) * ( b->y - a->y ) / ( b->x - a->x ) ? 1 : 0;
}

int is_inside( const Point* a, const Point* b, const Point* c, const Point* p )
{
    int n = 0;
    if( p->x == a->x && p->y < a->y && in_range( c->x, b->x, p->x ) ){
        n++;
    }
    if( p->x == b->x && p->y < b->y && in_range( a->x, c->x, p->x ) ){
        n++;
    }
    if( p->x == c->x && p->y < c->y && in_range( b->x, a->x, p->x ) ){
        n++;
    }
    return  n + under( a, b, p ) + under( b, c, p ) + under( c, a, p ) == 1;
}




この投稿にコメントする

削除パスワード

No.19629

Re:点の包含判定
投稿者---かずま(2005/01/28 13:38:23)


#include <stdio.h>

typedef struct { double x, y; } Point;

double line(Point *a, Point *b, Point *c)
{
    return (a->y - b->y)*(c->x - b->x) - (a->x - b->x)*(c->y - b->y);
}

int is_inside(Point *a, Point *b, Point *c, Point *p)
{
    return line(a, b, c) * line(a, b, p) > 0
        && line(b, c, a) * line(b, c, p) > 0
        && line(c, a, b) * line(c, a, p) > 0;
}

int main(void)
{
    Point a = {0, 0}, b = {4, 0}, c = {3, 3}, p;

    for (p.x = -1; p.x <= 5; p.x++)
        for (p.y = -1; p.y <= 4; p.y++)
            printf("(%2g,%2g) %s\n", p.x, p.y,
                is_inside(&a, &b, &c, &p) ? "in" : "out");
    return 0;
}



この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧