직선과 선분 - 알고리즘카

선분은 양 끝점 두 개로 지정할 수 있습니다. 순서는 상관없습니다. 선분은 벡터와 달리 방향이 없기 때문입니다.

struct segment {
    r p, q;
};

계산 기하학에서는 기하학적 대상들의 상대적 위치를 판별할 수 있어야 하는 경우가 많습니다. 예를 들어, 선분들이 교차하는지 확인하는 것입니다. 여기에는 내적과 외적, 그리고 간단한 경우 분석이 도움이 됩니다:

곱의 관점에서 보면, 예를 들어 “선분의 양 끝점이 다른 선분을 기준으로 서로 반대편에 놓인다"는 조건은 다음과 같이 쓸 수 있습니다:

$$ [(M_1 - P_1) \times (P_2 - P_1)] \cdot [(M_2 - P_1) \times (P_2 - P_1)] < 0 $$

$(M_1, M_2)$를 분리 선분으로 하는 조건을 하나 더 추가로 적으면, 두 선분이 교차할 때 그리고 그때에만 참이 되는, 쉽게 계산할 수 있는 술어를 얻게 됩니다.

#반직선과 직선

반직선은 한쪽 방향으로 무한한 선분입니다. 반직선은 한 점과 함께 명시적인 방향 벡터를 저장하거나, 반직선 위의 다른 아무 점을 저장하는 방식으로 표현할 수 있습니다.

직선의 경우는 조금 더 복잡합니다. 직선을 저장하는 데에는 쓸 만한 방법이 무려 4가지나 있습니다:

일반 방정식으로: $A \cdot x + B \cdot y + C = 0$.
두 점으로.
한 점과 방향 벡터(임의의 것)로: $\vec{r} = \vec{a}t + \vec{b}$.
점과 법선 벡터(임의의 것)로.

또한 학교에서처럼 $y = kx + b$ 형태의 방정식으로 저장하는 것이 편리할 때도 있지만, 이 경우 수직인 직선에 대해서는 별도의 땜질 처리를 해야 합니다.

입력에서는 직선이 한 가지 형태로 주어지는 경우가 많지만, 다른 형태로 다루는 편이 더 편리할 때가 많습니다. 주요 변환은 다음과 같이 구현합니다:

$2 \rightarrow 1$: 방정식 2개와 미지수 3개로 이루어진 연립방정식의 해를 아무것이나 하나 구하면 충분합니다.
$1 \rightarrow 3$: 직선이 방정식으로 주어지면 벡터 $\overline{(-B; A)}$는 직선의 방향 벡터입니다(직선에는 두 개의 “방향"이 있다는 점을 기억하는 것이 중요합니다).
$1 \rightarrow 4$: 직선이 방정식으로 주어지면 벡터 $\overline{(A; B)}$는 직선의 법선 벡터입니다(직선에는 두 개의 «법선 방향»이 있다는 점을 기억하는 것이 중요합니다).
$4,3 \rightarrow 1$: 앞의 항목들에서 적절한 $A$와 $B$를 이미 알고 있으므로, 미지수 1개에 대한 방정식 1개로 이루어진 연립방정식을 풀면 됩니다.
$1 \rightarrow 2$: 직선 위의 아무 두 점이나 고르면 충분합니다. 예를 들면 다음과 같습니다.

// даны A, B, C (A^2 + B^2 != 0)
r a, b;
if (eq(A, 0)) // если это горизонтальная прямая
    a = {0, -C/B}, b = {1, -C/B);
else
    a = {-C/A, 0}, b = {-(C+B)/A, 1);

#검사

방법 2-4의 경우 모든 검사는 선분의 경우와 거의 같습니다. 사실 기하 문제에서는 «bounding box», 즉 경계가 매우 멀리 떨어진 정사각형을 도입할 수 있는 경우가 많으며, 그 바깥에 있는 모든 점은 «무한대»로 간주합니다. 그러면 무한한 직선과 반직선을 이 무한한 경계에 닿는 선분으로 바꾸어, 모든 검사를 일반 선분과 같은 방식으로 수행할 수 있습니다.

공식으로 주어진 직선의 경우에는 사정이 완전히 다릅니다.

#점과 직선 사이의 거리

직선이 $Ax + By + C = 0$ 꼴의 방정식으로 주어진다면, 반평면도 같은 형태의 부등식으로 나타낼 수 있다는 점에 주목합시다. 이를 이용하면 점이 직선의 어느 쪽에 있는지 바로 확인할 수 있습니다.

이 직선의 법선 벡터는 좌표 $(A, B)$를 가집니다. 법선 벡터는 직선에 수직이며, 반평면 $Ax + By + C \geq 0$의 경우에는 반평면 자체가 있는 쪽을 가리킵니다.

점 $(x_0, y_0)$에서 직선 $Ax + By + C = 0$까지의 거리를 구하려면 다음 공식을 사용할 수 있습니다:

$$ d = \frac{|Ax_0+By_0+C|}{\sqrt{A^2+B^2}} $$

이 공식은 점 벡터와 정규화된($\frac{1}{\sqrt{A^2+B^2}}$) 법선 벡터의 내적으로 생각할 수 있으며, 이는 기하학적으로 점을 법선 벡터에 정사영한 것과 같습니다.

반면 직선이 두 점으로 주어진 경우에는 삼각형의 넓이 공식에서 높이를 구할 수 있습니다:

$$ A = \frac{1}{2} bh \implies h = \frac{2A}{b} $$ 그리고 이 높이를 다음과 같이 계산할 수 있습니다: $$ \rho(P, L(A, B)) = \frac{|\overrightarrow{PA} \times \overrightarrow{PB}|}{|\overrightarrow{AB}|} $$

분자에 외적이 있다는 점에 주목하십시오. 외적의 절댓값이 삼각형 $\angle PAB$ 넓이의 두 배와 같다는 사실을 이용했습니다,

#직선의 교점

두 직선의 교점을 찾는 것은 두 직선의 방정식이 나타내는 조건을 모두 만족하는 점을 찾는 것과 같습니다:

$$ \begin{cases} A_1 x + B_1 y + C_1 = 0 \\ A_2 x + B_2 y + C_2 = 0 \end{cases} $$ 두 방정식에서 각각 $x$를 나타낸 뒤 서로 같다고 놓으면 다음을 얻습니다 $$ \begin{cases} -x = \frac{B_1 y + C_1}{A_1} \\ -x = \frac{B_2 y + C_2}{A_2} \end{cases} \implies \frac{B_1 y + C_1}{A_1} = \frac{B_2 y + C_2}{A_2} \implies y = - \frac{A_1 C_2 - A_2 C_1}{A_1 B_2 - A_2 B_1} $$

마찬가지로, $x = \frac{B_1 C_2 - B_2 C_1}{A_1 B_2 - A_2 B_1}$입니다(부호에 주의하십시오).

분모가 0이 될 수 있다는 점에 유의하십시오. 이는 법선 벡터의 외적이 0이라는 뜻이며, 따라서 두 직선은 평행합니다. 이 경우 교점이 없거나, 두 직선이 일치하는 경우에는 교점이 무한히 많습니다. 이 경우는 별도로 처리해야 합니다.

구성적 접근 방식의 몇 가지 예를 살펴보겠습니다.

#점의 직선 위로의 사영

점 $P$를 직선 $L$에 사영하려면, 길이가 $\rho(P, L)$이 되도록 조정하고 점에서 직선을 향하도록 한 직선의 법선 벡터를 점에 더하면 충분합니다. 법선 벡터는 서로 다른 (그러나 서로 반대인!) 두 방향을 가리킬 수 있으므로, 두 경우를 모두 시도해 보고 얻어진 점에서 직선까지의 거리가 더 작은 쪽을 택하면 충분합니다.

#직선에 대한 대칭

점 $(x_0, y_0)$를 주어진 직선 $ax+by+c=0$에 대해 대칭으로 반사해야 한다고 합시다.

순전히 교육적인 목적으로, 이 문제를 수학자처럼 풀어 봅시다. 앞으로 다시는 이렇게 하지 않기 위해서입니다.

$$ \Pr_a b = \frac{a \cdot b}{|a|} \frac{a}{|a|} = \frac{|a| |b| \cos \alpha}{|a|} \frac{a}{|a|} = |b| \cos \alpha \frac{a}{|a|} $$

기하학적 의미는 길이에 방향 단위 벡터를 곱한 것입니다.

우리는 이 공식들을 좌표별로 전개하여 완성된 답을 제시하고 싶지 않습니다. 그 답이 번거로워질 것임을 알고 있기 때문입니다. 모든 것을 부분별로 계산하는 것은 아깝지 않습니다. 여기서는 최적화에 신경 쓸 이유가 없습니다. 또한 모든 것을 부분별로 처리하고 싶은 이유는 그렇게 하면 알고리즘의 논리가 더 명확해지고, 그 결과 디버깅하기도 더 쉬워지기 때문입니다.

// прямая r = at + b, точка c
r pr(r a, r b, r c) {
    c -= b; // пусть c и a выходят из одной точки
    return b + (a * b / len(a) / len(a)) * a;
}

r reflect(r a, r b, r c) {
    return c + 2*(pr(a, b, c)-c);
}