Die Mathe-Redaktion - 23.06.2018 10:28 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 260 Gäste und 16 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Effizienter Algorithmus für diskrete Projektion
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Effizienter Algorithmus für diskrete Projektion
gaussmath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.06.2007
Mitteilungen: 9039
Aus: Hannover
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-05-21


Hallo,

ich benötige einen effizienten Algoritmus für eine diskrete Projektion. Zunächst einmal eine Grafik, um den Sachverhalt zu verdeutlichen.



Gegeben ist eine diskretisierte Kurve P. Die Punkte liegen in einer beliebigen Reihenfolge vor, was übrigens das Problem ist. Weiterhin ist eine diskretisierte Linie L mit einer Auflösung res gegeben. Die Aufgabe ist es nun, L auf P zu projizieren.

Da nicht zu jedem Punkt aus L ein Projektionspunkt auf P existiert (Lücken), sollen einfach alle Punkte von P genommen werden, die im Bereich (x_start, x_end) von L liegen.

Das Problem ist nun, dass die Punkte auf P, die hinter der Kurvenfont liegen, natürlich nicht betrachtet werden sollen. Im Grund brauche ich eine Kurvenverfolgung von (x_start,y_start) nach (x_end,y_end).

Was ich gemacht habe bisher, ist nun, dass ich mit einem AlphaShape Algoritmus die konkave Kurve von P berechne, was mir die richtige Reihenfolge der Punkte auf P liefert. Leider ist die Laufzeit zu groß.

Hat jemand Ideen?

Grüße, Mark



  Profil  Quote  Link auf diesen Beitrag Link
Yggdrasil
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.07.2004
Mitteilungen: 812
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-05-25


Hallo Gaussmath,

kannst du dich bei der Suche nicht einfach auf die Punkte einschränken, welche im Bereich (x_start, x_end) von L liegen? Dann müsste der AlphaShape-Algorithmus, stückweise angewendet, doch schneller laufen‽ (Ich sehe beim Überfliegen der Wikipedia-Seite keine Angabe zur Laufzeitkomplexität…)
(Könnte andererseits sein, dass man damit nur einen Sortierungsschritt /Filter gleich am Beginn des Algorithmus auslagert.)

Des weiteren wäre noch wichtig zu wissen wie gutartig die Daten aussehen.
Man kann sich ja viele Kriterien ausdenken, um weiter entfernt liegende Punkte auszusortieren, wenn die Objekte in der Praxis gewisse Kriterien erfüllen (z.B. Krümmung der Kurve beschränkt; Auflösung feiner als minimaler Durchmesser des Objektes, etc.)


Gruß Yggdrasil



  Profil  Quote  Link auf diesen Beitrag Link
sebp
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 10.12.2017
Mitteilungen: 119
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-05-25


Wie kann es denn sein das eine Kurve gegeben ist,
aber die Punkt keine Reihenfolge haben?
Hast du dann eine Punktwolke und einen vorgegebenen Algorithmus?



  Profil  Quote  Link auf diesen Beitrag Link
gaussmath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.06.2007
Mitteilungen: 9039
Aus: Hannover
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2018-05-30 09:57


Hallo,

vielen Dank für eure Antworten.  smile

Zunächst einmal zur Thematik der Reihenfolge der Punkte. Die stetige Kurve existiert auf dem realen Objekt. Die diskrete Punktmenge entsteht durch einen 3D Scan mit sich überlappenden Scanfahrten, so dass im Allgemeinen keine konsistente Reihenfolge vorliegt.

Eine Optimierung durch Einschränkung auf das Intervall [x_start,x_end] ist leider aus folgenden Gründen nicht möglich:

* Ich halte die Punktemenge (nur die Front in Scanrichtung) in rotierter Form (n Rotationen) als Map<angle, RotatedPoints> vor, um die Performance zu optimieren
* Das Intervall ist a priori nicht bekannt

Ich muss also initial die gesamte Punktemenge konsitent sortieren. Schon ab 1000 Punkten liegt die Laufzeit bei mehreren Sekunden und übertrifft damit den restlichen Berechungsaufwand. Es kann aber durchaus zu Größenordnungen von bis zu 5000 Punkten kommen.

Insofern muss ich mein usprüngliches Anliegen anpassen. Ich suche also einen möglichst schnellen Algorithmus, um die Punktemenge (intial) zu sortieren.




  Profil  Quote  Link auf diesen Beitrag Link
