由 benice 於 星期六 六月 09, 2018 5:21 am
先用兩點式求出座標格的邊線方程式:
通過 (x1,y1) 與 (x2,y2) 的直線 L1: (x2 - x1)*(y - y1) = (y2 - y1)*(x - x1)
通過 (x2,y2) 與 (x3,y3) 的直線 L2: (x3 - x2)*(y - y2) = (y3 - y2)*(x - x2)
通過 (x3,y3) 與 (x4,y4) 的直線 L3: (x4 - x3)*(y - y3) = (y4 - y3)*(x - x3)
通過 (x4,y4) 與 (x1,y1) 的直線 L4: (x1 - x4)*(y - y4) = (y1 - y4)*(x - x4)
為簡化表示式,令
f1(x,y) = (x2 - x1)*(y - y1) - (y2 - y1)*(x - x1)
f2(x,y) = (x3 - x2)*(y - y2) - (y3 - y2)*(x - x2)
f3(x,y) = (x4 - x3)*(y - y3) - (y4 - y3)*(x - x3)
f4(x,y) = (x1 - x4)*(y - y4) - (y1 - y4)*(x - x4)
由所給數據知 (或假設) x2 > x1, y3 < y2, x4 < x3, y1 > y4,所以
L1 下方區域之不等式為 f1(x,y) < 0
L2 左方區域之不等式為 f2(x,y) < 0
L3 上方區域之不等式為 f3(x,y) < 0
L4 右方區域之不等式為 f4(x,y) < 0
因此,座標格範圍內之不等式為
f1(x,y) < 0 and f2(x,y) < 0 and f3(x,y) < 0 and f4(x,y) < 0
或用最大值函數 max 表示成
max(f1(x,y), f2(x,y), f3(x,y), f4(x,y)) < 0
給定一個點 (x,y) 及一個座標格,並計算 M(x,y) = max(f1(x,y), f2(x,y), f3(x,y), f4(x,y)) 值,
則:
(1) 如果 M(x,y) < 0,則點 (x,y) 落在此座標格範圍內;
(2) 如果 M(x,y) > 0,則點 (x,y) 落在此座標格範圍外;
(3) 如果 M(x,y) = 0,則點 (x,y) 位於此座標格邊界上。
註:
如果所有相鄰的座標格都緊密接合,則點 (x,y) 所在座標格為唯一 (座標格的邊線除外),
因此只有一個座標格的 M(x,y) 值小於零,所以可以比較所有座標格的 M(x,y) 值,值最小
的那個就是你要找的。