์ฝ๋ฐฑํจ์์ธ๊ฑด ์๊ฒ ๋๋ฐ
์ถฉ๋ ์ค๋ธ์ ํธ๊ฐ n๊ฐ์์๊ฒฝ์ฐ
๋ด๋ถ์ ์ผ๋ก
์ถฉ๋๊ฒ์ฌ๋ฅผ ์ํ์ n*n๋ฒ ์คํํ๋๊ฑด๊ฐ์
์ฝ๋ฐฑํจ์์ธ๊ฑด ์๊ฒ ๋๋ฐ
์ถฉ๋ ์ค๋ธ์ ํธ๊ฐ n๊ฐ์์๊ฒฝ์ฐ
๋ด๋ถ์ ์ผ๋ก
์ถฉ๋๊ฒ์ฌ๋ฅผ ์ํ์ n*n๋ฒ ์คํํ๋๊ฑด๊ฐ์
์๋ฐํ๊ฒ๋ ์๊ธฐ์์ ํ๊ณ ๋น๊ต๋ ์ ์ธ๋๊น (n-1)*(n-1) ์ด๊ฒ ์ง
์์ผํ์ ใ ใ
sweep and prune ์
๊ฒ์ํด๋ณด๋๊น ๋ง๋๊ฑฐ๊ฐ์์ฌ ใณ ์ถ๊ฐ์ ์ผ๋ก ๋ ์ง๋ฌธํ๊ณ ์ถ์๊ฒ ์๋๋ฐ ํน์ ์ ๋ํฐ์๋ ์ฝ๋ฐฑ์ผ๋ก ์ธํ ์ถฉ๋์ฒดํฌ๋ง๊ณ API์ Intersectrect์ฒ๋ผ ํจ์ํธ์ถ ๋ฐฉ์์ผ๋ก ์ถฉ๋๊ฒ์ฌ ํ ์ ์๋ ๋ฐฉ๋ฒ์ด ์๋์?? ๋ ์ด์บ์คํธ ๋ง๊ตฌ ์๋ฅผ๋ค์ด ๊ทธ ์ค๋ธ์ ํธ์ ์์น๋ ์ฝ๋ผ์ด๋ ์ ๋ณด๋ง ๊ฐ๋ค์ฃผ๋ฉด ์ด๊ฒ ๋ค๋ฅธ์ค๋ธ์ ํธ์ ์ถฉ๋์ค์ธ์ง ์๋์ง ์์์๋ ์ผ๋ฐ์ ์ธ ํธ์ถํจ์
๋น์ฐํ ์์ ธ !
๋ฌผ๋ฆฌ์์ง์ ๊ณต๊ฐ์ ๋ถํ ํด์ ๊ด๋ฆฌํจ. ๊ทธ๋ฌ๋ n์ ๊ณฑ์ ๋๋ก ๊ธฐํ๊ธ์์ ์ผ๋ก ์ฐ์ฌ๋์ด ๋์ด๋์ง ์์