Du bist nicht angemeldet.

Werbeanzeige

1

14.07.2020, 08:33

Polygondaten optimieren

Hi,

angenommen, ich habe folgendes Rechteck:


Quellcode

1
2
3
4
    A---------B
    |         |
    |         |
    D---------C


A, B, C und D sind die jeweiligen Koordinaten.

Dieses Rechteck wird im Optimalfall durch die Koordinaten A-B-C-D-A festgelegt. Genau so gut kann es aber auch durch A-D, B-C-D, B-A festgelegt werden. Für die Darstellung macht das keinen Unterschied, es ergibt wieder das gleiche Rechteck. Für die interne Datenverwaltung und die Zeichenfunktione einer Software ist der Unterschied allerdings deutlich größer, besonders wenn das bei Polygonen mit deutlich mehr Ecken auftritt.

Deswegen würde ich diese Koordinatenarrays gerne neu anordnen und optimieren. Bevor ich mir jetzt selber eine Sortier- und Umorganisierfunktion schreibe und damit das Rad möglicherweise schon wieder erfinde: kennt eventuell jemand eine fertige Lösung/Bibliothek, die sowas leistet und solche Koordinatenarrays auf Ihr absolut notweniges Minimum eindampft?

Danke!

David Scherfgen

Administrator

Beiträge: 10 278

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

2

14.07.2020, 11:44

Ich bin mir nicht sicher, ob ich dein Anliegen richtig verstehe. Was genau meinst du mit der Schreibweise A-B-C-D-A und A-D, B-C-D, B-A? Was möchtest du letztlich mit dieser Optimierung erreichen? Speicher einsparen? Ist diese Optimierung für dein Problem wirklich nötig, oder ist das rein theoretisch?

Deine Frage hat mich aber zum Nachdenken gebracht. Wenn die Darstellungen ABC, BCA und CAB jeweils dasselbe Dreieck beschreiben, dann gibt es da eine gewisse Redundanz. Kann man diese Redundanz irgendwie wegkriegen und dadurch ein bisschen Speicher einsparen?

Jonathan

Community-Fossil

  • Private Nachricht senden

3

14.07.2020, 14:23

Für die interne Datenverwaltung und die Zeichenfunktione einer Software ist der Unterschied allerdings deutlich größer, besonders wenn das bei Polygonen mit deutlich mehr Ecken auftritt.


Also wenn das Polygon mit OpenGL oder Direct3D gerendert wird, ist doch die Reihenfolge der Vertices eh quasi vorgegeben. Die Effizienz sollte sich mit der Reihenfolge nicht groß ändern, aber bei der 'falschen' Reihenfolge ist das Ergebnis halt kaputt.

Um was für eine Software geht es denn überhaupt und aus welche Quelle kommen die Daten? Eine Beschreibung wie "A-D, B-C-D, B-A" erscheint mir absolut unüblich. Ohne konkrete Beispiele hört sich das für mich wie ein theoretisches Problem an, und da fällt es schwer praktische Lösungen vorzuschlagen.
Lieber dumm fragen, als dumm bleiben!

David Scherfgen

Administrator

Beiträge: 10 278

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

4

14.07.2020, 15:12

Ach so, jetzt glaube ich es verstanden zu haben. Es geht nur um die Linienzüge, oder? A-B-C-D-A bedeutet: Zeichne eine Linie von A nach B, dann von B nach C, ... so wie GL_LINE_STRIP in OpenGL. Analog für Dreiecke gibt es ja Triangle Strips (GL_TRIANGLE_STRIP). Dazu gibt es Verfahren, wie man die Geometrie entsprechend optimieren kann. Google mal nach "triangle strip optimization". Vielleicht kannst du diese Verfahren auf Line Strips übertragen.

5

14.07.2020, 15:14

Also es geht primär nicht um OpenGL oder um die Darstellung, sondern um die Art, wie Polygone im Speicher gehalten werden (in meinem Fall ist das ein eigenes Datenformat innerhalb meiner Software, aber das ist für die Aufgabenstellung ja nicht entscheidend). Dabei beschreibt mein Beispiel einmal den Optimalzustand "A-B-C-D-A" für ein Rechteck und einmal das, was man z.B. bekommt, wenn man DXF- oder SVG-Dateien importiert. Je nach dem, was der Zeichner sich gedacht hat oder wie oft an einer Zeichnung schon herumgebastelt wurde, kann dabei nämlich so ein verhackstücktes Zeug herauskommen.

Das Problem dabei ist, dass es für die Darstellung zwar egal ist, für die Verarbeitung der Daten aber nicht. Im Fall von Polygonen mit sehr vielen Ecken kann diese Redundanz die Datenmenge da nämlich ganz schön anwachsen lassen - und zwar so stark, dass es sich rein von der Rechenzeit her lohnen sollte, die Teilstücke der Polygone gleich nach dem Import eben einmal zu sortieren und optimieren.

Und Bibliotheken wie Clipper oder boost::polygon kommen z.B. NICHT mit der zerhackten Darstellung klar, die können da kein geschlossenen Polygon mehr erkennen und scheitern an Berechnungen, die mit den "ordentlich" angeordneten Koordinaten problemlos laufen würden.

6

14.07.2020, 15:17

Ach so, jetzt glaube ich es verstanden zu haben. Es geht nur um die Linienzüge, oder? A-B-C-D-A bedeutet: Zeichne eine Linie von A nach B, dann von B nach C


Ja genau - OK, das hätte ich wohl etwas mehr ausführen sollen :-)

