Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

[C++] georithm: eine C++17 constexpr 2D-Geometrie library

Werbeanzeige

anti-freak

Alter Hase

  • »anti-freak« ist der Autor dieses Themas

Beiträge: 635

  • Private Nachricht senden

1

25.12.2017, 22:02

[C++] georithm: eine C++17 constexpr 2D-Geometrie library

Die Idee (zumindest die Grundidee) für diese Library existiert schon seit Jahren, und habe sie des öfteren auch erstellt und neu erstell..., und neu erstellt.

Nunja, ein wenig zu den Hintergründen.

Ich bin generell mathematisch interessiert, wenn auch lange kein Experte. Die Geometrie hat mich schon immer gereizt, deswegen habe ich irgendwann angefangen, Algorithmen für Schnittpunkte von Kreisen und/oder Rechtecken zu schreiben. Das Design der ersten Library war komplett runtime polymorph. Das hat am Anfang super funktioniert, nur war ich irgendwann unzufrieden, weil ich eigentlich gar keine Runtime-Polymorphie haben wollte.
Das war der erste Schritt zur template Library. Die war sogar recht gut (zumindest aus meiner Sicht), hatte aber auf Grund von weniger tiefgehenden template Erfahrungen, ein recht bloatiges Auftreten. Es funktionierte zwar, aber war eben nicht hübsch genug.
Nun habe ich vor ein paar Monaten das Ganze noch einmal aufgelegt, mit ein paar essentiellen Verbesserungen. Vor allem durch C++17 bin ich um einiges zufriedener als damals (unter anderem std::optional finde ich super ;)).
Nun, da diese Library aber immer noch Teil meiner privat Sammlung ist, und ich mir nicht vorstellen kann, dass irgendjemand sich das antun würde, bin ich nun dabei meinen kompletten geometry namespace aus meiner Sammlung, in eine neue Library zu übertragen.
Und voilà, geboren wurde georithm.

Was ist georithm?
Georithm ist lediglich ein Zusammensetzung aus Geometrie und Algorithmus (natürlich die englischen Begriffe, geometrie und algorithm). Im Zuge des Auslagerns ist mir noch die Idee gekommen, dass es cool wäre, möglichst alles constexpr zu definieren. Das ist jetzt also praktisch schon der 4. Umbau, aber ich bin zuversichtlich, dass es nun so bleibt, wie es ist.

Was heißt das jetzt genau?
Georithm bietet die Möglichkeit, geometrische Formen und Algorithmen zur compile-time auszuwerten. Natürlich ist das Anwendungsfeld für sowas nicht sonderlich groß, aber alleine die Möglichkeit ist, zumindest momentan noch, ein Alleinstellungsmerkmal. Abgesehen von constexpr dürfte es auch ziemlich cool sein, unterschiedliche Formen miteinander zu kombinieren.

Allerdings, und hier bin ich ganz ehrlich, bin ich lange kein Experte. Ich plane für den Anfang mit den Formen Circle, Rect und Triangle, und den Algorithmen contains (bool), intersects (bool), boundingRect und intersections (tatsächliche Schnittpunkte). Ebenso sind manche Algorithmen möglicherweise nicht optimal abgebildet oder für entsprechende Shape-Kombinationen überladen. Daher kann es natürlich sein, dass ich hier und da tatsächlich nicht ganz so gute performance liefer, wie ich es gerne würde.

Weiterhin geplant sind kleinere Sachen wie Fläche und Umfang, wofür mir bei beiden noch der passende englische Begriff fehlt (kennt den jemand vielleicht?).

Ihr seht, ich plane eine kleine aber feine Library, die übrigens auch von mir im Projekt Coregrounds eingesetzt wird. Es gibt also tatsächlich einen UseCase von mir ;)

Das repo wird die nächsten Tage weiter mit Content gefüllt; habe praktisch grade erst angefangen mit Übertragen und Dokumentieren. Dennoch wäre es schön, wenn man mir vll ein wenig Feedback geben könnte, ob man nicht jetzt schon was verbessern kann (Art der Dokumentation, etc.).

