Classificar Four Points em sentido horário Order

Question

aponta Quatro 2D em uma matriz. Eu preciso classificá-los em ordem no sentido horário. Eu acho que isso pode ser feito com a operação apenas uma troca, mas eu não tenho sido capaz de colocar este para baixo formalmente.

Edit: Os quatro pontos são um polígono convexo no meu caso

.

Edit: Os quatro pontos são os vértices de um polígono convexo. Eles não precisam estar em ordem.

Answer 1

Se você quiser dar uma perspectiva mais matemática, podemos considerar as permutações de 4 pontos

No nosso caso, existem 4 permutações que estão em ordem no sentido horário

A B C D
B C D A
C D A B
D A B C

Todas as outras permutações possíveis pode ser convertido em uma dessas formas com 0 ou 1 swaps. (Eu só irá considerar permutações começando com A, como é simétrico)

1. A B C D - feito
2. A B D C - troca C e D
3. A C B D - troca B e C
4. A C D B - troca de A e B
5. A D B C - troca de A e D
6. A D C B - troca B e D

Assim, apenas uma troca é sempre necessária - mas pode levar algum trabalho para identificar quais

.

Ao olhar para os primeiros três pontos, e verificar o sinal da área assinada do ABC, podemos determinar se eles são no sentido horário ou não. Se eles são no sentido horário, então estamos no caso 1 2 ou 5

para distinguir entre esses casos, temos de verificar mais dois triângulos -. Se ACD é no sentido horário, em seguida, podemos estreitar esse baixo para o caso 1, caso contrário, deve ser no caso de 2 ou 5

Para escolher entre os casos 2 e 5, podemos testar ABD

Podemos verificar para o caso de ABC anti-horário semelhante.

No pior caso, temos de testar 3 triângulos.

Se os seus pontos não são convexas, você iria encontrar o ponto dentro, tipo o resto e, em seguida, adicioná-lo em qualquer borda. Note-se que, se o quad é convexo, em seguida, 4 pontos não determinar de forma exclusiva o quad, existem 3 quads igualmente válidas.

Answer 2

Um par de pena pensamentos considerando aqui;

• No sentido horário só é significativa no que diz respeito a uma origem. Eu tenderia a pensar na origem como o centro de gravidade de um conjunto de pontos. por exemplo. No sentido horário em relação a um ponto na posição média dos quatro pontos, ao invés da origem, possivelmente, muito distante.

• Se você tem quatro pontos, a, b, c, d, existe vários ordenamentos horário desses pontos em torno de sua origem. Por exemplo, se (a, b, c, d) formada uma ordenação dos ponteiros do relógio, de modo que seria (b, c, d, a), (c, d, a, b) e (d, a, b, c)

• Faça o seu quatro pontos já formam um polígono? Se assim for, é uma questão de verificação e invertendo o enrolamento, em vez de triagem os pontos, por exemplo a, b, c, d, torna-se d, c, b, um. Se não, eu iria classificar com base na junção tendo entre cada ponto ea origem, como por resposta Cunhas.

Editar: sobre seus comentários em que pontos a troca;

No caso de um triângulo (a, b, c), podemos dizer que é no sentido horário se o terceiro ponto c , está no lado direito da linha de ab . Eu uso a seguinte função de um lado para determinar isso com base em coordenadas do ponto;

int side(double x1,double y1,double x2,double y2,double px,double py)
{
 double dx1,dx2,dy1,dy2;
 double o;

 dx1 = x2 - x1;
 dy1 = y2 - y1;
 dx2 = px - x1;
 dy2 = py - y1;
 o = (dx1*dy2)-(dy1*dx2);
 if (o > 0.0) return(LEFT_SIDE);
 if (o < 0.0) return(RIGHT_SIDE);
 return(COLINEAR);
}

Se eu tiver um polígono convexo de quatro pontos, (a, b, c, d), eu posso considerar isso como dois triângulos, (a, b, c) e (c, d, A). Se (a, b, c) é no sentido contrário, que se altera o enrolamento (a, b, c, d) a (a, d, c, b) para alterar o enrolamento do polígono como um todo para a direita.

