게임 클라 개발

※ 매개변수로 표현할 수 있는 곡선 (ex. 베지에 곡선)의 경우만 다룸. 관련 글 : 2021.07.11 - [이론] - 곡선(Curve) & 스플라인(Spline) 곡선(Curve) & 스플라인(Spline) 곡선 곡선을 표현하기에 앞서, 두 정점 (A, B) 사이에 있는 점 P를 다음과 같이 표현할 수 있다. 또한 곡선은 t에 대한 방정식(P(t))으로 표현할 수 있다. 베지에 곡선(Bézier Curves) n차 베지에 곡선은 n tsyang.tistory.com 문제 Q ) t에대한 다항식으로 이뤄져 있는 곡선 $q(t)$ 와 곡선 밖의 점 $P$가 있다. 이때 점 $P$와 가장 가까운 곡선 $q(t)$ 위의 점 $X$는 어떻게 구할 수 있을까? 곡선 $q(t)$를 2차원상의 3차 베지에 곡선이..

루트격리(root isolation) 루트 격리는 근이 여러 개인 다항식에서 정해진 개수의 근이 존재하는 구간을 구하는 것이다. (주로 근이 1개인 구간을 구한다.) 이를 이용해서 근 구하기 알고리즘 등을 사용한다. 1. 스트룸 정리 아래에 있는 데카르트 부호 법칙에 기반한 방법이나, 빈센트 정리에 기반한 방법보다는 느리고 덜 효율적이다. 중근을 한 개로 간주한다는 특징이 있어 덜 효율적이지만 꽤 쓰이는 듯. https://tsyang.tistory.com/62 스트룸 정리 (Strum's theorem) 루트 격리 (root isolation) 위 다항식의 실수 근을 구하는 알고리즘을 짜려면 어떻게 해야할까? 뉴턴 방법이나 이분 매칭 등을 써서 그 값을 구할 수 있지만 위와 같이 실근이 2개 이상인 경..

2021.08.13 - [수학] - 스트룸 정리 (Strum's theorem) 스트룸 정리 (Strum's theorem) 루트 격리 (root isolation) 위 다항식의 실수 근을 구하는 알고리즘을 짜려면 어떻게 해야할까? 뉴턴 방법이나 이분 매칭 등을 써서 그 값을 구할 수 있지만 위와 같이 실근이 2개 이상인 경우 모든 tsyang.tistory.com 목표 : 스트룸 정리를 이용하여 다항식의 해 찾기. 다항식 클래스 우선 다항식을 표현할 방법이 필요하여 Polynomial 클래스를 만들었다. Polynomial 클래스는 $a_0x^0 + a_1x^1+a_2x^2+ ... + a_nx^n$ 으로 표현되는 다항식의 각 계수 $(a_0, a_1, ... , a_n)$를 저장한다. 스트룸 정리에 ..

루트 격리 (root isolation) 위 다항식의 실수 근을 구하는 알고리즘을 짜려면 어떻게 해야할까? 뉴턴 방법이나 이분 매칭 등을 써서 그 값을 구할 수 있지만 위와 같이 실근이 2개 이상인 경우 모든 실근을 구하는 방법은 꽤 고민이 된다. 그런데 이때, 만약 위 방정식의 실근이 구간 [-1.5, -1.0] , [-0.5, 0], [1.0, 1.5] 에 하나씩 있다는 정보가 주어진다면? 각 구간에 이분 매칭 혹은 뉴턴 방법을 사용한다면 매우 쉽게 모든 실근을 구할 수 있을 것이다. 이렇게 루트가 하나만 있는 구간을 구하는 것을 루트 격리(root isolation)라고 한다. 루트 격리는 여러 방법이 있는데 그 중 하나가 스트룸 정리이다. 스트룸 정리(Strum's theorem) 스트룸 정리 (..