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
 [RIA SERVICES] INCLUDE ET DOMAINDATASOURCE[RIA SERVICES] INCLUDE ET DOMAINDATASOURCE par Audrey
Dans un de mes articles précédents , j'avais parlé des DomainDataSource avec RIA Services dans le cas d'une interface Maître - Détail. Dans le même principe, je vais parler d'une autre manière de mettre en forme ce cas d'interface avec RIA Services. Et po...
Cliquez pour lire la suite de l'article par Audrey ZUNE : VERSION ZUNE SOFTWARE V 4.2 ET LA SOCIALISATIONZUNE : VERSION ZUNE SOFTWARE V 4.2 ET LA SOCIALISATION par ROMELARD Fabrice
Une des nouveautés de la version V 3.0 était l'apparition de l'onglet Social qui ne fonctionnait que si le MarketPlace était activé sur son poste. Cela limitait donc son intérêt, car hors du cadre commercial USA-CANADA, peu de monde trouva...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice PRATIQUE DE SILVERLIGHT PAR ERIC AMBROSIPRATIQUE DE SILVERLIGHT PAR ERIC AMBROSI par MPOWARE
Je viens de finir la lecture du dernier livre d'
Eric Ambrosi
éditions PEARSON
Son livre donne une approche pratique de Silverlight qui sera aussi bien comprise par le développeur que par le designeur.
Tous les aspects du développement RIA sont abor...
Cliquez pour lire la suite de l'article par MPOWARE APPRENDRE à DéVELOPPER POUR LES MOBILES AVEC LA NOUVELLE GéNéRATION .NETAPPRENDRE à DéVELOPPER POUR LES MOBILES AVEC LA NOUVELLE GéNéRATION .NET par odewit
2 déclinaisons de Silverlight et 2 déclinaisons de Mono permettent dorénavant (ou permettront prochainement) de développer des applications .NET mobiles pour les principales plates-formes du marché :
Silverlight pour Symbian, basé sur Silverlight 2...
Cliquez pour lire la suite de l'article par odewit ZUNE : NOUVELLE VERSION DU ZUNE SOFTWARE - V 4.2ZUNE : NOUVELLE VERSION DU ZUNE SOFTWARE - V 4.2 par ROMELARD Fabrice
Avec la dernière génération du lecteur MP3 de Microsoft, le ZUNE HD, Microsoft a publié une nouvelle version du logiciel pour PC. Ainsi, je me suis décidé à installer celle-ci sur mon Tablet PC ACER, comme toujours le logiciel est donc tél...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice
Forum
 RE : ESPEAK RE : ESPEAK par ghanim13
Cliquez pour lire la suite par ghanim13
Logiciels
 Academy System (10.9.4.0)ACADEMY SYSTEM (10.9.4.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Xilisoft Convertisseur Vidéo Ultimate (5.1.39.0305)XILISOFT CONVERTISSEUR VIDéO ULTIMATE (5.1.39.0305)Xilisoft Convertisseur Vidéo Ultimate est un outil puissant de conversion vidéo, facile à utilise... Cliquez pour télécharger Xilisoft Convertisseur Vidéo Ultimate Xilisoft DVD Ripper Ultimate (5.0.64.0304)XILISOFT DVD RIPPER ULTIMATE (5.0.64.0304)Xilisoft DVD Ripper Ultimate est un logiciel excellent pour copier et convertir DVD vers presque ... Cliquez pour télécharger Xilisoft DVD Ripper Ultimate Rigs of Rods (63.3)RIGS OF RODS (63.3)c'est un jeu de multi-simulation camions,autobus voitures, avions, bateaux, hélicoptère avec défo... Cliquez pour télécharger Rigs of Rods
|