Anforderungen und Abhängigkeiten:
Da die stl leider ihre Algorithmen nicht constexpr deklariert hat, habe ich mich dazu entschlossen, die Library Sprout optional einzusetzen. Es ist kein Muss, aber wenn diese nicht gewünscht ist, wird das Feature constexpr leider nicht unterstützt. Daher sind auch alle Funktionen mit dem Makro GEORITHM_CONSTEXPR ausgestattet. Mit GEORITHM_DISABLE_CONSTEXPR lässt sich constexpr komplett abschalten, und man kann auf Sprout verzichten. Ich habe ja die Hoffnung, dass in C++20, zumindest die Algorithmen, constexpr deklariert werden, und ich komplett auf Sprout verzichten kann.

Abgesehen von Sprout, ist natürlich ein aktueller C++17 Compiler von Nöten. Ich mache regen Gebrauch von allerlei Features aus C++17 und plane nicht, eine Art fallback solution zu implementieren, damit auch ältere Compiler supported werden können. Dafür hab ich einfach zu wenig Zeit.

Features:
- constexpr
- keine Heap Allokationen notwendig
- Kombination von unterschiedlichen Formen

Links:
github-repo
Dokumentation

Dokumentation
Die Dokumentation erstelle ich per Doxygen. Es ist ein wenig unübersichtlich, aber immer noch besser als im Code rumwühlen zu müssen. Wenn sich jemand damit besonders gut auskennt, und mir ein wenig helfen möchte, das übersichtlicher zu gestalten, darf Derjenige sich gerne bei mir melden.

Lizenz:
Die Library wird unter der Boost Software License verfügbar gemacht. D.h. sie ist für alle verfügbar, egal ob privat oder kommerziell.

Vielen Dank fürs Lesen.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »anti-freak« (25.12.2017, 22:12)

anti-freak

Alter Hase

  • »anti-freak« ist der Autor dieses Themas

Beiträge: 635

  • Private Nachricht senden

2

26.12.2017, 23:58

Nachdem ich heute den ganzen Tag damit beschäftigt war, die Library zu portieren, bin ich nun soweit, dass die Shapes Line, Rect und Circle nun vollständig vorhanden sind.
Zusätzlich gibt es für Polygone (genau genommen im Moment eben nur für Rect) die "algorithmen" vertices und edges. Damit lässt sich über ein Wrapper struct eine Range der Ecken und Kanten erstellen, mit iterator Support. D.h. range-based-for-loop und std Algorithmen können damit benutzt werden.
Als ersten wirklich aufwändigen Algorithmus habe ich "contains" portiert. Dieser gibt per bool return an, ob ein Shape oder Vector innerhalb eines Shapes liegt oder nicht.

Um mal ein kleines Beispiel zu zeigen, wie das Ganze zu benutzen ist:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <georithm/rect.hpp>
#include <georithm/circle.hpp>
#include <georithm/contains.hpp>
#include <georithm/vertices.hpp>
#include <georithm/edges.hpp>

int main()
{
    georithm::Rect<int> rect(1, 1, 4, 4);   // Rechteck an der Position (1/1) mit der Größe (4/4)
    georithm::Circle<int> circle(2, 2, 2);  // Kreis mit der Center Position (2,2) und dem Radius 2

    std::cout << "rect contains circle: " << georithm::contains(rect, circle) << std::endl; // prüft ob circle innerhalb von rect liegt (tut es übrigens nicht :P)

    std::cout << "rect contains center of circle: " << georithm::contains(rect, circle.getCenter()) << std::endl; // prüfen ob wenigstens der Center von circle in unserem rect liegt (das trifft zu)

    // das Ausgeben der Kanten Koordinaten
    std::cout << "Kanten gegen den Uhrzeigersinn:" << std::endl;
    for (auto edge : georithm::edges(rect))
    {
        std::cout << "from x: " << edge.getPosition().getX() << " y: " << edge.getPosition().getY() <<
            " to x: " << edge.getPosition().getX() + edge.getDirection().getX() << " y: " << edge.getPosition().getY() + edge.getDirection().getY() << std::endl;
    }

    // doch lieber anders rum
    auto edgesRange = georithm::edges(rect);
    std::cout << "\nKanten mit dem Uhrzeigersinn:" << std::endl;
    for (auto itr = edgesRange.crbegin(); itr != edgesRange.crend(); ++itr)
    {
        auto edge = *itr;
        std::cout << "from x: " << edge.getPosition().getX() << " y: " << edge.getPosition().getY() <<
            " to x: " << edge.getPosition().getX() + edge.getDirection().getX() << " y: " << edge.getPosition().getY() + edge.getDirection().getY() << std::endl;
    }
    return 0;
}


