N Les points sont donnés en entrée.Points colinéaires maximum dans un plan
Disons (x1,y1), (x2,y2)... (xn,yn).
Existe-t-il une solution non-combinatoire pour trouver le nombre maximum de points colinéaires? Peuvent-ils être disposés dans une structure de données fantaisie qui aiderait ce calcul?
Pour chaque point i, recherchez la pente sur un point j et recherchez les doublons. Les doublons peuvent être trouvés en triant les pentes et en comparant les valeurs adjacentes. Le point i est colinéaire avec les points en chaque ensemble de doublons. Gardez une trace de l'ensemble maximal que vous allez.
Pour chaque i, vous avez n-1 pentes à calculer, trier et comparer. Par conséquent, en utilisant un tri (n log n), la complexité de l'algorithme est O (n^2 log n).
Les paires de points peuvent avoir la même pente mais être parallèles plutôt que colinéaires. Vous devez regarder l'ordonnée à l'origine ainsi que la pente. –
Les pentes sont relatives au point que je suis en train d'étudier. Il n'y a donc aucune possibilité de lignes parallèles. –
Salut kotlinski, Peut-on ajouter un exemple de code? Je suis confronté à un problème dans la recherche de lignes en double. Donc, mon résultat est multiplié par le nombre de doublons. –
Lire par la discussion sur cette question here sur
suivant pourrait être une façon de le résoudre: 1) Trouver toutes les pistes en sélectionnant C (n, 2) paires 2) Bin ces pentes en plusieurs seaux. 3) Au sein de ces seaux trouvent des lignes indépendantes (car ils pourraient contenir la famille de lignes parallèles) 4) Mettre en place le plus long segment de ligne
Plus concrètement: 1) Effectuer (n-1) * (n-1) calculs pour trouver autant de pistes. Une carte pourrait être utilisée pour enregistrer ces points avec des pentes comme clés. La valeur de la carte peut être représentée à l'aide d'un ensemble. L'ensemble pourrait contenir un objet représentant deux points. Quelque chose comme ceci: { slope1: [(p1, p2), (p1, p3), (p1, p2), (p4, p5)]} { slope2: ....}
2) Maintenant, , dans chaque ensemble de points trouver des lignes indépendantes. Je crois que l'itération sur chaque point de l'ensemble, nous pouvons arriver à cela. Par exemple en visitant (p1, p2), (p1, p3), (p1, p2), (p4, p5) nous pouvons diviser cela en n-ensembles qui forment des points colinéaires. L'ensemble pourrait commencer par: [p1, p2], quand nous rencontrons la paire suivante (p1, p3), nous vérifions si l'un d'entre eux est déjà dans l'ensemble courant. Si au moins l'un d'entre eux est alors nous ajoutons les nouveaux points à cet ensemble, sinon créez un nouvel ensemble. Après itération sur tous les points de cet ensemble de points, nous aurons les deux ensembles suivants, représentant 2 segments de ligne indépendants: [p1, p2, p3] [p4, p5] La taille de ceux-ci pourrait maintenant être utilisée pour établir le le segment de ligne le plus long que nous trouvons
Complexité, cela devrait être O ((n-1) * (n-1) + n) ~ O (n^2). En supposant que rechercher des objets dans Set est O (1)
Jetez un oeil à cette question et à ses réponses: http://stackoverflow.com/questions/4179581/what-is-the-most-efficient-algorithm-to- find-a-straight-line-that-goes-through-mo – brainjam