4. Polygon - Mittelpunkt und Schwerepunkt?

Polygon - Mittelpunkt und Schwerepunkt?

  • F

    @TaucherOne sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    Seltsamerweise ist das bei mir aber ziemlich ungenau... Ich habe da x:17.2598 y:12.9228 anstatt x:15 y:11.6667 raus. Ich kann mir das nicht erklären.

    Ist ja schonmal die richtige Grössenordnung 😉 ... ich kenne den Algo nicht und hab ihn mir nicht genau angesehen, aber vielleicht konvergiert der einfach nicht sonderlich gut (sofern korrekt implementiert). Hast du mal mit der Anzahl der Iterationen gespielt? Ich würde so ins Blaue vermuten, dass das die 5000 in Zeile 57 ist. Wirds mit 10000 oder 100000 eventuell besser?

    0
    T
     1 Antwort

  • @Finnegan sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    Dadurch ergibt sich das Problem mit dem hohen Rang des zentralen Vertex erst gar nicht, da jedes Dreieck nur einmal in das Ergebnis einfliesst.
    Edit: Achja, und wenn alle Dreiecke die gleiche Fläche haben, dann zerfällt das tatsächlich zu (p_0 + p_1 + ... p_n) / n, d.h. für eine gute Triangulierung erhält man selbst mit der falschen Methode eine "ziemlich richtiges" Ergebnis... aber eben nur unter ganz bestimmten Voraussetzungen

    Danke für die Info, ist ja sehr einfach.

    Gute Triangulierungen sehe ich selten. Ich bin aber auch im Bereich der digitalen Geländemodelle unterwegs und so mancher Geländeschnitt oder so manche Bruchkante verändert die Vermaschung öfters negativ. In einem extremen Fall hatte ich eine Vermaschung wo auf 1% der Fläche 99% der Dreiecke waren und das völlig korrekt!

    0
    F
     1 Antwort
  • T
    Gesperrt

    @Finnegan Habe den Fehler, glaube ich, entdeckt ...

    Wenn man sich noch einmal die Definition des Schwerpunkts ansieht, dann ist die Entfernung zu allen SEITEN maximal. Ich habe aber getestet, ob die Entfernung zu allen Ecken (Punkten) maximal ist ... Das wäre demnach nicht der Schwerpunkt (sondern stattdessen ein anderer Punkt).

    Hier noch einmal geändert:

    #include <vector>
#include <iostream>
#include <complex>

namespace std
{
    vector<double> calculateCenterOfGravity(vector<vector<double>> poly)
    {
        double sum1 = 0;
        double sum2 = 0;
        double area = 0;
        for (size_t i = 0; i < poly.size() - 1; i++)
        {
            auto p1 = poly[i];
            auto p2 = poly[i + 1];
            double x0 = p1[0];
            double x1 = p2[0];
            double y0 = p1[1];
            double y1 = p2[1];
            double s1 = (x0 + x1) * (x0 * y1 - x1 * y0);
            double s2 = (y0 + y1) * (x0 * y1 - x1 * y0);
            double s3 = x0 * y1 - x1 * y0;
            sum1 += s1 / 6.0;
            sum2 += s2 / 6.0;
            area += s3 * 0.5;
        }
        vector<double> result;
        result.push_back(sum1 / area);
        result.push_back(sum2 / area);
        return result;
    }

    double pDistance(double x, double y, double x1, double y1, double x2, double y2)
    {
        double A = x - x1;
        double B = y - y1;
        double C = x2 - x1;
        double D = y2 - y1;

        double dot = A * C + B * D;
        double len_sq = C * C + D * D;
        double param = -1;
        if (len_sq != 0)
        {
            param = dot / len_sq;
        }

        double xx, yy;

        if (param < 0)
        {
            xx = x1;
            yy = y1;
        }
        else if (param > 1)
        {
            xx = x2;
            yy = y2;
        }
        else
        {
            xx = x1 + param * C;
            yy = y1 + param * D;
        }

        double dx = x - xx;
        double dy = y - yy;
        return sqrt(dx * dx + dy * dy);
    }

