How can I find the largest quadrangle

Question

How can I find the largest quadrangle in this case?

In the attached image you can see what I have (in the left) and what I wantto get (in the rigth).

This code won't work because the largest rectangle has crosses instead of corners.

int GameController::GetIndexOfExternalContour(vector<vector<Point>> contours)
{
    int largest_area=0;
int largest_contour_index=0;

for( int i = 0; i< contours.size(); i++ )           // iterate through each contour. 
{
    double a = contourArea(contours[i], false);     //  Find the area of contour
    if(a > largest_area)
    {
        largest_area = a;
        largest_contour_index = i;                  //Store the index of largest contour
    }
}

Answer 1

I wanted to add a convexity defects approach.

Find largest contour, get defect points, connect the extremes.

// stl
#include <algorithm>
#include <iterator>
#include <limits>
using namespace std;

// cv
#include <opencv2/opencv.hpp>
using namespace cv;

int main()
{
    Mat sample = imread("path/to/sample.jpg");
    imshow("window", sample);
    waitKey(0);

    // images to work on
    Mat black = Mat(sample.rows, sample.cols, CV_8UC1, Scalar(0));
    Mat clone = sample.clone();

    // binarization
    Mat gray;
    cvtColor(sample, gray, CV_BGR2GRAY);
    threshold(gray, gray, 127, 255, CV_THRESH_OTSU);

    // find and fill the largest contour
    vector<vector<Point> > contours;
    vector<double> areas;
    findContours(gray, contours, CV_RETR_LIST, CV_CHAIN_APPROX_SIMPLE);
    for(unsigned int i = 0; i < contours.size(); i++)
    {
        areas.push_back(abs(contourArea(contours[i])));
    }
    vector<double>::iterator biggest = max_element(areas.begin(), areas.end());
    unsigned int ID = distance(areas.begin(), biggest);
    drawContours(black, contours, ID, Scalar(255), -1);
    imshow("window", black);
    waitKey(0);

    // get convexity defects of thelargest contour
    vector<Point> external = contours[ID];
    vector<int> hull;
    vector<Vec4i> defects;
    convexHull(external, hull);
    convexityDefects(external, hull, defects);

    // show defect points
    for(unsigned int i = 0; i < defects.size(); i++)
    {
        circle(clone, external[defects[i][1]], 1, Scalar(0, 255, 255), 3);
    }
    imshow("window", clone);
    waitKey(0);

    // find extremes
    Point tl, tr, bl, br;
    Point p;
    double d_tl, d_tr, d_bl, d_br;
    double m_tl = numeric_limits<double>::max();
    double m_tr = numeric_limits<double>::max();
    double m_bl = numeric_limits<double>::max();
    double m_br = numeric_limits<double>::max();
    for(unsigned int i = 0; i < defects.size(); i++)
    {
        p = external[defects[i][2]];
        d_tl = (double)sqrt((double)pow((double)(p.x),2) + pow((double)(p.y),2));
        d_tr = (double)sqrt((double)pow((double)(sample.cols - p.x),2) + pow((double)(p.y),2));
        d_bl = (double)sqrt((double)pow((double)(p.x),2) + pow((double)(sample.rows - p.y),2));
        d_br = (double)sqrt((double)pow((double)(sample.cols - p.x),2) + pow((double)(sample.rows - p.y),2));
        if(d_tl < m_tl)
        {
            tl = p;
            m_tl = d_tl;
        }
        if(d_tr < m_tr)
        {
            tr = p;
            m_tr = d_tr;
        }
        if(d_bl < m_bl)
        {
            bl = p;
            m_bl = d_bl;
        }
        if(d_br < m_br)
        {
            br = p;
            m_br = d_br;
        }
    }

    // draw rectangle
    line(sample, tl, tr, Scalar(0, 255, 255), 3);
    line(sample, tr, br, Scalar(0, 255, 255), 3);
    line(sample, br, bl, Scalar(0, 255, 255), 3);
    line(sample, bl, tl, Scalar(0, 255, 255), 3);
    imshow("window", sample);
    waitKey(0);

    return 0;
}

you just need to try some another approach for the last step (find extreme defects)