2次元平面上の2つの線分が交差するか判定する関数を作る。 構造体: typedef struct POINT_tag // POINT_t …… 点 { int x; // x 座標 int y; // y 座標 } POINT_t; typedef struct LINE_tag // LINE_t …… 線分、直線 { POINT_t a; // 始点 POINT_t b; // 終点 } LINE_t; 関数: //********************************************************* // 線分 e1, e2 が交差するか判定する。 // 線分 e1, e2 が交差すれば真、さもなくば偽を返す //********************************************************* int intersect( LINE_t *e1, LINE_t *e2 ) { // 線分 e1, e2 を対角線とする2つの長方形が交わらない場合、線分 e1, e2 が交わることはない。 if ( min(e1->a.x, e1->b.x) > max(e2->a.x, e2->b.x) ) return 0; if ( min(e1->a.y, e1->b.y) > max(e2->a.y, e2->b.y) ) return 0; if ( min(e2->a.x, e2->b.x) > max(e1->a.x, e1->b.x) ) return 0; if ( min(e2->a.y, e2->b.y) > max(e1->a.y, e1->b.y) ) return 0; // 線分 e2 が直線 e1 を跨ぎ、かつ、線分 e1 が直線 e2 を跨ぐならば、線分 e1, e2 は交差する。 return straddle( e1, &e2->a, &e2->b ) && straddle( e2, &e1->a, &e1->b ); }//intersect //********************************************************* // 点 a, b が直線 e を跨いで存在するか判定する。 // 点 a, b が直線 e を跨いでいれば真、さもなくば偽を返す // 点が直線上に存在する場合には『直線を跨ぐ』と判断する。 //********************************************************* int straddle( LINE_t *e, POINT_t *a, POINT_t *b ) { // 点 a, b が互いに有向線分 e の異なる側にあるならば、点 a, b は線分 e を跨ぐ。 return 0 >= ( side(a,e) * side(b,e) ); }//straddle 関連 | |