    vector<double> calculateCenterOfGravityMonteCarlo(vector<vector<double>> poly, const unsigned int seed, double delta)
    {
        srand(seed);
        double maxx = -(double)(unsigned int)(-1), minx = (unsigned int)(-1), maxy = -(double)(unsigned int)(-1), miny = (unsigned int)(-1);
        for (auto p : poly)
        {
            if (p[0] > maxx)
            {
                maxx = p[0];
            }
            if (p[0] < minx)
            {
                minx = p[0];
            }
            if (p[1] > maxy)
            {
                maxy = p[1];
            }
            if (p[1] < miny)
            {
                miny = p[1];
            }
        }
        double x, y;
        double currentBest = -(double)(unsigned int)(-1);
        for (size_t i = 0; i < 5000; i++)
        {
        a:
            double rx = (double)rand() / (double)RAND_MAX * (maxx - minx) + minx;
            double ry = (double)rand() / (double)RAND_MAX * (maxy - miny) + miny;
            double rBest = (unsigned int)(-1);
            for (size_t i = 0; i < poly.size() - 1; i++)
            {
                auto p1 = poly[i];
                auto p2 = poly[i + 1];
                double x0 = p1[0];
                double x1 = p2[0];
                double y0 = p1[1];
                double y1 = p2[1];
                double d = pDistance(rx, ry, x0, y0, x1, y1);
                if (d > delta)
                {
                    i++;
                    goto a;
                }
                if (d < rBest)
                {
                    rBest = d;
                }
            }
            if (rBest > currentBest)
            {
                x = rx;
                y = ry;
                currentBest = rBest;
                cout << " Found: " << x << " " << y << " " << rBest << "\n";
            }
        }

        vector<double> result;
        result.push_back(x);
        result.push_back(y);
        return result;
    }
} // namespace std

int main(int argc, char const *argv[])
{
    std::vector<std::vector<double>> poly;
    poly.push_back(std::vector<double>{10, 10});
    poly.push_back(std::vector<double>{30, 20});
    poly.push_back(std::vector<double>{5, 5});

    auto r = calculateCenterOfGravity(poly);
    std::cout << "x:" << r[0] << " y:" << r[1] << "\n";
    r = calculateCenterOfGravityMonteCarlo(poly, 7, 0.62);
    std::cout << "x:" << r[0] << " y:" << r[1] << "\n";
    return 0;
}

    Das goto ist natürlich unschön ... Aber eigentlich fehlt dort noch ein Test, ob die zwei jeweils zufällig gewählten Punkte innerhalb des Polygons liegen. Deshalb habe ich delta (magischer Wert) und goto eingefügt.

    Ich denke, es könnte auch noch dahin optimiert werden, dass es schneller konvergiert (wenn man max verringert oder min erhöht).

    BTW: delta sollte möglichst klein, aber nicht zu klein gewählt werden ... das ist ein bisschen Quacksalberei. 😉

    0
  • Mod

    Der Schwerpunkt eines Polygons liegt nicht notwendigerweise in seinem Inneren.

    0
    T
    F
     2 Antworten
  • T
    Gesperrt

    @SeppJ sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    Der Schwerpunkt eines Polygons liegt nicht notwendigerweise in seinem Inneren.

    Danke für den Hinweis!

    Edit: Mein Beispiel war auch nicht sonderlich toll ...

    #include <vector>
#include <iostream>
#include <complex>

namespace std
{
    vector<double> calculateCenterOfGravity(vector<vector<double>> poly)
    {
        double sum1 = 0;
        double sum2 = 0;
        double area = 0;
        for (size_t i = 0; i < poly.size() - 1; i++)
        {
            auto p1 = poly[i];
            auto p2 = poly[i + 1];
            double x0 = p1[0];
            double x1 = p2[0];
            double y0 = p1[1];
            double y1 = p2[1];
            double s1 = (x0 + x1) * (x0 * y1 - x1 * y0);
            double s2 = (y0 + y1) * (x0 * y1 - x1 * y0);
            double s3 = x0 * y1 - x1 * y0;
            sum1 += s1 / 6.0;
            sum2 += s2 / 6.0;
            area += s3 * 0.5;
        }
        vector<double> result;
        result.push_back(sum1 / area);
        result.push_back(sum2 / area);
        return result;
    }

    double pDistance(double x, double y, double x1, double y1, double x2, double y2)
    {
        double A = x - x1;
        double B = y - y1;
        double C = x2 - x1;
        double D = y2 - y1;

        double dot = A * C + B * D;
        double len_sq = C * C + D * D;
        double param = -1;
        if (len_sq != 0)
        {
            param = dot / len_sq;
        }

        double xx, yy;

        if (param < 0)
        {
            xx = x1;
            yy = y1;
        }
        else if (param > 1)
        {
            xx = x2;
            yy = y2;
        }
        else
        {
            xx = x1 + param * C;
            yy = y1 + param * D;
        }

        double dx = x - xx;
        double dy = y - yy;
        return sqrt(dx * dx + dy * dy);
    }

    vector<double> calculateCenterOfGravityMonteCarlo(vector<vector<double>> poly, const unsigned int seed, double delta)
    {
        const size_t NUM_ITERATIONS = 50000;
        srand(seed);
        double maxx = -(double)(unsigned int)(-1), minx = (unsigned int)(-1), maxy = -(double)(unsigned int)(-1), miny = (unsigned int)(-1);
        for (auto p : poly)
        {
            if (p[0] > maxx)
            {
                maxx = p[0];
            }
            if (p[0] < minx)
            {
                minx = p[0];
            }
            if (p[1] > maxy)
            {
                maxy = p[1];
            }
            if (p[1] < miny)
            {
                miny = p[1];
            }
        }
        double x, y;
        double currentBest = -(double)(unsigned int)(-1);
        for (size_t i = 0; i < NUM_ITERATIONS; i++)
        {
            double rx = (double)rand() / (double)RAND_MAX * (maxx - minx) + minx;
            double ry = (double)rand() / (double)RAND_MAX * (maxy - miny) + miny;
            double rBest = (unsigned int)(-1);
            for (size_t i = 0; i < poly.size() - 1; i++)
            {
                auto p1 = poly[i];
                auto p2 = poly[i + 1];
                double x0 = p1[0];
                double x1 = p2[0];
                double y0 = p1[1];
                double y1 = p2[1];
                double d = pDistance(rx, ry, x0, y0, x1, y1);
                if (d > delta)
                {
                    goto a;
                }
                if (d < rBest)
                {
                    rBest = d;
                }
            }
            if (rBest > currentBest)
            {
                x = rx;
                y = ry;
                currentBest = rBest;
                cout << " Found: " << x << " " << y << " " << currentBest << "\n";
            }
        a:;
        }

        vector<double> result;
        result.push_back(x);
        result.push_back(y);
        return result;
    }
} // namespace std

