我有一組頂點（稱爲A），我想要找到所有邊界頂點，以便此邊界頂點集是該形狀的輪廓。給定非凸多邊形中的一大組頂點，我如何找到邊？
A中的許多頂點都是多餘的，因爲它們在形狀內部，我想擺脫這些頂點。
我的問題類似Best Algorithm to find the edges (polygon) of vertices，但我需要它爲一個非凸多邊形的情況下工作。
編輯： 說明：下圖是一個凹多邊形。這就是我的意思是非凸的。如果我在它上面運行凸包算法，它不會保留多邊形的凹形部分（除非我錯了）。
我有一組頂點的內部和多邊形的邊界：[[X1，Y1]，[X2，Y2] ...] 我想降低設定使得頂點只是形狀的邊框輪廓。
您的描述有些模糊，但可能您正在尋找構建一組點的Convex Hull的算法。簡而言之，如果在所有頂點周圍放置橡皮筋，凸包就是您的形狀。
寫作二維凸包算法是不是非常困難的，也有一些庫，做到像qhull
（即答案在問題也給了你鏈接到這似乎是一個特殊的情況下，你問題）
凸包不會排除某些點，因爲它只會跟蹤凸多邊形？我在答案中添加了一張圖片來澄清形狀。 – 2010-04-30 17:28:27
它會但你怎麼能告訴哪個邊緣要分開把這兩個額外的邊緣？ – shoosh 2010-04-30 19:05:18
這是一個古老的，也許是遺棄的問題，但它讓我思考它。你不是在尋找一個凸包，你想要保持多邊形的形狀，但只是擺脫沿着一條線的「邊緣」之間的點。
解決方案可以是逐步通過相鄰點並計算第一個和第二個線性斜率，然後保存該斜率值，計算第二個和第三個斜率，如果pt1-pt2的斜率等於該斜率的pt2-pt3，那麼pt2在形成線路中是多餘的，因此可以刪除。繼續循環直到你回到pt1。
這將確保您的凹形狀保持不變，但不相關的加點被刪除。
你是指「爲非凸多邊形案件工作」是什麼意思？你鏈接的問題包括輸入頂點形成一個凹多邊形的情況，所以我沒有看到你的問題有什麼不同。 – outis 2010-04-30 00:56:20
如何區分多邊形內的哪些頂點以及邊上的哪些頂點？ – 2010-07-14 20:22:22