1

ポリゴンクリッピングライブラリClipperのc++バージョンを使用していますが、ポリゴンの頂点の数を減らして、ほぼ同じ形状を維持したいと考えています。

追加の要件として、ポリゴンを「外側のみ」に近似する必要があります。結果として得られる簡略化されたポリゴンは、元のポリゴンと一致している必要があります。

私は考えました:

  • 「外向きのみ」の条件を満たす凸包ですが、ポリゴンが単純化されすぎています
  • Ramer-Douglas-Peuckerアルゴリズム。これは、エラーを選択できるので優れていますが、「外向きのみ」の条件を満たしていません。

次に、psimplライブラリを調べました。私の要件に最も近いアルゴリズムは、Opheneimアルゴリズムのようでした。

最小距離公差と最大距離公差の両方を使用して、検索領域を制限します

ただし、最小距離を0にすることはできません。

この問題に対する可能な解決策はありますか?それを解決するC++ライブラリを知っていますか?

4

1 に答える 1

1

ポリゴンの周りを繰り返して、次のことを試してみてください。

  1. 頂点が凹面で線までの距離があり、隣接する頂点を接続している場合はtolerance、それを削除します。

  2. 頂点が凸状である場合、前のセグメントが線上にあると見なしL1、さらに反復し、L1次のセグメントを含む線と交差し、Pポリゴンの外側の点でポリゴンからの距離P< tolerance、およびセグメントの始点からL1<までの距離を指定しtoleranceます。その反復が停止したら(最初の反復ではなく)、中間点を削除し、交点を挿入します(現在がポリゴン内にある場合は前、境界上にある場合は現在)。

単純化が行われている間、ポリゴンを繰り返し続けます。また、許容範囲を確認するために、古いポイントをどこかに保持するようにしてください(たとえば、頂点を列挙し、単純化しながらインデックスを削除できますが、許容範囲を確認するときは、中間のインデックスも確認してください)

これは超高速アルゴリズムではありませんが、必要なことを実行します。

例

于 2013-03-26T12:12:25.813 に答える