找到布爾網格多邊形

-1

我有布爾的這樣找到布爾網格多邊形

2-dimensional array of bool

二維陣列的形狀不會有任何漏洞 - 即使它有 - 我會忽略他們。現在，我想找到的多邊形擁抱我的形狀：

embracing polygon

是否有任何的算法準備用於這種情況？我找不到任何東西，但我不確定我是否知道這個任務的正確搜索詞。

來源

2013-09-16 user2033412

它看起來好像你找到了多邊形。但也許你可以更多地解釋你有什麼和你想要什麼。你的陣列代表了什麼？你想要爲你想要找到的多邊形表示什麼樣的表示？ –

我手動找到了多邊形，但我想讓我的程序找到它。我想找到代表多邊形的x-y座標列表。 – user2033412

由於你有包括正方形的座標這個問題的答案 - http://stackoverflow.com/questions/17862162/sort-anticlockwise-the-points-of-rectilinear-polygon#comment26081406_17862162 - 會讓你其餘的路程。 –

-1

考慮了更多一點後，我發現它並且有一個O（n）方法來執行此操作：按行搜索包含至少一個相鄰字段的第一個座標，並將其設置爲true。從那裏你可以明確地向右邁出第一步。從現在開始，只要在四個相鄰的場地的基礎上走一圈，決定接下來走什麼方向。

來源

2013-09-18 07:26:38 user2033412

您可以使用delaunay三角剖分，然後移除最長的邊緣。我用所有邊的平均值乘以一個常數。

來源

2013-09-16 14:15:07 Bytemain

delaunay-triangulation是O（n * log（n）），我認爲這對我的任務來說太昂貴了。我敢打賭，有一個O（n） - 做到這一點。 – user2033412

找到布爾網格多邊形

回答

相關問題