전산 기하학 : 거울에서 회전, 평행 이동 또는 반사 후 삼각형이있는 위치를 찾으십시오.

Question

2 차원에서 삼각형을 형성하는 점 집합이 주어진 작은 대회 문제가 있습니다. 이 삼각형은 임의의 회전을 할 수도 있고 2D 평면에서 임의의 평행 이동을 할 수도 있으며 거울의 반사를받을 수도 있습니다 (). 치수는 그대로 유지됩니다. 그런 다음, 그들은 평면에서 점들을 제공하고, 하나 이상의 기하학 연산을 수행 한 후 삼각형을 형성하는 3 점을 찾아야합니다.

예 :

5 15 
8 5 
20 10 
6 
5 17 
5 20 
20 5 
10 5 
15 20 
15 10 
Output: 
5 17 
10 5 
15 20 

나는 몇 가지 알려진 알고리즘을 적용하기로 내기,하지만 난 어떤 몰라요. 볼록 선체, 스윕 비행기, 삼각 측량 등이 가장 일반적입니다.

팁을 줄 수 있습니까? 코드는 필요 없어요, 제발 밀어주세요!

Answer 1

주어진 삼각형은 세 가지 길이로 정의됩니다. 목록에서 길이가 정확히 구분 된 3 개의 점을 찾고 싶습니다.

sqrt으로 귀찮음을 피하기 위해 지정된 길이를 제곱하십시오.

목록에있는 모든 쌍의 점 사이의 거리의 제곱을 찾고 주어진 길이와 일치하는 점만 주목하십시오 : O (V^2), 그러나 계수가 작 으면 대부분의 길이가 일치하지 않기 때문입니다.

이제 O (V) 가장자리가있는 희소 그래프가 나타납니다. O (V) 시간에 크기 3의 모든주기를 찾아서 일치하는 부분을 잘라냅니다. (가장 좋은 방법은 모르겠지만, 적절한 크기의 here is one way.)

총 복잡성 : O (V^2)하지만 O (V)에서 사이클을 찾는 것이 포인트 수에 따라 제한 요소가 될 수 있습니다. 모든 쌍을 바라 보지 않도록 점 목록을 공간적으로 정렬하면 점근 행동을 향상시킬 수 있습니다.

Answer 2

이것은 일반적으로 행렬 계산으로 수행됩니다. This Wikipedia article은 회전, 평행 이동 및 반사 행렬을 다룹니다. 여기에 another site (사진 포함)이 있습니다.

Answer 3

삼각형은 3면의 길이로 고유하게 정의됩니다 (회전, 뒤집기 및 이동 무시). 원래 삼각형 A, B, C의 정점에 레이블을 붙입니다. 포인트 D, E, F에 대해 을 찾고 있습니다. | AB | = | DE |, | AC | = | DF | 및 | BC | = | EF |. 길이는 피타고라스 식으로 주어진다 (하지만 당신은 선분의 길이의 제곱 ... 비교하여 각각의 시험에서 제곱근 작업을 저장할 수 있습니다) 다음의 변환은 단지 회전하기 때문에,

Answer 4

스케일링 및 미러링 만약 삼각형의 양측의 내적 확인하여 삼각형 형태 변형 점 찾을 수 원래 삼각형 A, B, C를 들어

1. 을 AB.AC, BA.BC의 내적을 계산할 CA.CB
2. D, E, F의 3 개 세트 각각에 대해 DE.DF의 내적을 계산하고 1에있는 3 개의 내적을 비교하십시오.

이것은 AB.AC = | AB | x | AC | x cos (a)이고, 두 개의 길이와 그 사이의 각도는 삼각형을 정의합니다.

EDIT : 예, Jim이 맞습니다. 한 점의 제품만으로는 충분하지 않습니다. ED.EF 및 FD.FE를 포함하여 세 가지 모두를 수행해야합니다. 그래서 결국 사각형 거리 함수와 같은 수의 계산이 이루어집니다.