Tri d'un vecteur de point 2D de gauche à droite et de bas en haut

Version imprimable

Bonjour,

J'ai un vecteur de points que je souhaite trier de gauche à droite et de bas en haut.

Pour l'instant, j'arrive à le trier de façon symétrique en définissant ma propre fonction de tri que je donne à std::sort. J'utilise une distance non signée.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 struct sortLeftUpRightDown { inline bool operator() (const cv::Point & m1, const cv::Point & m2) const { // diagonale float vx = m2.x - m1.x; float vy = m2.y - m1.y; if(vx+vy<0) return true; else return false; } };
Lorsque je tente d'implémenter une fonction de tri de gauche à droite et de bas en haut. J'ai std::sort() qui plante. J'ai tenté ceci :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 struct sortLeftUpRightDown { inline bool operator() (const cv::Point & m1, const cv::Point & m2) const { // diagonale float vx = m2.x - m1.x; float vy = m2.y - m1.y; if(vy<0) return true; else if(vx<0) return true; else return false; } };
Si vous avez une réponse à mon problème, je suis preneur.

13/10/2011, 12h52
stardeath

bonjour,

déjà il faut définir ce que tu appelles haut, bas, gauche et droite, ou plus concrètement comment est ton repère de points, sinon, pas de tri possible.

ensuite pour un tri de ce genre, je verrai plutôt comparer les coordonnées directement et pas une différence.

Salut,

Je pense qu'un tri lexicographique devrait marcher. Ton prédicat devrait avoir cette tête là (pas testé, donc à ajuster en conséquence :P):
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 struct sortLeftUpRightDown { inline bool operator() (const cv::Point & m1, const cv::Point & m2) const { if ( m1.y < m2.y ) return true if ( m1.y == m2.y && m1.x < m2.x ) return true; return false; } };

Hello

Je confirme que tu n'as pas rédigé le prédicat correctement. Voici une version qui marche :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <vector>
#include <algorithm>
#include <iostream>
 
namespace cv
{
  struct Point
  {
    Point(int iX, int iY) : x(iX), y(iY) {}
    int x;
    int y;
  };
}
 
struct sortLeftUpRightDown
{
  inline bool operator() (const cv::Point & m1, const cv::Point & m2) const
  {
    float vx = m2.x - m1.x;
    float vy = m2.y - m1.y;
 
    if(vx == 0)
      return vy >0;
    else
      return vx > 0;
  }
};
 
 
 
int main(int argc, char* argv[])
{ 
  std::vector< cv::Point > points;
  points.push_back(cv::Point(3,-2));
  points.push_back(cv::Point(1,8));
  points.push_back(cv::Point(5,8));
  points.push_back(cv::Point(-7,8));
  points.push_back(cv::Point(-6,-8));
  points.push_back(cv::Point(6,6));
  points.push_back(cv::Point(-4,8));
  points.push_back(cv::Point(-10,7));
  points.push_back(cv::Point(-2,0));
  points.push_back(cv::Point(0,-5));
  points.push_back(cv::Point(-1,1));
  points.push_back(cv::Point(4,-7));
  points.push_back(cv::Point(-7,0));
  points.push_back(cv::Point(6,-1));
  points.push_back(cv::Point(0,-7));
  points.push_back(cv::Point(3,-9));
  points.push_back(cv::Point(3,2));
  points.push_back(cv::Point(7,-9));
  points.push_back(cv::Point(-5,9));
  points.push_back(cv::Point(7,-7));
  points.push_back(cv::Point(-7,8));
  points.push_back(cv::Point(-4,4));
  points.push_back(cv::Point(-9,-9));
  points.push_back(cv::Point(0,8));
  points.push_back(cv::Point(-10,-6));
  points.push_back(cv::Point(-3,9));
  points.push_back(cv::Point(8,-7));
  points.push_back(cv::Point(2,-8));
  points.push_back(cv::Point(4,9));
  points.push_back(cv::Point(-10,6));
  points.push_back(cv::Point(1,-7));
  points.push_back(cv::Point(9,-10));
  points.push_back(cv::Point(6,-7));
  points.push_back(cv::Point(5,-1));
  points.push_back(cv::Point(-9,-7));
  points.push_back(cv::Point(4,7));
  points.push_back(cv::Point(3,-3));
  points.push_back(cv::Point(-10,-9));
  points.push_back(cv::Point(8,3));
  points.push_back(cv::Point(1,-3));
  points.push_back(cv::Point(1,6));
  points.push_back(cv::Point(6,7));
  points.push_back(cv::Point(-7,-9));
  points.push_back(cv::Point(9,-3));
  points.push_back(cv::Point(-3,3));
  points.push_back(cv::Point(5,7));
  points.push_back(cv::Point(5,-8));
  points.push_back(cv::Point(8,-4));
  points.push_back(cv::Point(9,-3));
  points.push_back(cv::Point(-5,6));
 
  std::sort(points.begin(), points.end(), sortLeftUpRightDown() );
 
  for(std::vector<cv::Point>::iterator it = points.begin(); it != points.end(); it++)
    std::cout << "Point(" << it->x << "," << it->y << ")" << std::endl;
 
  return 0;
}

Edit : Celui de Pyros est correct mais trie de bas en haut et ensuite de gauche à droite.
Edit 2 : Pour ceux qui se demandent si je me suis farci la liste de points, à la main, la réponse est non. J'ai lancé ce trivial script python :

Code:

1
2
3
4
5
6
import random
 
for i in range(0,50):
    x = random.choice(range(-10,10))
    y = random.choice(range(-10,10))
    print("points.push_back(cv::Point(" + str(x) + "," + str(y) +"));")

J'ai utilisé le prédicat cité juste au dessus et il fonctionne bien si les valeurs sont sur une grille avec des valeurs entières fixes.

Mon soucis est que j'utilise maintenant des floats est que souhaite les associer à une grille (tableau) pour effectuer mon rangement.

Le sens de tri est le suivant :
Code:

1 2 3 4 1 2 3 4 5 6 7 8 9
J'ai utilisé ce prédicat :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 struct sortHorizontalMotif { inline bool operator() (const InfoMotif & m1, const InfoMotif & m2) const { if ( m1.bc.y < m2.bc.y ) return true; if ( fabs(m1.bc.y-m2.bc.y)<5 && m1.bc.x < m2.bc.x ) return true; return false; } };
J'ai rajouté un intervalle sur les Y mais la fonction std::sort plante dans certains cas.

Avez-vous une idée ?

26/10/2011, 10h03
Invité
Citation:
Envoyé par leolio69

J'ai utilisé ce prédicat :

Code:

1 2 3 4 if ( m1.bc.y < m2.bc.y ) return true; (1) if ( fabs(m1.bc.y-m2.bc.y)<5 && m1.bc.x < m2.bc.x ) return true; (2) return false;

Avez-vous une idée ?
Si tu utilises le sort de la stl, je pense que le problème vient de ce que ton prédicat n'est pas une relation d'ordre.

Par exemple si tes points sont (2,3) (1,4), tu as

(2,3) < (1,4) : parce que 3<4, c'est ta clause 1
mais également
(1,4) < (2,3), parce que fabs(4-3)<5 et 1<2,

Dans ces conditions, le tri n'est pas possible, et sort va perdre les pédales (et planter)

Francois
26/10/2011, 14h12
jblecanard

Citation:

Envoyé par fcharton

Si tu utilises le sort de la stl, je pense que le problème vient de ce que ton prédicat n'est pas une relation d'ordre.

Absolument ! Voir le wiki. D'ailleurs je ne comprend pas ce que tu essayes de faire avec ta grille.