Schnittpunkte von zwei Punktewolken

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
zauro
User
Beiträge: 9
Registriert: Freitag 8. Januar 2010, 23:01

Hallo Leute,

ich bin neu hier im Forum und habe schon meine erste Frage.
Wie kann ich von zwei Punktewolken die Schnittpunkte errechnen. Vielleicht könnt ihr mir eine Anregung geben.

Eine Punktewolke soll z.B. eine Gerade sein und die andere eine beliebige Funktion.

Danke schon mal.

Gruß Zauro
Benutzeravatar
Defnull
User
Beiträge: 778
Registriert: Donnerstag 18. Juni 2009, 22:09
Wohnort: Göttingen
Kontaktdaten:

Haben Punktwolken überhaupt Schnittpunkte?

Du könntest stumpf die nähe der Punkte prüfen, also das Minimum der Entfernung zweier beliebiger Punkt aus verschiedenen Wolken. Aber das ist eigentlich kein Python Problem.
Bottle: Micro Web Framework + Development Blog
...
User
Beiträge: 116
Registriert: Mittwoch 23. Dezember 2009, 20:22

Wenn die Punktewolken Funktionen darstellen sollen, dann hoffe ich, die Funktionen sind bekannt.

Dann könntest du sie nach x auflösen, die eine von der annern Abziehen, und hättest den Schnittpunkte...

Alternativ: Gugg dir mal matplotlib an.
Ich kann mir gut vorstellen das da entsprechende Funktionen verfügbar sind.

Immerhin macht das ja auch fast alles mit Punktwolken.
zauro
User
Beiträge: 9
Registriert: Freitag 8. Januar 2010, 23:01

Hallo Leute,

die Funktionen der beiden Graphen kenne ich leider nicht, aber das ist auch nicht wirklich von interesse für mich. Ich benötige eben nur den Schnittpunkt von zwei Kurven. Die Punkte zwischen zwei benachbarten Punkten einer Punktewolke sind linear miteinander verbunden.

Ich hänge mal ein Bild des Problemes an.

Bild
EyDu
User
Beiträge: 4881
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Hallo.

Dann teste auf den Schnitt zweier Segmente.
Das Leben ist wie ein Tennisball.
zauro
User
Beiträge: 9
Registriert: Freitag 8. Januar 2010, 23:01

und wie mach ich das am sinnvollsten?

also man könnte ja das scalarprodukt schrittweise anwenden und wenn da ein schnittwinkel bei rum kommt, schneiden sich die geraden .... aber das erscheint mir nicht als sinnvoll.

ich hatte seinerzeit mal ne funktion, die das in matlab konnte und hab das dann mal versucht in python zu implementieren ... ich häng den versuch mal auch an. Aber bitte nicht schlagen!!
Irgendwo ist der Wurm da drin. für ausnahmen scheint es zu funktionieren, aber nicht für das zuvor angehängte problem.

christians-carnivoren.de/curveintersect.py
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

@zauro:
So, Ich fürchte, so wie Du Dein Problem beschreibst, wird wohl kaum einer richtig helfen können. Wenn Du Deine Kurven nicht eindeutig beschreiben kannst, kannst Du auch keinen Schnittpunkt finden.

Aus zwei Punkten in der Ebene, läßt sich aber schon mal eine Geradengleichung austellen.

Dann fehlt noch die andere Kurve.
zauro
User
Beiträge: 9
Registriert: Freitag 8. Januar 2010, 23:01

Na dann versuche ich das noch einmal ein bisschen auszuschmücken.