int main(int argc, char const *argv[])
{
    {
        // Quadrat:
        std::vector<std::vector<double>> poly;
        poly.push_back(std::vector<double>{1, 1});
        poly.push_back(std::vector<double>{2, 1});
        poly.push_back(std::vector<double>{2, 2});
        poly.push_back(std::vector<double>{1, 2});
        poly.push_back(std::vector<double>{1, 1}); // schlißende Ecke vergessen
        auto r1 = calculateCenterOfGravity(poly);
        auto r2 = calculateCenterOfGravityMonteCarlo(poly, 7, 100.0); // "delta" eigentlich unnötig
        std::cout << "x:" << r1[0] << " y:" << r1[1] << "\n";
        std::cout << "x:" << r2[0] << " y:" << r2[1] << "\n";
    }
    {
        // Konvexes Polygon:
        std::vector<std::vector<double>> poly;
        poly.push_back(std::vector<double>{3, 1});
        poly.push_back(std::vector<double>{5, 2});
        poly.push_back(std::vector<double>{4, 3.5});
        poly.push_back(std::vector<double>{2, 4});
        poly.push_back(std::vector<double>{1, 2.5});
        poly.push_back(std::vector<double>{3, 1}); // schlißende Ecke vergessen
        auto r1 = calculateCenterOfGravity(poly);
        auto r2 = calculateCenterOfGravityMonteCarlo(poly, 7, 100.0); // "delta" eigentlich unnötig
        std::cout << "x:" << r1[0] << " y:" << r1[1] << "\n";
        std::cout << "x:" << r2[0] << " y:" << r2[1] << "\n";
    }
    return 0;
}

    Jetzt sollte es doch zumindest vom Prinzip her richtig sein.

    0
  • T
    Gesperrt

    Hier wäre eine Optimierung für eine schnellere Konvergenz ...

                if (rBest > currentBest)
            {
                x = rx;
                y = ry;
                currentBest = rBest;
                cout << " Found: " << x << " " << y << " " << currentBest << "\n";
                maxx -= (maxx - minx) * 0.1;
                minx += (maxx - minx) * 0.1;
                maxy -= (maxy - miny) * 0.1;
                miny += (maxy - miny) * 0.1;
            }

    Ich kann die Korrektheit aber nicht zeigen.

    Sorry, so:

                if (rBest > currentBest)
            {
                x = rx;
                y = ry;
                currentBest = rBest;
                cout << " Found: " << x << " " << y << " " << currentBest << "\n";
                const double FACTOR = 0.2;
                const double f1 = (maxx - minx) * FACTOR;
                const double f2 = (maxy - miny) * FACTOR;
                maxx -= f1;
                minx += f1;
                maxy -= f2;
                miny += f2;
            }
    0
  • Mod

    @TaucherOne sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    Ich kann die Korrektheit aber nicht zeigen.

    Ich bin mir auch nicht sicher, ob da die Korrektheit überhaupt garantiert ist. Da gibt es bestimmt Beispiele, wo dein Algorithmus fröhlich für immer in lokalen Minima verschwinden wird.

    0
  • T
    Gesperrt

    Da haste wahr. 😃 Obwohl das bei konvexen Polygonen eigentlich nicht der Fall sein sollte ...

    BTW, zusammen mit der Optimierung geht es fast schon in Richtung Simulated Annealing.

    Aber eigentlich ist das alles Overkill, man kann ja die Formel für den Schwerpunkt nutzen. ...

    0
  • F

    @SeppJ sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    Der Schwerpunkt eines Polygons liegt nicht notwendigerweise in seinem Inneren.

    Im Allgemeinen nicht, aber für konvexe Polygone schon. Wenn ich den Algorithmus richtig verstanden habe, liegen alle Zwischenschritte wie auch das Endergebnis zwischen zwei Punkten des Polygons. Aus der Definition eines konvexen Polygons folgt dann, dass die alle im Inneren* liegen.

    * Inklusive Rand. Bin grad etwas verwirrt - gehören die Randpunkte dazu, wenn man vom "Inneren" spricht? Vielleicht bin ich auch einfach gerade etwas zu pedantisch 😄

    0
  • T
    Gesperrt

    @Finnegan

    https://stackoverflow.com/questions/47004208/should-point-on-the-edge-of-polygon-be-inside-polygon

    The simple answer to the question is that a point on the edge is neither inside, nor outside of polygon, it is on the boundary of the polygon - the third option. [...]

    Antwort: Weder noch. 😅

    (Solche Fälle hat man aber auch selten)

    0
    F
     1 Antwort
  • F

    @TaucherOne sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    @Finnegan

    https://stackoverflow.com/questions/47004208/should-point-on-the-edge-of-polygon-be-inside-polygon

    The simple answer to the question is that a point on the edge is neither inside, nor outside of polygon, it is on the boundary of the polygon - the third option. [...]

    Antwort: Weder noch. 😅

    (Solche Fälle hat man aber auch selten)

    Der Rand ist eh so dünn, dass er gar nicht vorhanden ist. Den kann man getrost ignorieren, wenn man kein Mathematiker ist 😁

    Oder um Stanisław Lem zu zitieren:

    Nachdem er den Drahttelegraphen erfunden hatte, zog er schliesslich einen Draht so fein aus, dass gar keiner mehr da war. Und so entstand der drahtlose Telegraph.

    1
  • T
    Gesperrt

    🤣

    Ich hab es jetzt noch einmal schöner gemacht:

    #include <vector>
#include <iostream>
#include <complex>
#include <functional>

using namespace std;

void forEachPolyEdge(vector<vector<double>> poly, function<void(vector<double>)> f)
{
    for (auto &p : poly)
    {
        f(p);
    }
}

void forEachPolySite(vector<vector<double>> poly, function<void(vector<vector<double>>)> f)
{
    for (size_t i = 0; i < poly.size() - 1; i++)
    {
        f(vector<vector<double>>{poly[i], poly[i + 1]});
    }
}

