현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

다각형의 좌표를 주고 특정 x,y좌표값을 알때.. 다각형에 x,y값

rokmn3309의 이미지
글쓴이: rokmn3309 / 작성시간: 토, 2003/03/22 - 3:58오전

알고리즘적인걸. 여기에 올려도 될까 모르겠습니다..

오늘 오후내내 생각하다가. 답답해서 올립니다.
특정 다각형 (오각형 ,육각형 ... 그 사이의 특이한 형태까지)의 좌표값을 주고
시계 반대방향이나 시계 방향으로 회전하면서 값을 넣어주고
특정 위치의 x,y좌표값을 가지고 이 좌표값이 그 다각형에 포함유무를
체크 할려면 어떻게 해야할지..
많은 답글 부탁드립니다...

Forums: 
프로그래밍 QnA
keizie의 이미지

글쓴이: keizie / 작성시간: 토, 2003/03/22 - 4:34오전

어떤 다각형이든 결국 삼각형으로 쪼개서 검사한다고 들었는데
간단한 행렬 연산 정도로 해결되는 것으로 압니다.
(말은 쉽게. -_-a)

meteors의 이미지

글쓴이: meteors / 작성시간: 토, 2003/03/22 - 5:56오전

혼자 고민하지 마시고 책을 보세요.
Computational Geometry에 관련된 책에 나와 있습니다.

3각형, 4각형, 5각형 같은 볼록한 꼭지점만 있는 경우라면 반평면(half-space)계산으로 쉽게 계산할 수 있습니다. 한 변을 나타내는 직선의 방정식을 구해서 주어진 점이 어떤 방향에 있는지를 검사하고(직선이 평면을 2로 나누니까 한쪽에 있겠죠.) 모든 직선에 대해 내부 방향에 있다면(다각형 각 꼭지점의 순서가 시계방향인지 반시계방향인지에 달려 있겠죠.) 점은 안에 있는 것일겁니다.

하지만.. 오목한 꼭지점이 있는 경우(별 모양) 볼록한 꼭지점이 있는 다각형으로 나누어야 합니다. 그러면 위에 설명한 방법으로 계산이 가능합니다.
나누는 방법은 너무 기니 책을 참조하시길..

taeyeung의 이미지

글쓴이: taeyeung / 작성시간: 토, 2003/03/22 - 8:35오전

알고자 하는 점과 다각형 사이에 충분히 떨어진 임의의 한 점을 잡습니다.

보통은 알고자 하는 점이 (4, 5)이고 다각형을 포함하는 영역이

(0, 0) ~ (20, 20)이라고 한다면 (4, 200)정도의 점을 하나 지정합니다.

그리고 나서 (4,5) ~ (4, 200)의 직선과 다각형을 구성하는 직선들과의

교차점의 갯수를 구합니다. 만약 홀수이면 (4,5)는 다각형의 내부이고

짝수이면 (4, 5)는 다각형의 외부에 있습니다.

댓글 달기

텍스트 포맷에 대한 자세한 정보

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.