n각형의 안팎을 판단하는 알고리즘이 궁금합니다.

drfaust의 이미지

제가 궁금해 하는 문제는 지금 임의의 n각형이 있을 때 랜덤하게 한 점을 찍고 그 점이 n각형 안에 있는지 없는지를 판단하는 것을 간단하게 할 수 있는 알고리즘 입니다.
예를 들어 원 같은 경우에는 하나의 함수로 도형을 표현할 수 있기 때문에 안에 있는지 밖에 있는지 판단하기 쉬운데 임의의 n각형의 경우 생각보다 단순한 것 같지는 않습니다.
이런 문제를 해결할 수 있는 힌트라도 좀 알려주세요 ^^;;
웬지 컴퓨터 그래픽스 관련된 쪽에서는 이런 문제를 다룰 것 같은데......;; 어디서 찾아야 할지 누구한테 물어야 할지 잘 모르겠네요.

File attachments: 
첨부파일 크기
파일 inout.c811바이트
fox9의 이미지

그래픽쪽의 임의의 다각형의 내부를 칠하는 함수와 같은 형태로 해서 작성할 수 있지 않을까요?

아르아의 이미지

이런것은 그림없이 말로 설명하면 알아듣기가 힘들지 않을까 하네요.
그래도 글로 답글을 달아야 하니! 제 생각을 말씀드리자면,

1. 외접원, 내접원의 지름을 구합니다
2. 중점에서 점까지의 거리를 구합니다.
3. 내접원, 외접원 사이에 있는 점만 해결하면 되는데...
3.1. 해당점과 가장 가까운 다각형의 선분을 구합니다.
3.2. 중점에서 3.1의 선분에 수선을 그을 수 있죠? 그 수선의 방향벡터 n를 구합니다.
3.3 중점에서 점으로 가는 벡터를 V라고 했을때 V dot n > 내접원반지름 인지 판단합니다

kane의 이미지

임의의 점을 지나는 직선이 n각형과 몇 번 만나는지를 가지고 판단하는 방법이 있습니다. 다각형 밖에서 임의의 점까지 직선을 그었을 때, 다각형 둘레와 짝수번 만나면 점은 외부에 있고, 홀수번 만나면 점은 내부에 있습니다. 이 때 직선이 꼭지점을 지나는 경우 등을 고려해서 처리해주어야 합니다.
(아이디어로만 알고 있는 내용이라 구현에는 도움을 드릴 수 없을 것 같군요.)

asiawide의 이미지

간단하게 생각하면 임의의 n각형은(n>2) n-1개의 삼각형으로 나눌수 있기 때문에 각 삼각형에 대해서 점이 속하는지 파악하면 구할 수 있을 것 같네요. 아마도 computational geometry 로 찾아보시면 이 문제에 대한 답이 있을 것입니다.

kane의 이미지

김지훈 wrote:
이런것은 그림없이 말로 설명하면 알아듣기가 힘들지 않을까 하네요.
그래도 글로 답글을 달아야 하니! 제 생각을 말씀드리자면,

1. 외접원, 내접원의 지름을 구합니다
2. 중점에서 점까지의 거리를 구합니다.
3. 내접원, 외접원 사이에 있는 점만 해결하면 되는데...
3.1. 해당점과 가장 가까운 다각형의 선분을 구합니다.
3.2. 중점에서 3.1의 선분에 수선을 그을 수 있죠? 그 수선의 방향벡터 n를 구합니다.
3.3 중점에서 점으로 가는 벡터를 V라고 했을때 V dot n > 내접원반지름 인지 판단합니다


오목 다각형이면 내접원 자체를 구하기 곤란하겠네요.
vacancy의 이미지

일단 볼록 다각형의 경우는 좀 쉽게 되잖을까 싶은데,
오목한 부분이 있으면 쉽게 될지 모르겠네요.

다각형 내부 체크를 여기에 다 적는 건 좀 무리같고요.
( 한참 쓰다가 지웠네요. :cry: )
도움이 될만한 것만 하나 적으면요.
한 직선의 식을 f(x, y) = 0 라고 하고,
어떤 점이 있을 때 이 점을 (p, q)라고 하면,
직선의 한쪽에서는 f(p, q) > 0이고,
다른 한쪽에서는 f(p, q) < 0이 됩니다.

예를 들어 y = 2x + 3 이라는 직선이 있다면요.
f(x, y) = 2x - y + 3 = 0 이라고 직선을 표현할 수도 있죠.
이 직선의 양쪽에 있는 점인 (1, 2)와 (3, 10)을 여기 넣어보면,
f(1, 2) = 2 - 2 + 3 > 0
f(3, 10) = 6 - 10 + 3 < 0
.. 으로 서로 다른 부호를 나타냄을 알 수 있습니다.
이 함수에선 직선보다 위에 있으면 음이고, 아래 있으면 양이로군요.