double getMaxDbl()
{
    return (unsigned int)(-1);
}
double getMinDbl()
{
    return -(double)(unsigned int)(-1);
}

double pointLineDistance(double x, double y, double x1, double y1, double x2, double y2)
{
    double A = x - x1;
    double B = y - y1;
    double C = x2 - x1;
    double D = y2 - y1;

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = -1;
    if (len_sq != 0)
    {
        param = dot / len_sq;
    }

    double xx, yy;

    if (param < 0)
    {
        xx = x1;
        yy = y1;
    }
    else if (param > 1)
    {
        xx = x2;
        yy = y2;
    }
    else
    {
        xx = x1 + param * C;
        yy = y1 + param * D;
    }

    double dx = x - xx;
    double dy = y - yy;
    return sqrt(dx * dx + dy * dy);
}

vector<double> calculateCenterOfGravityProbabilistic(vector<vector<double>> poly)
{
    // init random
    srand(time(NULL));

    // bounding box
    double maxx = getMinDbl(), minx = getMaxDbl(), maxy = getMinDbl(), miny = getMaxDbl();
    forEachPolyEdge(poly, [&](vector<double> p)
                    {
            if (p[0] > maxx)
            {
                maxx = p[0];
            }
            if (p[0] < minx)
            {
                minx = p[0];
            }
            if (p[1] > maxy)
            {
                maxy = p[1];
            }
            if (p[1] < miny)
            {
                miny = p[1];
            } });

    // Monte Carlo
    double x, y;
    double currentBest = getMinDbl();
    for (;;)
    {
        double rx = (double)rand() / (double)RAND_MAX * (maxx - minx) + minx;
        double ry = (double)rand() / (double)RAND_MAX * (maxy - miny) + miny;
        double rBest = getMaxDbl();
        forEachPolySite(poly, [&](vector<vector<double>> ps)
                        {
                double x1 = ps[0][0];
                double x2 = ps[1][0];
                double y1 = ps[0][1];
                double y2 = ps[1][1];
                double dist = pointLineDistance(rx, ry, x1, y1, x2, y2);
                if (dist < rBest) {
                    rBest = dist;
                } });
        if (rBest > currentBest)
        {
            if (rBest - 0.001 <= currentBest)
            {
                break;
            }
            x = rx;
            y = ry;
            currentBest = rBest;
            cout << " Found: " << x << " " << y << " " << currentBest << "\n";
            const double FACTOR = 0.15;
            double f1 = (maxx - minx) * FACTOR;
            double f2 = (maxy - miny) * FACTOR;
            maxx -= f1;
            minx += f1;
            maxy -= f2;
            miny += f2;
        }
    a:;
    }

    // prepare results
    vector<double> result;
    result.push_back(x);
    result.push_back(y);
    return result;
}

vector<double> calculateCenterOfGravityFallback(vector<vector<double>> poly)
{
    double sum1 = 0;
    double sum2 = 0;
    double area = 0;
    forEachPolySite(poly, [&](vector<vector<double>> ps)
                    {
            double x1 = ps[0][0];
            double x2 = ps[1][0];
            double y1 = ps[0][1];
            double y2 = ps[1][1];
            double s1 = (x1 + x2) * (x1 * y2 - x2 * y1);
            double s2 = (y1 + y2) * (x1 * y2 - x2 * y1);
            double s3 = x1 * y2 - x2 * y1;
            sum1 += s1 / 6.0;
            sum2 += s2 / 6.0;
            area += s3 * 0.5; });
    vector<double> result;
    result.push_back(sum1 / area);
    result.push_back(sum2 / area);
    return result;
}

