跟蹤頂點的連接和determening當多邊形由

Question

我想在C＃中的遊戲機制，涉及到連接的頂點和多邊形形成工作。

可以有任意數量的5 - 30頂點。每個頂點可以用直線連接（線不能相交）。當線關閉多邊形時，多邊形的內部會以特定顏色着色。 （不能關閉期間關閉多邊形是否會有裏面的一個點）

例如下面兩張圖片是不可能發生的：

然而，這可以：

我遇到的麻煩是如何辨別我剛剛關閉的多邊形並記住它（如果我關閉與它共享邊的多邊形）。我可以有多個封閉多邊形，直到可以繪製每個頂點可以繪製的所有線條而不違反相交規則。

我試圖記住，繪製AB，ED，CD，CA等線..並尋找一個週期，但是當我關閉多個多邊形，我需要更多的信息來了解哪些多邊形已經關閉。但是我很難搞清楚如何去做。

例如（如下圖），如果線條n被繪製，我想找到剛製成的多邊形。

沒有人有任何想法如何，我可能做到這一點？ 任何想法，幫助，洞察力都會有幫助。

Answer 1

可能有點簡單，但你可以存儲Dictionary<Face,List<Vertex>>，你可以使用LINQ查詢。

您可以通過添加反向查找簡化它。 Dictionary<Vertex, List<Faces>>

方案1：路徑觸及邊緣，即同一張臉

的一部分，以測試新的路徑DC你得到的2個頂點，d和C，找到它同時包含任何面。在List<Vertex>中以D開頭，並創建到C的路徑。

現在，請執行C -> D。

你現在有兩個路徑，使用D -> C所以現在你必須枚舉所有的頂點，並消除其包含現有頂點的面孔D -> E -> C和C -> A -> B -> D都形成有效的面孔。

方案2：路徑接觸的邊緣不屬於任何面

此路徑是開放的一部分。

方案3：路徑觸摸EGES它們是不同的面孔

面1的一部分：ABDEC Face2：AGF

測試路徑FC。 F是Face2的一部分C是Face1的一部分。

找到十字路口：Face1.Face2 ==它是這兩個列表中唯一的一點，這次你得到2組2個路徑。

FA
FGA

AC
ABDEC

從F轉到A，這些路徑乘

FAC FGAC FABDEC FGABDEC

這些面，現在可以經過有效性測試。

對於更復雜的場景（3個臉部接觸，臉部共享邊緣）也可以更容易地保留所有相連邊緣的圖形，這將爲您提供一種更簡單的方法來檢測2個頂點之間的可能路徑。

請注意，包含3個頂點任何路徑形成可以有效性

Answer 2

當玩家改掉權利要求一個新的邊緣，你可以檢查一個可能的臉：

• check that the edge does not cross現有的任何聲稱邊緣;
• 對由所要求邊緣形成的圖形（它們不在兩個多邊形的邊界上）執行寬度優先搜索，以查看是否存在從到達另一端的新邊緣的一端開始的現有路徑新邊緣 - 在這種情況下將形成多邊形;和
• 如果一個多邊形已經形成：
  • check to see if there are any vertices inside the polygon - 在這種情況下，播放器不能聲稱邊緣。
  • 每條邊都有兩條邊。已形成的多邊形的內部將位於沿其邊界的每條邊的一側上 - 您可以跟蹤此內容，然後任何後續由這些邊中的一個（或多個）邊界限定的多邊形必須位於該邊的另一側（ s）是你遊戲中的有效選擇。如果邊在兩側聲明瞭多邊形，則它不能位於任何後續多邊形的邊界上。

您可能需要生成點周圍的凸包排除外部的多邊形，這樣，當玩家正在形成的多邊形要限制它們的凸包的內部。