---

hi lispler!

ist nicht gerade ein lisp-problem, aber ich versuch' es trotzdem mal hier:

gegeben ist ein punkthaufen mit n punkten.
durch diesen punkthaufen soll eine "ausgleichende gerade" gelegt werden, die mir eine optimale fehlerverteilung ergibt. (z.B. gebäudeflucht, bestimmt über mehr als zwei punkte)
in der vermessung löst man so eine aufgabe i.d.r. mit einer ausgleichung beginnend mit der aufstellung von fehlergleichungen.
ich bin mir aber nicht so ganz sicher ob ich mit diesem verfahren zum ziel komme, da ich glaube, dass es für die "ausgleichende gerade" keine eindeutige lösung gibt. (z.B. 4 Punkte die genau auf einem quadrat liegen -> 4 Lösungen)
hat sich jemand schon mal mit dem thema beschäftigt und evtl. einen lösungsansatz, einstieg etc.

ciao georg

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Tag.

Ja, ich habe mich schon einmal mit diesem Thema befasst, das dürfte allerdings so um die 15 Jahre her sein und ist dem entsprechend nicht mehr besonders parat.

Das Verfahren zur Gewinnung einer, wie du sie nennst "Ausgleichsgeraden" durch eine 2D-Punktmenge heißt lineare Regression und angewandt wird meist die Methode der kleinsten Quadrate. Nun kenne ich die vermessungs-technischen Verfahren kein bißchen, nehme aber an, dass es da die selben Verfahren zum Einsatz kommen.

Nach einem passenden Algorithmus wirst du allerdings selber suchen müssen, denn ich habe gerade keinen parat. Allerdings lässt sich, soweit mich meine Erinnerung nicht allzu sehr trügt, die Methode der kleinsten Quadrate als Lösung einens Linearen Gleichungs-Systems vergleichsweise einfach implementieren. Als Einstig sollte dir das ersteinmal genug Stoff zum Stöbern bieten.

Achim Dabrunz

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Mal einen unoptimierten Ansatz auf Lisp : (funktioniert so wie Achim angedeutet hat)

(defun Ausgleichsgerade ( PUNKTLISTE / N X Y SUMMEX SUMMEY SUMMEXY SUMMEX2)
  (if (and(=(type PUNKTLISTE) 'LIST) (> (length PUNKTLISTE) 1))
    (progn   
      (setq N (length PUNKTLISTE)
            SUMMEX  0.0
            SUMMEY  0.0
            SUMMEX2 0.0
            SUMMEXY 0.0
      )     
      (foreach PKT PUNKTLISTE       
        (setq X (car  PKT))
        (setq Y (cadr PKT))       
        (setq SUMMEX  (+ SUMMEX X))       
        (setq SUMMEY  (+ SUMMEY Y))       
        (setq SUMMEX2 (+ SUMMEX2 (* X X)))       
        (setq SUMMEXY (+ SUMMEXY (* X Y)))       
      )
      ;Anstieg
      (setq A (/ (-(* N SUMMEXY)(* SUMMEX SUMMEY))
                (-(* N SUMMEX2)(* SUMMEX SUMMEX))
              ) 
      )
      ; Schnittpunkt mit y-Achse
      (setq B (/ (-(* SUMMEX2 SUMMEY) (* SUMMEX SUMMEXY))
                (-(* N SUMMEX2)(* SUMMEX SUMMEX))
              ) 
      )     
      ; Entsprechende Konstruktionslinie
      (entmake (list '(0 . "XLINE")
                    '(100 . "AcDbEntity")
                    '(100 . "AcDbXline")
                      (cons 10 (list 0.0  B  0.0))
                      (cons 11 (list 1.0  A  0.0))   
              )
      )
    ) 
  )               
)

Aufruf dann z.B. mit
(Ausgleichsgerade '((13.3164 12.8242 0.0) (2.57726 32.9874 0.0) (14.1569 47.643 0.0) (-2.65223
3.116 0.0) (-34.216 4.60957 0.0)))

------------------
- Thomas -

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Klasse!

Ich konnte mich nicht mehr daran erinnern, dass in diesem Fall 'ne geschlossenen Lösung vorliegt (muss auch zugeben, dass ich ersteinmal im Bronstein nachgeschlagen hab', weil ich's nicht glauben konnte - hätte ich vielleicht gleich tun sollen).

Auf den 1. Blick lässt sich hier auch nicht mehr viel optimieren - jedenfalls nicht mit der geschlossen Lösungs-Form. Unter 4*n Additionen und 2*n Multiplikationen ist hier wohl nix zu machen. Evtl. lässt sich noch etwas Zeit durch Anwendung von apply und mapcar gewinnen, aber das ändert nix am allgemeinen Laufzeitverhalten - es ergibt sich höchstens ein konstanter Faktor als Verbesserung.

Achim Dabrunz

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

ag.txt

hallo achim und thomas!

methode der kleinsten quadrate ist auch das verfahren das in der ausgleichsrechnung verwendet wird.
hab' natürlich sofort den code von thomas ausprobiert und dabei folgendes überraschendes ergebnis erhalten. (siehe anhang fall 2 = fall 1 um 100gon gedreht  txt=dwg).
denke dass das ganze auch nicht so einfach zu lösen ist, zumindest nicht ohne vorgegebenen näherungswert. wie "erkläre" ich z.B. einem algorithmus, dass bei einer punktwolke ähnlich einem rechteck die gerade senkrecht zu den langen seiten ausgerichtet sein soll.

ciao georg

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

... ja, beim drehen werden aus den "x" ja auch die "y" , und der Algorithmus unterscheidet ja zwischen x und y und deren Summen. Aber mehr als 2 Lösungen dürfte es nicht geben...

Mußt du halt für deine Zwecke noch ein bißchen anpassen ;D

------------------
- Thomas -

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Ok - Ok, eigendlich wollte ich ja nicht allzu tief in die Materie einsteigen, aber jetzt ist's zu spät ..

Dei Lineare Regression ist eine Methode aus der Statistik und liefert nur unter bestimmten Voraussetzungen ein passendes Resultat. Zu diesen Voraussetzungen gehört:

• es gibt eine lineare Abhängigkeit zwischen X und Y
  
• die Abweichung der "Messpunkte" Y von der optimalen Gerade ist normalverteilt
  

Sind diese Voraussetzungen nicht erfüllt, dann wird's nix mit der Regressions-Geraden.

Den ersten Punkt kannst du mit dem sog. Korrelationskoeffizienten prüfen, musst du aber nicht, wenn du von vorne herein weißt, dass eine Gerade zugrunde liegt.

Recht gut verständlich werden die Zusammenhänge in diesem Selbstlern-Projeket für die Jahrgangsstufe 11 erläutert. Dort kann man auch ganz gut sehen, dass die Ermittlung einer Regressions-Geraden nicht eindutig ist.

Als kleine Ergänzung noch mal die nötigen Formeln:

(SCHLAMPEREI: Ich habe eine Wurzel vergessen und dann ohne Überlegung 'rumgeschlampt! das habe ich aber jetzt korrigiert)

Ich werde die auch noch später in Code fassen, wenn's jemand wünscht.

Achim Dabrunz

[Diese Nachricht wurde von Dabrunz am 06. Jul. 2004 editiert.]

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP