geometrische Probleme



  • Hallo alle zusammen,

    ich sitze hier an einem, wie ich finde, ziemlich komplexen Problem:

    Gegeben habe ich ein Gitter, wobei ich von den Zellen die Eckkkordinaten kenne. Desweiteren habe ich einen Haufen von geometrischer Objekte wie Punkte, Linienzüge und Polygone (konvex und konkav möglich) mit bekannten Koordinaten.

    Ich möchte für jede Zelle rausfinden, ob sie eines der Objekte schneidet bzw. beinhaltet.

    Positiv-Fälle:

    Bei den Punkten
    - liegt innerhalb Zelle (klar, wie zu berechnen)

    Bei den Linien
    - bei Schnitt oder völlig innerhalb Zelle

    Bei den Polygonen
    - Polygon (konvex/konkav) liegt vollständig innerhalb Zelle (klar, wie zu berechnen)
    - konvexes Polygon umschliesst Zelle (klar wie zu berechnen)
    - Polygon kollidiert mit Zelle, wobei ein Teil drin liegen muss (Schnitt)

    Die Prüfung soll auch möglichst fix gehen. Gibt es die Möglichkeit, um um die aufwendigen Strecken-Schnittpunkt-Berechnung herumzukommen? Natürlich kann man erstmal die einfachen Fälle prüfen, ehe man das komplizierte macht, aber mir geht es um das Prinzip.
    Ich hab auch einiges zu Verfahren wie BSP / R-Tree usw... gelesen, komme aber noch nicht dahinter, wie ich das für mich anpassen kann. Hat jemand eine Inspiration für mich ;)?

    Danke schonmal!



  • mach boundingboxen um die objekte und mach dann simple box-box tests.



  • Ein andere Idee wäre, wenn das Gitter schön regelmäßig ist zu versuchen die geometrischen Objekte zu zeichnen. Und zwar mit der Gitterzellengröße als Pixelgröße. 🙂



  • Dieser Thread wurde von Moderator/in rüdiger aus dem Forum Rund um die Programmierung in das Forum Mathematik verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.



  • rapso schrieb:

    mach boundingboxen um die objekte und mach dann simple box-box tests.

    jou. wenn die objekte aber sehr viel größer sind, als einzelne kästchen, solltest du das zB mit einem quad-tree rekursiv weiterunterteilen, und erst ganz am schluss die schnittpunkte mit einzelnen strecken überprüfen.

    Ein andere Idee wäre, wenn das Gitter schön regelmäßig ist zu versuchen die geometrischen Objekte zu zeichnen. Und zwar mit der Gitterzellengröße als Pixelgröße. 🙂

    das hier ist exakte geometrie, hier gibt es keine pixel :p



  • Andrey schrieb:

    Ein andere Idee wäre, wenn das Gitter schön regelmäßig ist zu versuchen die geometrischen Objekte zu zeichnen. Und zwar mit der Gitterzellengröße als Pixelgröße. 🙂

    das hier ist exakte geometrie, hier gibt es keine pixel :p

    Wäre echt nett, wenn Dir vielleicht die Zeit nehmen würdest meinen Lösungsansatz vollkommen zu durchdenken. Zwei kleine Hinweise: Es ist Exakt und es werden keine echten Pixel verwendet.



  • Danke erstmal für eure schnellen Antworten.

    @rapso: die MBB - Tests sind klar. Viel interessanter sind die Fälle, dass die Polygone nicht vollständig drin sind oder ein konkaves Polygon um die Zelle sich windet (ohne zu schneiden). Hier versagen diese Tests.

    @Jester: Wie meinst du das konkret mit dem Zeichnen? Die Zellen haben alle dieselben Abmessungen (allerdings nicht quadratisch).

    @Andrey: Ich nehme an, du meinst mit dem weiter unterteilen die Objekte weiter unterteilen und prüfen, ob sich grade meine aktuelle Zelle drin befindet bzw. schneidet?



  • Jester schrieb:

    Wäre echt nett, wenn Dir vielleicht die Zeit nehmen würdest meinen Lösungsansatz vollkommen zu durchdenken. Zwei kleine Hinweise: Es ist Exakt und es werden keine echten Pixel verwendet.

    hmm... sry, verstehe das nicht so wirklich. 😕
    um zu entscheiden, ob ein pixel "gezeichnet" wird, musst du ja wissen, ob er von den primitiven geschnitten wird oder nicht... wie bringt das denn einen weiter? 🙄

    OP schrieb:

    @Andrey: Ich nehme an, du meinst mit dem weiter unterteilen die Objekte weiter unterteilen und prüfen, ob sich grade meine aktuelle Zelle drin befindet bzw. schneidet?

    am einfachsten, du machst es mit kreisen: ziehst zuerst einen großen kreis um die ganze figur und sagst, dass da was drin ist. Jetzt überprüfst du, ob es eine zelle schneidet. Falls ja: machst du genau dasselbe mit 4 weiteren kleineren kreisen, die auch jeweils "wissen" ob sie leer oder gefüllt sind. das machst du immer weiter, bis es dir genau genug ist, um mit einzelnen primitiven (strecken) zu testen.
    google ma nach "kollisionserkennung BSP octree" ...



  • Sind die Zellen alle rechteckig?

    Um zu erklären was ich meine formuliere ich mal folgendes Problem. Ich hab nen Bildschirm mit rechteckigen Pixeln. Nun möchte ich da verschiedene Sachen zeichnen. Dazu muß ich feststellen, welche Pixel ich farbig anmalen muß. Nämlich die, die von einer Linie oder einem Polygon geschnitten werden. Du siehst, das ist im Prinzip genau Dein Problem. Nur dass Deine Zellen halt keine Pixel sind. Aber das ändert ja nix an der Anwendbarkeit der bekannten Algorithmen, die diese Probleme lösen.

    Zu den Rasterizing-Algorithmen kann Dir rapso bestimmt einiges sagen. Allerdings funktionieren die gängen wohl nur für rechteckige Pixel (notfalls kann man die ja sogar so skalieren, dass sie quadratisch sind). Aber ich wette, dass es auch Algorithmen für andere regelmäßige Gitterstrukturen gibt. Die sind aber vermutlich deutlich komplexer und ob die in irgendeiner Weise praktikabel sind kann ich nicht sagen.



  • Andrey schrieb:

    Jester schrieb:

    Wäre echt nett, wenn Dir vielleicht die Zeit nehmen würdest meinen Lösungsansatz vollkommen zu durchdenken. Zwei kleine Hinweise: Es ist Exakt und es werden keine echten Pixel verwendet.

    hmm... sry, verstehe das nicht so wirklich. 😕
    um zu entscheiden, ob ein pixel "gezeichnet" wird, musst du ja wissen, ob er von den primitiven geschnitten wird oder nicht... wie bringt das denn einen weiter? 🙄

    Okay, Du hast bemerkt, dass Pixel malen genau das gleiche Problem ist. Prima. Was meinst Du wie Grafikkarten zeichnen? Kollisionstests von Pixelzellen mit den Objekten? -- Nein, das wird anders gemacht. Und diese Algorithmen sollte man zur Lösung des Problems verwenden. Die sind nämlich auf diese spezielle Situation angepaßt.

    Wenn die Zellen natürlich nicht die Voraussetzungen für solche Algorithmen erfüllen, dann klappt das nicht. Sind die Voraussetzungen aber erfüllt, dann sind die Algorithmen die auf Kollisionstests basieren ziemlich sicher langsamer.

    btw.: wenn ich gerade selber auf dem Schlauch stehe würde ich den hier: 🙄 eher vermeiden.



  • Andrey schrieb:

    rapso schrieb:

    mach boundingboxen um die objekte und mach dann simple box-box tests.

    jou. wenn die objekte aber sehr viel größer sind, als einzelne kästchen, solltest du das zB mit einem quad-tree rekursiv weiterunterteilen,

    dafuer muestest du die boxen des quadtrees gegen die objekte testen, ich glaube gerade das war das anfangsproblem, wie primitiv vs quad testen... oder ich hab das problem falsch verstanden (kann ja auch selten mal passieren).



  • Jester schrieb:

    Zu den Rasterizing-Algorithmen kann Dir rapso bestimmt einiges sagen.

    ich kann sagen dass es nicht trivial ist es wirklich 100%ig sauber und schnell hinzubekommen.

    Jester schrieb:

    Was meinst Du wie Grafikkarten zeichnen? Kollisionstests von Pixelzellen mit den Objekten?

    ehrlichgesagt machen das graphikkarten so heutzutage, seit ca geforce zeiten. natuerlich wird der bereich moeglichst eingegrenzt der zu pruefen ist, aber dann...

    ich ging von kleinen primitiven aus, deswegen boundingboxes, wenn sie jedoch groeser sind wuerdich

    fuer lines kannst du nach nem schnellern line-box intersectiontest suchen, da gibt es was gutes bei google.

    bei tris kannst du von der mitte der mitte (oder den eckpunkten) der boxen aus versuchen bis ausserhalb der boundingbox der polygones eine linie gegen die raender testen. gerade anzahl von hits heisst die box ist ausserhalb, ungerade sagt sie waere innerhalb. duerfte sehr verlaesslich sein.
    natuerlich musst du nicht komplett alle boxen testen, sndern nur die die innerhalb der boundingbox des poly sind...



  • achso, ja... an diese interpretation der fragestellung habe ich nicht gedacht



  • rapso schrieb:

    Jester schrieb:

    Was meinst Du wie Grafikkarten zeichnen? Kollisionstests von Pixelzellen mit den Objekten?

    ehrlichgesagt machen das graphikkarten so heutzutage, seit ca geforce zeiten. natuerlich wird der bereich moeglichst eingegrenzt der zu pruefen ist, aber dann...

    Echt? Nix mit schnellem Bresenham für Linien? Und für Dreiecke dann Bresenham und horizontale Verbindungslinien? Und komplexere Objekte triangulieren? Hast Du irgendwo was zu Lesen darüber wie man sowas heute macht?

    Möglicherweise funktionieren diese alten Verfahren aber trotzdem noch. Dann sieht das eigentlich nach ner sehr effizienten Lösung aus.



  • Jester schrieb:

    Echt? Nix mit schnellem Bresenham für Linien?

    es werden locker 512pixel gleichzeitig abgearbeitet, da ist bresenham nicht so super. zudem ist subpixelgenauigkeit vorgeschrieben, das waere bei linearem interpolieren nicht so trvial zu loesen.
    du brauchst zudem nicht clippen, keine teure logic die eventuel in spezialfaellen fehler macht etc.
    nur ebenengleichungen, test von point in poly, was in 2d dann auch ein sehr einfacher collisiontest ist (man projeziert ja alles auf den screen).

    Und für Dreiecke dann Bresenham und horizontale Verbindungslinien?

    niemand will horizontale linien, sondern lokale verflechtungen die sehr viele cachehits liefern.

    Und komplexere Objekte triangulieren?

    graphikkarten koennen eigentlich nur dreiecke.

    Hast Du irgendwo was zu Lesen darüber wie man sowas heute macht?

    sowas bekommt man wohl so ziemlich nicht oeffentlich, du muesstest in patenten schauen, da sind die rasterizierungsmuster oft angegeben.



  • rapso schrieb:

    Jester schrieb:

    Echt? Nix mit schnellem Bresenham für Linien?

    es werden locker 512pixel gleichzeitig abgearbeitet, da ist bresenham nicht so super. zudem ist subpixelgenauigkeit vorgeschrieben, das waere bei linearem interpolieren nicht so trvial zu loesen.
    du brauchst zudem nicht clippen, keine teure logic die eventuel in spezialfaellen fehler macht etc.
    nur ebenengleichungen, test von point in poly, was in 2d dann auch ein sehr einfacher collisiontest ist (man projeziert ja alles auf den screen).

    Okay, die Gründe sehe ich ein. Aber für diesen konkreten Anwendungsfall sehen mir die alten Verfahren trotzdem nach ner ziemlich guten Lösung aus.



  • ich kenne keinen normalen rasterizer den concav polygone zeichnen kann. ist sicherich ne herausforderung 🙂



  • rapso schrieb:

    ich kenne keinen normalen rasterizer den concav polygone zeichnen kann. ist sicherich ne herausforderung 🙂

    Jo klar, die müßte man halt triangulieren. Das stellt ja aber weniger ein Problem dar.



  • Danke für eure zahlreichen Tips! Werde mir das, sobald ich wieder dazu komme, überlegen. Ziel war es ja, aufwendige Berechnungen wie Geradengleichungen, Schnittpunkte (über Matrizen) zu ersparen.

    @Jester: Ja, es handelt sich um ein regelmässiges, rechteckiges Gitter.

    Bei den konkaven Polygonen, muss ich wohl noch einiges mehr machen.


Log in to reply