다각형에 특정 점 포함 유무선별

오랫만에 글을 쓰게됬다.

이번에 스터디까페를 만들면서 글을 병행하며 쓰고 있다.

http://cafe.naver.com/cse2study

이번 알고리즘은 기존의 AABB의 단점인 직각사각형(그것도 수직, 수평인 사각형)에만 적용되는 단점을 보완하고자

OBB 모든 다각형에 대해 다각형2다각형의 충돌영역을 검출하고자 하였다.

처음으로 다각형2점 을 선별하기 위해 요즘 공부하고 있는 LUA로 코드를 짜봤다.

RECT = {{x=10,y=10},{x=15,y=25},{x=20,y=5},{x=25,y=20}}

P = {x=15,y=15}

isInner = false

for i=1,2,1 do

local d1 = {x=RECT[1+i].x-RECT[1].x,y=RECT[1+i].y-RECT[1].y}

local d2 = {x=RECT[2+i].x-RECT[1].x,y=RECT[2+i].y-RECT[1].y}

local p  = {x=P.x-RECT[1].x,y=P.y-RECT[1].y}

t2 = (p.x*d1.y-p.y*d1.x)/(d2.x*d1.y-d2.y*d1.x)

t1 = (p.x-t2*d2.x)/d1.x

if t1>=0 and t1<=1 and t2>=0 and t2<=1 and t1+t2>=0 and t1+t2<=1 then

isInner = true

end

end

if isInner == true then

print("isInner")

else

print("isOutter")

end

만약 n각형이라면 최상단의 for문을 n-2까지 검출하면 된다.

for문에서 isInner가 검출된다면 break으로 나와도 무관하다.