Liegt Punkt in einem 2D-Dreieck

Fragen zu mathematischen Problemen
AnGaiNoR
Beiträge: 212
Registriert: Sa Jul 19, 2008 7:07 pm
Wohnort: Dresden

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von AnGaiNoR » Mo Jan 25, 2010 5:55 pm

cloidnerux hat geschrieben:Fehler gefunden:
http://www.zum.de/Foren/mathematik/archiv/a24.html
Der Punkt liegt im Dreieck, wenn 0 <= r, s <= 1 und r+s <= 1.
Das hat das Problem gelöst. Ich danke für die Hilfe.
Das ist mir heute Vormittag auch eingefallen. Übrigens hatte ich das in meinem Beweis auch mit angeführt ^^
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » Mo Jan 25, 2010 6:10 pm

Übrigens hatte ich das in meinem Beweis auch mit angeführt ^^
Aber ich nicht in meinen gedanken^^
Hatte etwas wenig Zeit, habe also den Beweis nicht richtig durchgerechnet und das ein oder andere übersehen.
Hier der Funktionierende Code, geschrieben in C#:

Code: Alles auswählen

 /// <summary>
        /// Errechnet ob ein Punkt P innerhalb des Dreiecks ABC liegt
        /// </summary>
        /// <param name="p">Der zu Prüfende Punkt</param>
        /// <param name="A">Der Eckpunkt A des Dreiecks</param>
        /// <param name="B">Der Eckpunkt B des Dreiecks</param>
        /// <param name="C">Der Eckpunkt C des Dreiecks</param>
        /// <returns>true wenn der Punkt innerhalb des Dreieck liegt</returns>
        public static bool IsPointInTriangle(Point p, Point A, Point B, Point C)
        {
            VectorF vc = new VectorF(B.X - A.X, B.Y - A.Y);
            VectorF vb = new VectorF(C.X - A.X, C.Y - A.Y);
            VectorF vp = new VectorF(p.X - A.X, p.Y - A.Y);
            float r, s;
            r = ((vp.X * vc.Y) - (vp.Y * vc.X)) / ((vb.X * vc.Y) - (vc.X * vb.Y));
            s = ((vp.Y * vb.X) - (vp.X * vb.Y)) / ((vb.X * vc.Y) - (vc.X * vb.Y));
            if (r >= 0 && r <= 1 && s >= 0 && s <= 1 && (r + s) <= 1)
            {
                return true;
            }
            return false;
        }
class VectorF
        {
        /// <summary>
        /// Die Vectorangaben
        /// </summary>
        float x, y;
        /// <summary>
        /// Die X-Länge des Vectors
        /// </summary>
        public float X
        {
            get
            {
                return x;
            }
            set
            {
                x = value;
            }
        }
        /// <summary>
        /// Die Y-Länge des Vectors
        /// </summary>
        public float Y
        {
            get
            {
                return y;
            }
            set
            {
                y = value;
            }
        }

        public VectorF()
        {
            X = 0;
            Y = 0;
        }

        public VectorF(float vX, float vY)
        {
            X = vX;
            Y = vY;
        }

        /// <summary>
        /// Gibt den Winkel des Vectors zurück
        /// </summary>
        /// <returns></returns>
        public double GetAngel()
        {
            return System.Math.Asin(y / this.GetLength());
        }

        /// <summary>
        /// Gibt die Länge des Vectors zurück
        /// </summary>
        /// <returns></returns>
        public double GetLength()
        {
            return System.Math.Sqrt(y * y + x * x);
        }

        #region Operatoren
        public static VectorF operator +(VectorF v1, VectorF v2)
        {
            return new VectorF(v1.X + v2.X, v1.Y + v2.Y);
        }

        public static VectorF operator -(VectorF v1, VectorF v2)
        {
            return new VectorF(v1.X - v2.X, v1.Y - v2.Y);
        }

        public static VectorF operator *(VectorF v1, float skalar)
        {
            return new VectorF(v1.X * skalar, v1.Y * skalar);
        }

        public static float operator *(VectorF v1, VectorF v2)
        {
            return ((v1.X * v2.X) + (v1.Y * v2.Y));
        }
        #endregion
    }
Redundanz macht wiederholen unnötig.
quod erat expectandum

