Version imprimable
Soit un quadrilatère Q dont les 2 diagonales font 1700cm et 1800 cm
On recherche une famille de surfaces convexes S1,...,Sn de Q tel que
- la distance entre Si et Sj est tj >= à 500cm
- chaque Si a une surface maximale égal à 1/17 de la surface du quadrilatère
- la somme des surfaces Si est maximale
Qui sait faire?
J'ai pas bien compris cette partie. :koi:Citation:
Envoyé par Nemerle
tu cherches à faire un pavage du quadrilatère ?
Tu travailles dans quoi et où Nemerle ? T'as souvent des problèmes de maths durs mais marrants ou intéressants.
Le problème aurait été peut-être plus simple s'il n'y avait pas la contrainte d'optimalité sur la somme des Si...
Chuuut!! C'est secret! :mouarf:Citation:
Envoyé par HanLee
Inspiration pratique:
j'ai un terrain et je veux y construire des enclôts de la taille de 1/17 du terrain, chaque enclôt étant à au moins 500m de distance des autres.
Je proposerais ça... je ne sais si ça suffit.
- Mettons qu'on soit sur un segment S de longueur L plutôt qu'un quadrilatère Q.
Sur ce segment, il faudrait placer des segments Si de 1/17 de la longueur de S.
Entre chaque Si on aurait la contrainte d'espacement e (500cm).
Il y a n segments Si, et (n - 1) espacements. Donc L = n * (L/17) + (n - 1) * e.
D'où n.
- En 2 dimensions sur un quadrilatère Q (est il quelconque ? d'après l'énoncé c'est au moins un parallélogramme... ?)
Il faudrait appliquer le raisonnement sur l'un des cotés de Q, pour ne pas perdre l'espacement dans les deux dimensions L1 et L2. Donc les Si seraient des bandes.
On choisit le coté en fonction du max de n1 * L1 * L2 et du max de n2 * L1 * L2. Où n1 et n2 se trouvent en appliquant le calcul pour le "coté-segment" correspondant.
Qu'en pensez vous ?
Pourquoi ne pas juste découper le quadrilatère en pavés (taille 1/17, forme quelconque, avec un contour de 250cm) et fusionner les pavés trop petits (ceux qui sont sur le bords du quadrilatère) ?
Pseudocode: pas une mauvaise idée, tu fais alors varier ton maillage pour trouver une bonne solution.
Mais cela ne donnera pas la meilleure solution...
Alikendarfen: le quadrilatère est convexe, mais pas parallélogramme; et puis l'objectif sera après d'appliquer l'algo sur une forme de terrain quelconque).
Petite remarque: si on "place" une surface S dans le quadrilatère, on peut chercher à minimiser la surface S+T, où T est la surface des points alors interdits (règle de l'espacement de 500 mètres). Quelle est la forme de la surface S qui minimise S+T ? Y-a p'tèt différents cas...
une solution :
tu places 1 boite de taille max dans un angle.
tu additionnes a son contour la distance mini.
tu en deduis le nouveau contour interieur de Q.
Tu iteres... Si taille max ne peut plus rentrer, tu diminues taille
Pourquoi vous prenez forcément un quadrilatère en guise de convexe ?
parce que c'est sa contrainte initiale :P
Moi j'ai pas dit quadrilatère. :koi:Citation:
Envoyé par HanLee
Non, c'est le terrain qui est en forme de quadrilatère. Après, on le remplit avec des surfaces convexes au choix.Citation:
Envoyé par souviron34
Ben, tu as dit pavé non ?Citation:
Envoyé par pseudocode
-------
Je critique pas, je me demande juste. Pourquoi pas des polygones qui comportent en guise de segments quelques arcs de cercle, plutôt que des polygones tout bêtes ?
j'aurais tendance a dire un triangle.....Citation:
Envoyé par Nemerle
par exemple comme ca:Citation:
Envoyé par HanLee
http://www.eggs-luginbuhl.ch/images/paves.jpg
Nan ;) faut pas oublier la figure la plus belle de l'univers...Citation:
Envoyé par souviron34
Et je reste preneur de toute idée les gars! P'têt semaine prochaine, je vous dirais ce que j'ai mis en place...
Ah... les énigmes de Nemerle. Ca m'énerve. A chaque fois, j'ai des pages de mon bloc-note remplies de dessins. :evilred:
Vivement la réponse. ;)
Citation:
Envoyé par Nemerle
Citation:
Envoyé par pseudocode
Citation:
Les gros cailloux
Un jour, un vieux professeur de l'École nationale d'administration
publique (ENAP) fut engagé pour donner une formation sur la
planification efficace de son temps à un groupe d'une quinzaine de
dirigeants de grosses compagnies nord-américaines. Ce cours constituait
l'un des cinq ateliers de leur journée de formation. Le vieux prof
n'avait donc qu'une heure pour "passer sa matière".
Debout, devant ce groupe d'élite (qui était prêt a noter tout ce que
l'expert allait enseigner), le vieux prof les regarda un par un,
lentement, puis leur dit : "Nous allons réaliser une expérience".
De sous la table qui le séparait de ses élèves, le vieux prof sortit
un immense pot Masson d'un gallon (pot de verre de plus de 4 litres)
qu'il posa délicatement en face de lui. Ensuite, il sortit environ une
douzaine de cailloux a peu près gros comme des balles de tennis et les
plaça délicatement, un par un, dans le grand pot.
Lorsque le pot fut rempli jusqu'au bord et qu'il fut impossible d'y
ajouter un caillou de plus, il leva lentement les yeux vers ses élevés
et leur demanda : "Est-ce que ce pot est plein?". Tous répondirent :
"Oui". Il attendit quelques secondes et ajouta : "Vraiment?".
Alors, il se pencha de nouveau et sortit de sous la table un
Récipient rempli de gravier. Avec minutie, il versa ce gravier sur les gros
cailloux, puis remua légèrement le pot. Les morceaux de gravier
s'infiltrèrent entre les cailloux... jusqu'au fond du pot.
Le vieux prof leva a nouveau les yeux vers son auditoire et
redemanda: "Est-ce que ce pot est plein?". Cette fois, ses brillants élèves
commençaient à comprendre son manège. L'un d'eux répondit :"Probablement pas!". "Bien!" répondit le vieux prof.
Il se pencha de nouveau et cette fois, sortit de sous la table un
Seau de sable. Avec attention, il versa le sable dans le pot. Le
sable alla remplir les espaces entre les gros cailloux et le gravier.
Encore une fois, il demanda :"Est-ce que ce pot est plein?". Cette fois, sans
hésiter et en chœur, les brillants élèves répondirent :"Non!".
"Bien!" répondit le vieux prof.
Et comme s'y attendaient ses prestigieux élèves, il prit le pichet
d'eau qui était sur la table et remplit le pot jusqu'à ras bord. Le vieux
prof leva alors les yeux vers son groupe et demanda :"Quelle grande
vérité nous démontre cette expérience?"
Pas fou, le plus audacieux des élèves, songeant au sujet de ce
cours, répondit :"Cela démontre que même lorsque l'on croit que notre
agenda est complètement rempli, si on le veut vraiment, on peut y ajouter
plus de rendez-vous, plus de choses à faire".
"Non" répondit le vieux prof. "Ce n'est pas cela. La grande vérité
que nous démontre cette expérience est la suivante : si on ne met pas
les gros cailloux en premier dans le pot, on ne pourra jamais les faire
entrer tous, ensuite".
Il y eut un profond silence, chacun prenant conscience de l'évidence
de ces propos.
Le vieux prof leur dit alors : "Quels sont les gros cailloux dans
Votre vie?" "Votre santé?" "Votre famille?" "Vos ami(e)s?" "Réaliser vos
rêves?" "Faire ce que vous aimez?" "Apprendre?" "Défendre une cause?"
"Relaxer?" "Prendre le temps...?" "Ou... toute autre chose?"
"Ce qu'il faut retenir, c'est l'importance de mettre ses GROS
CAILLOUX en premier dans sa vie, sinon on risque de ne pas réussir...sa vie.
Si on donne priorité aux peccadilles (le gravier, le sable), on
remplira sa vie de peccadilles et on n'aura plus suffisamment de temps précieux
a consacrer aux éléments importants de sa vie.
Alors, n'oubliez pas de vous poser a vous-même la question : "Quels
sont les GROS CAILLOUX dans ma vie?" Ensuite, mettez-les en premier dans
votre pot (vie)"
D'un geste amical de la main, le vieux professeur salua son
auditoire et lentement quitta la salle.
Surface maximale -> 18 m²
Si on ne tient pas compte des bornes, on doit donc avoir des hexagones de 2.4 m de côté espacés de 5m.
Mais les bornes sont très importantes car si on essaie simplement de prendre la solution régulière et de placer le quadrilatère au meilleur endroit, on en aura maximum 4, vraisemblablement pas complète. Il est possible que ce soit la meilleure solution, mais il avoir une zone centrale et 4 zones aux sommets du quadrilatère a des chances d'être meilleur (les zones n'ayant plus alors à être hexagonales, non seulement on en a plus, mais elles peuvent être plus complètes).
Desolé du retard, suis débordé en ce moment :(
Une surface Si placée qui minimise la place perdue (règle des 500 cm), ça a quelle forme? Par exemple, le long d'un bord, c'est
http://www.imageshotel.org/thumbs/Nemerle/test1.jpg
La réponse est: la portion de disque (et ceci est vrai dans tous les cas): si S est la surface maximale autorisée,
- le "rectangle" qui minimise la surface d'espacement est L=sqr(2S) et l=sqr(S/2)
- mais il est battu par le demi-disque de rayon R=sqr(2S/pi)
Donc clairement, il faut commencer au sommet d'un des 4 angles le plus aigu. Une fois la première étape effectuée, si l'on veut "avancer", continue-t-on avec l'une ou l'autre des possibilités suivantes?
http://www.imageshotel.org/thumbs/Nemerle/test2_1.jpg
La réponse est: la 1ière option, mais dans ce cas il faut savoir calculer la surface d'intersection de 2 disques, afin de pouvoir connaitre le rayon à partir de notre surface max autorisée... ça je sais faire ;)
A partir de là, un algorithme commence à s'imposer... mais ce n'est pas si simple que cela...
Dans le cas où le terrain est non convexe, on se heurte à des cas encore plus difficile. Par exemple:
http://www.imageshotel.org/thumbs/Nemerle/test3.jpg
Le calcul de la surface est.... je ne sais pas! :mouarf:
No return? ;)