Eu sugiro fortemente desenho isso com alguns pontos de amostragem, para ver o que eu estou falando. Note que você tem um monte de casos excepcionais para lidar com, como polígonos côncavos, pontos colineares, pontos coincidentes, etc ...

Answer 3

Se alguém estiver interessado, aqui está a minha solução rápida e suja de um problema similar.

Meu problema era ter meus cantos do retângulo ordenou na seguinte ordem:

canto superior esquerdo> superior direito> inferior direito> inferior esquerda

Basicamente é sentido horário a partir do canto superior esquerdo.

A idéia do algoritmo é:

Order os cantos por linhas e, em seguida, ordem de canto-pares por cols.

// top-left = 0; top-right = 1; 
// right-bottom = 2; left-bottom = 3;
List<Point> orderRectCorners(List<Point> corners) {    
    if(corners.size() == 4) {    
        ordCorners = orderPointsByRows(corners);

        if(ordCorners.get(0).x > ordCorners.get(1).x) { // swap points
            Point tmp = ordCorners.get(0);
            ordCorners.set(0, ordCorners.get(1));
            ordCorners.set(1, tmp);
        }

        if(ordCorners.get(2).x < ordCorners.get(3).x) { // swap points
            Point tmp = ordCorners.get(2);
            ordCorners.set(2, ordCorners.get(3));
            ordCorners.set(3, tmp);
        }               
        return ordCorners;
    }    
    return empty list or something;
}

List<Point> orderPointsByRows(List<Point> points) {
    Collections.sort(points, new Comparator<Point>() {
        public int compare(Point p1, Point p2) {
        if (p1.y < p2.y) return -1;
        if (p1.y > p2.y) return 1;
        return 0;
        }
    });
    return points;
}

Answer 4

Oliver está certo. Este código (comunidade wikified) gera e classifica todas as combinações possíveis de uma série de 4 pontos.

#include <cstdio>
#include <algorithm>

struct PointF {
    float x;
    float y;
};

// Returns the z-component of the cross product of a and b
inline double CrossProductZ(const PointF &a, const PointF &b) {
    return a.x * b.y - a.y * b.x;
}

// Orientation is positive if abc is counterclockwise, negative if clockwise.
// (It is actually twice the area of triangle abc, calculated using the
// Shoelace formula: http://en.wikipedia.org/wiki/Shoelace_formula .)
inline double Orientation(const PointF &a, const PointF &b, const PointF &c) {
    return CrossProductZ(a, b) + CrossProductZ(b, c) + CrossProductZ(c, a);
}

void Sort4PointsClockwise(PointF points[4]){
    PointF& a = points[0];
    PointF& b = points[1];
    PointF& c = points[2];
    PointF& d = points[3];

    if (Orientation(a, b, c) < 0.0) {
        // Triangle abc is already clockwise.  Where does d fit?
        if (Orientation(a, c, d) < 0.0) {
            return;           // Cool!
        } else if (Orientation(a, b, d) < 0.0) {
            std::swap(d, c);
        } else {
            std::swap(a, d);
        }
    } else if (Orientation(a, c, d) < 0.0) {
        // Triangle abc is counterclockwise, i.e. acb is clockwise.
        // Also, acd is clockwise.
        if (Orientation(a, b, d) < 0.0) {
            std::swap(b, c);
        } else {
            std::swap(a, b);
        }
    } else {
        // Triangle abc is counterclockwise, and acd is counterclockwise.
        // Therefore, abcd is counterclockwise.
        std::swap(a, c);
    }
}

void PrintPoints(const char *caption, const PointF points[4]){
    printf("%s: (%f,%f),(%f,%f),(%f,%f),(%f,%f)\n", caption,
        points[0].x, points[0].y, points[1].x, points[1].y,
        points[2].x, points[2].y, points[3].x, points[3].y);
}

