sample\algorithms\10_geometry.hsp » Plain Format
;============================================================
; アルゴリズム 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