Ergebnis 1 bis 2 von 2
  1. #1
    Richard Stallman
    Registriert seit
    09.07.2008
    Beiträge
    2.199

    Standard Prüfen ob verschiedene Regionen ein Punkt enthalten

    Hi, ich möchte ein optimiertes Verfahren für folgende Aufgabe finden:

    Später spielt sich das Ganze im 3-dimensionalen Raum ab, zum Verständnis tut es ein 2-dimensionaler Raum allerdings auch. Ich habe also ein Koordinatensystem (später in alle Richtungen) mit verschiedenen Rechtecken, die sich auch überlappen können. Die Rechtecke (Regionen auf meinem Feld) sind definiert durch ihren kleinsten Punkt (also dem Eckpunkt, der dem Ursprung am nächsten ist) und den jeweils gegenüberliegenden Punkt.
    Es gibt locker 100-200 Regionen und 300-500 Mal pro Sekunde muss geprüft werden, ob eine Koordinate in einer Region vorhanden ist.

    Minimiert werden soll die Zeit für die Ausführung, was vorher alles an Arbeit anfällt ist egal.

    Meine einzige Lösung bisher war die, dass ich alle Regionen für die jeweiligen Koordinaten pro Wert (minX, maxX, minY, maxY) jeweils in eine geordnete Datenstruktur eingefüge, sodass ich zumindestens alle ausschließe, die darüber liegen. Trotzdem werden eigentlich unnötige Rechnungen durchgeführt, nämlich von Regionen, die eigentlich schon vorher ausgeschieden sind. Um das zu vermeiden wäre es meiner Ansicht nach nötig, zur Laufzeit eine Art Liste mit Kandidaten zu erstellen, allerdings kommen mir dann langsam die Zweifel, ob ich im Endeffekt nicht mehr Arbeit verursache als ich einspare.

    Umgesetzt werden soll dies in Java. Vielleicht hat jemand eine gute Idee mit Erklärungen auf Lager
    Signatur hat Pause..


  2. #2
    Der mit Anatidaephobie Avatar von blackberry
    Registriert seit
    11.07.2008
    Beiträge
    2.350

    Standard

    Mein vielleicht etwas naiver Ansatz (aber das sinnvollste, was mir nach 10 Min dazu eingefallen ist):

    Du könntest deine Rechtecke in konzentrische Kreise um den Ursprung einbetten.
    Skizze:


    Dann könntest du deine Rechtecke evtl. in deiner Datenstruktur auch noch nach dem Radius ihres größtens sie noch berührenden Kreises anordnen. Die Euklid-Norm deines Punktes als Vektor aufgefasst kannst du ganz leicht berechnen; das musst du überdies auch nur einmal machen, denn die ändert sich ja während eines Durchlaufs nicht.

    Anschließend kannst du die Rechtecke finden, die für einen Vergleich überhaut infrage kommen. Wenn du ein großes Feld mit vergleichsweise kleinen Rechtecken hast, dann werden das von vornherein nicht sehr viele sein.

    Je nachdem wie geschickt du diese sortiert hast kannst du die ganz schnell finden und zum prüfen musst du auch nur den kleinen und großen Radius mit der Norm des Vektors vergleichen.

    Wenn dann die Menge deiner Kandidaten schon so eingeschränkt ist kannst du für jedes dieser infrage kommenden Rechtecke einen "echten" Vergleich anstellen, ob dein Punkt nun drin liegt, oder nicht.

    PDFTT cr3w a.E. — ReiDC0Re, lindor, Sera, berry
    please do feed the trolls crew and elk
    Ehrenwerte Mitglieder im Ruhestand: OpCodez, SFX.
    "Was sich blackberry gerade denkt" — Vorsicht! Frei laufender Wahnsinn!
    Zitat von fuckinghot19: "PS: Blackberry ist auf FH der Trollkönig ^^."
    An dieser Stelle danke ich all meinen Fans und Hatern gleichermaßen ^.^

  3. Folgende Benutzer haben sich für diesen Beitrag bedankt:

    Hu5eL (17.12.2011)

Ähnliche Themen

  1. punkt in variablen
    Von systemless im Forum PHP
    Antworten: 3
    Letzter Beitrag: 02.12.2008, 21:41
  2. Antworten: 6
    Letzter Beitrag: 20.01.2008, 21:34
  3. [S][S] CS:S Crosshair PUNKT [S][S]
    Von 0XYGeN im Forum Games
    Antworten: 7
    Letzter Beitrag: 11.12.2007, 14:05
  4. Frage: Geburtsort rausfinden. Details enthalten
    Von Steav im Forum Social Engineering
    Antworten: 5
    Letzter Beitrag: 25.11.2007, 20:07

Stichworte

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •