如何從一個簡單的線條計算特定寬度的多邊形點？

Question

我目前正在開發一個應用程序，可以根據線條創建多邊形，並且遇到一個小問題：我有一組點，代表一條線。我想創建一個多邊形來顯示具有特定寬度的線條（例如，街道）。我有幾個想法如何計算外部多邊形點，但我認爲它們太複雜了...

我最好的想法是下面的圖片：線條的每個點必須投影到至少兩個點：兩者點必須與後續線段成90°，並且具有優選多邊形寬度的一半距離。

這工作不錯，你可以看到底，並開始描繪多邊形的點。現在複雜的部分：用這種方法，在一個角落裏，每個點都得到四個點。但是這些點對於外部多邊形是不正確的，因爲它們處於形狀中。線條相交併創建了一個醜陋的多邊形。

如何才能找到這樣一個多邊形的正確點？我認爲我的方法對於解決這個問題太複雜了。

任何人都可以幫助我解決這個問題嗎？

信息：我用openstreetmap標記了這個，因爲像Mapnik這樣的渲染器也有這個問題。

Answer 1

您正在查找的是多邊形（或線）抵消算法。這不一定是一個容易解決的問題，順便說一下：An algorithm for inflating/deflating (offsetting, buffering) polygons。

在過去的幾個星期裏，我一直致力於Maperitive的線抵消算法。在我來說，我只需要抵消線，所以我不是在尋找一個解決方案來創建它周圍的一個緩衝的多邊形，但我估計算法可以進一步在未來的擴展：

基本流程（約但魔鬼在細節）：

1. 對於每個折線點發現，具有從原始點的大號距離，位於一條線是垂直於原線，並通過原進了點點。
2. 現在通過該新點繪製一條偏移線。該行必須與原始行平行。
3. 對於拐角角度，您必須擴展兩條相鄰的偏移線並找到相交點，它將成爲偏移線的下一個點。

有些事情要注意以下幾點：

• 通知適用於凹角度畫面右側的斜接限制。
• 在計算偏移線之前，您需要簡化原始多段線以排除太小而不能保持偏移量的段（結果可以在圖片的左側中心看到）。
• 我只實現了對斜接連接的支持，但一個好的算法也應該能夠渲染圓連接（使用弧）。