PointWithinShape (日本語)

地点が領域内に存在するかどうか試験するための関数集です。

PointWithinShape(shape, x, y)

指定された形状の境界内 (x,y) を形成する場合は true を返します。形状は 0 から n {x=x, y=y} まで値 の配列により定義されます。

それは一般的に他方で困難な作業を行うファイルにて別の関数を延期します (CrossingsMultipyTest(...), PointWithinLine(...), BoundingBox(...) および colinear(...))

BoundingBox(box, x, y)

指定された点が二地点により定義されたボックスの内部であるならば true を返します(再び PointWithinShape(...) により取得された同一形式)。

colinear(line, x, y, e)

指定された地点が二点ずつ定義された無限線上に存在するならば true を返します(PointWithinShape(...) により取得された同一形式)。

どのように閉じられた (x,y) が共線への線を制御するか指定されたならば e は選択制です。標準値は 0.1 です。

PointWithinLine(line, x, y, e)

指定された地点が二点ずつ定義された有限線上に存在するならば true を返します(再び PointWithinShape(...) により取得された同一形式)。

どのように閉じられた (x,y) が内線への線を制御するか指定されたならば e は選択制です。標準値は 0.66 です。

CrossingsMultiplyTest(polygon, x, y)

指定された地点が三つまたは点として定義された多角形の領域内に存在するならば true を返します(再び PointWithinShape(...) により取得された同一形式)。

(Point in Polygon Strategies のコードを元にしています)

GetIntersect( points )

PointWithinShape(...) により取得された同一形式の x, y 交差座標を返します。

(Bambo により追加 - "General math" スニペットの動作に対して checkIntersect が必要になります)

function PointWithinShape(shape, tx, ty)
	if #shape == 0 then 
		return false
	elseif #shape == 1 then 
		return shape[1].x == tx and shape[1].y == ty
	elseif #shape == 2 then 
		return PointWithinLine(shape, tx, ty)
	else 
		return CrossingsMultiplyTest(shape, tx, ty)
	end
end

function BoundingBox(box, tx, ty)
	return	(box[2].x >= tx and box[2].y >= ty)
		and (box[1].x <= tx and box[1].y <= ty)
		or  (box[1].x >= tx and box[2].y >= ty)
		and (box[2].x <= tx and box[1].y <= ty)
end

function colinear(line, x, y, e)
	e = e or 0.1
	m = (line[2].y - line[1].y) / (line[2].x - line[1].x)
	local function f(x) return line[1].y + m*(x - line[1].x) end
	return math.abs(y - f(x)) <= e
end

function PointWithinLine(line, tx, ty, e)
	e = e or 0.66
	if BoundingBox(line, tx, ty) then
		return colinear(line, tx, ty, e)
	else
		return false
	end
end