Ich habe zwei Kurven. Eigentlich soll es egal sein, wie die Kurven (Funktionen sind unbekannt) geartet sind. Ich möchte eine Funktion haben, die es mir dann ermöglicht sämtliche Schnittpunkte der beiden Kurven zu ermitteln.
In diesem speziellen Fall ist die eine Kurve so geartet, dass sie streng monoton fallend ist und die andere streng monoton wachsen (annährend eine Gerade).
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Wie bereits gesagt, kannst Du die Schnittpunkte einfach ausrechnen, wenn Du die Funktionen kennst. Für eine numerische Lösung kann z.B. das helfen.
MfG
HWK
zauro
User
Beiträge: 9
Registriert: Freitag 8. Januar 2010, 23:01

Leider kenne ich keine der beiden Funktionen.

Hat sich einer mal das Bild (daraus wird ersichtlich, dass es keine normale math. Funktion ist) und das Python Skript angeschaut und dort eventuell den Fehler entdeckt?
BlackJack

@zauro: Ist mir persönlich jetzt ein wenig zu lang und unübersichtlich. Und Du solltest Dich mal mit dem Python-Tutorial auseinandersetzen. So oft wie da das Muster ``for i in range(len(obj))`` vorkommt, ist das dringend nötig. ;-)

Ausserdem scheinst Du da einen Haufen Zeugs nachzubauen, den `numpy` schon kann. Du importierst das ja sogar.
zauro
User
Beiträge: 9
Registriert: Freitag 8. Januar 2010, 23:01

Hi BlackJack

ja du hast in der Tat recht, dass ich ziemlich viele sachen, da genutzt habe, die Numpy eigentlich schon hat. Als ich damals das erste mal diese Funktion gebaut habe, hatte ich nur einen Rechner mit Standartpython installation zur Verfügung. Dort wars auch nicht möglich Numpy und andere Erweiterungen zu installieren.

Wo finde ich denn das Tutorial ?
BlackJack

@zauro: Das Tutorial ist Bestandteil der Python-Dokumentation.

Dein eigenes Bubblesort ist auch nett. Listen haben eine `sort()`-Methode. ;-)
zauro
User
Beiträge: 9
Registriert: Freitag 8. Januar 2010, 23:01

kann man mit der sort methode auch zwei listen sortieren, die voneinander abhängen? Ich meine hiermit z.B. die x und y koordinaten einer Kurve.
Benutzeravatar
cofi
Python-Forum Veteran
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Ja, du kannst eigene Compare-Funktionen uebergeben: http://docs.python.org/library/stdtypes ... ence-types
BlackJack

@zauro: Man kann als Sortierkriterium auch die Elemente einer anderen Liste mit dem `key`-Argument angeben. Das klingt aber nicht besonders gesund. Wenn die Elemente zusammengehören sollten sie nicht in *zwei* Listen stecken, sondern in *einer*.
zauro
User
Beiträge: 9
Registriert: Freitag 8. Januar 2010, 23:01

Der Source Code, den ich angehangen hatte, funktioniert übrigens doch. Allerdings muss darauf geachtet werden, dass die x Komponenten aufsteigend sortiert sein müssen. Das habe ich gerade herausgefunden.

wie sollte denn dann die Liste ausschauen, wenn ich da x- und y- Koordinaten drin haben möchte ? so [[x1,y1],[x2,y2]] ?

Ich danke euch schon mal für die Hilfe. Hoffentlich wird mein Programmierstil immer besser, da ich einen Großteil meiner Promotion in Python schreiben werde.
BlackJack

@zauro: Zum Beispiel so, oder als Tupel für die Punkte.
BlackJack

@zauro: Wenn Du in mehr in Python machen willst, dann lohnt sich vielleicht noch eine ausführlichere Kritik am gezeigten Quelltext.

Einrücken solltest Du mit 4 Leerzeichen pro Ebene statt Tabs. Dann läufst Du nicht Gefahr irgendwann Einrückungsfehler zu haben, die man nicht so ohne weiteres sieht, und man kann Quelltext besser mit anderen Leuten austauschen.