int main(){
    PointF points[] = {
        {5.0f, 20.0f},
        {5.0f, 5.0f},
        {20.0f, 20.0f},
        {20.0f, 5.0f}
    };

    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(j == i)  continue;
            for(int k = 0; k < 4; k++){
                if(j == k || i == k) continue;
                for(int l = 0; l < 4; l++){
                    if(j == l || i == l || k == l) continue;
                    PointF sample[4];
                    sample[0] = points[i];
                    sample[1] = points[j];
                    sample[2] = points[k];
                    sample[3] = points[l];

                    PrintPoints("input: ", sample);
                    Sort4PointsClockwise(sample);
                    PrintPoints("output: ", sample);
                    printf("\n");
                }
            }
        }
    }

    return 0;
}

Answer 5

Calcular a área a partir das coordenadas com a fórmula agulheta (desprovido do valor absoluto de tal modo que a área pode ser positiva ou negativa) para os pontos permutações. Os valores de área máxima parece corresponder à quadriláteros diretos simples: quadriláteros diretos simples encontrado com a fórmula cadarço

Answer 6

Work it out o caminho mais longo, em seguida, otimizá-lo.

Um problema mais específico seria a de classificar as coordenadas, diminuindo o ângulo em relação ao eixo x positivo. Este ângulo, em radianos, será dada por esta função:

x>0
    AND y >= 0
       angle = arctan(y/x)
    AND y < 0
       angle = arctan(y/x) + 2*pi
x==0
    AND y >= 0
       angle = 0
    AND y < 0
       angle = 3*pi/2
x<0
    angle = arctan(y/x) + pi

Então, é claro, é apenas uma questão de classificar as coordenadas pelo ângulo. Note-se que arctan (w)> arctan (z) se e somente se x> z, para que possa optimizar uma função que compara ângulos uns aos outros muito facilmente.

ordem de tal modo que o ângulo é monótona decrescente ao longo de uma janela (ou de tal modo que ele aumenta no máximo uma vez) é um pouco diferente.

Em vez de um uma extensa prova eu ??vou falar que eu verificado que uma única operação de swap vai tipo 4 2D pontos no sentido horário. Determinar qual operação de swap é necessário é o truque, é claro.

Answer 7

Eu tenho uma melhoria adicional a acrescentar à minha resposta anterior

lembre-se -. Estes são os casos podemos estar em

1. A B C D
2. A B D C
3. A C B D
4. A C D B
5. A D B C
6. A D C B

Se ABC é anti-horário (tem negativo área assinado), então estamos nos casos 3, 4, 6. Se trocar B & C neste caso, em seguida, ficamos com as seguintes possibilidades:

1. A B C D
2. A B D C
3. A B C D
4. A B D C
5. A D B C
6. A D B C

Em seguida, podemos verificar se há ABD e swap B & D se é anti-horário (casos 5, 6)

1. A B C D
2. A B D C
3. A B C D
4. A B D C
5. A B D C
6. A B D C

Finalmente, precisamos verificar ACD e swap C & D se ACD é anti-horário. Agora sabemos que os nossos pontos são tudo em ordem.

Este método não é tão eficiente quanto o meu método anterior - isto requer 3 cheques a cada tempo, e mais do que uma troca; mas o código seria muito mais simples.

Answer 8

var arr = [{x:3,y:3},{x:4,y:1},{x:0,y:2},{x:5,y:2},{x:1,y:1}];
var reference = {x:2,y:2};
arr.sort(function(a,b)  {
    var aTanA = Math.atan2((a.y - reference.y),(a.x - reference.x));
    var aTanB = Math.atan2((b.y - reference.y),(b.x - reference.x));
    if (aTanA < aTanB) return -1;
    else if (aTanB < aTanA) return 1;
    return 0;
});
console.log(arr);

Quando o ponto de referência está dentro do polígono.

