Accueil > Forum > > > > Point dans region (geometrie)
 Point dans region (geometrie)
vendredi 19 octobre 2007 à 17:38:42 |
Point dans region (geometrie)
24Karas
|
Bonjour. J'ai un petit probleme pour trouver un algo qui fonctionne bien. Voilà le probleme : j'ai un point de coordonnées x et y // point(x,y) J'ai mon plan qui est découpé en un ensemble de polygones qui peuvent avoir un nombre de cotés différents. Exemple : des rectangles, des losanges, ... Pour chaque polygome je connais tout les points. Les polygomes ne se chevauchent pas. En gros le point ne peut etre que dans un seul polygone à la fois Comment trouver à partir du x et y du point dans quel polygome est mon point ? Merci pour toute suggestion ++ 24K |
|
vendredi 19 octobre 2007 à 20:52:01 |
Re : Point dans region (geometrie)
juju12
|
Réponse acceptée !
Salut
C'est pas évident, surtout si tes polygones sont un peu complexes; quelques suggestions tout de même si ton maillage est fixe:
tu peux découper (une fois pour toutes en début de prog) chaque polygone en triangles élémentaires beaucoup plus simples à tester; également tu peux faire un deuxième découpage (en plus, toujours début de prog) du plan en carrés ou rectangles qui te donnera un tableau où tu stockeras les indices des polygones qui sont en contact avec le carré, ce qui te permettra plus tard, en fonction de la résolution, de tester beaucoup moins de polygones.
|
|
samedi 20 octobre 2007 à 11:55:02 |
Re : Point dans region (geometrie)
luhtor
|
Réponse acceptée !
C'est pas si compliqué...
Donc pour chaque polygon, tu vas tester si ton point est dedans. Donc je viens d'imaginer un test pour gérer n'importe quelle forme, il me semble de marcher, mais faudrait y réfléchir un peu plus.
En fait si tes polygones sont convexes, c'est simple, et je détails meme pas (voir produit scalaire).
Si tes polygones sont qcq, l'idée est de tracer un segment qui part de ton point avec chaque point du polygone en cours de test.
Si ce segment intersecte un nombre impaire de segments du polygon, alors il est à l'intérieur, sinon il est a l'extérieur.
|
|
samedi 20 octobre 2007 à 12:15:27 |
Re : Point dans region (geometrie)
juju12
|
Réponse acceptée !
Par 'pas évident' j'entendais coûteux en temps d'exécution. Luthor, ton test marche très bien mais il risque d'être un peu long s'il y a beaucoup de polygones...cependant il aura l'avantage de marcher même si le pavage évolue au cours du temps, contrairement à ce que j'ai proposé.
|
|
samedi 20 octobre 2007 à 12:43:19 |
Re : Point dans region (geometrie)
luhtor
|
Réponse acceptée !
C'est vrai que le test est un peu couteux, mais on peut optimiser l'algorithme facilement rien qu'en intégrant des boundings. On augmente considérablement et facilement les performances de l'algo. Mais bon, c'est à lui de voir apres, suivant ses besoins.
|
|
dimanche 21 octobre 2007 à 13:52:20 |
Re : Point dans region (geometrie)
luhtor
|
Réponse acceptée !
Juste une petite correction, il suffit en fait de tester qu'un seul point du polygone:
si le segment partant de ton point a tester et passant par un point de ton polygone (n'importe lequel), intersecte un nombre impaire de fois le ton polygone, alors il est à l'intérieur, sinon il est à l'extérieur.
Hypothèses:
- le polygone ne se coupe pas lui meme
- le polygone est fermé
|
|
lundi 22 octobre 2007 à 10:11:37 |
Re : Point dans region (geometrie)
24Karas
|
Merci pour toutes vos idées !
je vais voir ce que je peux dev dès que j'ai un peu de temps :-)
|
|
vendredi 8 mai 2009 à 21:05:53 |
Re : Point dans region (geometrie)
Zakata
|
J'ai trouvé un contre exemple : le point (*) intersecte un nombre paire de segment du polygone
_______________
| * |
___________ |
| |
___________| |
| __ |
____/ \________
*Les fautes d'orthographes jointes à la présente missive, sont la propriété exclusive de l'auteur. Toute copie illégale pourra être passive de poursuites judiciaires, et soumises à des peines et sanctions exemplaires
|
|
vendredi 8 mai 2009 à 21:08:22 |
Re : Point dans region (geometrie)
Zakata
|
bon le polygone est mal passé, les | de droite sont alignés verticalement. Le polygone ressemble à un "u" couché sur le coté avec une ouverture en forme de "^" sur le segment inférieur.
*Les fautes d'orthographes jointes à la présente missive, sont la propriété exclusive de l'auteur. Toute copie illégale pourra être passive de poursuites judiciaires, et soumises à des peines et sanctions exemplaires
|
|
Cette discussion est classée dans : trouver, probleme, region, geometrie, polygome
 Répondre à ce message
 Sujets en rapport avec ce message
probleme de convertion en c++6 [ par nubis ]
je n'arrive pas a trouver une fonction qui convertisse directement une variable int en binaire(peut etre qu'elle n'existe pas!c pkoi je vous le demand
PROBLEME DE SOUS SEQUENCE [ par fredorine ]
Bonjour,je dois trouver un algorithme pour trouver la plus longue sous sequence croissante d'une chaine de n caracteres.par exemple si la chaine initi
Trouver le centre du cercle [ par stanlenoan ]
Bonjour à tous,Je travaille sur un programme de traitement d'images venant d'une webcam, à partir de la bibliothèque openCV.Pour le moment je veux sui
Probleme C++ [ par El_Catalan_Francesco ]
Bonjour à tous, j'aurai besoin de votre science lol, en effet dans le cadre de mon bts je dois réaliser un programmme et j'aurai besoin de convertir u
Probleme de syntaxe dans boucle while (problemes de pointeurs) [ par pif56 ]
Bonjour,J aimerais savoir ce qui cloche dans la syntaxe ci-dessous. Je recois 5 erreurs provenant de la ligne commencant par while.J ai essaye de join
[allegro] c++: menu déroulant [ par lord anubis ]
Le probleme du jour, le voici, le voilà: Est-il possible, sous allegro, d'integrer un menu déroulant, pour orienter l'utilisateur plus rapidement dans
Probleme concernant la méthode Move [ par fab3131 ]
Je code sous visual.net et jai un petit soucis conceranant la méthode move qui me permet de déplacer un fichier texte d'un endroit a un autre en cliqu
LPD3DXMATRIXSTACK: probleme [ par barraq ]
Salut à tous...Voila je suis entrain de développer une application 3D, et j'ai un petit (gros quand meme :) )souci....voila, j'utilise la structure de
trouver un HWND depuis un PID [ par ctx_man ]
Salut ! Je cherche le moyen de retrouver le HWN de la fenetre principale d'un processus dont je n'ai que le pID. La fenetre n'etant pas toujours prés
 Livres en rapport
|
Derniers Blogs
 [SHAREPOINT] LES SESSIONS TECHDAYS 2012.[SHAREPOINT] LES SESSIONS TECHDAYS 2012. par Patrick Guimonet
Voici donc pour ceux qui n'ont pas pu venir, ou ceux qui n'ont pas pu toutes les suivre la liste des sessions SharePoint aux TechDays 2012, que je mettrais à jour dès que les liens des vidéo seront disponibles. Ou ici : http...
Cliquez pour lire la suite de l'article par Patrick Guimonet TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3 par ROMELARD Fabrice
Speaker: Bernard Ourghanlian Cette session est comme chaque jour transmise en live par BrainSonic, et j'ai donc suivi cette troisième pleinière par ce moyen sur mon iPad . Elle est dédiée comme chaque année à la mise en perspective de l'é...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice MISHRA READER : UN LECTEUR RSS TRèS ZUNE STYLE EN OPEN SOURCE !MISHRA READER : UN LECTEUR RSS TRèS ZUNE STYLE EN OPEN SOURCE ! par Vko
Hier durant une session dédiée aux Techdays 2012, j'ai eu le plaisir d'annoncer la sortie de la Béta 2 de Mishra Reader. C'est quoi ? Pour les utilisateurs, c'est une vraie expérience de lecture de flux RSS sur Windows. Rien à voir avec les produit...
Cliquez pour lire la suite de l'article par Vko [FRAMEWORK 4] LES TASKS ET LE THREAD UI[FRAMEWORK 4] LES TASKS ET LE THREAD UI par fathi
Je viens de passer quelques temps au TechDay's et j'ai pu voir pas mal de session intéressante. Par contre une chose m'a un peu étonné lors de certaines de ces sessions qui abordaient les améliorations du framework .NET (donc le 4.5) : en gros, bea...
Cliquez pour lire la suite de l'article par fathi WORKFLOW FOUNDATION 3 A UN PIED DANS LA TOMBEWORKFLOW FOUNDATION 3 A UN PIED DANS LA TOMBE par JeremyJeanson
Depuis déjà un an, je conseille vivement les utilisateurs de Workflow Foundation 3 à migrer vers la version 4. L'information qui va suivre ne devrait donc pas trop prendre au dépourvu les personnes qui m'ont suivi. Je profite de ce poste, pour faire le re...
Cliquez pour lire la suite de l'article par JeremyJeanson
Logiciels
 Academy System (17.2.1.0)ACADEMY SYSTEM (17.2.1.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Easy-Planning (1.0.0.1)EASY-PLANNING (1.0.0.1)Basé sur les mêmes principes que MyPlanning, Easy-Planning permet de créer des plannings sous la ... Cliquez pour télécharger Easy-Planning COLLECTOR PLUS (3.00B)COLLECTOR PLUS (3.00B)COLLECTOR PLUS version 3.00B est un logiciel utilisant une base de données alimentée par :
- L... Cliquez pour télécharger COLLECTOR PLUS PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)PONAMEDIA TV DEVIENS HELLLOOO FLASH
LA TV SUR VOTRE ORDINATEUR.
Toute une plateforme Multi... Cliquez pour télécharger PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO LettresFaciles 2011 (8.0.0.1)LETTRESFACILES 2011 (8.0.0.1)LettresFaciles est un logiciel facilitant la création et la rédaction de lettres types.
Son inte... Cliquez pour télécharger LettresFaciles 2011
|