;============================================================
;  アルゴリズム 41〜45: 計算幾何 + ハッシュ
;    41. Point in Polygon (Ray Casting)
;    42. Line Segment Intersection
;    43. Triangle Area (Shoelace formula)
;    44. CRC32
;    45. FNV-1a hash (32 bit)
;============================================================

#include "hsp3cl_net_64.as"

; ----- 41. Point in Polygon (Ray casting) -----
#module
#defcfunc point_in_poly array _px, array _py, int _n, double _x, double _y, \
	local _i, local _j, local _inside, local _xi, local _yi, local _xj, local _yj
	_inside = 0
	_j = _n - 1
	repeat _n
		_i = cnt
		_xi = _px(_i) : _yi = _py(_i)
		_xj = _px(_j) : _yj = _py(_j)
		if (_yi > _y) != (_yj > _y) {
			if _x < (_xj - _xi) * (_y - _yi) / (_yj - _yi) + _xi : _inside = 1 - _inside
		}
		_j = _i
	loop
	return _inside
#global

; ----- 42. Line Segment Intersection -----
#module
#defcfunc seg_intersect double _x1, double _y1, double _x2, double _y2, \
                        double _x3, double _y3, double _x4, double _y4, \
                        var _ox, var _oy, \
                        local _den, local _ua, local _ub
	_den = (_x1 - _x2) * (_y3 - _y4) - (_y1 - _y2) * (_x3 - _x4)
	if absf(_den) < 1e-12 : return 0
	_ua = ((_x1 - _x3) * (_y3 - _y4) - (_y1 - _y3) * (_x3 - _x4)) / _den
	_ub = -((_x1 - _x2) * (_y1 - _y3) - (_y1 - _y2) * (_x1 - _x3)) / _den
	if _ua < 0.0 : return 0
	if _ua > 1.0 : return 0
	if _ub < 0.0 : return 0
	if _ub > 1.0 : return 0
	_ox = _x1 + _ua * (_x2 - _x1)
	_oy = _y1 + _ua * (_y2 - _y1)
	return 1
#global

; ----- 43. Triangle Area (Shoelace) -----
#module
#defcfunc tri_area double _x1, double _y1, double _x2, double _y2, double _x3, double _y3, \
	local _a
	_a = ((_x2 - _x1) * (_y3 - _y1) - (_x3 - _x1) * (_y2 - _y1)) * 0.5
	if _a < 0.0 : return -_a
	return _a
#global

; ----- 44. CRC32 -----
#module
#defcfunc crc32_compute var _data, int _len, \
	local _i, local _j, local _c, local _crc
	_crc = 0xFFFFFFFF
	repeat _len
		_i = cnt
		_c = _crc ^ peek(_data, _i)
		repeat 8
			if _c & 1 : _c = (_c >> 1) ^ 0xEDB88320 : else : _c = _c >> 1
		loop
		_crc = _c
	loop
	return _crc ^ 0xFFFFFFFF
#global

; ----- 45. FNV-1a (32 bit) -----
#module
#defcfunc fnv1a var _s, \
	local _h, local _i
	_h = 0x811C9DC5
	repeat strlen(_s)
		_h = _h ^ peek(_s, cnt)
		_h = _h * 16777619
	loop
	return _h
#global

; ===== デモ =====
	mes "=== Point in Polygon ==="
	; 四角形 (0,0)-(4,0)-(4,3)-(0,3)
	ddim px, 4 : px = 0.0, 4.0, 4.0, 0.0
	ddim py, 4 : py = 0.0, 0.0, 3.0, 3.0
	mes strf("  (2.0, 1.5) inside = %d (期待: 1)", point_in_poly(px, py, 4, 2.0, 1.5))
	mes strf("  (5.0, 1.5) inside = %d (期待: 0)", point_in_poly(px, py, 4, 5.0, 1.5))
	mes strf("  (0.0, 5.0) inside = %d (期待: 0)", point_in_poly(px, py, 4, 0.0, 5.0))

	mes ""
	mes "=== Segment Intersection ==="
	; (0,0)-(4,4) と (0,4)-(4,0) は (2,2) で交差
	ok = seg_intersect(0.0, 0.0, 4.0, 4.0, 0.0, 4.0, 4.0, 0.0, ix, iy)
	mes strf("  intersect? %d at (%.2f, %.2f)", ok, ix, iy)

	mes ""
	mes "=== Triangle Area (Shoelace) ==="
	ta = tri_area(0.0, 0.0, 4.0, 0.0, 0.0, 3.0)
	mes strf("  area((0,0),(4,0),(0,3)) = %.2f (期待: 6.0)", ta)

	mes ""
	mes "=== CRC32 ==="
	sdim buf, 64
	buf = "123456789"
	crc = crc32_compute(buf, 9)
	mes strf("CRC32('123456789') = %08X (期待: CBF43926)", crc & 0xFFFFFFFF)

	mes ""
	mes "=== FNV-1a ==="
	s = "hello"
	h = fnv1a(s) & 0xFFFFFFFF
	mes strf("FNV1a('hello') = %08X", h)
	s = "world"
	h = fnv1a(s) & 0xFFFFFFFF
	mes strf("FNV1a('world') = %08X", h)
	end 0