平鋪算法/數據結構？

我正在考慮創建一個程序讓我玩或解決slitherlink拼圖，就像在krazydad.com上一樣。它由4塊，5塊，6塊，7塊和8塊磚組成。除七面磚之外，所有面都具有相同長度的邊，其中兩面之間的兩面爲七面磚（因此將五面瓷磚連接到四面瓷磚）的邊長約爲正常長度的70％。正如您在下面的圖片中看到的，八邊形由交替的五邊形和六邊形包圍。這些與六邊形的遠端相連。連接到五邊形的尖端的是連接到連接到其他組的正方形的較小線。然後圍繞廣場形成具有兩個短邊的七邊形圖。我認爲外邊緣是通過忽略離中心太遠的瓷磚來定義的。平鋪算法/數據結構？

enter image description here

對於數據結構，我想我需要連接所有節點的圖。我可以讓用戶點擊以在最接近的鏈接上放置一條實線，並且我可以很容易地檢查循環或太多線條進入節點。我還需要爲它們創建切片和關聯線，並將內部線條分配給兩個切片，但將其視爲一條線。

至於設置它，我正在考慮手動計算出點並定義最小的重複貼圖集（1 8，4 5，4 6，4 7和1 4），然後將它們放在每個貼圖旁邊其他。放置時，我會檢查每個放置的現有關閉點，如果找到，則將它們組合。然後我需要檢查重複的行併合並它們。

是否有更容易或更乾淨的方法來A）生成平鋪或B）在進行平鋪時合併節點和鏈接？

來源

2011-08-16 Jason Goemaat

有沒有理由我的答案不好？ –

一些意見，這可能有助於：

，如果你加入的鄰近多邊形的中心，你有一個德勞內三角（1）。
雙Delaunay三角網（2）是上圖（略有不同的邊長，但可以調整，如果有必要）
有如何生成圖表這裏的討論（3）從Delaunay三角

所以，把它們一起，你可以：

生成瓷磚的中心（見下文）
構建瓷磚中心的delaunay三角測量（通過加入neigbours）。
找到雙重得到你想要的圖形（尋找雙重的過程中，應通過良好的圖形庫支持）

產生瓦中心的模式，以最少的一組和從中心開始8.對於每個90度左右的旋轉，添加（旋轉）最小組（除了你正在旋轉的那個外加一個8），去除重複。然後在已添加的8中執行相同操作（遞歸或使用堆棧）。

一旦你有了這些中心，我不確定連接鄰居的最佳方式是什麼 - 你想要一些生成一組候選人的有效方法。但這不是一個難題，只是很煩瑣（「奇特」的解決方案應該是四叉樹或空間哈希，但只是粗略的分箱就足夠了）。

來源

2011-08-16 02:55:28

因此，在加入中心來創建Delaunay三角剖分時，您正在採用原始圖形的對偶，對吧？我試圖在您的討論鏈接中使用python代碼，但無法獲取ATLAS進行編譯，因此scipy無法安裝。無論如何，我不知道如何在C＃中使用它。另外，我不認爲delaunay三角測量的對偶會將最終點放在正確的位置來形成規則的多邊形，對嗎？ –

是的，delaunay三角剖分是圖的對偶（接近 - voronoi曲面細分）。最後一點需要調整，是的（這就是我的意思是「稍微不同的邊緣長度），所以你需要修復它們，但這應該是一個相當簡單的問題（每個點都是8或6的成員？） –

5s和4s左右的點不是8s或6s的成員，不規則7s的中心是真正拋棄了我想通用定位算法的東西。關於爲每個尺寸創建類並讓它們以遞歸方式構建廣度優先的圖，首先創建中心8.創建點0（讓我們說左上角）現在創建點1（順時針右上角）創建top 5和設置兩點和線，但通過將點從0到1的矢量旋轉45度來創建另一個點，新線創建一個6，等等，然後繼續8。 –

平鋪算法/數據結構？

回答

相關問題