N각형이므로 N개의 직선으로 나타낼 수 있는데요.
각 직선을 표현한 함수에 대해 해당 점에 대한 함수값을 구해서,
볼록 다각형에 대한 내부/외부 판별을 할 수 있는 걸로 압니다.
근데 오목 다각형에 대해서는 똑같이 되는지 모르겠네요. :roll:

vacancy의 이미지

쓰는 동안 글이 많이 올라왔네요. :oops:

쓰고보니 kane님이 적어주신 방법이
제일 무난한 방법이 아닐까 싶기도 하네요.
오목/볼록 다각형 모두에 적용 가능할테고요.

cppig1995의 이미지

kane님이 제가 하고 싶었던 말을 잘 표현해 주셨네요.
map[point_x][point_y] 부터 map[max_x][point_y] 까지 댕겨주면서
만약 n각형의 변이 나온다면 그 때마다 flag를 반전시켜 줍니다.
물론 flag의 초기값은 false 여야 합니다.
그 뒤 flag 가 false 이면 밖, true 이면 안이라고 생각하시면 됩니다.
구현은 간단하답니다.

Real programmers /* don't */ comment their code.
If it was hard to write, it should be /* hard to */ read.

cppig1995의 이미지

방금전 대충 짰습니다. Turbo C 2.01 에서 작동 확인했습니다.

예 :

5 5 3 3
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0

과 같이 입력하면, 5줄 5칸의 맵에서 1부터 시작하는 (3, 3) 위치에
있는 점이 nonzero 값 속에 있는지를 확인하는 프로그램입니다.
Source Code 올립니다.

그런데 drfaust (파우스트 박사?? :P)님,
시도시는 것이 몬테카를로 알고리즘이신가요?

댓글 첨부 파일: 
첨부파일 크기
파일 0바이트

Real programmers /* don't */ comment their code.
If it was hard to write, it should be /* hard to */ read.

only2sea의 이미지

예전에 선형대수 아니면 미적 하다가 비슷한 걸 한적이 있는것 같기도 합니다. 일단 좌표계가 2차원이라는 것에서 기분좋게 시작할 수 있습니다.

일단 문제를 명확히 해 봅시다. 임의의 n각형의 각 꼭지점의 좌표들...

P_0 = (x_0,y_0),
P_1 = (x_1, y_1),
...,
P_n-1 = (x_n-1, y_n-1)
단, x_k, y_k는 실수 (k = 0, 1, ..., n-1)

이런 좌표가 있을테지요.
변이 n개 생기고 각각의 변은

E_0 = P_0~P_1
E_1 = P_1~P_2
...
E_n-1 = P_n-1~P_0

이렇게 되겠죠.

일단 선분과 선분의 교차를 판단하는 함수를 하나 만들어야 합니다. 이것은 직선과 직선의 교차를 판단하는 함수(2차원에서는 평행하지 않으면 무조건 교차죠.)와 틀립니다. 선분은 길이가 유한하기 때문에 직선의 함수끼리 교차하더라도 선분은 교차하지 않을수도 있습니다.

두 선분의 교차는 아주 간단한 함수로 구현할 수 있습니다. 벡터 연산을 이용해서 삼각형 넓이 구하는 방법을 이용해서 부호 검사 하면 됩니다. 이건 구글링해보시면 많은 자료가 있으니 참고하시기 바랍니다.

선분의 교차를 판단하는 함수가 만들어지면 레이저 광선을 찍은 점에서 외부로 쏘아서 몇번 통과하는지 보면 됩니다. 외부의 점의 좌표는 P_0부터 P_n-1까지의 각 점들을 포함하는 대충만든 큰 사각형 울타리를 치고 그 밖에 있는 점을 선택하면 됩니다. 즉, 각각의 x좌표 중 최소값보다 작거나 최대값보다 크거나 y좌표의 경우도 마찬가지로 그런 식으로 잡으면 쉽게 잡을 수 있습니다. x 좌표는 최대값보다 크고 y 좌표는 평균값을 잡아도 되고 여러가지 방법이 있습니다.

찍은 점에서 외부점까지의 선분과 각각의 변과 교차 여부를 검사합니다. 교차하는 회수가 짝수이면 찍은 점은 외부에 있고 홀수이면 직은 점은 내부에 있습니다. 주의할 점은 컴퓨터에서 계산할 경우 선분의 끝부분에서 약간의 오차가 생길 수 있습니다. 정확하게 선분이 꼭지점을 지나가는 경우가 있는데 이것을 막기 위해서 선분 교차 알고리즘에 적용할 때 점을 넘기는 방향을 일정하게 해서 일률적으로 그런 상황에 대처하면 두번 카운트 되는 것을 막을 수 있습니다.

해보시면 생각보다 코드량은 얼마 되지 않습니다.

p.s.) 예전에 해본 적이 있어서 반드시 되는 겁니다.
p.s.2) 물론 볼록, 오목의 경우에 다 가능합니다.

vacancy의 이미지

에, 그런데요.
N각형이 우리 모니터 화면처럼 dot들로 구성되는게 아니라,
보통은 수학적 좌표계에서의 점 (x_1, y_1) ~ (x_n, y_n) 을 뜻하는 관계로;
변에 대한 직선(사실은 선분) 식들을 필요로 하는 경우가 많지요.

