J'ai 2d points (x, y) avec des coordonnées flottantes, quand je les dessine, je dois grouper des points s'ils sont proches les uns des autres, et ils doivent être groupés avec iwith aide de rectangle avec taille fixe. Et le problème est que ces rectangles ne devraient pas se croiser, et tous les points-voisins devraient être groupés.
Si vous avez un papier à proximité, vous pouvez dessiner un grand rectangle, par exemple 4 * 5cm - zone où tous les points sont situés. Maintenant, mettez des points au hasard, et disons, s'il y a des points dont la distance est de 1 cm - ils devraient être groupés dans le rectangle 2 * 3.grouper des points lorsqu'ils sont proches
Je n'arrive pas à trouver d'algorithme pour le faire, et la performance compte aussi ... J'ai cherché l'imbrication, le regroupement mais ce dont j'ai besoin est un peu différent. Et en passant, si certains rectangles de regroupement doivent être hors de la zone commune pour s'adapter aux conditions, que ce soit, ce n'est pas un problème. Par exemple. vous avez la zone 4 * 5 et les points
(1,0), (2,1), (4,1), (4,3), (2,4)
THEN résultat voudrais rectangles (0,0 - 3,2) & (3,1 - 6,3) and one point left (2,4) parce que tous les autres points ont été regroupés et ce point n'a pas de voisins maintenant.
Les coordonnées de mes points ne sont pas entières mais flottantes, et le nombre de points peut être de quelques centaines (jusqu'à 500). Et je ne veux pas casser de surface sur les mêmes rectangles et juste calculer combien de points y a-t-il, je veux dire par exemple ci-dessus je pourrais faire des réfringangles (0,0 - 3,2), (3,0 - 6,2) , (0,3 - 3,6), (3,3 - 6,6) et juste résumer les points 2 pour le premier rect, 1 (!) Pour le second ce que les moyens le laisser tel quel, 1 pour le troisième et 1 pour le 4ème => un rect sera dessiné et tous les autres points => mauvais résultat selon la tâche. Des idées? Au moins quels algorithmes peuvent être utiles, où chercher ...
P.S. pour l'instant, le nombre de groupes/points dans le résultat n'a pas d'importance, e.i. un autre résultat autorisé par exemple ci-dessus pourrait être des rectangles (1,0-4,2) et (2,2-5,4), et aucun point ne reste
Les dimensions du rectangle que vous êtes autorisé à utiliser sont donc fixes et alignées sur les axes? Et je suppose que vous voulez minimiser le nombre de points qui sont laissés de côté ... correct? – Jacob
oui, les dimensions sont fixes (x * y), je ne peux pas les faire pivoter (x * y signifie x * y et je ne les change pas y * x), et elles sont alignées. A propos de la minimisation, pour l'instant non. le résultat ne doit pas contenir de points, qui ont un autre point plus proche que la distance donnée, et c'est tout – Maxym
Est-ce que ce doit être des rectangles et précis? Vous pourriez utiliser quelque chose comme k signifie clustering: http://jsfiddle.net/8NpNp/2/ – david