/*
 *	clipint.h
 *
 *	整数演算ライブラリ
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2016 Naoyuki Sawa
 *
 *	* Sat Sep 12 20:19:17 JST 2009 Naoyuki Sawa
 *	- 新規作成。
 *	- clipflt.hモジュール互換仕様の整数版です。
 *	  今回はrender_vec2i_alternate_concaves()だけが必要だったので、そのための最小限の関数以外はほとんど未実装です。
 *	* Wed Nov 18 21:37:53 JST 2015 Naoyuki Sawa
 *	- 'extern "C" {'〜'}'で囲みました。.cppを含むWin32プロジェクトからもインクルード出来るようにするためです。
 *	* Tue Oct 04 23:23:40 JST 2016 Naoyuki Sawa
 *	- これまで長い間、当モジュールで実装済みだった関数はvec2i_is_point_in_concave,vec2i_is_point_in_alternate_concaves,render_vec2i_alternate_concavesだけで、
 *	  それ以外の関数は未実装のままだったのですが、今回、DxlibHelper.cppの「太いポリラインの描画」のために整数ベクトル演算が必要になって、それ以外の関数も実装を行いました。
 *	  詳細は、以下の通りです。
 *	- sqrtiを追加しました。(sqrt,sqrtf,sqrtlの命名規則に倣っただけで、標準Cライブラリで定義されている関数ではありません。)
 *	- vec2i_0,vec2i_1,vec2i_x,vec2i_yが未実装だったのを、実装しました。
 *	- vec2i_add,vec2i_sub,vec2i_mul,vec2i_divが未実装だったのを、実装しました。
 *	- vec2i_neg,vec2i_normalが未実装だったのを、実装しました。
 *	- vec2i_mag,vec2i_mag2,vec2i_dot,vec2i_crossが未実装だったのを、実装しました。
 *	- vec2i_dist,vec2i_dist2が未実装だったのを、実装しました。
 *	- vec2i_distance_l_p,vec2i_intersection_l_p,vec2i_intersection_l,vec2i_is_intersected_lsが未実装だったのを、実装しました。
 *	- vec2i_is_point_in_convex,vec2i_is_intersected_pが未実装だったのを、実装しました。
 *	- 今回の実装は、ほとんど、clipflt1.cのソースをコピーして〜fを〜iに変えた事以外は、型の違いによる修正を少し行っただけです。
 *	  ただし、本当にそれで正しく動作しているか、まだ検証が不十分です。
 *	  今後、実際にアプリケーションで使用しながら、検証を行う予定です。
 *	  尚、vec2i_is_point_in_concave,vec2i_is_point_in_alternate_concaves,render_vec2i_alternate_concavesだけは既に実装済みだった関数で、2009年当時の実装時にある程度検証済みです。
 *	- vec2f_〜は浮動小数演算なのでゼロ除算例外は発生しませんでしたが、vec2i_〜では整数演算なのでゼロ除算例外が発生する事に注意して下さい。
 *	  具体的には、vec2i_div(),vec2i_normal(),vec2i_distance_l_p(),vec2i_intersection_l()、及び、それらを内部で呼び出している処理で、ゼロ除算例外が発生する可能性が有ります。
 *	  ゼロ除算が発生しないように、呼び出し側で、引数を検査して下さい。
 *	  ちなみに、VC++6.0やP/ECEでは、浮動小数演算のゼロ除算例外は発生しませんが、「Borland C++ 5.5.1 for Win32」では、浮動小数演算でもゼロ除算例外が発生するようです。
 *	* Thu Oct 06 21:47:33 JST 2016 Naoyuki Sawa
 *	- sqrtu()を追加し、既存のsqrti()と追加したsqrtu()の実装を共通化しました。
 *	  詳細は、以下の通りです。
 *	- これまでは、開平法の解説が判り易い、「プログラムモグモグ」(http://itchyny.hatenablog.com/)さんの「2010-12-22 平方根なんてビット演算ですればいいじゃない」(http://itchyny.hatenablog.com/entry/20101222/1293028538)のソースを利用させて頂いていました。
 *	  今回、簡潔でP/ECEに適した開平法の実装である、「Ｐ／ｗａｒｅ」(http://park17.wakwak.com/~hitode/)さんの「平方根(2003-05-21)」「平方根その２(2003-05-22)」(http://park17.wakwak.com/~hitode/piece/index.html#isqrt)を見付けたので、そちらに変更しました。
 *	  C言語版は、「平方根(2003-05-21)」の「isqr()」をそのまま利用させて頂きました。
 *	  アセンブラ版は、「平方根その２(2003-05-22)」の「isqr:」(筆算方式)をベースに、少しだけ改善させて頂きました。
 *	  本当は、P/ECEでは、「平方根その２(2003-05-22)」の「isqr2:」(掛け算方式)の方が早くて小さいのですが、今回は開平法の勉強と言う事で、敢えて「isqr:」(筆算方式)の方を使う事にしました。
 *	* Sun Oct 23 10:04:30 JST 2016 Naoyuki Sawa
 *	- vec2i_split_polygon_into_triangles()を追加しました。
 *	* Mon Oct 24 21:50:37 JST 2016 Naoyuki Sawa
 *	- vec2i_split_polygon_into_triangles()の戻り値の意味を変更しました。
 *	  変更前は「分割成功(1)/分割失敗(0)」でしたが、変更後は「分割した三角形の数(0〜(n-2)」としました。
 *	  変更した理由は、以下の通りです。
 *	- vec2i_split_polygon_into_triangles()は、以下のような原因で、分割失敗する可能性が有ります。
 *	  ・指定された多角形の中に、交差している辺が有る。(=正しい多角形ではない)
 *	  ・演算誤差のために、誤って、三角形の内部に残りの頂点が有ると見なしてしまい、分割出来ないと判断してしまう。
 *	  これまでは、前者,後者共に、分割処理中に一回でも上記のケースが生じたら、全体を分割失敗と見なしていたのが問題でした。
 *	  少しでも分割出来ない部分が有ると、その多角形全体が描かれず、見た目にちらつきが生じるからです。
 *	- そこで、見た目のちらつきを緩和するための対策として、一か所でも失敗したら全体を描かないのではなく、分割出来た所までは描くように変更しました。
 *	  そのために、vec2i_split_polygon_into_triangles()の戻り値の意味を変更し、分割出来た所までの三角形の数を返す事にしました。
 *	  呼び出し側では、戻り値の数ぶんの所まで、tri_p[]を描画すれば良いです。
 *	  もし、分割が完全に成功したか、一部でも失敗したかを、呼び出し側で判断する必要が有る場合は、戻り値が(n-2)に等しいかを判定すれば良いです。
 *	- 実験した所、誤差による分割失敗が起き易い頂点の多い多角形(100角形等)でも、実際に分割失敗するのは、最後の98個目の三角形の切り取り時でした。
 *	  要するに、最後に残った3頂点が、演算誤差で逆回りの形で残ってしまい、切り取りに失敗するようです。
 *	  この場合、既に97個の三角形が切り取れているわけで、それを描くだけで見た目上はほぼ十分です。
 *	  従って、今回の対策は有効であると思います。
 */