Das produziert dann folgenden output:

Zitat

rect contains circle: 0
rect contains center of circle: 1
Kanten gegen den Uhrzeigersinn:
from x: 1 y: 1 to x: 1 y: 5
from x: 1 y: 5 to x: 5 y: 5
from x: 5 y: 5 to x: 5 y: 1
from x: 5 y: 1 to x: 1 y: 1

Kanten mit dem Uhrzeigersinn:
from x: 5 y: 1 to x: 1 y: 1
from x: 5 y: 5 to x: 5 y: 1
from x: 1 y: 5 to x: 5 y: 5
from x: 1 y: 1 to x: 1 y: 5


Wie ihr seht, sollte das Ganze recht straight forward sein.

mfg

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »anti-freak« (27.12.2017, 15:37)

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

3

27.12.2017, 09:20

Die Begriffe, die du suchtest, sind "area" für Fläche und "circumference" für Umfang.
Ich sehe, dass deine Geraden einen "slope" haben. Dieser Begriff steht eigentlich die Steigung, also z. B. Steigung = 1 für einen 45°-Anstieg. Der Code legt aber nahe, dass dein "slope" ein Richtungsvektor ist. Dann wäre "direction" der richtige Begriff.
Deine Algorithmen scheinen bei Polygonen davon auszugehen, dass sie konvex sind (denn ansonsten würden die Algorithmen falsche Ergebnisse liefern). Dann würde ich die entsprechende Klasse "ConvexPoly(gon)" nennen, um dies direkt klar zu machen.
David Scherfgens Website | Konzentrationstest Polizei

anti-freak

Alter Hase

  • »anti-freak« ist der Autor dieses Themas

Beiträge: 635

  • Private Nachricht senden

4

27.12.2017, 15:21

Hey David,

vielen Dank für dein Feedback. Area für Fläche hatte ich bereits auf dem Schirm, dachte nur, da gäbe es einen spezielleren Begriff für. Aber damit kann ich leben :D
Circumference ist gut, danke.
Das meine Polygone nur konvex sein dürfen, ist mir bewusst und auch so gewollt. Ich plane bisher ja keine "Polygon" Klasse; die gibt es lediglich als type_trait. Dennoch danke für den Hinweis.

Das mit der Slope ist ein guter Hinweis. Werde ich ändern, danke.

DNKpp

Alter Hase

  • »DNKpp« ist der Autor dieses Themas

Beiträge: 635

  • Private Nachricht senden

5

21.05.2018, 00:43

So, es ist nun schon ein wenig her, seitdem ich effektiv an georithm arbeiten konnten. Dennoch habe nun endlich mal wieder ein wenig Zeit gehabt und ein wenig Progress gemacht.
Prinzipiell ist die Portierung aus meiner Lib nach georithm nun vollständig. D.h. es gibt die Shapes:
- Point
- Line (Line, LineSegmen, Ray)
- Rect
- Circle

Die lib beherrscht nun folgende unären algorithmen:

- vertices
- edges
- center
- bounding_rect

und folgende binären algorithmen (prinzipiell mit beliebigen Shape-Kombinationen)
- intersects
- contains
- overlaps

Bisher gebe die binären algorithmen lediglich boolsche Angaben darüber zurück, ob etwas stattfindet oder nicht. Alles weitere wird im Laufe der Entwicklung noch folgen.


Auch habe ich mich dazu entschieden, eine strikte Trennung zwischen Point und Vector einzubauen. Ein Vector entspricht nun tatsächlich der Mathematik; ein Point ist hingegen lediglich eine Position. Es können 2 Points miteinander subtrahiert werden; als Differenz erhält man einen Vector. Für Vectoren gibt es auch eine Hand voll algorithmen:
- lenght(_squared)
- dot_product
- cross_product (bisher nur das "nicht definierte" im 2d Raum)
- normalize
- projection
und ein paar weitere.

Point hat deutlich weniger:
- distance(_squared)
und 2 Konvertierungs-Funktionen Point <-> Vector


Vielleicht hat ja jemand Lust, sich das Ganze mal genauer anzusehen.

mfg

Werbeanzeige

Ähnliche Themen