c++ - 直線を使用して 2 組の点を分割する

Question

2D 空間に 2 組の点 A と B があるとします。A のすべての点を片側に、B のすべての点をもう一方の側に持つ単一の直線が存在するかどうかを知りたいのですが、可能であれば、そのような直線を 1 つ見つけます。検索中にこの質問を見つけましたが、それは「最適な線」の問題です。

直観的には、クロス積に関する質問のように感じますが、どうすればそれができるのかわかりません。

score 2 · Accepted Answer

ポイントのセットごとに凸包を見つけ、この質問の手順に従って、交差するかどうかを判断します (交差しない場合は分割線を返します)。

score 0 · Accepted Answer

機械学習では、これに対する従来のソリューションはサポートベクターマシン (SVM) です。N 次元に一般化し、解がない場合に最適な近似を見つけます。解が複数ある場合は、分割線の左右のマージンを最適化します。おそらくやり過ぎかもしれませんが、すでに複数の実装が利用可能です。(例: OpenCV)

2 に答える 2