AnGaiNoR
Beiträge: 212
Registriert: Sa Jul 19, 2008 7:07 pm
Wohnort: Dresden

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von AnGaiNoR » Mo Jan 25, 2010 6:35 pm

cloidnerux hat geschrieben:

Code: Alles auswählen

 
if (r >= 0 && r <= 1 && s >= 0 && s <= 1 && (r + s) <= 1)
Die Überprüfung ob r und s höchstens eins sind kannst du weglassen, das folgt ja direkt aus dem letzten Vergleich.
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

l1a2r3s4
Beiträge: 1
Registriert: So Nov 11, 2012 10:35 pm

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von l1a2r3s4 » So Nov 11, 2012 11:06 pm

ist zwar lange her das thema, aber ich hätte auch ne gute idee, die eventuel etwas schneller wär. vor allen da er weniger multiplikatoren (6), und keine divisionen benötigt.

zuerst bildet man 3 hilfvectoren h1,h2,h3 die 90° gedreht zu den 3 seiten der dreicke stehen. einfach indem man x=-(y1-y2),y=x1-x2 rechnet. das macht man für a->b b->c c->a. sind 6 subtarktionen und 3 negationen, die alle in einen takt erledigt werden könten dachnah erzeugt man 3 vectoren p1,p2,p3 von jeden punkt nach p

wenn man dann das die skalaprodukte bildet mit sa=h1.x*p1.x+h1.y*p1.y , und das natürlich nich für sb und sc dann hat man 3 werte die positiv oder negativ sind. ist das dreick immer im drehsinn reich dir prüfung sa>0 & sb>0 & sc > 0. wenn es auch mal anderesrum sein kann prüft man sa>0 & sb>0 und sc>0 | sa<0 & sb<0 & sc < 0 , da wenn alle produkte gleich sind der punkt sich innen befindet und wenn sie ungleich sind sich der punkt ausen befindet.

insgesamt bruach man
-9 additionen oder subtraktionen(1 takt)
-3 negationen(1takt)
-6 multiplikatoren(glaube bis 32 takte bei 32 bit zahlen)
-keine division(die soweit ich weis länger braucht als eine multiplikation)
-keine sin cos oder tan funtionen
-3 oder 6 prüfungen

ihr brauchtet schon 2 multiplikatoren und 3 divisionen für s, eine weitere multiplikation und divisionj für r , was jetzt schon länger ist, auch wenn ihr eventuel nur eine prüfung braucht, und wenn das false ergibt, müst ihr das alles noch mal wiederholen.

da find ich meine lösung schneller und auch einfacher zu verstehen. mathematische beweise kann ich nicht liefern, da ich vector rechnung über wikipedia vor einer woche gelernt hab XD

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » Mo Nov 12, 2012 9:03 am

Hallo und Willkommen im Forum.
ist zwar lange her das thema, aber ich hätte auch ne gute idee, die eventuel etwas schneller wär. vor allen da er weniger multiplikatoren (6), und keine divisionen benötigt.
Ich habe mal beide Algorithmen gegeneinander verglichen.
Hier mein Code:

Code: Alles auswählen

#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