int main(int argc, char const *argv[])
{
    {
        // Quadrat:
        vector<vector<double>> poly;
        poly.push_back(vector<double>{1, 1});
        poly.push_back(vector<double>{2, 1});
        poly.push_back(vector<double>{2, 2});
        poly.push_back(vector<double>{1, 2});
        poly.push_back(vector<double>{1, 1});
        auto r1 = calculateCenterOfGravityFallback(poly);
        auto r2 = calculateCenterOfGravityProbabilistic(poly);
        cout << "x:" << r1[0] << " y:" << r1[1] << "\n";
        cout << "x:" << r2[0] << " y:" << r2[1] << "\n";
    }
    {
        // Konvexes Polygon:
        vector<std::vector<double>> poly;
        poly.push_back(vector<double>{3, 1});
        poly.push_back(vector<double>{5, 2});
        poly.push_back(vector<double>{4, 3.5});
        poly.push_back(vector<double>{2, 4});
        poly.push_back(vector<double>{1, 2.5});
        poly.push_back(vector<double>{3, 1});
        auto r1 = calculateCenterOfGravityFallback(poly);
        auto r2 = calculateCenterOfGravityProbabilistic(poly);
        cout << "x:" << r1[0] << " y:" << r1[1] << "\n";
        cout << "x:" << r2[0] << " y:" << r2[1] << "\n";
    }
    return 0;
}

    Leider hat die Auto-Formatierung von VSCode etwas gezickt. Na ja, aber so ist es "speicherungswert". 🙂

    0
    W
     1 Antwort
  • W

    @TaucherOne sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    void forEachPolyEdge(vector<vector<double>> poly, function<void(vector<double>)> f)

    Sicher, dass du poly per value übergeben willst (gilt allgemein für alle deine Funktionen!)?

    Aber wozu überhaupt diese Funktion? Mir ist der Nutzen gerade gar nicht klar. Du sparst doch mit dieser Funktion gar nichts? (range-based-for oder std::for_each tun doch dasselbe?)

    srand(time(NULL));

    Wenn du das nutzt, dann einmalig im Programm. Aber du könntest auch die Variante mit https://en.cppreference.com/w/cpp/numeric/random anschauen. Dann brauchst du keine Rechnungen wie double rx = (double)rand() / (double)RAND_MAX * (maxx - minx) + minx; selber machen (bist du hier sicher, dass das richtige rauskommt? Passen die Grenzen? Das muss man alles nicht überlegen/verifizieren, wenn man einfach eine uniform_real_distribution nimmt (oder uniform_int_distribution, je nachdem, was man braucht)

    double getMaxDbl()
{
    return (unsigned int)(-1);
}
double getMinDbl()
{
    return -(double)(unsigned int)(-1);
}

    Was sind das denn für wilde Funktionen? Das ist nicht minDbl, sondern max unsigned integer als double.
    Suchst du vielleicht nach std::numeric_limits<double>::min() (bzw ...::max())? Siehe https://en.cppreference.com/w/cpp/types/numeric_limits

    Ganz allgemein scheint noch, dass dein Poly als vector von vector irgendwie nicht sinnvoll modelliert ist. Der innerste vector soll ja Edges darstellen? Oder einen vertex? Das hat ja immer nur 2 Werte (warum dann ein vector?) Ich würde versuchen, das als class oder struct zu modellieren und nicht einen vector von vector verwenden. Der vector von vector könnte ja irgendwas sein und hat keine direkte Verbindung zu einem Polygon. Eine allereinfache Verbesserung wäre ein std::vector<Point2d>, wobei Point2d dann eine Klasse mit x und y wäre. Dein forEachPolyEdge hat mich noch viel mehr verwirrt, weil es doch ein forEachPolyVertex ist? Das macht ja nicht mit Kanten, sondern ruft die Funktion für jede Ecke auf.

    2
    T
     3 Antworten
  • T
    Gesperrt

    @wob sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    Aber wozu überhaupt diese Funktion? Mir ist der Nutzen gerade gar nicht klar. Du sparst doch mit dieser Funktion gar nichts?

    Oh doch. Ich brauche mir keine Gedanken um ein (sich wiederholendes) Schleifenkonstrukt und die passenden Indices machen.

    Dass nicht per Referenz aufgerufen wird, ist richtig. Daran hatte ich nicht gedacht. Danke.

    0
  • T
    Gesperrt

    @wob sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    Der innerste vector soll ja Edges darstellen?

    Die x- und y-Komponente einer Ecke, ja.

    0
    W
     1 Antwort
  • W

    @TaucherOne sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    @wob sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    Der innerste vector soll ja Edges darstellen?

    Die x- und y-Komponente einer Ecke, ja.

    Eine Edge ist aber eine Kante, kein Ecke. (ich kam aufgrund deines Funktionsnamens zu dieser Frage!)

    0
    T
     1 Antwort
  • T
    Gesperrt

    @wob sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    @TaucherOne sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    @wob sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    Der innerste vector soll ja Edges darstellen?

    Die x- und y-Komponente einer Ecke, ja.

    Eine Edge ist aber eine Kante, kein Ecke.

    Ja, Sie haben Edges geschrieben. Das gesamte Polygon ist durch seine Ecken, nicht Kanten/Seiten, angegeben. Quasi eine Punktemenge. Aber ich will jetzt nicht so sehr hinab in die Graphentheorie.^^

    E:

    @wob sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    (ich kam aufgrund deines Funktionsnamens zu dieser Frage!)

    Sorry, der ist auch falsch gewählt. 😞

    0
  • T
    Gesperrt

    @wob sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    Was sind das denn für wilde Funktionen? Das ist nicht minDbl, sondern max unsigned integer als double.

    Eigentlich habe ich nur einen für die meisten Fälle groß genug bzw. klein genug (magischen) Wert gesucht ... Ich seh schon, dort droht auch ein Pitfall.

    0

  • Kann mich da @wob nur anschließen, modellier' ne vernünftige Polygon Klasse mit Point2D als Punktmenge. vector<vector<double>> ist nur durch Erklärung als Polygon zu erkennen. Wie wird denn ein Stützpunkt dargestellt, gehören jeweils zwei aufeinanderfolgende Vektorelemente zusammen und bilden einen Punkt?

    Die Funktionen forEachPolyEdge und forEachPolySite (was genau soll die können? Was hat Site mit Polygonen zu tun?) sind verwirrend (auch das wurde schon erwähnt), dafür gibt`s std::for_each (und std::transform). Zusammen mit nem vernünftigen Modell ist das auch deutlich besser lesbar.

    struct Point2D
{
   double X = 0.0;
   double Y = 0.0;

   Point2D() = default;
};

struct Line2D
{
   Point2D  Start;
   Point2D  End;

   Line2D() = default;
   Line2D( Point2D const& s, Point2D const& e ) : 
      Start( s ), End( e )
   {
   }
};


struct Polygon
{
   std::vector<Point2D> Vertices;

   Polygon() = default;

   // Überladung für []-Operator vielleicht? vertex_count() + edge_count()

   Line2D edge( unsigned int index ) const
   {
      // TO DO: Test auf Gültigkeit von index nachrüsten
      return Line2D( Vertices[index], Vertices[index +1] );
   }
};
  
int main()
{
   Polygon p = {...};
   
   auto UnaryOps = []( Point2D const& pt )
   {
      // tu was mit nem Punkt
   };
   std::for_each( p.Vertices,begin(), p.Vertices.end(), UnaryOps );
};
    1
    T
     1 Antwort
  • F

    @Quiche-Lorraine sagte in Polygon - Mittelpunkt und Schwerepunkt?:

    Gute Triangulierungen sehe ich selten. Ich bin aber auch im Bereich der digitalen Geländemodelle unterwegs und so mancher Geländeschnitt oder so manche Bruchkante verändert die Vermaschung öfters negativ. In einem extremen Fall hatte ich eine Vermaschung wo auf 1% der Fläche 99% der Dreiecke waren und das völlig korrekt!

    Ich glaube ich kann mir das vorstellen: Wenn das Gelände z.B. eine grosse Ebene hat, dann kann man diese eben mit nur einem Dreieck darstellen. Ich denke hinter diesen Dreiecksnetzen steckt eine andere Motivation, nämlich (datensparsam) die Anzahl der Dreiecke zu minimieren.

    Man kann natürlich auch die grossen Dreiecke weiter unterteilen und eine möglichst gleichförmige Triangulation finden. Ich denke im Bereich (physikalischer) Simulationen dürfte es einige Verfahren geben, welche in einem Vorverarbeitungsschritt eine solche Triangulation aus vorhandenen Modellen erzeugen. Schliesslich will man Ebenen und Gebirge vielleicht nicht unbedingt unterschiedlich präzise simulieren 🙂

    0
Anmelden zum Antworten