Mais informações neste href="http://social.msdn.microsoft.com/Forums/en/csharplanguage/thread/c4c0ce02-bbd0-46e7-aaa0-df85a3408c61" local

Answer 9

Se você só precisa lidar com 4 pontos, então há uma maneira mais fácil de fazer isso

1. ordenar por valor y

2. linha superior é os dois primeiros pontos, linha de baixo é o restante 2 pontos

3. para linha superior e inferior, classificá-los por valor x

.

corners.sort(key=lambda ii: ii[1], reverse=True)
topRow = corners[0:2]
bottomRow = corners[2:]

topRow.sort(key=lambda ii: ii[0])
bottomRow.sort(key=lambda ii: ii[0])
# clockwise
return [topRow[0], topRow[1], bottomRow[1], bottomRow[0]]

Answer 10

Eu acredito que você está certo de que uma única troca pode garantir que um polígono representado por quatro pontos no plano é convexo. As questões que ainda precisam ser respondidas são:

• É este conjunto de quatro pontos convexo polígono?
• Se não, então que dois pontos precisam ser trocados?
• Que direção é no sentido horário?

Após uma reflexão mais aprofundada, eu acho que a única resposta para a segunda pergunta acima é "os dois do meio".

Answer 11

Como sobre isso?

// Take signed area of ABC.
// If negative,
//     Swap B and C.
// Otherwise,
//     Take signed area of ACD.
//     If negative, swap C and D.

Idéias?

Answer 12

Você deve dar uma olhada na digitalização do Graham. Claro que você vai precisar para adaptá-lo, uma vez que encontra a pontos anti-horário.

P.S: Este pode ser um exagero para 4 pontos, mas se o número de pontos de aumentá-lo poderia ser interessante

Answer 13

if AB crosses CD
   swap B,C
elif AD crosses BC
   swap C,D

if area (ABC) > 0
   swap B,D

(I mean area(ABC) > 0 when A->B->C is counter-clockwise).
Let p*x + q*y + r = 0 be the straight line that joins A and B.
Then AB crosses CD if  p*Cx + q*Cy + r  and  p*Dx + q*Dy + r
have different sign, i.e. their product is negative.

O primeiro 'if / elif' traz os quatro pontos em sentido horário ou sentido anti-horário. (Desde seu polígono é convexo, a única outra alternativa 'cruzamento' é 'AC atravessa BD', o que significa que os quatro pontos já estão classificadas.) A última 'se' inverte orientação sempre que é anti-horário.

Answer 14

se assumirmos que ponto x é maior do que o ponto y se o ângulo que tem com o ponto (0,0) é maior, então nós podemos implementar isso dessa maneira no c #

    class Point : IComparable<Point>
    {
        public int X { set; get; }
        public int Y { set; get; }

        public double Angle
        {
            get
            {
                return Math.Atan2(X, Y);
            }
        }

        #region IComparable<Point> Members

        public int CompareTo(Point other)
        {
            return this.Angle.CompareTo(other.Angle);
        }

        #endregion

        public static List<Point>  Sort(List<Point> points)
        {
            return points.Sort();
        }
}

Answer 15

A resposta de Wedge está correto.

Para implementá-lo facilmente, acho que da mesma forma que smacl: você precisa encontrar o centro do limite e traduzir os seus pontos para que o centro

.

Como esta:

centerPonintX = Min(x) + (  (Max(x) – Min(x)) / 2  )
centerPonintY = Min(y) + (  (Max(y) – Min(y)) / 2  )

Em seguida, diminuir centerPointX e centerPointY de cada poin, a fim de traduzi-lo para a origem do limite.

Finalmente, aplique a solução da Cunha com apenas um toque:. Obter o valor absoluto de arctan (x / y) para cada instância (trabalhou para mim dessa forma)

Answer 16

if( (p2.x-p1.x)*(p3.y-p1.y) > (p3.x-p1.x)*(p2.y-p1.y) )
    swap( &p1, &p3 );

O '>' pode estar enfrentando o caminho errado, mas você começa a idéia.