Contour d'objets non sécants

[Luna]

Coucou,

Pour commencer, je ne recherche aucunement des programmes tout fait, tout propre chat ne m'intéresse pas :3
Mon but est simplement de trouver une logique permettant de répondre à un problème afin que je puisse par la suite transposer en programme.

Donc pour faire relativement simple, il existe bon nombre de programmes (LeeMac, TheSwamp, etc) permettant de générer un contour sur un jeu de sélection d'objets linéaires sécants (des images valent mieux que des mots donc voici une démonstration du programme de LeeMac). Les conditions à respecter pour que ce programme fonctionne c'est :
 - Les objets sont compatibles avec la commande "_BOUNDARY" (ou "CONTOUR")
 - Les objets se croisent donc sont coplanaires et possèdent des points d'intersections entre-eux

J'avais déjà discuté de ce programme avec @didier mais je n'ai jamais vraiment eu le temps de me pencher plus en avant sur le sujet (le soucis, c'est que l'idée est toujours dans ma tête, d'où mon problème ^^).
Le but étant d'avoir un principe similaire à une exception près parmi les conditions ci-dessus : les objets ne possèdent pas de points d'intersections entre-eux...
Pour le contexte, je travaille dans un BE d'implantation de centrales photovoltaïques et donc on travaille constamment avec des modules et des structures qui sont espacés les uns des autres (les écarts ne sont pas fixes donc on ne peut pas fixer une valeur pour les recherches), cependant ces éléments sont très souvent regroupés via des zonages divers et variés (emprise PV, répartitions des puissances, types de modules, architecture élec', etc). Donc structurellement parlant, ces éléments sont distincts les uns des autres (pas de superposition ou autre) mais ils sont tous liés selon une propriété précise générant des zonages plus ou moins complexes. Le soucis, c'est que les itérations au sein d'un même projet sont nombreuses, donc ces zonages sont souvent modifiés et cela prend donc du temps.

Mon idée est donc de pouvoir générer un contour à partir d'un jeu de sélection qui soit suffisamment précis pour englober l'ensembles des objets sélectionnés sans englober d'autres objets non concernés... Le programme devrait pouvoir fonctionner avec des objets linéaires (pour commencer disons simplement lignes et polylignes) puis s'étendre avec des blocs (mais si c'est possible de le faire avec des objets linéaires, cela ne posera pas de soucis de faire la même chose avec des blocs puisqu'il suffira de générer un contour précis au sein d'une définition de bloc pour ensuite utiliser ce contour dans la génération du contour en EO).

Pour donner un exemple, je joins un fichier .dwg afin d'illustrer la chose.
Dans ma logique, j'avais pensé à une analyse longue et fastidieuse qui s'apparente à la technique du drap. Le but étant de générer un contour global du jeu de sélection (par exemple (LM:ssboundingbox) qui permet de s'assurer que l'ensemble des objets sont présent dans ce rectangle). On définit un point M tel que M appartient à la polyline ABCD (fermée) et aux droites Dh et Dv, avec ABCD le contour du jeu de sélection, Dh la droite horizontale passant par M et Dv la droite verticale passant par M (selon la position du point M sur ABCD). Les droites Dh et Dv vont générer des points d'intersection avec les objets présents dans la surface ABCD, que l'on nommera M' tels que M' soit la projection horizontale ou verticale du point M sur les objets composants le jeu de sélection initial. On obtient donc une liste de points d'intersection pour chaque point M dont on peut récupérer facilement la borne inférieure et la borne supérieure donc on a pour tout points M, une liste de 2 points correspondant à la borne inférieure et supérieure (ou 1 point si la borne inférieure et supérieure sont confondue).

En affectant un pas pour générer une liste de point M, on obtient tout un ensemble de couples de points correspondant à l'emprise réelle des objets (sous forme de dessin la forme est proche du zonage attendu, mais sous forme de liste, les points ne sont pas ordonnés correctement, à moins de ne choisir uniquement le point d'intersection le plus proche du point M (car (vl-sort M'-list '(lambda (e1 e2) (< (distance M e1) (distance M e2))))) mais auquel cas il faudra parcourir 100% du périmètre de la boundingbox, et non 50%).
Si on affecte un lien entre le point et l'objet issu de cette intersection, il suffira ensuite de récupérer pour chaque projection le sommet réel des objets "coupés" le plus proche de la projection pour limiter le nombre d'objets (et limiter également un contour trop serré) et également éliminer les sommets situés à une distance beaucoup trop importante par rapport à ses voisins (cf. fichier .dwg).

