Questions marquées «computational-geometry»

Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then...

J'ai deux ensembles de points dans le plan bidimensionnel. Je veux trouver la paire de points la plus proche telle que , , et la distance euclidienne entre est aussi petite que possible. Comment cela peut-il être fait efficacement? Peut-on le faire en temps , où?S,TS,TS,Ts,ts,ts,ts∈Ss∈Ss \in...

J'essaie d'utiliser une caméra couleur pour suivre plusieurs objets dans l'espace. Chaque objet aura une couleur différente et afin de pouvoir bien distinguer chaque objet, j'essaie de m'assurer que chaque couleur assignée à un objet est aussi différente de n'importe quelle couleur sur n'importe...

Étant donné un ensemble de points et un rayon . Quelle est la complexité de trouver le point avec un plus grand nombre de points à une distance inférieure à . Par exemple, celui qui maximise ?x1,…,xn∈R2x1,…,xn∈R2x_1, \ldots, x_n \in \mathbb{R}^2rrrrrr∑ni = 11∥ x - xje∥ ≤ r∑i=1n1‖x−xi‖≤r\sum_{i=1}^n...

Pour le plaisir, j'essaie de créer une visionneuse filaire pour le DCPU-16 . Je comprends comment faire tout sauf comment cacher les lignes qui sont cachées dans le fil de fer. Toutes les questions ici sur SO supposent toutes que vous avez accès à OpenGL, malheureusement je n'ai pas accès à quelque...

Pour un graphe planaire donné noyé dans le plan, défini par un ensemble de segments de droite , chaque segment est représenté par ses extrémités . Construisez une structure de données DCEL pour la subdivision planaire, décrivez un algorithme, prouvez son exactitude et montrez la complexité.G ( V,...

Il est bien connu que les polygones monotones jouent un rôle crucial dans la triangulation des polygones . Définition: Un polygone dans le plan est appelé monotone par rapport à une droite , si chaque ligne orthogonale à coupe au plus deux fois.L L PPPPLLLLLLPPP Étant donné une ligne et un polygone...

Supposons que je vous donne un graphique non orienté avec des bords pondérés, et que je vous dise que chaque nœud correspond à un point dans l'espace 3D. Chaque fois qu'il y a une arête entre deux nœuds, le poids de l'arête est la distance entre les points. Votre objectif est de reconstruire les...

J'ai un ensemble de points qui sont définis dans un espace métrique - donc je peux mesurer une «distance» entre les points mais rien d'autre. Je veux trouver le point le plus central de cet ensemble, que je définis comme le point avec la somme minimale des distances à tous les autres points. Le...

Étant donné une triangulation (sans points de Steiner) d'un simple polygone , on peut considérer le dual de cette triangulation, qui est défini comme suit. Nous créons un sommet pour chaque triangle de notre triangulation, et nous connectons deux sommets si les triangles correspondants partagent...

Que sont les polygones dégénérés? Comment vérifier si une paire de polygones donnée est dégénérée ou

Étant donné deux ensembles et contenant chacun points disjoints dans le plan, calculez la distance la plus courte entre un point dans et un point dans , c'est-à-dire .AAABBBnnnAAABBBmin { dist(p,q) | p∈A∧q∈B }min { dist(p,q) | p∈A∧q∈B }\min \space \{\mbox{ } \text{dist}(p, q) \mbox{ } | \mbox{ } p...

On me fait un exercice malheureusement je n'ai pas réussi par moi-même. Il y a un ensemble de rectangles et un rectangle . En utilisant un algorithme de balayage plan, déterminez si est complètement couvert par l'ensemble de .R1..RnR1..RnR_{1}..R_{n}R0R0R_{0}R0R0R_{0}R1..RnR1..RnR_{1}..R_{n} Pour...

Le problème suivant a-t-il été étudié auparavant? Si oui, quelles approches / algorithmes ont été développés pour le résoudre? Problème ("Problème de hauteur d'empilage maximale") Étant donné polygones, trouvez leur disposition stable et sans chevauchement qui maximise leur hauteur d'empilement sur...

Dans une vidéo présentant les avantages des filtres à particules pour la localisation, il a été laissé entendre qu'il existe une certaine ambiguïté quant au coût de complexité de la mise en œuvre des filtres à particules. Est-ce correct? Quelqu'un pourrait-il expliquer...

Pour les maillages polygonaux 2D, les représentations de structure de données QuadEdge et HalfEdge sont suffisantes pour stocker et permettre une interrogation efficace de toutes les informations topologiques et d'incidence. Existe-t-il des structures de données compactes et efficaces pour les...

Supposons que l'on nous donne une liste de points, dont les coordonnées et sont toutes non négatives. Supposons également qu'il n'y ait pas de points en double. On ne peut aller du point au point si et . La question est: étant donné ces points, quel est le nombre maximum de points que nous pouvons...

[Remarque: ce problème a été inspiré par Pokemon Go. Je vais d'abord expliquer le problème en termes mathématiques, puis expliquer la connexion à Pokemon Go. Mon objectif n'est pas de tricher dans le jeu. Si je voulais tricher, de meilleures informations seraient disponibles plus facilement.]...

Je sais que les problèmes de sac à dos 2D et 3D sont des NPC, mais existe-t-il un moyen de les résoudre dans un délai raisonnable si les instances ne sont pas très compliquées? La programmation dynamique fonctionnerait-elle? Par sac à dos 2D (3D), je veux dire que j'ai un carré (cube) et une liste...

Comme je l'ai dit, je veux construire un programme pour générer n points équidistants dans un espace euclidien. De ce que je sais 1d: tous les deux points 2d: tous les triangles équilatéraux 3D: tous les tétraèdres équilatéraux jusqu'à 3d: je suppose que cela s'appelle un hypertriangle équilatéral...