Comment trouver les points les plus proches (formant ainsi un polygone) entourant un point particulier? (Voir image)

8

Je travaille avec un moteur de jeu, et ma tâche consiste à ajouter du code pour simuler la rupture de maillages rigides.

Pour l'instant, je ne travaille qu'à casser un cube.

J'utilise l'algorithme de Voronoi pour créer un éclat fracturé (réaliste) et j'utilise la méthode du demi-plan pour générer une cellule de Voronoi.

pour trouver les points les plus proches (entourés de rouge) autour du Voronoi (point violet)

Maintenant, la façon dont je fais cela est pour chaque point de départ, je fais des plans qui sont des plans perpendiculaires à la bissectrice (les lignes noires droites dans l'image) avec le reste des points de départ et je calcule les intersections de tous ces plans pour me donner des points distincts ( tous les points orange).

Je suis allé jusqu'ici.

De tous ces points d'intersection calculés, je n'ai besoin que de ceux qui sont les plus proches et entourant le point de départ (les points entourés en rouge) et j'ai besoin de jeter tout le reste.

Informations dont je dispose:

1) Équations planes de tous les plans (définies par des vecteurs normaux normalisés et leur distance par rapport à l'origine)

2) Points d'intersection (que j'ai calculés)

Quelqu'un peut-il m'aider à savoir comment trouver les points entourés de rouge?

nilspin
la source
Pas de réponse, mais c'est un problème intéressant!
Tim Holt

Réponses:

4

En suivant la méthode du demi-plan , vous aurez trouvé les segments de ligne à chaque autre point et les bissectrices perpendiculaires de chacun de ces

étape 1: segments de ligne étape 2: bissectrices perpendiculaires

que vous avez ensuite intersecté pour trouver des sommets potentiels de la cellule de Voronoi.

Maintenant, vous voulez exclure ceux qui coupent l'un des demi-plans "distants" formés par les bissectrices.

Deux intersections correspondantes, une inégalée

J'ai coloré les demi-plans "éloignés" d'un bleu translucide pour plus de clarté.

Ici, les deux points rouges encerclés réussissent le test: ils ne se trouvent dans aucun demi-plan. Le point rouge non entouré ne passe pas, car il se trouve dans le demi-plan formé vers le point en haut à droite.

Cela signifie effectivement tester si chaque point est de l'autre côté de chaque ligne bissectrice (par rapport au site de Voronoi) et éliminer ceux qui le sont. (Attention aux erreurs d'arrondi.)

Anko
la source
Cette réponse a été très utile. Pour vérifier si les deux points se trouvent du même côté du plan, j'ai substitué les vecteurs dans les équations du plan et j'ai recherché leurs signes. Si les deux étaient positifs / négatifs, alors ils sont du même côté. Sinon, ils sont du côté opposé. Cela marche! Mon code semble enfin produire des sommets corrects pour les fragments Voronoi!
nilspin
quel programme avez-vous utilisé pour générer ces images dans votre réponse?
nilspin
@nilspin Inkscape .
Anko
3

Vous pouvez simplement parcourir les bords et filtrer tous les sommets qui ne sont pas dans le même demi-plan avec le point d'intérêt.

Comme optimisation, itérez des bords les plus proches aux plus éloignés. Je pense que vous pouvez même filtrer les sommets tout en générant des tranches.

C'est comme trancher la tarte avec un couteau sans fin, jusqu'à ce qu'il ne reste plus qu'un petit morceau de cerise dessus. Si vous aimez les analogies. Il suffit de couper et de voir quelle partie sera prise et laquelle sera jetée.

Ombres sous la pluie
la source