[완료] 2차원 평면에서 임의의 한 점이 주어진 Polyline 의 왼쪽에 있는지 오른쪽에 있는지 알아내는 법이 있을까요?
글쓴이: kleinstein / 작성시간: 금, 2011/04/08 - 10:56오후
네. 제목 그대로 입니다.
2차원 평면에 임의의 한 점 A가 주어집니다.
그리고 역시 임의의 Polyline이 주어집니다.
이때 이 점 A가, 주어진 Polyline의 왼쪽에 있는지 오른쪽에 있는지 알아내는 법이 있을까요?
단 Polyline의 모양은 임의로 주어질수 있고 다만 서로 겹치지지는 않습니다.
첨부파일 처럼 말이죠..
File attachments:
| 첨부 | 파일 크기 |
|---|---|
 polyline_point.png | 5.27 KB |
Forums:
지금 제시한 예제 그림의 경우에는 왼쪽인지 오른쪽인지
지금 제시한 예제 그림의 경우에는 왼쪽인지 오른쪽인지 모르겠네요
보통은, 확실히 왼쪽에 있는 점을 하나 선택하여 그 점과 주어진 점을 잇는 직선을 만들고, 그렇게 만들어진 직선과 폴리라인이 몇번 만나는지 보면 됩니다. (조르당의 곡선 정리 응용)
짝수번이면 같은쪽, 홀수번이면 반대쪽이죠.
피할 수 있을때 즐겨라! http://melotopia.net/b
왼쪽과 오른쪽이 어떤의미인지는... 잘 이해가 가지 않지만...
하튼.
Polyline의 전체 x좌표 길이의 중심을 기준으로 좌측이냐 우측이냐를 따진다면.
x좌표의 min max 좌표값을 얻은후. 1/2해서 그 값보다 크거나 작을 경우로 따지면 되지 않을까 생각됩니다.
----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
외적을 이용하세요.
주어진 폴리곤의 모든 선분보다 왼쪽에 있으면 왼쪽에 있는 것이죠. 폴리곤의 임이의 점 A와 그 다음 점 B 에, 그리고 주어진 점 C를 3차원으로 보고 (B-A) 외적 C 의 z성분이 0보다 크면 왼쪽에 있는 것 입니다. 아니면 Computational Geometry 라이브러리들을 알아보세요. cgal이 꽤나 좋았던듯 합니다.
애초에 저 polyline을 기준으로 "왼쪽" 이라는
애초에 저 polyline을 기준으로 "왼쪽" 이라는 정의가 어찌 되는지 궁금하군요.
예를 들어 U 자 모양의 polyline 이 있고 점이 그 가운데 있으면 이걸 "왼쪽" 으로 보나요 "오른쪽" 으로 보나요?
그 정의에 따라 갈릴것으로 보입니다만.
Neogeo - Future is Now.
polyline 벡터 기준이지요. 벡터는 방향이
polyline 벡터 기준이지요.
벡터는 방향이 있으니 왼쪽 오른쪽이 생깁니다.
------------------------------
How many legs does a dog have?
원글엔 어디를 봐도 벡터라는 말이 없는데 무슨
원글엔 어디를 봐도 벡터라는 말이 없는데 무슨 기준으로 벡터로 정하는건가요?
점의 순서에 따라 결정되는 걸까요?
뿐만아니라 벡터의 방향에 의해 결정된다고 가정하면,
V . 이런상황에선 . 이 오른쪽인가요 왼쪽인가요?
Neogeo - Future is Now.
컴퓨터에서 공간상의 선은 벡터로 표시합니다.단지
컴퓨터에서 공간상의 선은 벡터로 표시합니다.
단지 그걸 벡터로 보느냐 안보느냐의 차이가 있을 뿐입니다.
종이에 그릴때는 화살표가 없으면 그린 사람조차 어느 방향으로 그렸는지 확인이 힘들지만,
컴퓨터에서 그릴때는 너무나도 명확하게 메모리상에 값이 들어가 있기 때문에 늘 확인이 가능합니다.
컴퓨터에서 어떤 방법으로 선을 그리든, 시작점과 끝점은 필요합니다.
명시적으로 시작점과 끝점을 기록하는게 아니라, 로고처럼 어떠한 프로세스에 의해서 선을 그린다고 하더라도,
결과적으로는 시작점과 끝점을 모두 도출해낼 수 있습니다.
그리는 사람이 방향성을 인식하고 있다면, 오른쪽이나 왼쪽을 구분하는 건 너무나도 쉽습니다.
-----
원래 최초에 물었던 부분을 제가 제대로 보지않았군요.
제대로 보지도 않고 헛소리만 하고 있었네요.
죄송합니다.
polyline의 왼쪽 오른쪽 문제는 알고리즘에서
convex hull 같은 경우에 평가를 하는데, 모든 polyline에 대해서 왼쪽이거나, 모든 polyline에 대해서 오른쪽인 경우에, polyline 안에 있다고 봅니다.
만약 polyline중에서 하나라도 점이 왼쪽과 오른쪽이 상이하게 나온다면, 그냥 밖에 있다고 보지요.
보는 순간 이 문제를 생각했고, 이 문제를 기준으로 별로 생각없이 댓글을 달았네요.
------------------------------
How many legs does a dog have?
생각보다 많은 분들이 관심을 가져주셔서
생각보다 많은 분들이 관심을 가져주셔서 감사합니다.
제 질문이 명확하지 못했군요. 죄송합니다.
왼쪽 오른쪽이라고 표현한것은,
Polyline으로 갈려지는 평면의 두 부분을 말하는 겁니다.
굳이 왼쪽 오른쪽이라고 표현하지 않고 이편, 저편 이렇게 표현하는게 오히려 편할까요?
아무튼..
그래서 제 고민이 많습니다.. 각 선분의 외적이라던지 등등으로 계산을 해보아도..
당연히 Polyline이 임의로 그어질수 있기 때문에, 경우에 따라 Polyline의 모든 선분보다 왼쪽에 있지 않을수도 있습니다..
아무튼.. (겹치지는 않는 임의의) Polyline으로 갈리는 두 부분 중에 어느 쪽에 속하는지 알아낼수 있어야 합니다... 아이디어 없으신가요??
그냥 떠오른 생각이지만
도움이 될런지는 잘 모르겠습니다만 이렇게 생각해 보면 어떨까요 ?
2차원 평면에서 어느 위치에 Polyline이 생겨도 절대적으로 오른쪽일 수 밖에 없는 점, 가장 쉬운 예로 2차원 평면의 가장 오른쪽 가장 아래쪽 좌표, 즉 오른쪽 아래부분의 꼭지점 부분을 기준으로 삼습니다.
임의의 점에서 이 꼭지점을 직선으로 선을 그어놓고 이 직선위에 Polyline과 만나는 점이 있다면, 임의의 점은 Polyline의 왼쪽에, 그렇지 않다면 Polyline의 오른쪽에 있다고 봐도 괜찮치 않을까요 ?
고민이 많아 고민인 애늙은이 입니다.
그건 제 아이디어를 활용하면 됩니다. 자세한 내용은
그건 제 아이디어를 활용하면 됩니다. 자세한 내용은 조르당의 곡선 정리( http://en.wikipedia.org/wiki/Jordan_curve_theorem )를 참고하시면 됩니다.
문제는, polyline이 폐곡선이 아닌데 고려해야 하는 영역 전체를 반으로 자르지 않고, 완전히 안에 포함된 경우입니다.
즉, 엄밀히 말해서, 폴리라인이 폐곡선이 아니면서 폴리라인과 영역의 경계(도화지의 바깥쪽 가장자리) 사이에 교집합이 없는 경우. 예를 들면, 그림에 제시하신 경우가 그런 경우죠. 수학적으로는 이편-저편이 의미가 없습니다. (왜 의미가 없는지 궁금하면 그림판에서 "채우기" 기능으로 색칠해보면 됩니다.)
만약 엄밀하게는 폴리라인이 영역을 반으로 자르지 않지만, 인간이 보기에 왼쪽-오른쪽을 갈라놔야 한다면, 이때는 추가적인 조건이나 방법이 필요합니다. 가장 단순하게는, 양쪽 끝 점으로부터 바깥쪽(?)으로 가는 반직선을 그려서 강제로 영역을 반으로 나누도록 하는 방법이 있겠죠. 이 경우에도, 바깥쪽으로 가는 반직선을 그리는 건 "매우 주의깊게" 생각해야 합니다. 별 희한한 경우가 발생할 수 있기 때문에... 폴리라인을 구성하는 각각의 각들이 예각인 경우와 둔각인 경우를 잘 고려해야겠죠.
피할 수 있을때 즐겨라! http://melotopia.net/b
snowall님께서 제시한 답변이 제일 타당해
snowall님께서 제시한 답변이 제일 타당해 보이는데요?
저 이상의 해결법이 있을 수 있나요?
2차평면이라고 하셨는데
폴리라인으로 두면이 분할될때 어느쪽에 속하는지 아시는게 문제지요?
2차평면의 크기가 주어질때 한쪽 면의 끝점으로 부터 점까지 직선을 긋고 폴리라인과 만나는 횟수를 카운트하면 되겠네요.
Chaos to Cosmos,
Chaos to Chaos,
Cosmos to Cosmos,
Cosmos to Chaos.
이 문제를 여기서도 보게 되네요.
"2차원 평면에서 임의의 한 점이 주어진 Polyline 의 왼쪽에 있는지 오른쪽에 있는지 알아내는 법" 왜 필요할까요?
무엇을 구현 & 서비스하고 싶어서?!
새로운 주소체계때문에?
애초에 문제 정의를 정확하게 하실 필요가
애초에 문제 정의를 정확하게 하실 필요가 있습니다.
지금까지 설명을 미루어 보면,
무한이 아닌 임의의 평면이 있고 그 평면을 반드시 둘로 나누는 겹치지 않는 임의의 polyline 이 있으며 ( 나누어진 면적의 크기는 달라도 무관 ) polyline 상이 아닌 곳에 임의의 한점 P가 있을때, 그 점이 속한 부분이 어디인지 판별 하라 인가요?
영역이 나누어지지 않는 상황에서 polyline 이 vector 같은 방향성도 없는 상황이라면 위에 분 말씀대로 왼쪽 오른쪽 구별이라는거 자체가 불가능할거 같군요.
그런 문제라면, 이미 그래픽스에 fill 문제로 여러번 다루어졌을꺼라고 봅니다. 가장 빠르게 찾는 거라면 다른 이야기지만...
Neogeo - Future is Now.
애초에 문제 정의를 애매하게 한것 같아 너무 죄송스럽습니다..
neogeo 님/ 말씀하신대로.. 제가 애초에 문제 정의를 너무 애매하게 한게 큰 잘못같습니다. 간단한 해답이 있을거라는 생각에서 가볍게 질문을 던졌던건데.. 아무튼.. 많은 분들이 헷갈려하셔서 송구스럽습니다.
"무한이 아닌 임의의 평면이 있고 그 평면을 반드시 둘로 나누는 겹치지 않는 임의의 polyline 이 있으며 ( 나누어진 면적의 크기는 달라도 무관 ) polyline 상이 아닌 곳에 임의의 한점 P가 있을때, 그 점이 속한 부분이 어디인지 판별 하라 인가요?"
네 . 맞습니다.
polyline은 사용자의 마우스 클릭에 의해 한 선분씩 연결되어 만들어지게 되어 있어서 polyline은 2차원 평면상의 벡터들의 모임으로 볼수도 있겠습니다.
아무튼.. 전 이런 경우에 어떻게 하는 것이 가장 좋은 해답인지 여전히 찾고 있습니다.
물론, 임시적인 해결책으로 dingkyu 님의 제안을 사용하긴 했습니다만..
좀더 아름다운? 해결책을 찾고 있습니다.
아름다운 방법인지는 모르겠지만
가로지르는 벡터의 평균을 구하고
임의의 점에 해당하는 좌표를 구해서 벡터 평균의 분산만큼 이동시키면
쉽게 구할수 있지 않을까요 ?
이 방법은 그렇게 했는데 polyline을 넘어가는
이 방법은 그렇게 했는데 polyline을 넘어가는 경우가 발생할 수 있기 때문에 곤란합니다. 만약 polyline이 같은 x값에 대해서 한점만 지나간다면 이 방법도 좋은 방법이지만, 그게 보장되면 그냥 위/아래 판정만 하면 되기 때문에 큰 의미가 없어보이네요
피할 수 있을때 즐겨라! http://melotopia.net/b
아아 그렇군요.
그렇다면 snowall님 께서 말씀하신 방법이 가장 깔끔한 방법 일 것 같은데요 ?
fill을 통한 전수조사 방법도 있겠지만, 이건 좀 아름답지는 않은것 같구요.
dingkyu님의 제안은 polyline과 2번 이상
dingkyu님의 제안은 polyline과 2번 이상 만나는 경우에 대한 판정이 없다는 문제가 있습니다.
만약 특정점과 주어진점을 잇는 선분이 polyline을 2번 건너간다면, 두 점은 같은 영역에 있습니다. 좀 더 엄밀히 말해서, 짝수번 건너가면 같은 영역, 홀수번 건너가면 반대 영역에 있게 됩니다. 그리고 이게 조르당의 곡선정리의 내용이죠.
이것까지 포함하면 제가 제안한 방법이 됩니다. (제가 제안했다기보다는... 그냥 알려드린 방법이죠...)
피할 수 있을때 즐겨라! http://melotopia.net/b
더 이상의 진전은 없는것 같아서..
댓글로 여러가지 방법들을 제안해 주셔서 감사합니다.
아마도... 더 이상의 방법은 나오지 않을듯해서.. 일단 [완료] 말머리를 붙여서 이 글타래는 접을까 합니다.
감사합니다.
댓글 달기