從輸入的四點確定形狀的高效算法

Question

我想解決Uva上的Determine the shape問題。從閱讀問題後我可以得到它是一個Ad Hoc幾何問題，我們必須使用幾何定理來確定我們在2D平面上輸入的四個點的形狀。花了好幾個小時後，我仍然想不出有效的算法，可以在給定的時間內有效地解決問題。我嘗試使用距離公式和斜率，但沒有多大幫助。請提出一些好的算法或定理，我可以用它來解決這個問題。

Answer 1

我首先想到的是以下內容：

1. 確定每個邊的長度。使用公式sqrt((a - x)^2 + (b - y)^2)。
2. 確定每個角度。
3. 確定哪些形狀：
   • 如果所有角90
     • 如果所有側相等，返回SQUARE
     • 否則，返回RECTANGLE
   • 否則，如果角度1 = 3和角度2 = 4等於
     • 如果所有面相等，則返回RHOMBUS
     • 否則，返回平行四邊形
   • 否則，如果角1 + 2 == 180，或角3 + 4 == 180，返回TRAPEZIUM
   • 否則，返回普通四邊形

但請考慮遵循here的邏輯;他們已經使用了矢量數學，並簡單地計算是否有一個直角或兩條線是平行的，而不是計算所有角度。

1. 準備一些函數來計算兩條線是否平行，以及角是否是直角（使用矢量數學）。
2. 對點進行排序，以便它們按正確的旋轉順序排列（實際順序對凹形不明確，但它應該沒有關係，應該仍然返回普通四邊形）。
3. 確定每條線的長度。
4. 確定形狀，給定長度以及線條是平行還是角度正確。

Answer 2

首先，不同的形狀具有以下關係：

Ordinary Quadrilateral --(with one pair of parallel sides)--> Trapezium 

Trapezium --(with additional pair of parallel sides)--> Parallelogram 

Parallelogram  
--(with four equal straight lines)--> Rhombus--(with four 90 degree angles)-->square  
|--(with four 90 degree angles)--> Rectangle --(with four equal lines)--> square 

鑑於四個點A，B，C，d，採取隨機一個（比方說A），並且我們需要計算統計數據（角以下四點對（不是全部），包括

(1) AB and CD, A1, L1 
(2) AC and BD, A2, L2 
(3) AB and AC, A3, L3 
(4) AB and AD, A4, L4 

然後我想招就如何組織分支，使我們可以有最小的計算和代碼路徑和長度）。我的建議如下：

A3 = getAngle(AB, AC) 
A4 = getAngle(AB, AD) 
if A3 > A4 
    we know AD is the diagonal line, then use A, B, C to calculate 
else 
    we know AC is the diagonal line, then use A, B, D to calculate 
# following suppose we use A, B, C to do the calculation, we could easily do the A, B, D thing if define new variables 
L3 = LengthEqual(AB, AC) 
A1 = getAngle(AB, AD) 
if A3 == 90 && A1 == 0 
     if L3 == True 
      Square 
     else 
      Rectangle 
else 
     A2 = getAngle(AC, BD) 
     L2 = LengthEqual(AC, BD) 
     if A2 == 0 && A1 == 0 
      if L2 == True 
       Rhombus 
      else 
       Parallelogram 
     else if A2 == 0 || A1 == 0 
      Trapezium 
     else 
      Ordinary Quadrilateral 

在該手段，力求做到相對較少的計算聰明地轉移到我們想要的結果。希望這可以幫助。