sebp
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 10.12.2017
Mitteilungen: 119
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-05-30 20:43


Also Sortieralgorithmen gibt es fertig in jeder Sprache.

Sortierst du nun schon und es dauert trotzdem zu lange,
oder willst du erst noch sortieren?

Wenn du schon sortierst, dann glaube ich du machst irgend etwas falsch.
Evtl. liegts an deinen Datenstrukturen.
Wie sieht denn Map<angle, RotatedPoints> aus?



  Profil  Quote  Link auf diesen Beitrag Link
gaussmath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.06.2007
Mitteilungen: 9039
Aus: Hannover
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2018-05-31 16:51


Hallo sebp,

ich muss die Punktemenge noch sortieren. Darum geht's im Grunde. Allerdings sind es ja 2D Punkte. Das zyklus-/überschneidungsfrei zu sortieren, ist nicht gerade trivial. Welche Sprache bringt sowas onboard mit? Ich verwende übrigens C#.



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 1504
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2018-05-31 17:02


C# Listen können mit einem benutzerdefinierten Vergleich (Comparison) sortiert werden.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
sebp
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 10.12.2017
Mitteilungen: 119
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-05-31 20:00


Einfältiger:
Listen sollte man nicht sortieren!

gaussmath:
Ich weiß nicht, ob das was du willst nur mit sortieren möglich ist.
Wenn die Kurve immer so ähnlich aussieht wie oben, dann ja.
Also ich meine damit, man muss die Kurve aus zwei Funktionen vorne(x) und hinten(x) zusammenbauen können.





  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1295
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2018-05-31 22:01


Wenn es nur darum geht, eine kreuzungsfreihe Verbindung der Punkte herzustellen, kann man die 2-opt-Heuristik benutzen:
Man startet mit einer zufälligen Reihenfolge der Punkte und prüft dann, ob es auf der Kurve (der direkten Verbindungslinien) zwei Kanten (s,t) und (u,v) gibt, die in der Summe länger sind als (s,u) und (t,v) zusammen. Wenn ja, ersetzt man diese durch die beiden anderen (die Strecken dazwischen unverändert, aber ggf. in umgekehrter Reihenfolge). Die Kurve wird damit verkürzt.
Gibt es kein solches Kantenpaar mehr, so ist die Kurve garantiert kreuzungsfrei.

Da es wahrscheinlich mehrere kreuzungsfreie Kurven gibt, ist die Lösung wohl aber nicht eindeutig.

Kay



  Profil  Quote  Link auf diesen Beitrag Link
gaussmath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.06.2007
Mitteilungen: 9039
Aus: Hannover
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2018-06-01 13:25


Also nochmal. Es existiert keine Ordnungselation auf R2. Man kann das also nicht einfach so sortieren. Man muss für jeden Punkt prüfen, welcher Punkt als Nachfolger in Frage kommen kann. Einfach nur den Abstand zu nehmen, führt zu nicht eindeutigen und auch falschen Reihenfolgen (gerade bei spitzen Ecken). Man muss also zusätzlich noch die Schnittfreiheit prüfen. Das klingt für mich zunächst einmal nach 2*O(n2) Komplexität...



  Profil  Quote  Link auf diesen Beitrag Link
Yggdrasil
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.07.2004
Mitteilungen: 812
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-06-01 15:51


Sind denn die Punkte innerhalb der N Scanvorgänge sortiert?

Edit:
Das ist gar nicht so wichtig, wie ich dachte, da man sie bei einem Scanvorgang ja sortieren kann, da es Oberflächenpunkte sind.

Edit:
Außerdem ist mir weiterhin unklar, ob alle Scanpunkte als Oberflächenpunkte angenommen werden sollen oder nicht. Beim ersten Beitrag klang es noch so, aber da nun von einer Sortierung aller(?) Punkte die Rede ist, nicht mehr.



  Profil  Quote  Link auf diesen Beitrag Link
gaussmath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.06.2007
Mitteilungen: 9039
Aus: Hannover
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2018-06-12 13:01


Es geht um die Punktemenge eines Schnittes mit dem Modell -> 2D. Die Punkte liegen grundsätzlich immer unsortiert vor.

Ich habe überlegt, die Punkte in ein Grid zu mappen und darüber eine (stark!?) beschleunigte Nachbarschaftsbetrachtung zu erhalten.



  Profil  Quote  Link auf diesen Beitrag Link
gaussmath hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]