/*
 *	framht2.c
 *
 *	2D当り判定ルーチンを定義します。
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2006 Naoyuki Sawa
 *
 *	* Sun Oct 08 13:37:42 JST 2006 Naoyuki Sawa
 *	- 作成開始。
 */
#include "clip.h"

/* 参考資料を、「keep/多角形の交差判定資料.7z」に保存してあります。 */

/*****************************************************************************
 *	ht2_seg_seg
 *****************************************************************************/

/* * Mon Oct 09 08:46:56 JST 2006 Naoyuki Sawa
 * - 「－ＫＯＮＥ's Ｄ－Ｓｔａｔｉｏｎ－」さんの記事 (http://kone.vis.ne.jp/)
 *   『多角形の交差判定編－２（点の内外判定）』      (http://kone.vis.ne.jp/diary/diaryb09.html#040518)
 *   『多角形の交差判定編－１（概要と辺の交差判定）』(http://kone.vis.ne.jp/diary/diaryb09.html#040528)
 *   を参考にさせていただきました。
 * - 「直線ABが点Cと点Dを分断しているか、または、点Cと点Dの少なくとも一方が直線AB上に有る」の判断式が、
 *   画面対角線ぐらいの大きさの線分同士の判定時に、固定小数演算ではすぐにオーバーフローしてしまいます。
 *   オーバーフローを防ぐために、乗算を使わず、符号ビット(bit31)のXorを取る方法で実装しました。
 *   もしも今後、浮動小数演算バージョンを作成する場合は、乗算を使う方法で作成してください。
 */
int
ht2_seg_seg(fixed ax, fixed ay, fixed bx, fixed by, fixed cx, fixed cy, fixed dx, fixed dy)
{
	fixed ab_xmin;
	fixed ab_xmax;
	fixed ab_ymin;
	fixed ab_ymax;
	fixed cd_xmin;
	fixed cd_xmax;
	fixed cd_ymin;
	fixed cd_ymax;
	//
	fixed dax;
	fixed day;
	fixed abx;
	fixed aby;
	fixed bcx;
	fixed bcy;
	fixed cdx;
	fixed cdy;
	//
	fixed dab;
	fixed abc;
	fixed bcd;
	fixed cda;

	/* 判定①:
	 * 線分ABと線分CDが同一直線上の離れた位置にある場合を除外するために、
	 * 線分ABと線分CDの境界矩形同士による重なり判定を行います。
	 * この判定を行わないと、判定②で誤って重なりと判断されてしまいます。
	 */
	if(fcom(ax, <=, bx)) { ab_xmin = ax; ab_xmax = bx; }
	else                 { ab_xmin = bx; ab_xmax = ax; }
	if(fcom(cx, <=, dx)) { cd_xmin = cx; cd_xmax = dx; }
	else                 { cd_xmin = dx; cd_xmax = cx; }
	if(fcom(ab_xmax, <, cd_xmin) || fcom(cd_xmax, <, ab_xmin)) {
		return 0;
	}
	if(fcom(ay, <=, by)) { ab_ymin = ay; ab_ymax = by; }
	else                 { ab_ymin = by; ab_ymax = ay; }
	if(fcom(cy, <=, dy)) { cd_ymin = cy; cd_ymax = dy; }
	else                 { cd_ymin = dy; cd_ymax = cy; }
	if(fcom(ab_ymax, <, cd_ymin) || fcom(cd_ymax, <, ab_ymin)) {
		return 0;
	}

	/* 判定②:
	 * 線分ABと線分CDの交差を判断するために、以下の条件をチェックします。
	 * ・直線ABが点Cと点Dを分断しているか、または、点Cと点Dの少なくとも一方が直線AB上に有る
	 * ・直線CDが点Aと点Bを分断しているか、または、点Aと点Bの少なくとも一方が直線CD上に有る
	 * 二つの条件が同時に満たされる場合、線分ABと線分CDは交差しています。
	 */
	dax = fsubr(dx, ax); day = fsubr(dy, ay);	/* DA */
	abx = fsubr(ax, bx); aby = fsubr(ay, by);	/* AB */
	bcx = fsubr(bx, cx); bcy = fsubr(by, cy);	/* BC */
	cdx = fsubr(cx, dx); cdy = fsubr(cy, dy);	/* CD */
	dab = fsub(fmul(dax, aby), fmul(abx, day));	/* DA×AB */
	abc = fsub(fmul(abx, bcy), fmul(bcx, aby));	/* AB×BC */
	//if(ficom(fmul(dab, abc), >, 0)) {
	//↓オーバーフロー防止
	if(dab && abc && ((int)dab ^ (int)abc) > 0) {
		return 0;
	}
	bcd = fsub(fmul(bcx, cdy), fmul(cdx, bcy));	/* BC×CD */
	cda = fsub(fmul(cdx, day), fmul(dax, cdy));	/* CD×DA */
	//if(ficom(fmul(bcd, cda), >, 0)) {
	//↓オーバーフロー防止
	if(bcd && cda && ((int)bcd ^ (int)cda) > 0) {
		return 0;
	}

	return 1;
}

