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
 UNE JOLIE-HORLOGE ET PAS QU'UN PEU !UNE JOLIE-HORLOGE ET PAS QU'UN PEU ! par neodante
Pour les possesseurs d'iPhone, ça y est Bijin Tokei - qui se traduit littéralement en Français par " Jolie Horloge " - est arrivé et GRATUITEMENT s'il vous plaît ! Après la version Tokyo, Hokkaido, night club, racing, Gal, "pour les mademoiselles'", . voi...
Cliquez pour lire la suite de l'article par neodante TECHDAYS PARIS 2010 : CONNECTEZ VOS DONNéES à SHAREPOINT 2010 AVEC LES BUSINESS CONNECTIVITY SERVICESTECHDAYS PARIS 2010 : CONNECTEZ VOS DONNéES à SHAREPOINT 2010 AVEC LES BUSINESS CONNECTIVITY SERVICES par ROMELARD Fabrice
Animé par: Gaetan Bouveret et Julien Chomarat Business Connectivity Services (BCS) est dans SharePoint 2010 la version 2 de Business Data Catalog (BDC dans SharePoint 2007). Il s'agit de la solution permettant de visualiser des données provenan...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice [DIVERS] SUIVRE VOS SéRIES PRéFéRéS SUR LA TOILE[DIVERS] SUIVRE VOS SéRIES PRéFéRéS SUR LA TOILE par orion
Comme de nombreux geek, je suis un grand amateur de série TV et je rate régulièrement des épisodes de mes séries préférés. Une solution s'offre à vous avec ce merveilleux site : Tv Gorge - www.tvgorge.com Moteur de recherche à l'appui, vous pouvez ...
Cliquez pour lire la suite de l'article par orion TECHDAYS PARIS 2010 : LA BI DANS SHAREPOINT 2010TECHDAYS PARIS 2010 : LA BI DANS SHAREPOINT 2010 par ROMELARD Fabrice
Animé par: Vincent Bellet et Baptiste Giraudier La BI dans SharePoint 2010, Les nouveaux services d'application dans SP2010 et SQL Server Reporting services 2008 R2. La BI dans SharePoint est généralisée pour tous afin de permettre à tous les coll...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice
Forum
 RE : WIN APIRE : WIN API par racpp
Cliquez pour lire la suite par racpp
Logiciels
 DB-MAIN (9.1.0)DB-MAIN (9.1.0)DB-MAIN is a data-modeling and data-architecture tool. It is designed to help developers and anal... Cliquez pour télécharger DB-MAIN Xilisoft DPG Convertisseur (5.1.37.0120)XILISOFT DPG CONVERTISSEUR (5.1.37.0120)Xilisoft DPG Convertisseur offre aux fans de Nintendo DS une bonne solution leur permettant de dé... Cliquez pour télécharger Xilisoft DPG Convertisseur GraphicsGale (2.01.01)GRAPHICSGALE (2.01.01)GraphicsGale est un logiciel de PixelArt avec de nombreuse fonctionnalités permettant de réalisé ... Cliquez pour télécharger GraphicsGale Architecte 3D (Platinum 2010)ARCHITECTE 3D (PLATINUM 2010)Architecte 3D Platinium vous permet de concevoir facilement les plans votre future maison, de l'é... Cliquez pour télécharger Architecte 3D TeamViewer 5 (TeamViewer 5)TEAMVIEWER 5 (TEAMVIEWER 5)Dépanner un ami,expliquer une manipulation devient un jeu d'enfant.
Prise en main d'un autre ord... Cliquez pour télécharger TeamViewer 5
Comparez les prix
HTC Hero
Entre 550€ et 550€
|