-------------------------------------------------------------------------
-- 以下の関数は次のコードを元にしています
-- [ http://erich.realtimerendering.com/ptinpoly/ ]
--
--[[
 ======= 交差乗算アルゴリズム           =================================
 * 
 * 通常、このバージョンは Graphics Gems IV で発表されたものより、幾分か
 * 高速化されています。この部分の試験は X 軸の交差試験で技巧的な乗算を
 * 行うことにより高速化されていますが、除算により三角形に対する交差を
 * 毎回算出するよりも少し低速な "左右両側" の試験に対して付加的な効果が
 * あります。主に大幅な高速化となったのは三角形の試験であり、それは
 * 約 15% 高速されています。それ以外の複雑な多角形は全ての以前と比較して
 * ほぼ同じ速度でした。除算処理で非常に遅い計算機に関しては (試験を行った 
 * HP9000 シリーズについての場合ではなく)、この試験で全体的に旧版のコードよりも、
 * もっと高速化されています。 里程は変化する(事実、そうであろう)場合があり、
 * 機械と試験データに依存するため、一般にこのコードは両方ともより短くて
 * 高速化されていると信じています。この試験は Samosky および Mark Haigh-
 * Hutchinson により提出された未刊の Graphics Gems から刺激を受けました。 
 * Samosky による関連する研究は次のものがあります:
 *
 * Samosky, Joseph, "SectionView: A system for interactively specifying and
 * visualizing sections through three-dimensional medical image data",
 * M.S. Thesis, Department of Electrical Engineering and Computer Science,
 * Massachusetts Institute of Technology, 1993.
 *
 --]]

--[[ 半直線試験 + X 軸に沿って動かします。戦略として頂点 Y 値を
 * 試験地点 Y との比較を行い、直ちに半直線試験の片側にある端を
 * 全て切り捨てます。 CrossingsTest() のコードに関しては 凸面および屈曲のコードを
 * 追加できることに注意してください。それは明快さのためにここに残されています。
 *
 * 二次元多角形 _pgon_ へ頂点数 _numverts_ および試験地点 _point_ を入力します。
 *  1 ならば内側であり、 0 ならば外側です。
 --]]
function CrossingsMultiplyTest(pgon, tx, ty)
	local i, yflag0, yflag1, inside_flag
	local vtx0, vtx1
	
	local numverts = #pgon

	vtx0 = pgon[numverts]
	vtx1 = pgon[1]

	-- 上・下の X 軸に関する試験ビットを取得します。
	yflag0 = ( vtx0.y >= ty )
	inside_flag = false
	
	for i=2,numverts+1 do
		yflag1 = ( vtx1.y >= ty )
	
		--[[ X 軸 (Y 軸とは異なります) に関しては、端をまたぐ検査を行います
		 *  (つまり反対側です)。その場合は半直線 +X が、この終点を交差します。
		 * また、旧式の試験では右側の終点あるいは左側の試験地点の両方であるか
		 * どうかを確認していました。しかしながら、計算で下記で使用したものより
		 * 高速な交差地点を与えられたならば、この試験では三角形に関して、
		 * 大抵の三角形と敗者に対する損益分岐点命題であることが判明します
		 * (生存している端が 50% またはそれ以上である場合は、この試験は
		 * 四分区間を越えているため、とにかく X の交差が算出される
		 * 必要があります)。私は Joseph Samosky が私のコードにある "両方とも左または
		 * 両方とも右" の部分をボツにしようと奮起したことを評価します。
		 --]]
		if ( yflag0 ~= yflag1 ) then
			--[[ 半直線 +X で pgon 線分の交差を確認します。
			 * if >= 地点の X に注意しない場合は、半直線に当たります。
			 * 除算操作は最初の頂点である wrto の試験地点で符号を
			 * 確認することにより ">=" 試験は回避されます。
			 * Joseph Samosky と Mark Haigh-Hutchinson による
			 * 多角形包含試験により刺激された着想です。
			 --]]
			if ( ((vtx1.y - ty) * (vtx0.x - vtx1.x) >= (vtx1.x - tx) * (vtx0.y - vtx1.y)) == yflag1 ) then
				inside_flag =  not inside_flag
			end
		end

		-- 可能ならば情報を保持して、頂点の次にある一対を移動します。
		yflag0  = yflag1
		vtx0    = vtx1
		vtx1    = pgon[i]
	end

	return  inside_flag
end

function GetIntersect( points )
	local g1 = points[1].x
	local h1 = points[1].y
	
	local g2 = points[2].x
	local h2 = points[2].y
	
	local i1 = points[3].x
	local j1 = points[3].y

	local i2 = points[4].x
	local j2 = points[4].y
	
	local xk = 0
	local yk = 0
	
	if checkIntersect({x=g1, y=h1}, {x=g2, y=h2}, {x=i1, y=j1}, {x=i2, y=j2}) then
		local a = h2-h1
		local b = (g2-g1)
		local v = ((h2-h1)*g1) - ((g2-g1)*h1)

		local d = i2-i1
		local c = (j2-j1)
		local w = ((j2-j1)*i1) - ((i2-i1)*j1)

		xk = (1/((a*d)-(b*c))) * ((d*v)-(b*w))
		yk = (-1/((a*d)-(b*c))) * ((a*w)-(c*v))
	end
	return xk, yk
end