📐

삼각형 내 점이 있는지 구별하는 법

간단소개

삼각형 내에 점이 있는지 구별하는 공식을 검색하는 과정부터, 간단 이해와 적용까지.

팔만코딩경 컨트리뷰터

ContributorNotionAccount

주제 / 분류

C++

수학

Scrap

태그

9 more properties

삼각형 내에 점이 있는지 구별하는 공식을 검색하는 과정부터, 이해와 적용까지의 내용을 담았다.

검색과정

음… 뭔 소리인지 하나도 모르겠다.

구글에 검색해 봤지만, 도무지 뭔 소리인지 못 알아들었다. 그러다 한 stackoverflow 글을 보았는데, 거기에 이런 코드가 있는 것이다.

이걸 따라 했고, 동작도 제대로 되는 것을 확인했는데, 도무지 저게 어떻게 돌아가는지 이해가 되지 않았다. 그래서 공식을 찾아보기 시작했다.

공식

위의 그림을 간단히 해석하자면, point p를 기준으로, 삼각형을 세 가지 영역으로 나눈다. 그리고 u, w, v의 면적을 구하고, 이 세 면적의 합이 삼각형 면적과 동일하다면, p는 삼각형 내부의 점이라는 소리다.

만약 point p가 삼각형 외부에 있다면, 세 면적의 합이 삼각형보다 크기에 p는 삼각형 외부의 점이라는 뜻이다. 혹 이 글이 이해가 안 간다면 이 영상을 참고하라.

Check if a point lies inside a triangle

This video explains a very tricky yet simple interview question based on basic geometry which is to determine if a given point lies inside a triangle, on a triangle or outside a triangle. This is frequently asked in interviews just to check the basics of a candidate. I hope you will enjoy this as much as i enjoyed creating the video. CODE LINK is present in the description below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :) CODE LINK: https://gist.github.com/SuryaPratapK/d41cbf8d6d31b7e4f0fd6cb61316a7df

https://www.youtube.com/watch?v=qObJQesvZUU

글을 살펴보면 area of ABC라고 해서 삼각형의 면적을 구하는 공식이 나온다. 만약

A = (x1, y1)

B = (x2, y2)

C = (x3, y3)

라고 가정했을 때, 공식은 아래와 같다.

area. of ABC = (x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)) / 2

A = (2, 8)

B = (8, 3)

C = (2,3)

P = (4, 6)

이라고 가정했을 때 삼각형의 면적을 구해보자.

[2(3-3)+8(3-8)+2(8-3)]/2\\ = [2(0)+8(-5)+2(5)]/2\\ = (0-40+10)/2\\ = (|30|)/2\\ = 15

그럼 위 공식을 사용해서

△ABC == △APB + △APC + △BPC

공식을 만족시키면

P

는 삼각형 내부의 점이라는 것을 알 수 있다. 그런데 이 방식은 여전히 아래의 공식과 다르다.

((x1-x3)(y2-y3)-(x2-x3)(x1-y3))/2

최대한 이해해보려 했지만, 이해할 수 없어 stackoverflow 페이지만 계속 보다 누가 이렇게 답변 남긴 것을 보았다. 답변에서 clockwise라는 힌트를 얻어, 무언가 아래와 관련 있지 않을까 하고 추측하고 있다. (누가 아시면 댓글 좀 달아주세요)

stackoverflow 답변에 있는 사진. 위의 공식과 연관이 있는 것 같다.

적용

결국 위 코드를 해석하면 아래와 같다.

Fixed sign(const Point a, const Point b, const Point c) {
  return (a.getXValue() - c.getXValue()) * (b.getYValue() - c.getYValue()) -
         (b.getXValue() - c.getXValue()) * (a.getYValue() - c.getYValue());
}

bool isInside(const Point a, const Point b, const Point c, const Point point) {
  Fixed d1, d2, d3;
  bool is_neg, is_pos;

  d1 = sign(point, a, b);
  d2 = sign(point, b, c);
  d3 = sign(point, c, a);

  is_neg = (d1 < 0) || (d2 < 0) || (d3 < 0); // 값 중 하나라도 음수가 있으면 true
  is_pos = (d1 > 0) || (d2 > 0) || (d3 > 0); // 값 중 하나라도 양수가 있으면 true
  return !(is_neg && is_pos); // 만약 음수, 양수 값이 함께 있는 경우 false
}
C++
복사

위 코드는 면적의 크기를 다 더해서 확인해 보는 것보다 훨씬 간단해서 이 방법을 사용했다. 만약 P가 삼각형 밖에 있을 경우, d1, d2, d3 이 세 개의 값이 음수, 양수가 섞여서 나온다. 삼각형 안에 있다면 전부 음수 또는 양수로 나온다.

피드백에 의하면, sign() 함수가 면적을 구하는 것은 맞는데, 값에 나누기 2를 한 다음 절대값을 붙여줘야 제대로 된 넓이가 나온다. 아니라면 P가 어디에 있든 세 면적의 합이 같다. (잘못된 부분 알려주신 카뎃님 감사합니다!)

여담

더 깊게 알아보고 싶다면 barycentric coordinate system이라는 공식을 참고하기를 바란다. 한국어로 하면 무게중심 좌표라고 한다. 혹 틀리거나 잘못 이해한 부분이 있다면 알려달라.