Je me rends compte que j'ai de vrais problèmes de concision dans mes explications moi...Donc pour ceux qui ont compris, j'aimerais savoir comment peut-on aborder un problème comme celui-ci sans avoir besoin de calculer les points d'intersection projetés de 2 milliard de points pour simplement générer un contour précis à un jeu de sélection...Car même si sur le papier, la technique du drap fonctionne, cela demande beaucoup de ressources et de temps, ce qui n'est pas le but non plus ! >n<
Donc je me dis qu'il existe probablement un théorème mathématique ou une logique permettant de gagner du temps sur les calculs, mais pour un sujet comme celui-ci, ma logique propre ne me permet pas de réfléchir autrement qu'en analytique...

Bref, merci pour les âmes charitables qui prendront non seulement le temps de me lire, mais également de me répondre ! (voyez chat comme...un challenge, sauf que je n'ai pas de solution toute faite :3)

Bisous,
Luna

SSBoundingLine.dwg

[(gile)]

Salut,

J'ai déjà fait un truc dans ce genre en vlisp en créant des régions, puis en faisant une union de ces régions, puis une décomposition de la (ou des) région(s) résultantes.

J'avais mal lu la demande. Tout ce que je peux te proposer comme piste mais qui ne répond pas vraiment à ta demande, c'est l'enveloppe convexe (convex hull).

[Luna]

Coucou,

Merci pour ta rapidité ! Bon du coup il va falloir que je finisse par regarder ces objets "régions", car j'en entends souvent parlé, mais je n'ai jamais eut à les utiliser jusque-là :S
Je vais me renseigner sur le sujet en tout cas, merci bien !

Bisous,
Luna

[(gile)]

Non, avec l'union des régions, il faut que les objets soient sécants.

Cherche plutôt du côté de l'enveloppe convexe (convex hull). Une implémentation en .NET sur CADxp mais il me semble l'avoir aussi fait en LISP (peut-être sur TheSwamp)

[Fraid]

Bonjour,

Je ne suis pas sur d'avoir compris le truc

Mais il me semble avoir rencontrer un problème similaire avec des points que j'ai reliés en traçant une ligne entre chaque, ce qui m'a donner un polygone fermé.

tu peux le faire pour chaque poignées aussi

[Olivier Eckmann]

Bonjour,

 

Si on récupère chaque sommet de polyligne pour obtenir un ensemble de point, puis que l'on fait tourner un algo de ConcavHull ça devrait le faire.

La fonction de ConcavHull existe dans PostGis : http://www.postgis.org/documentation/manual-svn/ST_ConcaveHull.html

Je pense qu'il y a pas mal d'algo disponible pour cette problématique

 

Olivier

[Luna]

@Olivier Eckmann je vois que sa logique est similaire à la mienne xD

Quote

One can think of the concave hull as the geometry you get by vacuum sealing a set of geometries.

Après chacun(e) l'exprime à sa manière :3 En revanche, quel est le langage de programmation ? Et comment puis-je le tester ?
En tous cas, cela semble parfaitement adapté à ma recherche donc je vais creuser un peu plus.

@Fraid le soucis c'est que je n'ai pas de liste de points, pour cela, je dois la générer ! Créer une polyligne à partir d'une liste de points et simple mais générer cette liste est complexe :3

@(gile) oki je vais essayer de creuser un peu plus mais j'avoue que le C# et le F# je ne connais pas du tout donc je vais essayer de farfouiller un peu sur TheSwamp pour voir si je le trouve. Il semblerait que @Olivier Eckmann et toi parliez à peu près de la même chose (si je ne dis pas de bêtises).

Bisous,
Luna

[Fraid]

19 minutes ago, Luna said:

Créer une polyligne à partir d'une liste de points et simple mais générer cette liste est complexe

Pas tant que cela, et en donnant une limite de longueur au ligne, tu obtient la même chose (à peu près) que algorithme cité 

par contre si on ne fait pas attention, il y a beaucoup d'itérations

[(gile)]

Je savais bien, voir ce message et le suivant.

[(gile)]

Un algorithme qui devrait pouvoir être implémenté en LISP :
Concave hull: A k-nearest neighbours approach for the computation of the region occuppied by a set of points