#ifndef __CLIP_INT_H__
#define __CLIP_INT_H__
#ifdef  __cplusplus
extern "C" {
#endif//__cplusplus
/****************************************************************************
 *	汎用
 ****************************************************************************/
//{{2016/10/06変更:sqrtu()を追加し、既存のsqrti()と追加したsqrtu()の実装を共通化しました。
//int sqrti(int x);
//↓2016/10/06変更:sqrtu()を追加し、既存のsqrti()と追加したsqrtu()の実装を共通化しました。
int sqrti(int s/*0〜INT_MAX*/);
unsigned sqrtu(unsigned s/*0〜UINT_MAX*/);
//}}2016/10/06変更:sqrtu()を追加し、既存のsqrti()と追加したsqrtu()の実装を共通化しました。
/****************************************************************************
 *	整数ベクトル(2D)
 ****************************************************************************/
typedef struct _vec2i {
	int x, y;
} vec2i;
/*--------------------------------------------------------------------------*/
extern const vec2i vec2i_0;
extern const vec2i vec2i_1;
extern const vec2i vec2i_x;
extern const vec2i vec2i_y;
/*--------------------------------------------------------------------------*/
void vec2i_add(vec2i* vec1, const vec2i* vec2);
void vec2i_sub(vec2i* vec1, const vec2i* vec2);
void vec2i_mul(vec2i* vec1, const vec2i* vec2);
void vec2i_div(vec2i* vec1, const vec2i* vec2);
/*--------------------------------------------------------------------------*/
void vec2i_neg(vec2i* vec);
void vec2i_normal(vec2i* vec);
/*--------------------------------------------------------------------------*/
int vec2i_mag(const vec2i* vec);
int vec2i_mag2(const vec2i* vec);
int vec2i_dot(const vec2i* vec1, const vec2i* vec2);
int vec2i_cross(const vec2i* vec1, const vec2i* vec2);
/*--------------------------------------------------------------------------*/
/* 二点間の距離を求める */
int vec2i_dist(const vec2i* vec1, const vec2i* vec2);
/* 二点間の距離の二乗を求める */
int vec2i_dist2(const vec2i* vec1, const vec2i* vec2);
/*--------------------------------------------------------------------------*/
/* 点a,bを通る直線と点cとの距離 */
int vec2i_distance_l_p(const vec2i* a, const vec2i* b, const vec2i* c);
/* a,bを通る直線と、点cから直線へ下ろした垂線との交点計算 */
vec2i vec2i_intersection_l_p(const vec2i* a, const vec2i* b, const vec2i* c);
/* a1,a2を通る直線とb1,b2を通る直線の交点計算 */
vec2i vec2i_intersection_l(const vec2i* a1, const vec2i* a2, const vec2i* b1, const vec2i* b2);
/* a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定 */
int vec2i_is_intersected_ls(const vec2i* a1, const vec2i* a2, const vec2i* b1, const vec2i* b2);
/*--------------------------------------------------------------------------*/
/* 点pと、v[nv]を頂点とする凸多角形の内外判定 */
int vec2i_is_point_in_convex(const vec2i* p, const vec2i* v/*[nv]*/, int nv);
/* 点pと、v[nv]を頂点とする凹多角形の内外判定 */
int vec2i_is_point_in_concave(const vec2i* p, const vec2i* v/*[nv]*/, int nv);
/* a[na]を頂点とする凹多角形と、b[nb]を頂点とする凹多角形の交差判定 */
int vec2i_is_intersected_p(const vec2i* a/*[na]*/, int na, const vec2i* b/*[nb]*/, int nb);
/* 点pと、交互モードで描かれた複数の閉じた多角形の内外判定 */
int vec2i_is_point_in_alternate_concaves(const vec2i* p, const vec2i* v/*[sum(nv[0...n-1])]*/, const int* nv/*[n]*/, int n);
/*--------------------------------------------------------------------------*/
/* n角形を、(n-2)個の三角形に分割する。 */
int vec2i_split_polygon_into_triangles(const vec2i p[/*n*/], int n/*0不可*/, vec2i tri_p[/*(n-2)*/][3]);
/*****************************************************************************
 *	
 *****************************************************************************/
#ifdef  __cplusplus
}//extern "C"
#endif//__cplusplus
#endif//__CLIP_INT_H__
