Ceci est arrivé lorsqu'un ami a parlé d'un concours de programmation et nous nous sommes demandé quelle était la meilleure approche:
Étant donné une liste de points, trouvez le centre d'un cercle de taille prédéterminée qui couvre le plus de points. S'il y a plusieurs de tels cercles, il est seulement important de trouver l'un d'entre eux.
Exemple d'entrée: 1000 points, dans un espace 500x500 et un cercle de 60 diamètre.
4 Réponses :
idée très rapide, pas nécessairement juste un:
semble être une complexité n ^ 2, à condition que le calcul des intersections de zones en forme de cercle soit facile
La question est donc la suivante: comment calculez-nous efficacement / stocker des intersections de cercles? :)
Que diriez-vous d'utiliser un algorithme de clustering pour identifier le groupe de points. Ensuite, vérifiez le cluster avec le nombre maximum de points. Prenez le point méchant du cluster ayant le maximum de points comme centre de votre cercle, puis dessinez le cercle.
Matlab prend en charge Mise en œuvre de k-signifie algorithme et renvoie une matrice 2-D (une matrice à préciser) de des moyens de grappes et des identifiants de cluster correspondants.
Un côté basculement bien connu de K-moyen est en train de décider de K (nombre de grappes) avant la main. Cela peut être résolu mais - on peut apprendre la valeur de K des points de données. Veuillez vérifier cet papier .
J'espère que cela vous aidera.
acclamations
sauf si j'ai manqué quelque chose d'évident, je pense qu'il y a une réponse simple.
Pour une zone rectangulaire MXN, nombre de points P, rayon r:
Ceci est O (p), en supposant que p est la variable d'intérêt.
Cela fonctionne pour une grille entière, mais si les coordonnées du point sont des valeurs réelles, vous pourriez avoir un problème.
(Affiche originale) me rappelle l'une de mes bowvotes les plus injustes: Stackoverflow.com/questions/244452/... :)
@Mark - Bon point - Je pense que la même technique peut probablement toujours être appliquée si nous pensons à chaque élément de la carte en tant que "bin", mais cela peut toujours laisser des cas de bord que nous ne trouverons pas de cette méthode.
Ceci est O (p ^ 2), car le comptage naïf des points en cercles est déjà O (p).
Ma meilleure approche jusqu'à présent est:
Chaque cercle contenant des points doit avoir un point de vue gauche. Il fait donc une liste de tous les points à droite d'un point potentiellement dans les limites d'un cercle. Il trie les points de x d'abord, pour rendre le balayage sain d'esprit.
Il les trie à nouveau, cette fois par le nombre de voisins à droite qu'ils ont, de sorte que le point avec le plus de voisins obtiennent examiné d'abord.
Il examine ensuite chaque point et pour chaque point à droite, il calcule un cercle où cette paire de points est sur le périmètre gauche. Il compte ensuite les points dans un tel cercle.
Parce que les points ont été triés par potentiel, il peut tôt à la fin une fois que cela est considéré comme tous les nœuds pouvant potentiellement conduire à une meilleure solution.