/*****************************************************************************
 *	ht2_pt_pgn
 *****************************************************************************/

/* * Mon Oct 09 08:46:56 JST 2006 Naoyuki Sawa
 * - 以前に浮動小数バージョンで実装したものと、ほぼ同じアルゴリズムです。
 *   「keep/01_浮動小数版演算描画コード保存/clipmath.c」の、point_in_polygon()を参照してください。
 * - point_in_polygon()に較べて、以下の三点を改善しました。
 *   ・いちばん上の頂点を探すときに、同時に境界矩形を求め、おおまかな当り判定を行って高速化しました。
 *   ・パラメータFは「-F」の形で用いられるので、あらかじめ「-F」として求めておくよう変更しました。
 *   ・点が、多角形の辺上または頂点上に有る場合に、誤って外側と判断される場合があったのを修正しました。
 *	①─２	たとえば、左図のような多角形1-2-3-4の、頂点1上に存在する点の内外判定を行った場合、
 *	│　│	辺4-1との判定時に一回、辺2-3との判定時に一回の、合計二回で外側と判断されていました。
 *	４─３	この問題を防ぐため、点が多角形の辺上または頂点上にある場合は、直ちに内側と判断します。
 */
int
ht2_pt_pgn(fixed px, fixed py, const fixed pgn[/*n*/][2/*x,y*/], int n)
{
	int i;
	int j;
	int cross;
	fixed x0;
	fixed y0;
	fixed x1;
	fixed y1;
	fixed  C;
	fixed  D;
	fixed  E;
	fixed _F;
	fixed DE_CF;
	fixed Dprev;
	fixed xmin;
	fixed xmax;
	fixed ymin;
	fixed ymax;

	/* 多角形の頂点数が0ならば、当り判定無しと見なします。(2006/10/17追加) */
	if(!n) {
		return 0;
	}

	/* いちばん上の頂点を検索しながら、同時に境界ボックスを求め、おおまかな当り判定を行います。 */
	i = 0;
	xmin = xmax = pgn[i][0];
	ymin = ymax = pgn[i][1];
	for(j = 1; j < n; j++) {
		x0 = pgn[j][0];
		y0 = pgn[j][1];
		if(fcom(x0, <, xmin)) { xmin = x0;        } else if(fcom(x0, >, xmax)) { xmax = x0; }
		if(fcom(y0, <, ymin)) { ymin = y0; i = j; } else if(fcom(y0, >, ymax)) { ymax = y0; }
	}
	if(fcom(px, <, xmin) || fcom(px, >, xmax) ||
	   fcom(py, <, ymin) || fcom(py, >, ymax)) {
		return 0;
	}

	/* 点を始点とする半直線と、多角形の辺の交差回数を求め、奇数ならば内側、偶数ならば外側です。 */
	cross = 0;
	Dprev = 0;
	x0 = pgn[i][0];
	y0 = pgn[i][1];
	for(j = 0; j < n; j++) {
		if(++i == n) {
			i = 0;
		}
		x1 = pgn[i][0];
		y1 = pgn[i][1];

		 C = fsub(x1, x0);
		 D = fsub(y1, y0);
		 E = fsub(x0, px);
		_F = fsub(py, y0); /* -F */

		DE_CF = fadd(fmul(D, E), fmul(C, _F)); /* DE-CF */
		if(!DE_CF) {
			return 1; /* 点が、多角形の辺上、または、頂点上に有る */
		}
		if(ficom(D, >, 0)) {
			if(ficom(Dprev, >, 0)) { if(ficom(DE_CF, >, 0) && ficom(_F, > , 0) && fcom(D, >=, _F)) cross++; }
			else                   { if(ficom(DE_CF, >, 0) && ficom(_F, >=, 0) && fcom(D, >=, _F)) cross++; }
			Dprev = D;
		} else if(ficom(D, <, 0)) {
			if(ficom(Dprev, <, 0)) { if(ficom(DE_CF, <, 0) && ficom(_F, < , 0) && fcom(D, <=, _F)) cross++; }
			else                   { if(ficom(DE_CF, <, 0) && ficom(_F, <=, 0) && fcom(D, <=, _F)) cross++; }
			Dprev = D;
		}

		x0 = x1;
		y0 = y1;
	}
	return cross & 1;
}

/*****************************************************************************
 *	ht2_pgn_pgn
 *****************************************************************************/

/* * Mon Oct 09 08:46:56 JST 2006 Naoyuki Sawa
 * - 「－ＫＯＮＥ's Ｄ－Ｓｔａｔｉｏｎ－」さんの記事 (http://kone.vis.ne.jp/)
 *   『多角形の交差判定編－２（点の内外判定）』      (http://kone.vis.ne.jp/diary/diaryb09.html#040518)
 *   『多角形の交差判定編－１（概要と辺の交差判定）』(http://kone.vis.ne.jp/diary/diaryb09.html#040528)
 *   を参考にさせていただきました。
 */
int
ht2_pgn_pgn(const fixed a[/*na*/][2/*x,y*/], int na, const fixed b[/*nb*/][2/*x,y*/], int nb)
{
	int i;
	int j;
	fixed ax0;
	fixed ay0;
	fixed ax1;
	fixed ay1;
	fixed bx0;
	fixed by0;
	fixed bx1;
	fixed by1;
	fixed a_xmin;
	fixed a_xmax;
	fixed a_ymin;
	fixed a_ymax;
	fixed b_xmin;
	fixed b_xmax;
	fixed b_ymin;
	fixed b_ymax;

	/* 多角形の頂点数が0ならば、当り判定無しと見なします。(2006/10/17追加) */
	//if(!na || !nb) {	// cmp %NA,0; jreq EXIT; cmp %NB,0; jreq EXIT;
	//↓少し高速化
	if(!(na & nb)) {	// ld.w %TMP,%NA; and %TMP,%NB; jreq EXIT;
		return 0;
	}

	/* 境界矩形を求め、おおまかな当り判定を行います。 */
	a_xmin = a_xmax = a[0][0];
	a_ymin = a_ymax = a[0][1];
	for(i = 1; i < na; i++) {
		ax0 = a[i][0];
		ay0 = a[i][1];
		if(fcom(ax0, <, a_xmin)) { a_xmin = ax0; } else if(fcom(ax0, >, a_xmax)) { a_xmax = ax0; }
		if(fcom(ay0, <, a_ymin)) { a_ymin = ay0; } else if(fcom(ay0, >, a_ymax)) { a_ymax = ay0; }
	}
	b_xmin = b_xmax = b[0][0];
	b_ymin = b_ymax = b[0][1];
	for(i = 1; i < nb; i++) {
		bx0 = b[i][0];
		by0 = b[i][1];
		if(fcom(bx0, <, b_xmin)) { b_xmin = bx0; } else if(fcom(bx0, >, b_xmax)) { b_xmax = bx0; }
		if(fcom(by0, <, b_ymin)) { b_ymin = by0; } else if(fcom(by0, >, b_ymax)) { b_ymax = by0; }
	}
	if(fcom(a_xmax, <, b_xmin) || fcom(b_xmax, <, a_xmin) ||
	   fcom(a_ymax, <, b_ymin) || fcom(b_ymax, <, a_ymin)) {
		return 0;
	}

	/* 線分同士の交差判定を行い、多角形同士が交差しているか判断します。 */
	ax0 = a[na - 1][0];
	ay0 = a[na - 1][1];
	for(i = 0; i < na; i++) {
		ax1 = a[i][0];
		ay1 = a[i][1];
		bx0 = b[nb - 1][0];
		by0 = b[nb - 1][1];
		for(j = 0; j < nb; j++) {
			bx1 = b[j][0];
			by1 = b[j][1];
			if(ht2_seg_seg(ax0, ay0, ax1, ay1, bx0, by0, bx1, by1)) {
				return 1; /* 交差している */
			}
			bx0 = bx1;
			by0 = by1;
		}
		ax0 = ax1;
		ay0 = ay1;
	}

	/* 一方の多角形にもう一方の多角形が完全に含まれているか判断します。 */
	if(ht2_pt_pgn(a[0][0], a[0][1], b, nb)) {
		return 1; /* 多角形Aが多角形Bを含んでいる */
	}
	if(ht2_pt_pgn(b[0][0], b[0][1], a, na)) {
		return 1; /* 多角形Bが多角形Aを含んでいる */
	}

	return 0;
}

/*****************************************************************************
 *	ht2_srt_pgn
 *****************************************************************************/

void
ht2_srt_pgn(const SRT* srt, const fixed pgn_in[/*n*/][2/*x,y*/], fixed pgn_out[/*n*/][2/*x,y*/], int n)
{
	if(n) { /* "while(n--){...}"よりも"do{...}while(--n);"の方が早いので、先に判定しておきます。 */
		const fixed* p_in  = &pgn_in [0][0];
		      fixed* p_out = &pgn_out[0][0];
		if(ficom(srt->r, ==, 0) && ficom(srt->s, ==, 1)) {
			/* 拡縮回転無しのケースが多いと思うので、単純に高速化します。 */
			do {
				*p_out++ = fadd(*p_in++, srt->x);
				*p_out++ = fadd(*p_in++, srt->y);
			} while(--n);
		} else {
			/* | Xout |   | cos(r)*s -sin(r)*s x | | Xin |
			 * | Yout | = | sin(r)*s  cos(r)*s y | | Yin |
			 * |    1 |   |        0         0 1 | |   1 |
			 */
			fixed c = fmul(fcos(srt->r), srt->s);
			fixed s = fmul(fsin(srt->r), srt->s);
			do {
				fixed x = *p_in++; /* pgn_in==pgn_outの場合のために、 */
				fixed y = *p_in++; /* 取り出しておく必要があります。  */
				*p_out++ = fadd(fsub(fmul(c, x), fmul(s, y)), srt->x);
				*p_out++ = fadd(fadd(fmul(s, x), fmul(c, y)), srt->y);
			} while(--n);
		}
	}
}
