Quel est l'algorithme le plus efficace pour trouver une ligne droite qui passe par la plupart des points?

la Hough Transform peut vous donner une solution approximative. Il est approximatif parce que la technique de binning a une résolution limitée dans l'espace des paramètres, de sorte que la bin maximum vous donnera une gamme limitée de lignes possibles.

si vous limitez le problème aux lignes passant par l'origine, vous pouvez convertir les points en coordonnées polaires (angle, distance de l'origine) et les Trier par angle. Tous les points avec le même angle se trouvent sur la même ligne. O (N logn)

Je ne pense pas qu'il y ait une solution plus rapide dans le cas général.

encore une solution O (N^2) avec un pseudo code. L'idée est de créer une table de hachage avec la ligne elle-même comme clé. La ligne est définie par la pente entre les deux points, le point où la ligne coupe l'axe des abscisses et le point où la ligne coupe l'axe des ordonnées.

suppose des langages comme Java, C# où la méthode égale et les méthodes hashcode de l'objet sont utilisées pour la fonction de hachage.

créer un objet (appeler SlopeObject) avec 3 champs

1. Pente // Peut être l'Infini
2. point d'interception avec axe des abscisses -- poix / / sera (infini, une certaine valeur de y) ou (valeur de x, 0)
3. Count

poix sera une paire de points (x, y). Si la ligne traverse l'axe des x, le poix (un certain nombre, 0). Si la ligne est parallèle à l'axe des abscisses, alors poix = (infini, un certain nombre) où la valeur de y est où la ligne croise l'axe des ordonnées. Outrepasser égale la méthode où 2 objets sont égales si Slope et poix sont égaux.

est remplacé par une fonction qui fournit le hashcode basé sur la combinaison des valeurs de Slope et poix . Quelques pseudo-codes en dessous de

Hashmap map;
foreach(point in the array a) {
    foeach(every other point b) {
        slope = calculateSlope(a, b);
        poix = calculateXInterception(a, b);
        SlopeObject so = new SlopeObject(slope, poix, 1); // Slope, poix and intial count 1.
        SlopeObject inMapSlopeObj = map.get(so);
        if(inMapSlopeObj == null) {
            inMapSlopeObj.put(so);
        } else {
            inMapSlopeObj.setCount(inMapSlopeObj.getCount() + 1);
        }
    }
}
SlopeObject maxCounted = getObjectWithMaxCount(map);
print("line is through " + maxCounted.poix + " with slope " + maxCounted.slope);

comme déjà mentionné, il n'y a probablement pas de meilleur moyen de résoudre le cas général de ce problème que O(N^2). Cependant, si vous supposez qu'un grand nombre de points se trouvent sur la même ligne (disons la probabilité qu'un point aléatoire dans l'ensemble des points se trouvent sur la ligne avec le nombre maximum de points est p) et que vous n'avez pas besoin d'un algorithme exact, un algorithme aléatoire est plus efficace.

maxPoints = 0
Repeat for k iterations:
    1. Pick 2 random, distinct points uniformly at random
    2. maxPoints = max(maxPoints, number of points that lies on the 
       line defined by the 2 points chosen in step 1)

Notez que dans la première étape, si vous avez choisi 2 points qui se trouve sur la ligne avec le nombre maximum de points, vous obtiendrez la solution optimale. En supposant que n soit très grand (c'est-à-dire que nous pouvons traiter la probabilité de trouver 2 points souhaitables comme un échantillonnage avec remplacement), la probabilité que cela se produise est p^2. Par conséquent, la probabilité de trouver une solution sous - optimale après les itérations k est (1-p^2)^K.

supposons que vous pouvez tolérer un taux de faux négatif = err. Cet algorithme s'exécute alors dans O(nk) = O(n * log(err) / log (1 - p^2)). Si les deux n et p sont assez grands, ce qui est beaucoup plus efficace que O(N^2). (i.e. supposez n = 1.000.000 et vous savez qu'il y a au moins 10.000 points qui se trouvent sur la même ligne. Alors n^2 serait nécessaire sur l'ampleur de 10^12 opérations, alors que randomisés algorithme exigerait sur l'ampleur de 10^9 opérations pour obtenir un taux d'erreur de moins de 5*10^-5.)

il est peu probable qu'un algorithme $o (N^2)$ existe, puisque le problème (de vérifier même si 3 points dans R^2 sont collinéaires) est 3Sum-hard ( http://en.wikipedia.org/wiki/3SUM )

ce n'est pas une solution meilleure que O(N^2), mais vous pouvez faire ce qui suit,

1. pour chaque point convertissez-le d'abord comme s'il était dans la coordonnée (0,0), puis faites la traduction équivalente pour tous les autres points en les déplaçant la même distance x,y que vous aviez besoin de déplacer le point choisi d'origine.

2.Traduire ce nouvel ensemble de points traduits à l'angle par rapport au nouveau (0,0).

3.Gardez stocké le nombre maximum (MSN) de points qui sont dans chaque angle.

4.Choisissez le nombre maximum stocké (MSN), et ce sera la solution