查找一組點的特定輪廓

Question

我有一組「塊」（用紅線和綠線表示）放置在「容器」（用藍線表示）內。

所有塊（綠色和紅色的點）和容器的所有相關信息的交叉點的（角度，梯度，開始，結束點等）是已知的。

我想在塊放置後（由綠線和點表示）提取結果圖的「最頂部」輪廓。

我試圖使用的方法，例如凸包，但它不給出確切的線（由紫線下圖中示出。）

我的問題是任何人都可以指向我一個解決方案或某種算法，我可以用來解決這類問題？

Answer 1

用所有點填充列表（數組）。 （T形節點中的重複點，如圖片中的第2個綠色點）
按Y座標對此列表排序
掃描列表（從頂點開始）像掃描線算法。
在每一個階段你都會得到一組具有相同Y座標（一對或多對）的點。
從左側和右側移除包括間隔（見下文）的點。
根據這些點對的間隔（通過X座標）。
在區間（分段）樹中添加這些區間。
加入鄰居間隔。
重複，直到單個間隔覆蓋所有頂部。

Answer 2

凸包應該做的工作。 對於許多凸包算法，您可以檢查：Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h)。

只要它觸及紅點，你會得到前後。