trouver des points valides dans un espace 2D avec des restrictions sur des régions arbitraires

Question

J'ai un espace 2D de précision double avec des régions (arbitrairement définies, principalement des cercles) qui sont "non valides", pour ainsi dire, et j'aimerais obtenir le plus proche point valide, donné une destination souhaitée (qui ne doit pas être valide). Maintenant, jusqu'ici, j'ai essayé au cas par cas d'éviter ces régions, mais quand il y a plusieurs contraintes (comme éviter d'avoir 2-3 régions qui sont proches/mélangées), cette approche ne fonctionne pas. Je pensais à une sorte de recherche, mais discrétiser l'espace serait un autre problème car ces régions ne seront pas vraiment compatibles avec cela.

J'espérais que vous pourriez me donner quelques conseils sur la façon de résoudre un problème comme celui-ci. Un cas connexe mais beaucoup plus simple serait this.

Merci!

Answer 1

Il est fondamentalement impossible, sauf si vous pouvez mettre des contraintes sur ces régions non valides. Considérons une région invalide (ou union de régions) sous la forme d'une grande goutte irrégulière avec un minuscule trou de validité quelque part à l'intérieur. Et supposons que votre destination soit à l'intérieur du blob, près du trou d'épingle, de sorte que le point désiré soit réellement dans le sténopé. Si la seule façon d'examiner ce blob est avec une méthode oui/non pour tester un point de validité, la seule façon de trouver le trou d'épingle sera par une recherche exhaustive, qui prendra une éternité.

Answer 2

Si toutes vos régions invalides sont disjointes, le problème est gérable. Pour un point donné, s'il se trouve dans l'une des régions, recherchez le point le plus proche sur la limite de la région. Ce n'est pas nécessairement trivial, mais il devrait y avoir beaucoup de références - même sur ce site - pour ce faire, étant donné les différents types de frontières - lignes droites, arcs, cercles, splines, etc

Si les régions ne sont pas disjoints, vous pouvez les combiner en régions qui le sont. CGAL provides libraries for 2D booleans (spécifiquement les syndicats).