Discussion :

[leolio69]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[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.

[pyros]

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 ):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
  }
};

[jblecanard]

Hello

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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) +"));")

[leolio69]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
1 2 3 
4 5 6
7 8 9

J'ai utilisé ce prédicat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[Invité]

J'ai utilisé ce prédicat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[jblecanard]

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.