그리고 돼지군님께서 작성하신 알고리즘은,
map[p_x][p_y] 에서 map[max_x][p_y] 까지 가는동안
운이 나빠서 기울기 0인 변을 만나면 난감해집니다.

JuEUS-U의 이미지

n각형이 항상 볼록다각형이라면
외적이라는 것을 사용하여
쉽게 구할 수 있습니다.

(유감스럽지만 식이 기억이 안나는군요 :cry: )

아무튼지간에
그 녀석에다가 (x1,y1,x2,y2,p,q) 이렇게 넣어주면
(x1,y1)과 (x2,y2)를 이어주는 선분과 임의의 점 (p,q)의 위치관계(?)를 리턴합니다.

시계/반시계 방향인지에 따라서 -,+를 리턴해 주구요,
선분과 일직선상에 있으면 0을 주는걸로 기억합니다 ;;;

도형의 각 선분에 대해서 이 공식을 적용해주면 될 것 같습니다.
모두 한쪽 방향을 가리킨다면 내부에 있다가 성립되겠지요.

볼록/오목 관련없는것은 처리해줄게 좀 많다고 생각합니다 :roll:

vacancy의 이미지

체스맨의 이미지

kane 님도 언급하셨고, 첨부 문서에 Crossing Count 알고리즘이라 되어있는게 프로그램 구현 알고리즘으로서는 가장 우수합니다. 관련 분야에서 솔리드 모델러를 개발해본 경험이 있는데요,

http://home.megapass.net/~heesc22/orion/ima/h_imaml.htm

저는 ray firing 알고리즘 이라는 이름으로 알고있었습니다. 참고 서적으로는 1988년 Martti Mantyla 의 An Introduction To Solid Modeling 이 있습니다. ( 구하기는 쉽지 않습니다만... 저도 제본으로 가지고 있습니다. ) 이 책에서는

(1) 검사하려는 점과 다각형의 임의 모서리 1/2 지점에 해당하는 두 점을 이용해서 하나의 선을 만든다.

(2) 각 모서리에 대해 (1)에서 만든 선과 교차점 테스트를 해서 교차점 갯수를 센다.

(3) 다각형 꼭지점이 ray 선상에 존재하는 경우 다른 모서리를 선택해서 처음부터 다시 한다.

(3) 은 교차하지 않으나, 다각형이 ray 에 접하는 경우를 고려한 것인데, 이런 점은 카운트되지 않아야하기 때문에 특별한 다른 테스트를 넣기보다는 다시 시도하는 쪽을 택하게 되어있습니다. 관련 논문을 찾으시면 ray-firing 의 개선된 알고리즘 들이 있습니다.

이 알고리즘은 여각, 둔각, 내부 루프가 있는 다각형 및 입체에까지 적용될 수 있습니다. 단, 수학적 수식으로 표현되는 알고리즘이 아니기때문에, 수학자들은 별로 좋아하지 않는다 합니다.

Orion Project : http://orionids.org

익명 사용자의 이미지

구글에서,
polygon clipping convex concave
라는 키워드로 검색해 보시면 도움이 되실듯도 합니다.
* polygon clipping : 그래픽스 관련 서적 참조
* convex : 볼록, 폴리곤을 직선으로 이뤄진 폐곡선이라고 가정할때, 폴리곤내의 임의의 두점을 직선으로 연결할때, 폴리곤을 이루는 임의의 직선과 교점이 없는 것
* concave : 오목, 예를 들어, 凹
* convex라고 가정하면, 수많은 방법이 나오게 됩니다.

drfaust의 이미지

많은 분들이 답변해 주셔서 감사합니다 ^^

일단 위에 제시해주신 방법대로 한 번 구현해 보도록 하겠습니다.

감사합니다~

senseyw의 이미지

오래된 자료였네요
저도 동일한 주제로 검색을 하다가 여기까지 오게 되었는데,
저와 같은 고민을 하는 다른 분들을 위해 정리 겸~ 메모를 남기고 갑니다.

The "Crossing Count" Algorithm 이라는 알고리즘이 있습니다.
임의의 점이 어떤 모양의 도형이든간에 도형 내부에 있는지를 판별하는 알고리즘인데
요약하자면 (2차원이라고 가정을 하고)임의의 점에서 y좌표를 충분히(도형 밖일만큼) 연장시킨 포인트
즉, 정 북쪽 방향으로 연장시킨 포인트와 일직선을 그었을 때
도형과 만나는 점의 갯수가 홀수냐 짝수냐로 판단하는 알고리즘입니다.
물론 해당 포인트가 도형 선에 걸쳐 있을 때는 내부가 아니라고 판단해야겠네요
일직선으로 교차하는 문제도 있고 하니까요. 물론 그에 해당하는 해결책은 고민해보면 있을 것 같습니다.


=====================
즐길 수 없으면 피하라.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.