Problème de géométrie tout simple - Page 1

... mais je suis trop con pour le résoudre



On connaît les ordonnées des points, et on sait que leurs abscisses sont consécutives.
On cherche une droite qui passerait sur le plan, de telle sorte que la moyenne de la distance des points par rapport à la droite soit nulle.

Pour parler intuitivement : il est clair que les points dessinent grossièrement une droite, et ma question revient à chercher l'équation de cette droite.

Si ce problème a une solution, alors je pourrais mettre au point un format de compression qui devrait être très performant d'après mes calculs (je préfère ne pas en dire plus pour éviter qu'on m'accuse de vaporware)

Merci beaucoup !

Tu veux dire quoi par "la moyenne de la distance des points par rapport à la droite"? Distance (projection orthogonale) ou distance verticale (projection parallèle à l'axe des ordonnées)? Et pour avoir la moyenne nulle, tu prends les distances orientées, n'est-ce pas?

normalement la distance a une droite c la projection orthogonale

Oui, mais de la manière qu'il le présente, ça me fait doûter. Je suppose qu'il veut coder des deltas par rapport à une droite prévue pour sa technique de compression, et les deltas sont des décalages en ordonnée seulement. L'abscisse est et reste le numéro de l'octet/bit/mot/unité.

si on sort du cadre des maths j'y connais rien donc je vais te croire sur parole

Je parle de la moyenne des distances "orthogonales", pas "verticales"

Ça ne s'appelle pas un régression linéaire ?

Bon, commençons par dire qu'il y a une infinité de possibilités. Raisonnement:
* Tu fixes une pente a arbitrairement (c'est de là que vient l'infinité de possibilités).
* Tu calcules ta moyenne des distances orientées (parce que tu dois bien parler de distances orientées - si tu prends une distance non orientée, elle n'est nulle que si tous les points sont exactement sur ta droite).
* Tu déplaces (translates) la droite de ta moyenne (longueur du vecteur de translation) en une direction (du vecteur de translation) orthogonale à sa direction et en un sens (du vecteur de translation) opposé à celui de ta moyenne de distances. Cela définit ton vecteur de translation de manière unique.
* Tu as une moyenne des distances orientées nulle.

Reste à fixer la pente a. Pour cela, tu devrais probablement la choisir de manière à minimiser l'amplitude des distances individuelles.

jackiechan
a écrit : Ça ne s'appelle pas un régression linéaire ?

Pas tout à fait. Ce qu'il veut est différent de manière subtile.

edit : une bêtise..

Si j'ai bien compris, il n'y a pas d'algorithme pour résoudre ce problème

il te faut une droite absolument ou une courbe ?

Une droite

Si je change le problème : il faut que la moyenne des distances soit la plus petite possible ?
Là, il y a une solution plus simple à trouver ?

A voir le shéma, une droite de régression linéaire ne correspondrait pas à cde que tu cherche ?

une courbe y a toujours l'interpolation de Lagrange; après tu prends la moyenne des dérivées et ca te donne ta pente. Ca peut etre pas mal

Tu ne veux pas expliquer ton principe de compression, ça m'intéresse

moi osi je pense +tot a de la reg lin mais bon ...

[google]régression linéaire[/google]

Ah non, en fait, je viens de relire l'énoncé du prob, et je ne pense pas qu'une régréssion linéaire fasse l'affaire. (comme l'a dit Kevin Kofler au début, en fait)

Ce que tu peux faire, c'est faire une régression linéaire standard pour avoir une pente, puis utiliser mon algorithme (#7) pour trouver l'ordonnée à l'origine correspondante. Mais je pense que ça ne te donnera pas la pente optimale. La pente donnée par la régression linéaire est celle qui donne les moindres carrés (least squares) avec l'ordonnée d'origine donnée. Si tu changes l'ordonnée à l'origine pour avoir une moyenne des distances orientées nulle, la pente ne sera probablement plus optimale.

tout a fait, c pas une régressionn car si on prend les points:
A (-1,3)
B (1,-1)
C (3,1)
on devrait trouver la droite y=x or avec une regression, on a:
y= - 0.5 x + 1.5

Ptet prendre le barycentre des points et faire tourner une droite sur ce point tant que les mileux sont pas nuls ....

Kevin Kofler
a écrit : Mais je pense que ça ne te donnera pas la pente optimale. La pente donnée par la régression linéaire est celle qui donne les moindres carrés (least squares) avec l'ordonnée d'origine donnée.

C'est laquelle, qui est optimale ? Puisqu'il y a une infinité de solutions ?

bon je cherche parcque la c plus une ti qui fô, c un ordinateur de décryptage rsa!

Tout d'abord, merci, vraiment, de votre participation massive

Vous avez vu le post #12 ?

jackiechan #15 : Je préfère garder toute info pour moi tant que mon système de compression est à l'état de création. C'est pour éviter des déceptions.
Pour être bref, j'ai inventé une méthode pour compresser des données audio. D'après mes calculs, si je ne me suis pas trompé bien sûr, la taille d'un WAV devrait se voir divisée par 10. La qualité ? je n'en sais encore rien. On le saura seulement quand l'encodeur fonctionnera. Il se pourrait qu'elle soit très bonne (aucune fréquence n'est éléminée, contrairement au MP3).
Elle est composée de beaucoup d'étapes d'analyse. Il n'y en a qu'une qui compresse les données avec des pertes. Je crois que cette étape se rapproche de ce qu'on appelle la compression par ondelettes.

jackiechan a écrit :
C'est laquelle, qui est optimale ? Puisqu'il y a une infinité de solutions ?

Je ne sais pas a priori.

Kevin Kofler a écrit :
Je ne sais pas a priori.

Non, mais je veux dire, elle est caractérisée par quoi quand elle est optimale ? Qu'est-ce qui la rend optimale ?

Suite du #23 : Pour l'anecdote, cette méthode m'est venu pendant que j'avançais mon IA de Dames

Thibaut> Tu m'as l'air doué en algorithmie Je ne sais pas si tu as lu des bouquins ou si tu trouves tout ça tout seul, mais je trouve que es doué.
Tu iras peut-être en finale au concours Prologin... (d'ailleurs, c'est/était quand, ta demi-finale ?)

jackiechan
a écrit : Non, mais je veux dire, elle est caractérisée par quoi quand elle est optimale ? Qu'est-ce qui la rend optimale ?

Le fait que la somme des carrés des distances des points à la droite est minimale (tout en gardant intact le critère de Thibaut; la différence avec la régression linéaire est en cette condition supplémentaire limitant la rangée de valeurs possibles).

jackiechan : pas tant que ça, vu que j'ai pas réussit à trouver d'algo pour résoudre cette étape de la compression
C'était le 1er Février ma demi-finale.