C++ - Sort particular points of a rectangle in a vector?

Question

I have a project in c++ where I should map regions of an image using the mouse click. The point is that I should get the mapping points in a specific storage order, as in the image below:

my problem begins at the moment of storing this data, because I created the following vector to store such points: pfileira = {P1, P2, P3, P4}. The problem is that by clicking on the image and obtaining the points, I can only store them in the order of the click, that is if I start mapping by P3 for example, the vector will be stored as: pfileira = {P3, P2, P1, P4} or = {P3, P4, P1, P2}. Is there a theorem I can use to sort my storage vector in order to get the sequence of points in the order = {P1, P2, P3, P4} in my point vector being selected from any point? I tried to use different forms using up to a numerical value of the module of each point, but it does not work for all cases. Would anyone like to help me with this problem if there is a solution? I would like to thank you.

Answer 1

The solution to your problem is quite simple. The basic algorithm is as follows::

1. Given the vertices of the polygon, calculate the midpoint (center of the polygon). To do this, just do, for each component of coordinates (that is, for x and then for y) the sum of the values of the components in each vertex and divide by 4 (since they are only 4 vertices).

2. Given the central point, calculate the vectors from this central point to each vertex (see linked reference. They are not vectors in the direction of matrices in programming, but vectors in space, with direction, direction and magnitude). The vector is important to obtain the direction in which the vertex lies "around the polygon".

3. For each vector, calculate the angle of inclination between this vector and the horizontal axis. To do so, use the calculation of arctangent of the value of y in relation to the value of x (the idea is a simplification of the calculation of the angle between vectors; for more information, see that reference). Save those angles.

4. Finally, sort the list of points based on the value of their angle. As in most computational systems the coordinates start in the upper left corner (that is, the 0.0 coordinate is in the upper left, with x growing to the right and y growing down) this means that the angles of the vectors will vary depending on the image below:

So the angles "grow" clockwise from the top left corner, according to the order you want.

Code Example

Your question has the tag c++, but does not say details of the operating system or the graphical platform used. Thus, I will make an example in Qt, which is much simpler and straightforward (at least for me). You can easily use it as the basis for whatever you’re doing. In the example, the order of the points is not given by clicks, but was placed arbitrarily.

Filing cabinet window.h

#ifndef WINDOW_H
#define WINDOW_H

#include <QWidget>
#include <QPoint>
#include <QVector>
#include <QVector2D>

/**
 * Janela para exibição dos dados
 */
class Window : public QWidget
{
    Q_OBJECT
public:

    /**
     * Construtor da classe.
     * @param oVertices Objeto QVector com as coordenadas dos vértices do polígono.
     * @param oVectors Objeto QVector com os vetores do centro a cada vértice do polígono.
     * @param oNames Objeto QVector com os nomes dos vértices (para exibição apenas).
     * @param oCenter Objeto QPoint com as coordenadas do centro do polígono.
     * @param pParent Objeto QWidget que será pai deste objeto criado. O default é 0 (NULL).
     */
    explicit Window(QVector<QPoint> oVertices, QVector<QVector2D> oVectors, QVector<QString> oNames, QPoint oCenter, QWidget *pParent = 0);

protected:

    /**
     * Sobrecarga do evento de pintura, para desenhar o polígono.
     * @param pEvent Instancia de QPaintEvent com os dados do evento.
     */
    void paintEvent(QPaintEvent *pEvent) Q_DECL_OVERRIDE;

private:

    /** Coordenadas dos vértices do polígono. */
    QVector<QPoint> m_oVertices;

    /** Vetores do centro para cada vértice do polígono. */
    QVector<QVector2D> m_oVectors;

    /** Nomes dos vértices do polígono. */
    QVector<QString> m_oNames;

    /** Coordenadas do centro do polígono. */
    QPoint m_oCenter;
};

#endif // WINDOW_H

Filing cabinet window.cpp

#include "window.h"
#include <QPainter>
#include <QPen>
#include <QPolygon>
#include <QtMath>

//-------------------------------------
Window::Window(QVector<QPoint> oVertices, QVector<QVector2D> oVectors, QVector<QString> oNames, QPoint oCenter, QWidget *pParent): QWidget(pParent)
{
    m_oVertices = oVertices;
    m_oVectors = oVectors;
    m_oNames = oNames;
    m_oCenter = oCenter;

    setBackgroundRole(QPalette::Base);
}

