Coordonnées de points extérieurs

max-mtp · January 2018

Bonjour,

J'ai une quantité finie de rectangles (R1, R2, etc.) imbriqués dont je connais les coordonnées de chaque point.

Le point inférieur gauche du rectangle R1 a toujours pour coordonnées (0;0) et aucun point des autre rectangles ne peut avoir de coordonnées inférieures.

Ces rectangles imbriqués forment un polygone à angles droits.

Ayant toutes ces infos, j'ai besoin, en partant du point (0;0) de déterminer les coordonnées de chacun point extérieur (f1, f2, f3, etc.) constituants ce polygone.

Est-ce que quelqu'un pourrait m'aider à trouver une formule svp :?

gerard0 · January 2018

Bonjour.

Si tu connais les coordonnées des points des rectangles et lesquels définissent le polygone, tu as ce que tu veux. Si tu n'as pas ça, il va falloir en dire plus : Comment sont définis les rectangles, comment est obtenu le polygone.
En plus, un schéma (un dessin) de la situation, sur un exemple, ne serait pas de trop.

Cordialement.

max-mtp · January 2018

Voici un exemple de figure.

Pour tout te dire, j'ai les coordonnées des points de chaque rectangle et je cherche à faire un petit algo qui va parcourir la figure à partir du point O (0;0) et déterminer les x et les y du point A, puis B, puis C, etc. 71282

gerard0 · January 2018

Tu as bien fait de faire un dessin, le mot "imbriqué" ne donnait pas du tout ce genre de dessin. Tes rectangles sont en fait accolés.
Si un spécialiste de l'algorithmique passe par là, il te donnera peut-être une idée.

Cordialement.

ev · January 2018

À partir du moment où tu sais déterminer si un point est à l'intérieur (resp. extérieur) d'un rectangle (quatre tests), il te reste à boucler sur tous les triangles avec un ou (resp. et)

e.v.

Math Coss · January 2018

@ev : Je ne comprends pas, pas du tout même. Tu voudrais expliciter ?

Edit : précision de qui et donc ce que je n'ai pas compris.

max-mtp · January 2018

Voici un Excel que j'ai fait et qui permet de mieux comprendre la problématique.
https://we.tl/nECBINLWMQ

[Contenu de la feuille de calcul en lien. AD] 71346

depasse · January 2018

Bonjour,

Sauf bêtise, un sommet est un couple qui apparaît une et une seule fois dans le tableau de toutes les coordonnées.

Cordialement
Paul

max-mtp · January 2018

Je pense que ce n'est pas exhaustif comme par exemple le point E

gerard0 · January 2018

