問題タブ [non-convex]

中心点の周りに多角形を形成する緯度経度のリストがあります。緯度経度の順序付けされたリストを時計回りに取得して、その順序付けられたリストで緯度経度頂点を接続し、非凸多角形を形成したいと考えています。

凸面ポリゴンと非凸面ポリゴンの両方を含む画像がいくつかあります。各画像には、ポリゴンが 1 つだけ含まれています。角の座標を検出し、時計回りまたは反時計回りに並べ替える必要があります。凸多角形の場合、コーナーの検出にはハリス コーナー検出を使用し、ポイントの並べ替えには凸包を使用します。しかし、凸でないポリゴンをソートする方法についてはわかりません。私の入力は画像であるため、ポリゴンの端に沿って移動することで、画像処理テクニックがそれらを整理するのに役立つと思います。複雑さが最も少ない方法はありますか？

画像例:

コーナーにランダムに名前を付けました。

期待される出力:

コーナー座標は次の順序 1 3 5 9 4 2 8 7 6 10またはであると予想され1 10 6 7 8 2 4 9 5 3ます。いつでも開始できますが、必ずしもそうである必要はありません1

編集1：

すべての凸多角形と一部の非凸多角形で機能するrayryengのソリューションの後、彼のアルゴリズムではうまくいかない非凸多角形がいくつかあります。

ここに例があります

ポリゴンが重なっているとします。どちらも必ずしも凸ではありません。どちらの境界上でもなく、両方の内側にあるポイントを見つける効率的なアルゴリズムは何ですか?

それらが重なり合い、ポリゴンが 3D の頂点のセットによって定義されていると仮定します。

非凸目的関数を最小化するためにScipy のLBFGSの実装を使用しています。結果は悪くありません。ただし、収束のステータスは「ABNORMAL_TERMINATION_IN_LNSRCH」です。

これは、目的関数が非凸である可能性がありますか? または、これは私の勾配 (分析的に手動で計算され、引数として Scipy の LBFGS に渡される) が間違っていることを意味するのでしょうか?

非凸問題 (最大尤度) を最適化する必要があります。bfgs、Nelder-Mead などの二次最適化アルゴリズムを試すと、極値が見つからず、代わりに鞍点が頻繁に発生します。

こちらからデータをダウンロードできます。

ここで、グリッド検索に行くことにし、scipy.optimize.brute を試しましたが、このエラーが発生しました。実際、私の実際の変数は 47 です。動作するように 31 に減らしましたが、それでも動作しません。助けてください。

非凸 QCQP ソルバーを知っていますか? 大きな問題は、学者や学生向けの無料のソフトウェアです。私は成功せずにそのようなソルバーを見つけようとしました...

私の問題は次の形式です。

• 線形（厳密および非厳密）不等式
• 不等式間の論理的制約 (同等性、含意など) がある
• X = {x1, ..., xn} を変数の集合とし、Y = {y1, ..., ym} を変数の集合とする。二次制約は次の形式です。
  • x1 = x1y1 + x2y2
  • x2 = x1y3 + x3y4
  • x3 = x2y5 + x1y6
  • ...
  • 左側の X からの 1 つの変数
  • 等式制約
  • 係数が 1 に等しい 2 つの変数の積の合計
  • st 2 つの変数の各積は、X の 1 つの変数と Y の 1 つの変数の間でのみ発生します。

目的関数は線形です。

ご協力ありがとうございました

L0-normmatlab でペナルティ関数をプロットすることに興味があります。

実際、L0-normベクトルx , ||の x ||_0 は、 x内の非ゼロ要素の総数を指定する値を返します。言い換えれば、|| x ||_0 = #(i | xi !=0)。

たとえば、 x の L1 ノルムの場合、 xの要素の絶対値の合計を返します。L_1 ノルム ペナルティ関数をプロットする matlab コードは次のとおりです。

しかし、今L_0ノルムはどうですか??

どんな助けでも大歓迎です！