Wie das grundsätzlich zu sortieren wäre (alle Koordinaten der Reihe nach abklappern, Anfangs/Endpunke suchen, zu dem es einen anderen Endpunkt gibt und dann die nachfolgenden Linien dort bis zu ihrem Ende vor- oder rückwärts anhängen) ist mir grundsätzlich klar. Ich wüsste halt nur gerne, ob es sowas schon fertig gibt, bevor ich das Rad noch mal erfinde und alles neu implementiere...

David Scherfgen

Administrator

Beiträge: 10 278

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

7

15.07.2020, 09:11

Wenn du geschlossene Polygone brauchst, was machst du bei sowas hier?

Quellcode

1
2
3
4
5
6
7
8
9
A--------B
|        |
|        |
|        |
C--------D
|        |
|        |
|        |
E--------F

Jonathan

Community-Fossil

  • Private Nachricht senden

8

15.07.2020, 11:09

Dabei beschreibt mein Beispiel einmal den Optimalzustand "A-B-C-D-A" für ein Rechteck und einmal das, was man z.B. bekommt, wenn man DXF- oder SVG-Dateien importiert. Je nach dem, was der Zeichner sich gedacht hat oder wie oft an einer Zeichnung schon herumgebastelt wurde, kann dabei nämlich so ein verhackstücktes Zeug herauskommen.

Interessant, ich hätte jetzt nicht gedacht dass irgendwelche Tools so eine Grütze exportieren. Ich kann mir auch kaum vorstellen, dass die Reihenfolge fürs Anzeigen wirklich egal ist, ich denke mir wenn man z.B. in Inkscape ein Polygon mit einer Farbe oder Muster füllen will, würde man die Punkte auch wirklich sortiert haben wollen. Gut vorstellbar, dass das dann intern auch passiert, aber eigentlich merkwürdig wieso die es dann nicht vernünftig exportiert wird...

Ich glaube ich würde tatsächlich dazu tendieren das Sortieren von Hand zu schreiben. Es sollte nicht besonders schwierig sein, und wenn es sich z.B. um ein C++ Projekt handeln sollte willst du vermutlich lieber einmal Code von Hand schreiben als für den Rest des Projektes eine externe Abhängigkeit pflegen.
Ich habe neulich erst Gaussian-Smoothing von Hand in C++ implementiert, das waren auch nur 30 Zeilen und insgesamt vermutlich weniger Arbeit als eine externe Bibliothek dafür zu finden, einzubinden und zu verwenden. Je nachdem was so eine Bibliothek für ein Interface hat ist es ja auch gar nicht so einfach die eigenen Datenstrukturen darauf zu mappen, der Vorteil des vorhandenen Codes wird bei so kleinen Problemchen also echt schnell wieder zunichte gemacht. Ich würde da gar nicht so lange drüber nachdenken und es einfach schnell von Hand machen. Wie man das am effizientesten Implementiert ist ja vielleicht auch eine Interessante Diskussion, aber da es vermutlich nur einmal durchlaufen muss, ist Effizienz vermutlich sowieso ziemlich zweitrangig...
Lieber dumm fragen, als dumm bleiben!

9

16.07.2020, 13:37

Wenn du geschlossene Polygone brauchst, was machst du bei sowas hier?

Quellcode

1
2
3
4
5
6
7
8
9
A--------B
|        |
|        |
|        |
C--------D
|        |
|        |
|        |
E--------F


Grundsätzlich sollte sowas bei meinen Daten eigentlich nicht vorkommen. Wenn doch, dann ist aber ein offenes Polygon zulässig, also z.B. A-B-C-D-A und D-F-E-C.

10

16.07.2020, 13:46

Interessant, ich hätte jetzt nicht gedacht dass irgendwelche Tools so eine Grütze exportieren. Ich kann mir auch kaum vorstellen, dass die Reihenfolge fürs Anzeigen wirklich egal ist, ich denke mir wenn man z.B. in Inkscape ein Polygon mit einer Farbe oder Muster füllen will, würde man die Punkte auch wirklich sortiert haben wollen. Gut vorstellbar, dass das dann intern auch passiert, aber eigentlich merkwürdig wieso die es dann nicht vernünftig exportiert wird...


Du solltest dich von dem Gedanken lösen, dass der Zeichner immer ans Füllen von Polygonen gedacht hat oder das überhaupt vorgesehen ist. Bestes Beispiel sind technische Zeichnungen oder Schaltpläne. Und wenn da ein Rechteck vorkommt und der vollpfostige Benutzer nicht etwa die Rechteck-Zeichenfunktion verwendet, sondern das aus vier Einzellinen zusammensetzt, dann hast du genau den von mir beschriebenen Datenmüll. Das Programm selber sollte das beim Export meiner Meinung nach eher nicht ungefragt optimieren - das weiß ja schließlich nicht, ob der Benutzer wirklich nur unfähig war, oder sich was dabei gedacht hat (und das geschlossene Rechteck in der Zeichnung z.B. gar keins ist bzw. später irgendwie anders verwendet werden soll).

Anderes Beispiel: Slicer von 3D-Druckprogrammen. Die erhalten als Eingangsdaten ein 3D-Mesh aus in der Reihenfolge oftmals wild über die Oberfläche verteilten Dreiecken. Die allermeisten Slicer sind dann echt saudumm und stoppeln die Linien der errechneten Schichten in genau der wirren Reihenfolge zusammen, wie die Dreiecke der Oberfläche gefunden wurden. Das Ergebnis ist dann ein Polygon mit gerne mal der doppelten Menge an Daten wie notwendig (jede Kante eine einzelne, getrennte Linie). Als Anwender kannst du das Problem nicht sehen, weil es in der Darstellung nicht zu erkennen ist - aber die Software könnte halt schneller sein, wenn Sie weniger Daten durch den Speicher schaufeln müsste.

Werbeanzeige