Dateien ab Python 2.5 wenn es geht mit ``with`` öffnen. Dann werden die auch in jedem Fall wieder ordnungsgemäss geschlossen. Bei Python 2.5 braucht man dafür noch ein ``from __future__ import with_statement`` als erste Anweisung im Programm, ab 2.6 gibt es die ``with``-Anweisung auch ohne diesen ``import``. Die `dat_write()` könnte dann so aussehen:

Code: Alles auswählen

def dat_write(vektor, filename):
    with open(filename, 'w') as datei:
        datei.writelines('%s\n' % i for i in vektor)
Typprüfungen sollte man vermeiden, und wenn dann nicht mit `type()` sondern `isinstance()` durchführen. Aber wie gesagt: am besten vermeiden. Die Funktionen von `numpy` sind da in gewisser Hinsicht schlechte Beispiele, dass die meisten auf Skalaren *und* "iterables" funktionieren. Auf die Weise geht immer irgendwo etwas "duck typing" verloren. Also die `signum()`-Funktion macht da IMHO zum Beispiel zuviel in der Richtung. Da hätte ich eher eine für Skalare geschrieben und eine für "iterables", und zwar für *alle* und egal was da *drin* ist. Wobei eine extra Funktion für "iterables" vielleicht sogar zuviel ist, denn es gibt ja `map()` und `itertools.imap()`. Dein `signum()` funktioniert zum Beispiel nicht für `float`, `decimal.Decimal` aus der Standardbibliothek, oder `gmpy.mpq`-Exemplaren, und das alles nur wegen dem expliziten Test auf den Typ `int`. Die Funktion hier kann das alles:

Code: Alles auswählen

def signum(x):
    if x == 0:
        return 0
    if x > 0:
        return 1
    if x < 0:
        return -1
    
    raise TypeError('Can not determine sign of %r' % x)
Und wenn man jetzt eine Liste mit solchen Zahlen hat, kann man einfach ``map(signum, liste)`` schreiben. Statt der Liste geht auch jedes andere iterierbare Objekt mit entsprechendem Inhalt. Das wird bei Deiner Funktion auch wieder durch die Typtests verhindert.

Bei `isempty()` hast Du auch wieder ein Typproblem. Das funktioniert nur mit Listen. Die Verwendung von `len()` würde dagegen mit viel mehr Typen funktionieren.

Was zum Henker ist `isequal()`? Das ist wohl zu ziemlich das Umständlichtste was ich für einen einfachen Vergleich bisher gesehen habe:

Code: Alles auswählen

def isequal(a, b):
    return a == b
Aber dafür würde ich keine Funktion schreiben. Und bei Python sollte man `True` und `False` anstelle von Zahlen nehmen, wenn man einen Wahrheitswert meint. Aus historischen Gründen kann man damit sogar Rechnen, denn ein `True` verhält sich wie eine 1 und ein `False` wie eine 0. Ist nicht schön, und sollte man nur in Code-Golf-Contests machen, aber es geht, wenn's sein muss. :-)

Dein `unique()` hat ein gruseliges Laufzeitverhalten. Das ist ziemlich deutlich eine Mengenoperation, dann sollte man auch `set()` verwenden:

Code: Alles auswählen

def unique(x, y):
    return sorted(set(x).update(y))
`any()` gibt's schon! Liesse sich aber auch einfacher implementieren, wenn man's selber machen müsste:

Code: Alles auswählen

def any(iterable):
    return True in itertools.imap(bool, iterable)
*Hust* `arange()` macht genau das was `range()` macht, mit Hilfe der `range()`-Funktion. ;-)

Code: Alles auswählen

In [77]: range(5, 10)
Out[77]: [5, 6, 7, 8, 9]
Der Rest ist mir zu kompliziert. :-)
BlackJack

Und noch einmal ich. Hier sind zwei Varianten, die das gleiche Ergebnis für Dein Beispiel berechnen. Alles Python 2.5-Standard, keine externe Bibliothek:

http://paste.pocoo.org/show/163787/
Antworten