C'était une belle idée, mais (10,4) apparaît 2 fois et est un des sommets cherchés.
Il y a d'ailleurs un problème dans les données, R6 n'est pas jointif (d'après les sommets (8,3) et (10,3)) de R7, il y a un trou !!

Cordialement.

gerard0 · January 2018

Plus généralement,

la méthode de construction de la figure n'est pas explicitée, ce qui fait qu'il est difficile de connaître les différents cas.

max-mtp · January 2018

Autant pour moi, je viens de corriger

max-mtp · January 2018

Selon moi, il faut parcourir la figure dans un sens précis à partir du point (0;0) pour définir chaque point par des tests selon les point suivants.

Ex. Si pour un point donné il n'y a pas de point ayant le même x ou le même y alors on tourne, etc.

gerard0 · January 2018

Le sommet (10,4) n'est toujours pas présent pour R6.

Et toujours pas de règle de construction.

max-mtp · January 2018

Il n'y a pas de règles de construction si ce n'est que les rectangles sont générés de façon aléatoire et forment un polygone à angles droit.

depasse · January 2018

Bien vu!

Disons alors, chaque couple qui apparaît un nombre impair de fois (et, encore à condition que la frontière soit sans point double, autrement dit que l'intérieur du polygone soit connexe).

gerard0 · January 2018

Max-mtp,

peux-tu expliciter "forment un polygone à angles droit" ??
Et tes rectangles ne sont pas vraiment aléatoires pour pouvoir être accolés.

Une de tes difficultés est peut-être tout simplement ça : Tu ne sais pas comment se construit ton polygone !

max-mtp · January 2018

Tu as raison gerard0, se sont des rectangles dont les dimensions respectent un ensemble de contraintes, notamment d'adjacence et de dimensions.

Le polygone constitué par ces rectangles est constitué d'angles à 90° et d'angles à 270°.

Lorsque j'aurai trouvé la solution, je te l'enverrai.

max-mtp · January 2018

Voici un premier jet de l'algo que je vais vérifier, corriger et tester

On part du couple (x0;y0) = (0;0) car c’est le point extérieur de référence dont on peut être sûr qu’il est seul et unique

S’il existe un couple (xi;yi) = (x0;y0) appartenant à 2 des 3 colonnes différentes de celle du couple (x0;y0)

Alors

Si (x0;y0) appartient à la colonne bg et (xi;yi) appartiennent aux colonnes hd ou bd (alors on compare (x0;y0) aux (xi;yi) du rectangle de la colonne bd)
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bg ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd et (xi;yi) appartiennent aux colonnes hd ou hg (alors on compare (x0;y0) aux (xi;yi) du rectangle de la colonne sg)
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sd ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg et (xi;yi) appartiennent aux colonnes bd ou bg (alors on compare (x0;y0) aux (xi;yi) du rectangle de la colonne bg)
alors on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd et (xi;yi) appartiennent aux colonnes bg ou sg (alors on compare (x0;y0) aux (xi;yi) du rectangle de la colonne bg)
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on réitère la boucle jusqu’à arriver au point (0;0).

S’il existe un couple (xi;yi) = (x0;y0) appartenant à une des 3 colonnes différentes de celle du couple (x0;y0)

Alors

(Cas des bg)

Si (x0;y0) appartient à la colonne bg et (xi;yi) appartient à la colonne bd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bg ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bg et (xi;yi) appartient à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bd ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bg et (xi;yi) appartient à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bg ;
on réitère la boucle jusqu’à arriver au point (0;0).

(Cas des bd)

Si (x0;y0) appartient à la colonne bd et (xi;yi) appartient à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bd ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd et (xi;yi) appartient à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bd ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd et (xi;yi) appartient à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sd ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

(Cas des sg)

Si (x0;y0) appartient à la colonne sg et (xi;yi) appartient à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg et (xi;yi) appartient à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg et (xi;yi) appartient à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bg ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

(Cas des sd)

Si (x0;y0) appartient à la colonne sd et (xi;yi) appartient à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd et (xi;yi) appartient à la colonne bd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sd ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd et (xi;yi) appartient à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sd ;
on réitère la boucle jusqu’à arriver au point (0;0).

S’il n’existe pas un couple (xi;yi) = (x0;y0) appartenant à une des 3 colonnes différentes de celle du couple (x0;y0)

Alors

S’il existe un ou plusieurs xi = x0

Alors

Si (x0;y0) appartient à la colonne bg et xi appartien(nen)t à la colonne bd
alors
on prend comme nouveau (x0;y0) le point (xi;max(yi<y0)) du rectangle Ri de la colonne bd ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd et xi appartien(nen)t à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;max(yi<y0)) du rectangle Ri de la colonne bg ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg et xi appartien(nen)t à la colonne bd
alors
on prend comme nouveau (x0;y0) le point (xi;max(yi<y0)) du rectangle Ri de la colonne bd ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd et xi appartien(nen)t à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;min(yi>y0)) du rectangle Ri de la colonne sg ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

S’il existe un ou plusieurs yi = y0

Alors

Si (x0;y0) appartient à la colonne bg et yi appartien(nen)t à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (min(xi>x0);yi) du rectangle Ri de la colonne sd ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd et yi appartien(nen)t à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (min(xi>x0);yi) du rectangle Ri de la colonne sd ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg et yi appartien(nen)t à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;max(yi<y0)) du rectangle Ri de la colonne bg ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd et yi appartien(nen)t à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;min(yi>y0)) du rectangle Ri de la colonne sg ;
on réitère la boucle jusqu’à arriver au point (0;0).

S’il n’existe pas de yi = y0 et de xi = x0

Alors

Si (x0;y0) appartient à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle R0 de la colonne bg ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle R0 de la colonne sd ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle R0 de la colonne bd ;
on enregistre l’ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu’à arriver au point (0;0). 71356

depasse · January 2018

Bonjour,

On a $n$ rectangles donnés par les coordonnées de leurs sommets. Leurs intérieurs sont deux à deux disjoints et leur réunion a pour frontière un polygone $P$ que je suppose non-croisé.

Un possible algorithme:
On liste, n'importe comment, les $4n$ couples de coordonnées. D'où $L_1$.
On trie $L_1$ selon l'ordre alpha-numérique. D'où $L_2$.
On vire de $L_2$ tous les doubles (j'ai supposé $P$ non-croisé) et quadruples.D'où $L_3$.

$L_3 :=(l_0, l_1, l_2.....)$ est la liste des sommets de $P$.
Cerise: les côtés verticaux de $P$ sont les $[l_{2i},l_{2i+1}]$.

Sauf erreur, comme d'hab

Cordialement
Paul

max-mtp · January 2018

Merci depasse,

C'est tout à fait pertinent

max-mtp · January 2018

Par contre, est-ce que cela fonctionne pour une forme particulière comme celle-ci ? 71392

depasse · January 2018

Bonsoir max, il manque un lien à ton message précédent.

max-mtp · January 2018

image
[Utiliser le lien "Joindre un fichier au message ...", au dessus de la fenêtre d'édition. AD] 71404

babsgueye · January 2018

Salut.

D’après votre figure, les sommets à enregistrer ne sont sommet que d'un seul triangle, à la différence des autres. Si ça peut vous servir...!

Bonne soirée.

depasse · January 2018

Si ça ne fonctionne pas, c'est que je me suis trompé!

Coordonnées de points extérieurs

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 35