int main()
{
    int  points[4][2];
    int hvector[3][2];      //hilfsvectoren (normalen)
    int pvector[3][2];      //Punktvectoren
    int scalar[3];

    float vectors[3][2];
    float r, s;
    int notInT = 0;
    srand(time(NULL));
    clock_t start, end, alg1, alg2;
    for(int i = 0; i < 1000; i++)
    {
        for(int a = 0; a < 4; a++)          //Some random data
        {
            points[a][0] = rand() % 1000;
            points[a][1] = rand() % 1000;
        }
        hvector[0][0] = -(points[1][1] - points[0][1]);
        hvector[0][1] = points[1][0] - points[0][0];
        hvector[1][0] = -(points[2][1] - points[1][1]);
        hvector[1][1] = points[2][0] - points[1][0];
        hvector[2][0] = -(points[0][1] - points[2][1]);
        hvector[2][1] = points[0][0] - points[2][0];
        for(int a = 0; a < 3; a++)
        {
            pvector[a][0] = points[3][0] - points[a][0];
            pvector[a][1] = points[3][1] - points[a][1];
        }
        for(int a = 0; a < 3; a++)
        {
            scalar[a] = hvector[a][0] * pvector[a][0] + hvector[a][1] * pvector[a][1];
        }

        vectors[0][1] = points[1][1] - points[0][1];
        vectors[0][0] = points[1][0] - points[0][0];
        vectors[1][1] = points[2][1] - points[0][1];
        vectors[1][0] = points[2][0] - points[0][0];
        vectors[2][0] = points[3][0] - points[0][0];
        vectors[2][1] = points[3][1] - points[0][1];
        r = ((vectors[2][0] * vectors[1][1]) - (vectors[2][1] * vectors[1][0])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
        s = ((vectors[2][1] * vectors[0][0]) - (vectors[2][0] * vectors[0][1])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
        if (((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1) && ((r + s) <= 1)) != ((scalar[0]>0 && scalar[1]>0 && (scalar[2]>0)) || (scalar[0]<0 && scalar[1]<0 && scalar[2] < 0)))
        {
            cout << "Someone is wrong!" << endl << "Points: ";
            for(int a = 0; a < 4; a++)
            {
                cout << a << ". X: " << points[a][0] << "Y: " << points[a][1] << "|";
            }
            cout << endl << "hvectors: ";
            for(int a = 0; a < 3; a++)
            {
                cout << a << ". X: " << hvector[a][0] << "Y: " << hvector[a][1] << "|";
            }
            cout << endl << "pvectors: ";
            for(int a = 0; a < 3; a++)
            {
                cout << a << ". X: " << pvector[a][0] << "Y: " << pvector[a][1] << "|";
            }
            cout << endl << "scalars: ";
            for(int a = 0; a < 3; a++)
            {
                cout << a << " " << scalar[a] << "|";
            }
            cout << endl << "vectors: ";
            for(int a = 0; a < 3; a++)
            {
                cout << a << ". X: " << vectors[a][0] << "Y: " << vectors[a][1] << "|";
            }
            cout << endl << "r: " << r << " s: " << s << endl;
        }
    }
    start = clock();
    for(int i = 0; i < 100000000; i++)
    {
        for(int a = 0; a < 4; a++)          //Some random data
        {
            points[a][0] = rand() % 1000;
            points[a][1] = rand() % 1000;
        }
        hvector[0][0] = -(points[1][1] - points[0][1]);
        hvector[0][1] = points[1][0] - points[0][0];
        hvector[1][0] = -(points[2][1] - points[1][1]);
        hvector[1][1] = points[2][0] - points[1][0];
        hvector[2][0] = -(points[0][1] - points[2][1]);
        hvector[2][1] = points[0][0] - points[2][0];
        for(int a = 0; a < 3; a++)
        {
            pvector[a][0] = points[3][0] - points[a][0];
            pvector[a][1] = points[3][1] - points[a][1];
        }
        for(int a = 0; a < 3; a++)
        {
            scalar[a] = hvector[a][0] * pvector[a][0] + hvector[a][1] * pvector[a][1];
        }
        if((scalar[0]>0 && scalar[1]>0 && (scalar[2]>0)) || (scalar[0]<0 && scalar[1]<0 && scalar[2] < 0))
            notInT++;
    }
    end = clock();
    cout << end << " from " << start << "(" << end - start << ") with " << notInT << " Points" << endl;
    alg1 = end - start;
    notInT = 0;
    start = clock();
    for(int i = 0; i < 100000000; i++)
    {
        for(int a = 0; a < 4; a++)          //Some random data
        {
            points[a][0] = rand() % 1000;
            points[a][1] = rand() % 1000;
        }
        vectors[0][1] = points[1][1] - points[0][1];
        vectors[0][0] = points[1][0] - points[0][0];
        vectors[1][1] = points[2][1] - points[0][1];
        vectors[1][0] = points[2][0] - points[0][0];
        vectors[2][0] = points[3][0] - points[0][0];
        vectors[2][1] = points[3][1] - points[0][1];
        r = ((vectors[2][0] * vectors[1][1]) - (vectors[2][1] * vectors[1][0])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
        s = ((vectors[2][1] * vectors[0][0]) - (vectors[2][0] * vectors[0][1])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
        if ((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1) && ((r + s) <= 1))
            notInT++;
    }
    end = clock();
    cout << end << " from " << start << "(" << end - start << ") with " << notInT << " Points" << endl;
    alg2 = end - start;
    cout << "Alg1: " << alg1 << " to Alg2:" << alg2 << " with " << (float)((alg2 - alg1) / (float)(alg1)) * 100.0f << "% diff";
    return 0;
}
Bei 100.000.000 Durchläufen mit Zufälligen Daten mit den Standardeinstellungen vom Qt Designer komme ich auf folgende Ergebnisse:

Code: Alles auswählen

16800000 from 0(16800000) with 7641610 Points
34260000 from 16800000(17460000) with 7641423 Points
Alg1: 16800000 to Alg2:17460000 with 3.92857% diff
Mit g++ direkt und O3 auf:

Code: Alles auswählen

15550000 from 0(15550000) with 7639944 Points
33030000 from 15550000(17480000) with 7641594 Points
Alg1: 15550000 to Alg2:17480000 with 12.4116% diff
Dein Code ist also um 3,92% schneller in einer realen Anwendung, 12,4% mit Optimierungen, benötigst aber deutlich mehr Variablen und es muss noch bewiesen werden, damit auch garantiert ist, das für alle Kombinationen dieser Algorithmus richtig ist. Nicht schlecht.
insgesamt bruach man
-9 additionen oder subtraktionen(1 takt)
-3 negationen(1takt)
-6 multiplikatoren(glaube bis 32 takte bei 32 bit zahlen)
-keine division(die soweit ich weis länger braucht als eine multiplikation)
-keine sin cos oder tan funtionen
-3 oder 6 prüfungen
Hier stößt du an das Problem, das Code und Programm keinen 1:1 Zusammenhang haben. Dein Compiler Optimiert deinen Code und passt ihn auf Architekturen an, bzw man kann es auch direkt für bestimmte Prozessoren optimieren und Performance aus speziellen Prozessoroperaionen ziehen.
Aber das kannst du nicht anhand von Code bewerten.
Das merkt man sehr deutlich, wenn man viele unterschiedliche Implementierungen vergleicht:
http://www.proggen.org/doku.php?id=project:wordcount
http://www.proggen.org/forum/viewtopic.php?f=49&t=4872

Edit: Die Werte waren ja noch mit Zufallszahlen. Ohne wird das ganze mit 03 alles Wegoptimiert und von Qt erhält man das:

Code: Alles auswählen

5270000 from 0(5270000) with 0 Points
7650000 from 5270000(2380000) with 0 Points
Alg1: 5270000 to Alg2:2380000 with -54.8387% diff
Wobei hier wieder die Frage ist, wie der Compiler hier Optimiert.
Man merkt, es ist nicht so einfach eine Qualitative Analyse von Quellcode zu erstellen.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » Mo Nov 12, 2012 12:13 pm

So, nochmal zur Perfomance-Analyse bevor sich wer beschwert: Ich hab das zu sehr vereinfacht. Das Generieren der Daten ist ein Additiver Bestandteil der die relative Bewertung verfälscht.
Ich habe jetzt einmal nur den Random-Data Teil gemessen und Abgezogen und komme auf das Ergebnis:

Code: Alles auswählen

Random Data: 14770000
36590000 from 14770000(21820000) with 7641955 Points
58260000 from 36590000(21670000) with 7639653 Points
Alg1: 7050000 to Alg2:6900000 with -2.12766% diff
Und bin verwirrt: Auf einmal ändern sich die Zeiten schon wieder, ohne ausdrückliche Optimierungen mit g++.
Und dann halt nochmal mit O0:

Code: Alles auswählen

[cloidnerux@cloidnerux-PC DreieckTest]$ g++ -o test main.cpp -O0
[cloidnerux@cloidnerux-PC DreieckTest]$ ./test
Random Data: 16220000
38620000 from 16220000(22400000) with 7639686 Points
60000000 from 38620000(21380000) with 7641633 Points
Alg1: 6180000 to Alg2:5160000 with -16.5049% diff
Bisher lief alles auf Fedora 17 x64 mit einem Core i5 ULV und 4GB Ram, jetzt das ganze nochmal auf Windows 7 64-Bit mit AMD Phenom II X4 und 8GB Ram:

Code: Alles auswählen

D:\Users\cloidnerux\Documents>g++ dreieck.cpp -o test.exe
D:\Users\cloidnerux\Documents>test.exe
Random Data: 20990
46502 from 21020(25482) with 7658701 Points
72063 from 46503(25560) with 7656565 Points
Alg1: 4492 to Alg2:4570 with 1.73642% diff
D:\Users\cloidnerux\Documents>g++ dreieck.cpp -o test.exe -O3

D:\Users\cloidnerux\Documents>test.exe
Random Data: 11256
32501 from 11258(21243) with 7654106 Points
55321 from 32502(22819) with 7654135 Points
Alg1: 9987 to Alg2:11563 with 15.7805% diff
Hier der Code:

Code: Alles auswählen

#include <iostream>
#include <stdlib.h>
#include <time.h>

#define RAND_DATA

using namespace std;

int main()
{
    int  points[4][2];
    int hvector[3][2];      //hilfsvectoren (normalen)
    int pvector[3][2];      //Punktvectoren
    int scalar[3];

    float vectors[3][2];
    float r, s;
    int notInT = 0;
    srand(time(NULL));
    clock_t start, end, alg1, alg2, data;
    for(int i = 0; i < 1000; i++)
    {
        for(int a = 0; a < 4; a++)          //Some random data
        {
            points[a][0] = rand() % 1000;
            points[a][1] = rand() % 1000;
        }
        hvector[0][0] = -(points[1][1] - points[0][1]);
        hvector[0][1] = points[1][0] - points[0][0];
        hvector[1][0] = -(points[2][1] - points[1][1]);
        hvector[1][1] = points[2][0] - points[1][0];
        hvector[2][0] = -(points[0][1] - points[2][1]);
        hvector[2][1] = points[0][0] - points[2][0];
        for(int a = 0; a < 3; a++)
        {
            pvector[a][0] = points[3][0] - points[a][0];
            pvector[a][1] = points[3][1] - points[a][1];
        }
        for(int a = 0; a < 3; a++)
        {
            scalar[a] = hvector[a][0] * pvector[a][0] + hvector[a][1] * pvector[a][1];
        }

        vectors[0][1] = points[1][1] - points[0][1];
        vectors[0][0] = points[1][0] - points[0][0];
        vectors[1][1] = points[2][1] - points[0][1];
        vectors[1][0] = points[2][0] - points[0][0];
        vectors[2][0] = points[3][0] - points[0][0];
        vectors[2][1] = points[3][1] - points[0][1];
        r = ((vectors[2][0] * vectors[1][1]) - (vectors[2][1] * vectors[1][0])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
        s = ((vectors[2][1] * vectors[0][0]) - (vectors[2][0] * vectors[0][1])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
        if (((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1) && ((r + s) <= 1)) != ((scalar[0]>0 && scalar[1]>0 && (scalar[2]>0)) || (scalar[0]<0 && scalar[1]<0 && scalar[2] < 0)))
        {
            cout << "Someone is wrong!" << endl << "Points: ";
            for(int a = 0; a < 4; a++)
            {
                cout << a << ". X: " << points[a][0] << "Y: " << points[a][1] << "|";
            }
            cout << endl << "hvectors: ";
            for(int a = 0; a < 3; a++)
            {
                cout << a << ". X: " << hvector[a][0] << "Y: " << hvector[a][1] << "|";
            }
            cout << endl << "pvectors: ";
            for(int a = 0; a < 3; a++)
            {
                cout << a << ". X: " << pvector[a][0] << "Y: " << pvector[a][1] << "|";
            }
            cout << endl << "scalars: ";
            for(int a = 0; a < 3; a++)
            {
                cout << a << " " << scalar[a] << "|";
            }
            cout << endl << "vectors: ";
            for(int a = 0; a < 3; a++)
            {
                cout << a << ". X: " << vectors[a][0] << "Y: " << vectors[a][1] << "|";
            }
            cout << endl << "r: " << r << " s: " << s << endl;
        }
    }
#ifdef RAND_DATA
    start = clock();
    for(int i = 0; i < 100000000; i++)
    {
        for(int a = 0; a < 4; a++)          //Some random data
        {
            points[a][0] = rand() % 1000;
            points[a][1] = rand() % 1000;
        }
    }
    end = clock();
    cout << "Random Data: " << end - start << endl;
    data = end - start;
#endif
    start = clock();
    for(int i = 0; i < 100000000; i++)
    {
#ifdef RAND_DATA
        for(int a = 0; a < 4; a++)          //Some random data
        {
            points[a][0] = rand() % 1000;
            points[a][1] = rand() % 1000;
        }
#endif
        hvector[0][0] = -(points[1][1] - points[0][1]);
        hvector[0][1] = points[1][0] - points[0][0];
        hvector[1][0] = -(points[2][1] - points[1][1]);
        hvector[1][1] = points[2][0] - points[1][0];
        hvector[2][0] = -(points[0][1] - points[2][1]);
        hvector[2][1] = points[0][0] - points[2][0];
        for(int a = 0; a < 3; a++)
        {
            pvector[a][0] = points[3][0] - points[a][0];
            pvector[a][1] = points[3][1] - points[a][1];
        }
        for(int a = 0; a < 3; a++)
        {
            scalar[a] = hvector[a][0] * pvector[a][0] + hvector[a][1] * pvector[a][1];
        }
        if((scalar[0]>0 && scalar[1]>0 && (scalar[2]>0)) || (scalar[0]<0 && scalar[1]<0 && scalar[2] < 0))
            notInT++;
    }
    end = clock();
    cout << end << " from " << start << "(" << end - start << ") with " << notInT << " Points" << endl;
    alg1 = end - start;
    notInT = 0;
    start = clock();
    for(int i = 0; i < 100000000; i++)
    {
#ifdef RAND_DATA
        for(int a = 0; a < 4; a++)          //Some random data
        {
            points[a][0] = rand() % 1000;
            points[a][1] = rand() % 1000;
        }
#endif
        vectors[0][1] = points[1][1] - points[0][1];
        vectors[0][0] = points[1][0] - points[0][0];
        vectors[1][1] = points[2][1] - points[0][1];
        vectors[1][0] = points[2][0] - points[0][0];
        vectors[2][0] = points[3][0] - points[0][0];
        vectors[2][1] = points[3][1] - points[0][1];
        r = ((vectors[2][0] * vectors[1][1]) - (vectors[2][1] * vectors[1][0])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
        s = ((vectors[2][1] * vectors[0][0]) - (vectors[2][0] * vectors[0][1])) / ((vectors[0][0] * vectors[1][1]) - (vectors[1][0] * vectors[0][1]));
        if ((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1) && ((r + s) <= 1))
            notInT++;
    }
    end = clock();
    cout << end << " from " << start << "(" << end - start << ") with " << notInT << " Points" << endl;
    alg2 = end - start;
    cout << "Alg1: " << (alg1 - data) << " to Alg2:" << (alg2 - data) << " with " << (float)((alg2 - alg1) / (float)(alg1 - data)) * 100.0f << "% diff";
    return 0;
}

Redundanz macht wiederholen unnötig.
quod erat expectandum

Banananananarama
Beiträge: 1
Registriert: So Mär 30, 2014 12:38 pm

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von Banananananarama » So Mär 30, 2014 12:46 pm

Hallo,

hat denn mal jemand geprüft ob die von l1a2r3s4 dargestellte Variante tatsächlich funktioniert? Ich hab die Implementierung (der Variante von l1a2r3s4) von cloidnerux direkt übernommen und sie funktioniert bei mir nicht! Die andere Variante hingegen funktioniert einwandfrei.

mfg
Banananananarama

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » So Mär 30, 2014 1:13 pm

Hi und Willkommen im Forum :D
hat denn mal jemand geprüft ob die von l1a2r3s4 dargestellte Variante tatsächlich funktioniert? Ich hab die Implementierung (der Variante von l1a2r3s4) von cloidnerux direkt übernommen und sie funktioniert bei mir nicht! Die andere Variante hingegen funktioniert einwandfrei.
Ich hatte in meinem Code zum Vergleich der beiden Algorithmen eine Überprüfung, ob beide für die selben Daten das selbe Ergebnis liefern. Ich hab mich damit ehrlich gesagt nicht weiter damit beschäftigt und auch nicht überprüft, ob die Implementation so stimmt.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Antworten