par "groupe", je veux dire un ensemble de pixels de sorte que chaque pixel a au moins un pixel adjacent dans le même ensemble, le dessin montre un exemple de groupe.
P>
Je voudrais trouver le pixel qui a la plus grande distance de ligne droite d'un pixel désigné (pour exemple, le pixel vert). Et la ligne droite reliant les deux pixels (la ligne rouge) ne doit pas quitter le groupe. P>
Ma solution est en boucle à travers les degrés et simulant la progression des lignes à partir du pixel vert avec le degré et voir Quelle ligne a parcouru la distance la plus éloignée. P>
longestDist = 0
bestDegree = -1
farthestX = -1
farthestY = -1
FOR EACH degree from 0 to 360
dx=longestDist * cos(degree);
dy=longestDist * sin(degree);
IF Point(x+dx , y+dy) does not belong to the group
Continue with next degree
//Because it must not be the longest line, so skip it
END IF
(farthestX , farthestY) = simulate(x,y,degree)
d = findDistance(x , y , farthestX , farthestY)
IF d > longestDist
longestDist = d
bestDegree = degree
END IF
END FOR
5 Réponses :
Premièrement, notez que la discrétisation d'angle dans votre algorithme peut dépendre de la taille de la grille. Si l'étape est trop grande, certaines cellules peuvent manquer certaines cellules, si elle est trop petite, vous finirez par vous rendre à nouveau à nouveau sur la même cellule et encore.
Je suggérerais d'énumérer les cellules de la région et de tester la condition de chacun individuellement. L'énumération peut être effectuée à l'aide d'une première recherche de largeur ou de première-profondeur (je pense que ce dernier serait préférable, car il lui permettra d'établir rapidement une liaison inférieure et de faire une élagité).
On peut conserver le point le plus éloigné X trouvé jusqu'à présent et pour chaque nouveau point de la région, vérifiez si (a) le point est plus éloigné que celui trouvé jusqu'à présent et (b) il est connecté à l'origine par une ligne droite ligne qui passe à travers les cellules de la région uniquement. Si les deux conditions sont satisfaites, mettez à jour le X, sinon continuer avec la recherche. Si l'état (A) n'est pas satisfait, la condition (b) ne doit pas être vérifiée.
La complexité de cette solution serait O (n * m) , où n est le nombre de cellules dans la région et m est la plus grande dimension de la région ( max (largeur, hauteur) ). Si la performance est essentielle, des heuristiques plus sophistiquées peuvent être appliquées, mais pour une grille de taille raisonnable, cela devrait fonctionner correctement.
recherche de pixels, pas pour la pente. Pseudocode.
bestLength = 0
for each pixel in pixels
currentLength = findDistance(x, y, pixel.x, pixel.y)
if currentLength > bestLength
if goodLine(x, y, pixel.x, pixel.y)
bestLength = currentLength
bestX = pixel.x
bestY = pixel.y
end
end
end
Cela ne gère pas l'exigence selon laquelle la ligne de connexion reste dans la région.
Je ne travaillerais pas avec des angles. Mais je suis presque sûr que la plus grande distance sera toujours comprise entre deux pixels au bord de l'ensemble, je trace ainsi le contour: de n'importe quel pixel dans l'ensemble, allez dans n'importe quelle direction jusqu'à atteindre le bord de l'ensemble. Puis déplacez-vous (couter) dans le sens des aiguilles d'une montre sur le bord. Faites cela avec n'importe quel pixel comme point de départ et vous pourrez trouver la plus grande distance. C'est toujours assez gourmand, mais je pensais que cela pourrait vous donner un point de départ alternatif pour améliorer.
Editer: Ce qui vient de venir à mon esprit: lorsque vous avez un pixel de départ EDIT2: et si vous appuyez sur un Edit3: Utilisez la méthode ci-dessus pour rechercher le premier Disclaimer: Ceci n'est pas testé et ne sont que des idées du sommet de ma tête, aucun dessin n'a été apporté pour justifier mes revendications et tout ce qui pourrait être faux (c'est-à-dire en réfléchir par vous-même avant de la mettre en œuvre; D) s et le pixel de fin E . Dans la première itération utilisant S le E correspondant sera adjacent (le suivant le long du bord dans le sens des aiguilles d'une montre). Comme vous pouvez itérer le bord, le boîtier pourrait survenir, qu'il n'y a pas de ligne droite à travers l'ensemble entre S et E . Dans ce cas, la ligne touchera une autre partie du bord de la consigne (le pixel p ). Vous pouvez continuer l'itération du bord à ce pixel ( e = p )
p , vous saurez qu'il ne peut y avoir plus de distance entre s et E dans le Itération suivante de S Vous pouvez ignorer cette partie du bord (entre s et p ) et démarrez sur p encore.
p . Prenez ce p comme suivant s et continue. Répétez la répétition jusqu'à atteindre votre premier P à nouveau. La distance maximale sera comprise entre deux de ces P sauf si le bord de l'ensemble est convexe dans quel cas vous ne trouverez pas un p .
Utilisez une double structure de données:
traversez l'angle trié et recherchez chaque pixel que la ligne est dans la région. Certains pixels auront le même angle. Vous pouvez donc vous rendre de l'origine le long de la ligne et aller jusqu'à votre sortie de la région. Vous pouvez éliminer tous les pixels qui sont au-delà de ce point. En outre, si la distance maximale augmentait, retirez tous les pixels qui ont une distance plus courte.
Traitez votre région en tant que polygone au lieu d'une collection de pixels. À partir de là, vous pouvez obtenir une liste de segments de ligne (les bords de votre polygone).
Dessinez une ligne de votre pixel de départ à chaque pixel que vous vérifiez. La ligne la plus longue qui ne coupe aucun des segments de ligne de votre polygone indique votre pixel le plus distant accessible par une ligne droite de votre pixel.
Il y a diverses optimisations que vous pouvez apporter à cela et quelques cas d'arêtes à vérifier, mais laissez-moi savoir si vous comprenez l'idée avant que je poste ces ... En particulier, comprenez-vous ce que je veux dire en traitant en tant que polygone Au lieu d'une collection de pixels?
Pour ajouter, cette approche sera nettement plus rapide que toute approche ou approche basée sur l'angle nécessitant une "marche" pour toutes les plus petites collections de pixels. Vous pouvez optimiser davantage car votre problème est équivalent à la recherche du point d'extrémité le plus distant d'un bord de polygone pouvant être atteint via une ligne droite ininterrite de votre point de départ. Cela peut être fait dans O (n ^ 2), où n est le nombre de bords. Notez que N aura beaucoup plus petit que le nombre de pixels et de nombreux algorithmes proposés que l'on utilise des angles une itération d'une / ou de pixels dépendra au lieu du nombre de pixels.
Notez que vous pouvez supprimer des calculs pour tous les pixels intérieurs.
Et vous n'avez pas besoin d'utiliser des angles. Vous avez juste besoin d'utiliser le théorème de Pythagore;)
@Dfens: "pixels intérieurs" - pourquoi? L'un d'entre eux pourrait être la solution.
@Karoly Horvath: Je comprends le problème que nous recherchons deux pixels les plus éloignés? Les pixels intérieurs ne seraient donc pas une solution?