Question JDelaunay

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Question JDelaunay

Nicolas F.
Administrator
Bonjour,

Comment on peut faire pour savoir si un DEdge est un segment de contrainte ?

merci
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Alexis.G
Bonjour,

Les Edge contraints ont la propriété "locked". Pour savoir si un DEdge est contraint, tu peux faire
ed.isLocked();
qui renvoie true si ed est une contrainte.


--
OrbisGIS supporter.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Nicolas F.
Administrator
ok merci. En fait je vais implémenter les trous dans le maillage en propageant sur tout les triangles contigus jusqu'aux contraintes.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Nicolas F.
Administrator
ah tiens il y a ConstraintPolygon. Peut être que s'est en cours d'implémentation ?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Alexis.G
Ça fait effectivement partie des choses que nous avons pris en compte lors de l'implémentation. Le problème n'est pas trivial, cependant, notamment à cause de la validation des données d'entrée (la méthode forceConstraintsIntegrity, dans ConstrainedMesh). Et cette étape de validation est importante, puisque c'est elle qui garantit qu'on travaille bien sur un planar straight linear graph...

Le 10/06/2011 08:54, Nicolas F. (LCPC) [via OrbisGIS] a écrit :
ah tiens il y a ConstraintPolygon. Peut être que s'est en cours d'implémentation ?


If you reply to this email, your message will be added to the discussion below:
http://orbisgis.3871844.n2.nabble.com/Question-JDelaunay-tp6458241p6461064.html
To start a new topic under OrbisGIS, email [hidden email]
To unsubscribe from OrbisGIS, click here.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Nicolas F.
Administrator
D'accord. Alors tu me conseil quoi , je continue à implémenter la suppression de triangles ou les "régions creuses" sont déjà implémentées ?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Alexis.G
Les "régions creuses", comme tu dis, ne sont pour l'instant pas
implémentées. Si tu en as besoin, et que tu penses pouvoir réaliser
l'opération dans une couche supérieure (dans ton plugin, avec GDMS), pas
de soucis pour que tu le fasses.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Nicolas F.
Administrator
Oui je vais le faire avec LayerJDelaunay.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Nicolas F.
Administrator
Encore une petite question. Est-ce qu'il y a une méthode dans JDelaunay pour trouver rapidement à partir d'un point x,y,z le triangle qui le contient ?
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Alexis.G
Non. Ça nécessite d'avoir une structure en arrière plan pour rechercher
le point en question.
Enfin... y a une méthode, malgré tout...

Les triangles implémentent l'interface Comparable. J'utilise un critère
de comparaison abusif, à savoir que je les classe en fonction de leu
barycentre, ce qui reste cohérent pour avoir un classement sensé, pour
deux raisons :

  - Deux triangles ne peuvent pas se superposer
  - Le barycentre d'un triangle est dans le triangle.

"Quel intérêt ?", vas tu me dire... :-p
Cette structure triée permet de chercher un point dans le maillage...
Pour ça, il suffit de créer un triangle dont le barycentre est le point
en question. Je pense que le triangle dont les trois sommets sont le
point marcherait (en admettant que ce soit accepté par DTriangle). En
faisant ça, tu obtiens un triangle "proche" de ton point. Du coup, tu
peux utiliser la méthode searchPointContainer, qyu devrait te renvoyer
un des triangles contenant le point.

C'est un peu "tordu", j'en conviens, et ce n'est pas aussi rapide qu'une
recherche dans un RTree. Ici, on fait pas du log(n), on fait du
n^(1/3)... Mais comme on devient limite en mémoire sur les gros jeux de
données, et qu'on n'a besoin d'indexation spatiale ni pour la
triangulation, ni pour le raffinement, je n'ai que ça à proposer.

Si je suis pas clair dans mes explications, n'hésite pas, je peux
rentrer plus dans le détail.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Nicolas F.
Administrator
re,

Ok merci beaucoup. En effet c'est bien pensé, on économise de la mémoire.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Nicolas F.
Administrator
In reply to this post by Alexis.G
J'ai eu un échec avec la méthode searchPointContainer. Juste que je vois pas comment t'envoyer le jeu d'essai en question, le domaine est calculé à la volé par subdivision. Mais c'est pas grave, c'est arrivé qu'une fois, et en cas d'échec je boucle sur tout les triangles; ça a résolu le problème.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

Nicolas F.
Administrator
In reply to this post by Alexis.G
Re,

La gestion des "trous" pour les polygones ont l'air de fonctionner. Je l'utilise dans FastObstructionTest qui utilise LayerJDelaunay pour faire les test d'intersection segment-polygones, vraiment très rapidement (gain de 40x par rapport à quadtree et jts intersection test). Avec au bas mot 3,4 milliards de tests d'intersection pour la commune de nantes, c'est important ^^

On donne une liste de coordonnées de trou  (variable holes). Ensuite l'algorithme navigue entre les triangles (sans récursivité) et marque les triangles avec la méthode externalgid pour les marquer comme vide, il stop la navigation si on tombe sur un segment de contrainte ou un triangle déjà vide. J'utilise externalgid, car je n'en ai pas l'utilité en dehors de ça.
//Remove triangles
for(Coordinate hole : holes) {
	DTriangle foundTri=findTriByCoordinate(hole,trianglesDelaunay);
	if(foundTri == null) {
		throw new LayerDelaunayError("hole outside domain ("+hole+")");
	}
	//Navigate through neighbors until it reach a deleted tri or locked segment
	Stack<DTriangle> navHistoryTri=new Stack<DTriangle>();
	Stack<Short> navHistoryDir=new Stack<Short>();
	navHistoryTri.push(foundTri);
	navHistoryDir.push((short)0);//Set as hole
	foundTri.setExternalGID(0);
	while(!navHistoryTri.empty()) {
		if(navHistoryDir.peek()==3) {
			navHistoryTri.pop();
			navHistoryDir.pop();							
		} else {
			DEdge ed = navHistoryTri.peek().getEdge(navHistoryDir.peek());
			if(!ed.isLocked()) {
				DTriangle neigh=ed.getOtherTriangle(navHistoryTri.peek());
				if(neigh != null) {
					if(neigh.getExternalGID()!=0) { //Not set as destroyed
						neigh.setExternalGID(0); //Set as hole
						navHistoryDir.push((short)(navHistoryDir.pop()+1));
						navHistoryDir.push((short)-1);
						navHistoryTri.push(neigh);
					}
				}
			}
			navHistoryDir.push((short)(navHistoryDir.pop()+1));
		}
	}
}

Si tu souhaites tu peut modifier ce code pour implémenter la fonction dans JDelaunay.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Question JDelaunay

ebocher
Administrator
Bonjour Nicolas,

Merci pour ce retour d'utilisation et le partage de la méthode. La triangulation des polygones et la prise en compte des trous sont en effet deux fonctions indispensables.

Je pense qu'Alexis va y jeter un œil.

Erwan.
Loading...