//-------------------------------------
void Window::paintEvent(QPaintEvent *pEvent)
{
    QPainter oPainter(this);
    oPainter.setRenderHint(QPainter::Antialiasing, true);

    int iFontHeight = oPainter.fontMetrics().height();

    QPen oNamePen; // Caneta para desenho dos nomes dos vértices
    oNamePen.setColor(QColor(0, 0, 0, 255)); // Preto
    oNamePen.setWidth(3);

    QPen oPolyPen; // Caneta para desenho do polígono formado pelos vértices
    oPolyPen.setColor(QColor(181, 230, 29, 255)); // Mesma cor da postagem no SOPT :)
    oPolyPen.setWidth(3);

    QPen oVertexPen; // Caneta para desenho dos pontos (em vértices e no centro)
    oVertexPen.setColor(QColor(255, 0, 0, 255)); // Vermelho
    oVertexPen.setWidth(8);

    QPen oVectorPen; // Caneta para desenho dos vetores
    oVectorPen.setColor(QColor(0, 0, 255, 255)); // Amarelo
    oVectorPen.setWidth(1);
    oVectorPen.setStyle(Qt::DashDotDotLine);

    // Desenha os vetores
    foreach(QVector2D vVector, m_oVectors)
    {
        // "Translada" o vetor "de volta para o centro", de forma a mudar a escala global
        // (origem no 0,0 da janela) para escala local (origem no ponto central)
        vVector = vVector + QVector2D(m_oCenter);

        oPainter.setPen(oVectorPen);
        oPainter.drawLine(m_oCenter, vVector.toPoint());
    }

    // Desenha o ponto médio
    QString sName = QString("C (%2, %3)").arg(m_oCenter.x()).arg(m_oCenter.y());
    oPainter.setPen(oVertexPen);
    oPainter.drawPoint(m_oCenter);
    oPainter.drawText(QPoint(m_oCenter.x(), m_oCenter.y() - iFontHeight), sName);

    // Desenha o polígono
    int x = 0, y = 0;
    QPolygon oPoly;

    for(int i = 0; i < m_oVertices.count(); i++)
    {
        QPoint oVertex = m_oVertices[i];
        QString sName = QString("%1 (%2, %3)").arg(m_oNames[i]).arg(oVertex.x()).arg(oVertex.y());

        QVector2D vVector = m_oVectors[i];
        double dAngle = qAtan2(vVector.y(), vVector.x());
        int iAdjust = dAngle >= 0 ? 1.5 * iFontHeight : -iFontHeight; // Posiciona o rótulo acima ou abaixo, conforme a direção do vetor

        oPainter.setPen(oNamePen);
        oPainter.drawText(QPoint(oVertex.x(), oVertex.y() + iAdjust), sName); // Desenha o nome do vértice
        oPainter.setPen(oVertexPen);
        oPainter.drawPoint(oVertex);

        oPoly.append(oVertex);
        x += oVertex.x();
        y += oVertex.y();
    }
    oPainter.setPen(oPolyPen);
    oPainter.drawPolygon(oPoly); // Desenha as linhas do polígono
}

Filing cabinet main.cpp

#include <QApplication>
#include <QtMath>
#include <QDebug>
#include <QPair>
#include "window.h"

int main(int argc, char** argv)
{
    QApplication oApp(argc, argv);

    // Define as coordenadas do polígono
    QVector<QPoint> oVertices;
    QVector<QString> oNames;
    oVertices.append(QPoint(930, 162)); oNames.append("P3");
    oVertices.append(QPoint(867, 47));  oNames.append("P2");
    oVertices.append(QPoint(247, 101)); oNames.append("P1");
    oVertices.append(QPoint(267, 238)); oNames.append("P4");

    // Calcula o ponto central (ponto médio) do polígono
    int x = 0, y = 0;
    foreach(QPoint oVertex, oVertices)
    {
        x += oVertex.x();
        y += oVertex.y();
    }
    int iVertices = oVertices.count(); // Número de vértices. No exemplo, é 4.  
    QPoint oCenter(x / iVertices, y / iVertices);

    // Calcula os vetores (do centro a cada vértice) e seus ângulos (em relação eo eixo horizontal)
    QVector<QVector2D> oVectors;
    QVector<double> oAngles;
    foreach(QPoint oVertex, oVertices)
    {
        // Aritmética vetorial, para obter o vetor indo do centro para o vértice
        // Ou, em outras palavras, o vértice tendo como origem o ponto central.
        QVector2D vVector = QVector2D(oVertex) - QVector2D(oCenter);
        oVectors.append(vVector);
    }

    // Exibe o desenho em uma janela
    Window oWindow(oVertices, oVectors, oNames, oCenter);
    oWindow.setFixedSize(1200, 400);
    oWindow.show();

    // Calcula os angulos
    qDebug() << "Angulos e Ordenacao";
    qDebug() << "-------------------";

    // Aqui tem que ser QMultimap, já que a chave são valores numéricos (ângulos) que podem
    // se repetir.
    QMultiMap<double, QPair<QString, QPoint>> mSorted;
    for(int i = 0; i < oVectors.count(); i++)
    {
        QVector2D vVector = oVectors[i];
        QString sName = oNames[i];
        QPoint oVertex = oVertices[i];

        // O arco-tangente retorna o ângulo (em radianos) do vetor com base no eixo x
        double dAngle = qAtan2(vVector.y(), vVector.x());

        qDebug("Angulo (em graus) do vetor que vai para [%s] = %3.2f", qPrintable(sName), qRadiansToDegrees(dAngle));
        mSorted.insert(dAngle, QPair<QString, QPoint>(sName, oVertex));
    }
    qDebug() << "-------------------";

    qDebug() << "Ordenacao Antes: ";
    for(int i = 0; i < oVertices.count(); i++)
        qDebug() << oNames[i] << ": (" << oVertices[i].x() << "," << oVertices[i].y() << ")";

    qDebug() << "Ordenacao Depois: ";
    QMultiMap<double, QPair<QString, QPoint>>::const_iterator it;
    for(it = mSorted.cbegin(); it != mSorted.cend(); ++it)
        qDebug() << it.value().first << ": (" << it.value().second.x() << "," << it.value().second.y() << ")";

    qDebug() << "-------------------";

    return oApp.exec();
}

This program generates the following window (with the vertices and center drawn in red, the polygon in solid green lines, and the vectors in dotted blue lines):

And print the following text output:

Angulos e Ordenacao
-------------------
Angulo (em graus) do vetor que vai para [P3] = 4.05
Angulo (em graus) do vetor que vai para [P2] = -17.24
Angulo (em graus) do vetor que vai para [P1] = -173.77
Angulo (em graus) do vetor que vai para [P4] = 161.95
-------------------
Ordenacao Antes: 
"P3" : ( 930 , 162 )
"P2" : ( 867 , 47 )
"P1" : ( 247 , 101 )
"P4" : ( 267 , 238 )
Ordenacao Depois: 
"P1" : ( 247 , 101 )
"P2" : ( 867 , 47 )
"P3" : ( 930 , 162 )
"P4" : ( 267 , 238 )
-------------------