Trouver le nombre de segments qui se croisent le moins

[anthonyF]

Bonjour,

Imaginons un ensemble de segments générés aléatoirement, donc qui se croisent fortement.

Comment pourrait ton identifier le sous-ensemble comportant un maximum de segments qui se croisent le moins !

J'ai essayé en réduisant l'ensemble par soustraction des segments qui en croisent le plus d'autres segments, mais ça le marche pas.

J'ai l'idée de soustraire par les angles des droites les plus loin de l'angle moyen de l'ensemble... mais je n’espère pas de résultat

On peut considérer plusieurs centaines de segments, donc un parcours total serait de l'ordre de x00! un peu trop grand.

Des idées, ou références sur ce travail ?

[nodjim]

J'imagine que les segments sont dans le plan, à confirmer.
Ta question n'est pas claire. Si tu as 1 segment isolé, tu ne pourras pas faire mieux que zéro croisement. Pareil, tu pourrais regrouper tous les segments isolés dans un sous ensemble, et alors zéro croisement. Apparemment, ce n'est pas vraiment ça que tu recherches. Il faut donner des précisions.

[Ben314]

Même réponse pour moi : ton énoncé ne permet pas de savoir s'il vaut "mieux" avoir par exemple 50 segments avec 60 points d'intersections ou plutôt 45 segments avec 54 intersections...
Et, évidement, temps qu'on ne connait pas la relation de classement, on risque pas d'avoir une idée de qui est "le meilleur"...

[anthonyF]

Même réponse pour moi : ton énoncé ne permet pas de savoir s'il vaut "mieux" avoir par exemple 50 segments avec 60 points d'intersections ou plutôt 45 segments avec 54 intersections...
Et, évidement, temps qu'on ne connait pas la relation de classement, on risque pas d'avoir une idée de qui est "le meilleur"...

Merci pour vos reponses

Mon besoin est d'identifier l'ensemble maximun, le plus grand nombre de segment qui ne croisent aucun autre segments = retirer le minimun de segment du groupe, jusqu'a ce que plus aucun segment ne croise d'autre segments

[beagle]

bon on ne comprend toujours pas où sont ces segments, dans tout le plan,
dans un carré , dans un rond, dans ...
combien sont-ils,comment tu génères des segments aléatoires?

perso sans rien comprendre mais en en parlant quand mème je prends le sous-ensemble des plus petits segments...

[anthonyF]

bon on ne comprend toujours pas où sont ces segments, dans tout le plan,
dans un carré , dans un rond, dans ...
combien sont-ils,comment tu génères des segments aléatoires?

perso sans rien comprendre mais en en parlant quand mème je prends le sous-ensemble des plus petits segments...

Dsl: Tous les segments sont dans un plan. Ils se croisent fortement.

Si vous voulez voir un exemple, voila un lien : http://jsfiddle.net/afaucogney/RwNXL/

Dans mon cas, j'ai deux carrés (un gauche un droite) :
Un segment aleatoire =
Une ligne entres 2 points aleatoires :
- Un a gauche
- Un a droite

Voila

[nodjim]

Là c'est plus clair, car moins tu ôtes de segments, plus ton nombre de segments isolés sera grand.
La stratégie que je choisirais serait de conserver les segments à peu près horizontaux.
En revanche, s'il faut chercher la preuve de la meilleure config., c'est autre chose....

[beagle]

en partie d'accord avec nodjim,
des quasi horizontaux, de toutes tailles si près d'un bord
plus c'est près du bord plus on peut prendre les grands quasi horizontaux,

puis plus on va vers segment qui coupe vers le centre, plus faut réduire la taille mais on peut alors
accepter plus d'inclinaison

les grands quasi horizontaux qui coupent près du centre ne sont pas top ...