C++ で巡回セールスマンの問題を解決しようとしていますが、ポイントのセットではなく、ポリゴンのセット間の最短距離をトラバースする必要があります。そうするために、代表的な「平均」内点で各ポリゴンを表現して、これらの平均内点で TSP を実行できるようにしています。
凸多角形の平均内部点を見つけるのは簡単です。これは単に算術平均点であるためです (凸多角形の場合は常に内側にあるため)。ただし、このアプローチは凹多角形では機能しません。ポリゴンの内側にします。
これについて助けますか？ありがとう。:-)
どうですか：
非凸多角形全体の真の重心は（潜在的に）多角形の外側にあるので、これよりも意味のある「代表的な」点の別の定義はないと思います。
1 つのアイデアは、各ポリゴンの凸包を構築し、凸包の中心を使用することです。多角形を輪ゴムで包むようなものであると理解すると、関心のあるポイントを見つけるために使用できるエンベロープが得られます。CGALを使用して計算できるはずです。しかし、すべてのポリゴンに対してこれを行うと、超高速にはなりません。三角形分割を作成すると、追加の手順として、元の多角形の凸包の中心点に最も近い内部点を効率的に見つけることができます。
ところで、凸多角形の点の中心を見つける適切な方法は、チェビシェフの中心を見つけることであり、これはCGALを使用して実行できる線形システムを解くことに対応すると思います。凸多角形のチェビシェフ中心を見つけるための線形計画問題は、ボイドの本で明確に定義されています。