頂点と<strong>N</strong>バウンディングボックスのセットが与えられる行

Question

に、2次元空間内のグループ、それらを境界ボックスのセットが与えられた座標：

"vertices": [ 
    { 
     "y": 486, 
     "x": 336 
    }, 
    { 
     "y": 486, 
     "x": 2235 
    }, 
    { 
     "y": 3393, 
     "x": 2235 
    }, 
    { 
     "y": 3393, 
     "x": 336 
    } 
    ] 

I行にグループバウンディングボックスをしたいと思います。

[1,2,3] 
[4,5,6] 
[7,8] 

[編集：明確化]グループの意思決定（例えば、[私は返すアルゴリズムをしたいと思い

：他の言葉では、このイメージにバウンディングボックスの絵図を与えられました4,5,6]および[7,8]）は、最小自乗のようなある種の誤差最小化に基づくべきである。

これにはアルゴリズムやライブラリ（できればPythonで）がありますか？

Answer 1

これはクラスタリングの問題だと思います。実際には、x座標を無視できるので、これは1次元クラスタリングの問題だと思います。 k-meansのようないくつかの標準的なクラスタリングアルゴリズムは、あなたが探しているものに相当するクラスタ中心からの二乗和を最小化するのに適しています。残念ながら、彼らは世界的に最良のソリューションを見つけることを保証しません。 1次元クラスタリングは、正確なアルゴリズムがある特殊なケースです。Cluster one-dimensional data optimally?を参照してください。