Trier quatre points dans le sens des aiguilles d'une montre
https://stackoverflow.com/questions/242404
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quatre points 2D dans un tableau. Je dois les trier dans le sens des aiguilles d'une montre. Je pense que cela peut être fait en une seule opération d’échange, mais je n’ai pas pu le noter formellement.
Edit: les quatre points sont un polygone convexe dans mon cas.
Modifier: les quatre points sont les sommets d’un polygone convexe. Ils n'ont pas besoin d'être en ordre.
La solution
Si vous souhaitez adopter une perspective plus mathématique, nous pouvons considérer les permutations de 4 points
Dans notre cas, il y a 4 permutations qui sont dans le sens des aiguilles d'une montre
A B C D
B C D A
C D A B
D A B C
Toutes les autres permutations possibles peuvent être converties en l'une de ces formes avec 0 ou 1 swaps. (Je ne considérerai que les permutations commençant par A, car elles sont symétriques)
- A B C D - terminé
- A B D C - échangez C et D
- A C B D - permuter B et C
- A C D B - permuter A et B
- A D B C - échangez A et D
- A D C B - permuter B et D
Ainsi, un seul échange est nécessaire, mais il vous faudra peut-être un peu de travail pour identifier lequel.
En examinant les trois premiers points et en vérifiant le signe de la zone signée de ABC, nous pouvons déterminer s’ils sont dans le sens des aiguilles d’une montre ou non. Si elles sont dans le sens des aiguilles d'une montre, nous sommes dans le cas 1 2 ou 5
pour faire la distinction entre ces cas, nous devons vérifier deux autres triangles - si ACD est dans le sens des aiguilles d'une montre, nous pouvons le réduire au cas 1, sinon nous devons être dans le cas 2 ou 5.
Pour choisir entre les cas 2 et 5, nous pouvons tester ABD
Nous pouvons vérifier le cas de ABC dans le sens inverse des aiguilles d'une montre.
Dans le pire des cas, nous devons tester 3 triangles.
Si vos points ne sont pas convexes, vous devez trouver le point intérieur, trier le reste et l'ajouter ensuite à n'importe quel bord. Notez que si le quad est convexe, alors 4 points ne le déterminent plus de manière unique, il existe 3 quadruples de valeur équivalente.
Autres conseils
Quelques réflexions intéressantes à considérer ici;
-
Dans le sens des aiguilles d'une montre n'a de sens que par rapport à une origine. J'aurais tendance à penser à l'origine comme centre de gravité d'un ensemble de points. par exemple. Dans le sens des aiguilles d'une montre par rapport à un point situé à la position moyenne des quatre points, plutôt qu'à l'origine peut-être très éloignée.
-
Si vous avez quatre points, a, b, c, d, il existe plusieurs ordres dans le sens des aiguilles d'une montre de ces points autour de votre origine. Par exemple, si (a, b, c, d) forme un ordre dans le sens des aiguilles d’une montre, il en va de même pour (b, c, d, a), (c, d, a, b) et (d, a, b, c)
-
Vos quatre points forment-ils déjà un polygone? Si tel est le cas, il s’agit de vérifier et d’annuler le remontage plutôt que de trier les points, par ex. a, b, c, d devient d, c, b, a. Sinon, je trierais en fonction du relèvement de la jonction entre chaque point et l'origine, conformément à la réponse Wedges.
Modifier: vos commentaires sur les points à échanger;
Dans le cas d'un triangle (a, b, c), on peut dire que c'est dans le sens des aiguilles d'une montre si le troisième point c se situe à droite de la ligne ab . J'utilise la fonction latérale suivante pour déterminer cela en fonction des coordonnées du point;
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);
}
Si j’ai un polygone convexe à quatre points (a, b, c, d), je peux le considérer comme deux triangles (a, b, c) et (c, d, a). Si (a, b, c) est dans le sens anti-horaire, je change l'enroulement (a, b, c, d) en (a, d, c, b) pour changer l'enroulement du polygone dans son ensemble dans le sens des aiguilles d'une montre.
Je suggère fortement de dessiner ceci avec quelques exemples de points, pour voir de quoi je parle. Notez que vous avez beaucoup de cas exceptionnels à traiter, tels que des polygones concaves, des points colinéaires, des points coïncidents, etc ...
Si quelqu'un est intéressé, voici ma solution rapide et sale à un problème similaire.
Mon problème était de commander mes coins rectangulaires dans l'ordre suivant:
en haut à gauche > en haut à droite > en bas à droite > en bas à gauche
Fondamentalement, il s’agit du sens des aiguilles d’une montre en partant du coin supérieur gauche.
L'idée de l'algorithme est la suivante:
Triez les coins par rangées, puis par paires de coins, par colonne.
// 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;
}
Oliver a raison. Ce code (wikified community) génère et trie toutes les combinaisons possibles d’un tableau de 4 points.
#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;
}
Calculez la surface à partir des coordonnées avec la formule de lacet de chaussure (sans tenir compte de la valeur absolue telle que la surface puisse être positive ou négative) pour chaque permutation de points. Les valeurs de surface maximales semblent correspondre à des quadrilatères simples directs: Quadrilatères directs simples trouvés avec la formule de lacet
Calculez le long chemin puis optimisez-le.
Un problème plus spécifique serait de trier les coordonnées par angle décroissant par rapport à l’axe des x positif. Cet angle, en radians, sera donné par cette fonction:
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
Ensuite, bien sûr, il suffit de trier les coordonnées par angle. Notez que arctan (w) > arctan (z) si et seulement si x > z, afin que vous puissiez optimiser une fonction qui compare les angles les uns aux autres assez facilement.
Trier un peu de manière à ce que l'angle décroissant de façon monotone sur une fenêtre (ou qu'il augmente au maximum une fois) est un peu différent.
Au lieu d’une preuve détaillée, je mentionnerai que j’ai vérifié qu’une seule opération d’échange trierait 4 points 2D dans le sens des aiguilles d’une montre. Déterminer quelle opération de swap est nécessaire est bien sûr l’astuce.
J'ai encore une amélioration à ajouter à ma réponse précédente
rappelez-vous - ce sont les cas dans lesquels nous pouvons être.
- A B C D
- A B D C
- A C B D
- A C D B
- A D B C
- A D C B
Si ABC est dans le sens inverse des aiguilles d'une montre (la zone signée négative), nous sommes dans les cas 3, 4, 6. Si nous échangeons B & amp; C dans ce cas, il nous reste alors les possibilités suivantes:
- A B C D
- A B D C
- A B C D
- A B D C
- A D B C
- A D B C
Ensuite, nous pouvons vérifier si ABD est actif et échanger B & amp; D si c'est dans le sens anti-horaire (cas 5, 6)
- A B C D
- A B D C
- A B C D
- A B D C
- A B D C
- A B D C
Enfin, nous devons vérifier ACD et permuter C & amp; D si ACD est dans le sens antihoraire. Nous savons maintenant que tous nos points sont recevables.
Cette méthode n’est pas aussi efficace que la méthode précédente. Elle nécessite 3 contrôles à chaque fois et plus d’un échange. mais le code serait beaucoup plus simple.
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);
Où le point de référence est situé à l'intérieur du polygone.
Plus d'informations sur ce site <> / a>
si vous avez juste besoin de gérer 4 points, il existe un moyen très simple de le faire
-
trier par valeur y
-
la ligne du haut représente les deux premiers points, la ligne du bas représente les 2 points restants
-
pour les rangées supérieure et inférieure, triez-les par valeur 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]]
Je pense que vous avez raison de dire qu’un seul échange peut garantir qu’un polygone représenté par quatre points dans le plan est convexe. Les questions qui restent à répondre sont les suivantes:
- Cet ensemble de quatre points est-il un polygone convexe?
- Si non, quels sont les deux points à échanger?
- Quelle direction est dans le sens des aiguilles d'une montre?
Après réflexion, je pense que la seule réponse à la deuxième question ci-dessus est "les deux du milieu".
Comment ça?
// Take signed area of ABC.
// If negative,
// Swap B and C.
// Otherwise,
// Take signed area of ACD.
// If negative, swap C and D.
Des idées?
Vous devriez jeter un coup d'œil au scan de Graham. Bien sûr, vous devrez l’adapter car il trouve des points dans le sens anti-horaire.
p.s: Cela pourrait être excessif pour 4 points, mais si le nombre de points augmente, cela pourrait être intéressant
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.
Le premier 'if / elif' amène les quatre points dans le sens horaire ou dans le sens inverse des aiguilles d'une montre. (Comme votre polygone est convexe, la seule autre alternative "croisement" est "AC croise BD", ce qui signifie que les quatre points sont déjà triés.) Le dernier 'si' inverse l'orientation chaque fois que c'est dans le sens inverse des aiguilles d'une montre.
si nous supposons que le point x est plus grand que le point y si l'angle qu'il a avec le point (0,0) est plus grand, nous pouvons l'implémenter de cette façon en 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();
}
}
La réponse de Wedge est correcte.
Pour le mettre en œuvre facilement, je pense de la même manière que smacl: vous devez trouver le centre de la frontière et traduire vos points en ce centre.
Comme ceci:
centerPonintX = Min(x) + ( (Max(x) – Min(x)) / 2 )
centerPonintY = Min(y) + ( (Max(y) – Min(y)) / 2 )
Ensuite, diminuez centerPointX et centerPointY de chaque point pour le traduire en origine.
Enfin, appliquez la solution de Wedge en un tour de main: obtenez la valeur absolue d’arctan (x / y) pour chaque instance (cela a fonctionné pour moi de cette façon).
if( (p2.x-p1.x)*(p3.y-p1.y) > (p3.x-p1.x)*(p2.y-p1.y) )
swap( &p1, &p3 );
Le '>' peut être confronté à la mauvaise façon, mais vous avez l'idée.
