OpenCVなどのPointデータの積集合を取る方法

OpenCVのPoint型で二次元座標を扱うとき、2つのPoint集合(vector)間での同じ座標だけを抽出したいことがあると思います。1個1個総当たりで探すという手段もありますが、std::set_intersectionを使うことで簡単に実現が出来るので、その方法をサンプルプログラムでご紹介します。

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include "opencv2/core.hpp"

// std::sortやstd::set_intersectionでpointを比較するための関数
bool cmp_points(const cv::Point2f& a, const cv::Point2f& b)
{
    return (a.x * a.x + a.y * a.y < b.x* b.x + b.y * b.y);
}
int main()
{
    std::vector<cv::Point2f> contours1 = { {0.0, 0.0},{2.0, 3.0},{0.0, 2.0},{2.0, 2.0},{4.0, 4.0} };
    std::vector<cv::Point2f> contours2 = { {1.0, 2.0},{3.0, 4.0},{2.0, 2.0},{0.0, 0.0},{2.0, 3.0} };

    // std::set_intersectionを呼び出す前に入力データをソート
    std::sort(contours1.begin(), contours1.end(), cmp_points);
    std::sort(contours2.begin(), contours2.end(), cmp_points);

    // std::set_intersectionを呼び出してcontours1とcontours2の積集合を取る
    std::vector<cv::Point2f> contours_intsec;
    std::set_intersection(contours1.begin(), contours1.end(),
        contours2.begin(), contours2.end(),
        std::back_inserter(contours_intsec), cmp_points);

    return 0;
}

入力データとしては std::vector 型の下記2つです。

contours1 = { {0.0, 0.0},{2.0, 3.0},{0.0, 2.0},{2.0, 2.0},{4.0, 4.0} }
contours2 = { {1.0, 2.0},{3.0, 4.0},{2.0, 2.0},{0.0, 0.0},{2.0, 3.0} }

ワザとランダムに並べていますが、積集合としては下記が正解です。

contours_intersec = { {0.0, 0.0},{2.0, 2.0},{2.0, 3.0} }

実装上の注意点としては2つあります。

• std::set_intersectionを呼び出す前に入力データを昇順にソート(std::sortを使う)しておく必要があります。
• std::sortとstd::set_intersectionでPointを扱うためにカスタムの比較関数を用意する必要があります。サンプルではcmp_points 関数として実装しています。この比較関数は昇順で比較するケースではaよりbが小さい場合(<)にtrueを返します。降順のソートを実装したい場合はその逆です。