폴리곤의 루프 방향...
김정희
이 다각형이 clock-wise 로 도는지, anti-clock wise 로 도는지를 판단하고
싶습니다.
제가 생각해 본 방법은,
이 다각형을 이루는 선분 하나를 아무거나 선택해서,
이 선분 벡터을 90도 회전시킨 방향으로 반직선을 그어,
다른 선분들과의 교점을 찾아 이 개수가 짝수이면, anti-clock, 홀수이면
clock-wise로
판단하는 것입니다.
그런데, 문제는 이 교점이 꼭지점 중의 하나에서 생기는 경우 입니다.
만일, (x, y) 값들이 모두 정수라면, 이 직선의 x, y 값에 0.5를 더해서 계산을
하면 될 것 같은데
(x, y) 값들이 실수 입니다.
제 방법의 잘못된 점이나, 다른 방법이 있으면 소개 부탁드립니다.
--
김정희
ps.
이런 류의 질문을 여기에 하는 것이 맞는지 잘 모르겠습니다.
잘못되었다면, 알려주시고 다른 NG 를 알려주시기 바랍니다.
Gyujin Han
"김정희" wrote:
>
> (x, y) 점의 리스트로 이루어 진 다각형이 있습니다.
> 이 다각형이 clock-wise 로 도는지, anti-clock wise 로 도는지를 판단하고
> 싶습니다.
>
> 제가 생각해 본 방법은,
> 이 다각형을 이루는 선분 하나를 아무거나 선택해서,
> 이 선분 벡터을 90도 회전시킨 방향으로 반직선을 그어,
> 다른 선분들과의 교점을 찾아 이 개수가 짝수이면, anti-clock, 홀수이면
> clock-wise로
> 판단하는 것입니다.
anti-clock??????
이런 표현도 사용하나요?
counter-clockwise, 줄여서 CCW라 하지요......
반대는 CW.
그건 그렇고...... 반직선이라면, 그 점에서 부터 한쪽 방향으로만 쏜다는
의미이겠지요......
이것을 ray라고 부릅니다.
그리고 그 점은 위의 설명대로라면 선분위에 있게 되겠지요?
그런데, 닫힌 곡선에 대해 ray를 위와 같이 쏘면, 그 시작점을 포함하였을
경우에는 항상 짝수개, 포함하지 않았을 경우에는 항상 홀수개가 나오게
됩니다. CW, CCW와는 상관 없이 말입니다.
이 방법은 임의의 점이 다각형 내부에 있는지 외부에 있는지를 검사하는
방법입니다. IN-OUT test라고 하지요.
여하트 IN-OUT 검사에 대해 조금 더 얘기를 해 봅시다.
>
> 그런데, 문제는 이 교점이 꼭지점 중의 하나에서 생기는 경우 입니다.
음...... 그리고 선분이 ray에 완전히 겹치는 경우도 문제가 있겠지요.
이 경우 한가지 해결 방법으로는 ray를 다른 방향으로 쏘는 것입니다. 겹치는
선분이나, 꼭지점과 만나는 일이 없어질 때 까지 말입니다. 이 방법은 재수
없을 경우 계속해서 쏘아대기만 하는 수가 생길 수 있으므로 별로 사용되지
않습니다. 그냥 그렇게 하는 수도 있다라고 생각하시면 되겠읍니다.
다른 방법으로는 ray와 만나는 꼭지점의 앞, 뒤 선분의 방향에 따라 처리하는
것입니다. 겹치는 선분의 경우 두 꼭지점에서 만나게 되니, 이 두 꼭지점을
하나로 생각해서 각각 앞 귀로 인접하는 선분을 사용하시면 되겠습니다.
그래서 그 방향이 ray에 대해 같은 방향이면 만나지 않는다라고 판정을
하고(혹은 2번 만난다라고...), 다른 방향이면 한번만난다라고 판정을 하는
것입니다.
> 만일, (x, y) 값들이 모두 정수라면, 이 직선의 x, y 값에 0.5를 더해서 계산을
> 하면 될 것 같은데
> (x, y) 값들이 실수 입니다.
>
> 제 방법의 잘못된 점이나, 다른 방법이 있으면 소개 부탁드립니다.
>
그러면, CW, CCW 판별법에 대해서는......
내가 수개월 전에 h.c.l.c에서 자세히 설명을 한 적이 있는데, 나의
뉴스서버에서는 이미 지워지고 없더군요.
3개월 까지 밖에 보관을 않하다니......
서버 관리자님들...... 연일 수고하시는 줄은 잘 알고 있습니다만, 아무래도
3개월은 너무 짧은 것 같습니다. 신경좀 써 주십시오.
dejanews등에서 찾아보십시오.
다각형의 signed area를 구하는 방법입니다.
다각형의 면적만 eps*eps보다 충분히 크다면 전혀 깨질 염려가 없는
robust하고 효율적인 방법입니다.
>
> ps.
> 이런 류의 질문을 여기에 하는 것이 맞는지 잘 모르겠습니다.
> 잘못되었다면, 알려주시고 다른 NG 를 알려주시기 바랍니다.
현재까지는 geometric algorithm을 논하는 NG가 없으니 이곳이 그래도
가장......
--
Gyujin Han <mailto:gyu...@cad.snu.ac.kr> UNITEL:은수아빠
This message is made of 100% recycled electrons.
C에 대한 초보질문들과 고수들의 대답이 정리된 곳 :
<http://www.eskimo.com/~scs/C-faq/top.html>
김정희
Gyujin Han <gyu...@cad.snu.ac.kr>이(가) 아래 메시지를
news:371437C2...@cad.snu.ac.kr에 게시하였습니다.
> "김정희" wrote:
> anti-clock??????
> 이런 표현도 사용하나요?
> counter-clockwise, 줄여서 CCW라 하지요......
> 반대는 CW.
anti-clockwise 라는 표현은 영국 영어라고 프라임 사전에 나와있네요.
사실은 그냥 생각나는데로 질문하다 보니, anti-clock wise 라는 말을 썼읍니다.
:)
> 그런데, 닫힌 곡선에 대해 ray를 위와 같이 쏘면, 그 시작점을 포함하였을
> 경우에는 항상 짝수개, 포함하지 않았을 경우에는 항상 홀수개가 나오게
> 됩니다. CW, CCW와는 상관 없이 말입니다.
쏘는 방향에 따라 다르지 않습니까?
^ (다각형의 선분)
|
| ------> (ray)
|
|
와 같은 식이라면, 위 선분이 직사각형의 왼쪽에 있는 선분이라면, 시작점을
포함하지 않고
교점이 1개 생기고 오른쪽에 있는 선분이라면 생기지 않을 것 같은데요...
--
김정희
김정희
> 그러면, CW, CCW 판별법에 대해서는......
> 내가 수개월 전에 h.c.l.c에서 자세히 설명을 한 적이 있는데, 나의
> 뉴스서버에서는 이미 지워지고 없더군요.
> 3개월 까지 밖에 보관을 않하다니......
> 서버 관리자님들...... 연일 수고하시는 줄은 잘 알고 있습니다만, 아무래도
> 3개월은 너무 짧은 것 같습니다. 신경좀 써 주십시오.
>
> dejanews등에서 찾아보십시오.
n 각형의 넓이에 대한 포스팅이 98년 8월 8일 시작되었더군요..
그런데, deja-news 에서 한규진님의 99 년도 이전의 article 이 전혀 없더군요.
혹시 e-mail 아이디를 바꾸셨나요? 99년 부터..
찾을 수 있는 방법이나, 아니면 다시한번 설명을 좀 부탁드리고 싶은데..
--
김정희
Gyujin Han
"김정희" wrote:
>
> Gyujin Han <gyu...@cad.snu.ac.kr>이(가) 아래 메시지를
> news:371437C2...@cad.snu.ac.kr에 게시하였습니다.
> > "김정희" wrote:
> > anti-clock??????
> > 이런 표현도 사용하나요?
> > counter-clockwise, 줄여서 CCW라 하지요......
> > 반대는 CW.
>
> anti-clockwise 라는 표현은 영국 영어라고 프라임 사전에 나와있네요.
> 사실은 그냥 생각나는데로 질문하다 보니, anti-clock wise 라는 말을 썼읍니다.
> :)
그렇군요.
내가 보았던 모든 책과 논문에서는 항상 CW, CCW라고 쓰길래......
>
> > 그런데, 닫힌 곡선에 대해 ray를 위와 같이 쏘면, 그 시작점을 포함하였을
> > 경우에는 항상 짝수개, 포함하지 않았을 경우에는 항상 홀수개가 나오게
> > 됩니다. CW, CCW와는 상관 없이 말입니다.
>
> 쏘는 방향에 따라 다르지 않습니까?
>
> ^ (다각형의 선분)
> |
> | ------> (ray)
> |
> |
>
> 와 같은 식이라면, 위 선분이 직사각형의 왼쪽에 있는 선분이라면, 시작점을
> 포함하지 않고
> 교점이 1개 생기고 오른쪽에 있는 선분이라면 생기지 않을 것 같은데요...
>
간단하게 사각형만 그려놓고 생각해 보세요.
Gyujin Han
"김정희" wrote:
>
> Gyujin Han <gyu...@cad.snu.ac.kr>이(가) 아래 메시지를
> news:371437C2...@cad.snu.ac.kr에 게시하였습니다.
>
> > 그러면, CW, CCW 판별법에 대해서는......
> > 내가 수개월 전에 h.c.l.c에서 자세히 설명을 한 적이 있는데, 나의
> > 뉴스서버에서는 이미 지워지고 없더군요.
> > 3개월 까지 밖에 보관을 않하다니......
> > 서버 관리자님들...... 연일 수고하시는 줄은 잘 알고 있습니다만, 아무래도
> > 3개월은 너무 짧은 것 같습니다. 신경좀 써 주십시오.
> >
> > dejanews등에서 찾아보십시오.
>
> n 각형의 넓이에 대한 포스팅이 98년 8월 8일 시작되었더군요..
> 그런데, deja-news 에서 한규진님의 99 년도 이전의 article 이 전혀 없더군요.
> 혹시 e-mail 아이디를 바꾸셨나요? 99년 부터..
>
> 찾을 수 있는 방법이나, 아니면 다시한번 설명을 좀 부탁드리고 싶은데..
>
나의 Sent folder에서 건졌습니다. ^_^
1998년 8월 10일 이로군요......
[인용시작]
그럼 지금부터 다각형 면적문제로 들어가서...
먼저 삼각형(OPR)의 signed-area부터 정의하면,
점 O가 고정되고, P, R이 순서를 가진다고 할 때, 3차원 벡터 O->P, O->R을
각각 p, q라 하면, p, q의 cross product에 1/2을 곱하면 그 절대값은
삼각형의 면적과 같게 되지요.
이때, 이 외적의 x, y 성분은 모두 영(0)이므로, (1/2 p X q)의 z성분을
고정점 O와 순서쌍 (P,Q)의 signed-area라 합시다.
그러면 다각형의 면적은 임의의 고정점 O에 대해 각변의 꼭지점으로
이루어지는 signed-area를 모두 구해 합하면 됩니다. (이 때 합이 양수이면
그 다각형은 반시계 방향, 음수이면 시계방향이지요. 이건 덤입니다.) 그림을
한번 그려 보세요.
임의의 O에 대해 성립하므로, O를 0(원점)으로 잡으면, p=P, q=Q가
되겠네요......
그럼... 여기가 h.c.l.c이니까 설라무네...
typedef Point { double x; double y; } Point;
double PolygonSignedArea (Point *VertexList, int n)
{
int i;
Point *Prev;
double Area2 = 0.0;
Prev = &VertexList[n-1];
for (i=0; i<n; i++)
{
Area2 += VertexList[i].x * Prev->y - VertexList[i].y * Prev->x;
Prev = &VertexList[i];
}
return Area2 / 2.0;
}
너무 간단하나요? 알고리즘을 설명하느니 그냥 코드를 쓰는게 빠르네요...
;-)
[인용 끝]
김정희
> typedef Point { double x; double y; } Point;
> double PolygonSignedArea (Point *VertexList, int n)
> {
> int i;
> Point *Prev;
> double Area2 = 0.0;
>
> Prev = &VertexList[n-1];
> for (i=0; i<n; i++)
> {
> Area2 += VertexList[i].x * Prev->y - VertexList[i].y * Prev->x;
> Prev = &VertexList[i];
> }
> return Area2 / 2.0;
> }
고맙습니다.
정말 깔끔한 답이군요...
그런데, 이 방법은 볼록 다각형이 아니라도 적용이 되는 것입니까?
그리고 위의 스레드에서 제 생각의 어느 부분이 틀렸는지 조금만 자세히 설명
부탁드리겠습니다.
--
김정희
Gyujin Han
Gyujin Han wrote:
>
> "김정희" wrote:
> >
> > > 그런데, 닫힌 곡선에 대해 ray를 위와 같이 쏘면, 그 시작점을 포함하였을
> > > 경우에는 항상 짝수개, 포함하지 않았을 경우에는 항상 홀수개가 나오게
> > > 됩니다. CW, CCW와는 상관 없이 말입니다.
> >
> > 쏘는 방향에 따라 다르지 않습니까?
> >
> > ^ (다각형의 선분)
> > |
> > | ------> (ray)
> > |
> > |
> >
> > 와 같은 식이라면, 위 선분이 직사각형의 왼쪽에 있는 선분이라면, 시작점을
> > 포함하지 않고
> > 교점이 1개 생기고 오른쪽에 있는 선분이라면 생기지 않을 것 같은데요...
> >
>
> 간단하게 사각형만 그려놓고 생각해 보세요.
>
음......
다시 생각해 보니, 이 방법으로도 CW, CCW를 판별할 수는 있겠네요.
박종대
> 그런데, 이 방법은 볼록 다각형이 아니라도 적용이 되는 것입니까?
예. simple polygon이면(즉, 변끼리 서로 겹치있지 않은 다각형이면) 동작합니다.
--
박종대
-- ' C-language Edition
#define cdpark /* KAIST, CSDept, Theory of Computation Lab. */
#include <signature.h> /* the Hitchhiker's Guide to the Internet?? */
박종대
더 간단히, "가장 왼 쪽에 있는 직선"이 올라가는 방향인지, 내려가는 방향인지만
알면 되지 않을까요?
조금만 생각해보면 간단히 구할 수 있을겁니다.
물론 구현하자면 tie breaking도 고려해야 하겠지만...
김정희
news:7f1vd6$vc6$3...@green.kreonet.re.kr에 게시하였습니다.
> 더 간단히, "가장 왼 쪽에 있는 직선"이 올라가는 방향인지, 내려가는
방향인지만
> 알면 되지 않을까요?
그렇군요.
> 물론 구현하자면 tie breaking도 고려해야 하겠지만...
tie breaking 이 어떤 것인지요?
--
김정희
박종대
> 그렇군요.
가장 왼쪽에 있는 직선을 어떻게 정의해야 하느냐죠.
가장 왼쪽 점을 포함하는 직선일텐데...
가장 왼쪽 점이 여럿 있다면 그 중에서 가장 밑 또는 위의 점을 골라야겠죠?
또 이 점에 인접한 선분 둘 중에 어느 쪽을 골라야 할지도...
(이 두 직선을 다 봐야 맞겠죠.)
말로는 쉽지만 code로 짜자면... (bug 없다는 걸 확신할 수 있는 code를...)
확실한 건 이 가장 왼쪽점의 왼쪽으로 반직선을 그었을 때는 어떤 선분과도
만나지 않는다는겁니다.
이 사실은 아니 이 부분이 CCW 부분인지 CW부분인지 신경쓰는건 한참 쉬워지겠죠.
Gyujin Han
ray쏘는 방법으로 CW, CCW를 판별할 수 있는지에 대해 조금 자세히
설명하자면......
나의 착각은 ray의 방향을 김정희님이 고정하였다는 사실을 간과한 것으로
부터 비롯되었읍니다.
그냥 "90도 회전한 방향으로"라고 표현하였지만, 그것이 반시계 방향으로를
의미한 것이라면 ray의 방향은 그 선분의 진행방향을 보고 있을 때, 왼쪽이
되지요. 여기에서 ray와 시작직선과의 교점을 count에서 뺀다면, 그것은 그
선분에서 진행방향을 기준으로 왼쪽으로 epsilon 만큼 떨어진 점에서
시작한다는 뜻이 되지요. 이 점이 다각형의 내부이냐, 외부이냐를 판단하는
문제로 볼 수 있습니다.
선분의 진행방향으로 보아 그 왼쪽이 내부이면 CCW, 오른쪽이 내부이면
CW입니다.
"박종대" wrote:
>
> > tie breaking 이 어떤 것인지요?
>
> 가장 왼쪽에 있는 직선을 어떻게 정의해야 하느냐죠.
> 가장 왼쪽 점을 포함하는 직선일텐데...
> 가장 왼쪽 점이 여럿 있다면 그 중에서 가장 밑 또는 위의 점을 골라야겠죠?
> 또 이 점에 인접한 선분 둘 중에 어느 쪽을 골라야 할지도...
> (이 두 직선을 다 봐야 맞겠죠.)
예, 쉬운 일은 아니지요.
특히 그 점이 구식 깡통따개 처럼 생겼다면 말입니다.
그려보자면......
|\
잘 안되는데 오른쪽 점으로 얘기합시다.
/|
요거 비슷하게 생겨먹었다면 인접 선분을 아무거나 고르다간 큰일나지요.
> 말로는 쉽지만 code로 짜자면... (bug 없다는 걸 확신할 수 있는 code를...)
>
> 확실한 건 이 가장 왼쪽점의 왼쪽으로 반직선을 그었을 때는 어떤 선분과도
> 만나지 않는다는겁니다.
>
> 이 사실은 아니 이 부분이 CCW 부분인지 CW부분인지 신경쓰는건 한참 쉬워지겠죠.
>
조금 확장하면, vertex들로 이루어지는 point set의 convex hull과 겹치는
선분의 방향이 그 다각형의 방향입니다.
물론 simple polygon일 때의 얘기지요.
simple polygon이 아닐 때는 CW, CCW 라는 것이 의미가 없어지겠지요.
그런데 어차피 모두가 "빅 오 오브 엔"인데, signed area보다 간단한 계산이
있을까요?
더군다나 골치아픈 if도 하나 없고요......
다각형의 면적이 eps*eps 보다 충분히 크고, 꼭지점들이 원점에서 너무
멀지만 않다면 실패할 염려가 전혀 없는데......
실수한번 하고 나니 횡수가 길어지네요...... ;-)
박종대
> 조금 확장하면, vertex들로 이루어지는 point set의 convex hull과 겹치는
> 선분의 방향이 그 다각형의 방향입니다.
convex hull과 겹치는 선분이 없는 다각형도 많습니다.
(가장 쉬운 예는... 별모양(☆))
> simple polygon이 아닐 때는 CW, CCW 라는 것이 의미가 없어지겠지요.
simple polygon인지 아닌지는 어떻게 판단할까요?
가장 쉬운 방법: 겹치는 선분이 있는지 검사한다.
> 그런데 어차피 모두가 "빅 오 오브 엔"인데, signed area보다 간단한 계산이
> 있을까요?
signed area는 실수 연산이 있고, underflow/overflow나 round off error의
위험성이 있습니다. (기하 관련 알고리즘에서 아주 조심해야죠..)
하지만 어떤 ray를 기준으로 하는 판별법은 복잡하긴 하지만, 모든 예외 경우를
자~알 처리한다면 아무 문제 없습니다. :)
Gyujin Han
"박종대" wrote:
>
> Gyujin Han <gyu...@cad.snu.ac.kr> wrote:
> > 조금 확장하면, vertex들로 이루어지는 point set의 convex hull과 겹치는
> > 선분의 방향이 그 다각형의 방향입니다.
>
> convex hull과 겹치는 선분이 없는 다각형도 많습니다.
> (가장 쉬운 예는... 별모양(☆))
아이고......
"과 겹치는 선분"을 빼어야겠습니다.
>
> > simple polygon이 아닐 때는 CW, CCW 라는 것이 의미가 없어지겠지요.
>
> simple polygon인지 아닌지는 어떻게 판단할까요?
> 가장 쉬운 방법: 겹치는 선분이 있는지 검사한다.
Computational Geometry의 고전적인 문제이지요.
O(NlogN)으로 알고있습니다만......
>
> > 그런데 어차피 모두가 "빅 오 오브 엔"인데, signed area보다 간단한 계산이
> > 있을까요?
>
> signed area는 실수 연산이 있고, underflow/overflow나 round off error의
> 위험성이 있습니다. (기하 관련 알고리즘에서 아주 조심해야죠..)
앞엤글에 분명히
"다각형의 면적이 eps*eps 보다 충분히 크고, 꼭지점들이 원점에서 너무
멀지만 않다면"
이란 표현을 썼는데......
(너무 기하학적으로 얘기했나? ;-)
실수연산이라......
int의 도메인으로 각 좌표를 매핑해서 정수연산만 해도 원만큼 정확히는
판별이 되겠지요? 이득이 오버헤드를 감안하고도 충분히 큰지는 또다른
문제이지만......
그런데 실수로 정의된 꼭지점 좌표로 부터 실수연산 없이 뭘 알아낼 수
있습니까?
꼭지점 좌표가 정수형에 저장되었다면 물론 signed area 방법에서도
실수연산은 필요가 없겠지요. overflow 등에 대한 고려가 보다 강화되어야
하겠지만 말입니다.
>
> 하지만 어떤 ray를 기준으로 하는 판별법은 복잡하긴 하지만, 모든 예외 경우를
> 자~알 처리한다면 아무 문제 없습니다. :)
>
이 문제에 대해서는 관점이 나와는 조금 다르시군요.
robustness의 문제인데......
첫째, 버그가 이 **복잡**과 **예외경우**라는 환경을 무척이나 좋아한다는
것입니다. 주요 서식지입니다.
둘째, **모든**이라는 개념인데, signed area의 경우 위에서 언급한 두가지를
생각하고서 "아 이것이 모두이다"라는 느낌이 드는데 반해서, ray의 경우에는
앞서 꼭지점이나 선분이 ray와 겹치는 예외 경우를 언급을 하였지만 "이들이
모두이다"라는 확신이 서지 않는다는 것입니다.
마지막으로, "자알 처리"의 문제인데 signed area의 경우에는,
double area = PolygonSignedArea(vertices, n);
orientation = fabs(area) < epsilon_squared ? SHRUNK_TO_A_POINT : area <
0.0 ? CW : CCW;
나, 필요하다면 for loop 안에서,
if (Area2 > some_treshold)
return I_THINK_ITS_TOO_BIG_YOUD_BETTER_USE_SOME_OTHER_METHOD
(VertexList, n);
와 같이 충분히 피해 갈 수 있지만 (왜냐, 명확히 보이므로),
ray의 경우에는 **처리** 방법이 이처럼 명확하지는 않다는 것이지요.
ray 방법의 robustness를 논하기 위해서는 **모든**과 **처리**에 대해
의견을 주셔야 할 것 같습니다.
나는 performance를 조금 떼어 주더라도, robustness를 삽니다.
Gyujin Han
Gyujin Han wrote:
>
> 나, 필요하다면 for loop 안에서,
>
> if (Area2 > some_treshold)
> return I_THINK_ITS_TOO_BIG_YOUD_BETTER_USE_SOME_OTHER_METHOD
> (VertexList, n);
>
이 부분은 오버플로우를 피해가기 위해 Area2를 모니터하는 방법을
설명하였는데, 틀렸군요......
if (Area2 > some_treshold || Area2 < - some_treshold)
가 되어야 겠지요. 오버플로우가 걱정이 된다면......
그러나 나는 그런 걱정을 하지 않으렵니다.
Area2의 geometric interpretation은 면적인데, 그 절대값의 최대치는 원점과
각 꼭지점을 잇는 직선들, 그리고 다각형의 변들로써 이루어지는 envolrope의
면적(의 2배)을 넘지 못합니다.
이것이 double 형의 오버플로우를 야기시키는 사태는 맨정신으로는 도저히
생길 수 없다고 보기 때문이지요.
만약에 그러한 사태가 발생한다면, 다각형을 생성하고 조작하는 다른부분의
코드를 검토하는 것이 순서이겠지요......
그나 저나, 논의가 수학의 범주에서 점점 멀어지는 듯 하는군요......
(죄송)
김정희
<인용시작>
일단 부호 있는 넓이(signed area)를 계산하면 (Subject 2.01), 이 면적이
양수 일때 회전 방향은 반시계 방향이다.
조금 더 빠른 방법은 면적을 계산할 필요가 없다는 점에 기인한다. 가장
아래에 있는 vertex 를 찾은 뒤 (만일 가장 아래에 있는 점이 한 개가
아니라면, 그 중 가장 오른쪽에 있는 점을 선택), 그 점의 앞, 뒤에 있는
선분 벡터의 외적을 구한다. 두 방법들은 n개의 점에 대해, O(n)이지만,
단지 오른쪽 모서리의 외적 한 번으로 충분할 때, 앞의 방법은 전체 면적
을 구하기 위해 낭비를 하는 것으로 보인다. 이에 대한 코드는
ftp://grendel.csc.smith.edu/pub/code/polyorient.C (2K)에서 얻을 수
있다.
좌측 최하단의 점(또는 다른 극점)이 선택되는 이유는 이 점에서의 내각
이 당연히 볼록하기 때문이며, pi 보다 작기 때문이다 (최하단의 점이 여
러개 존재할 지라도).
<인용 끝>
굉장히 간단하고 깔끔한 방법인 것 같습니다.
참, 제가 comp.algorithm.graphics 의 FAQ 를 주말에 거의 번역을 다 했는데,
요걸 어디에 포스팅 하면 될까요? 할 장소가 없다면, 제 홈페이지에나 올릴
계획입니다.
물론 만드신 분에게는 번역하겠다고 메일을 띄웠고, 허락을 기다리는 중입니다.
--
김정희
Gyujin Han
대단히 수고하셨습니다.
앞으로 이 문제가 또 제기되면 이제는 "faq를 보라"라는 얘기만 해주면
되겠군요.
위의 방법은 simple polygon을 가정 하더라도, 그 점에 연결된 선분들의
길이가 매우 짧거나, 사잇각이 매우 작을 경우, pi에 근접하는 경우, zero에
매우 근접하는 결과가 나오겠군요.
이와 같이 선택된 점 근처의 local property 때문에 global property인
다각형의 방향성이 애매해 질 수 있다는 점만 충분히 고려한다면, 훌륭한
방법이 되겠습니다.
Kim Sung-bom
>
> 참, 제가 comp.algorithm.graphics 의 FAQ 를 주말에 거의 번역을 다 했는데,
> 요걸 어디에 포스팅 하면 될까요? 할 장소가 없다면, 제 홈페이지에나 올릴
> 계획입니다.
> 물론 만드신 분에게는 번역하겠다고 메일을 띄웠고, 허락을 기다리는 중입니다.
이곳에든, 김정희님 홈페이지에든, 올려 주시면 많은 도움이 될 것 같네요.
(한글 뉴스그룹에 알고리즘 관련 그룹이 따로 없다는 것이 아쉽지만..)
좋은 일을 해 주신 김정희님께 격려와 감사의 말씀을 미리 드리면서.. :)
--
김승범