[gelöst] Punkt in Dreieck

Halli hallo 😁
also vorweg ich hab gegoogelt und auch was gefunden, doch war es dort mit Vektoren beschrieben und da ich Vektoren in der Schule noch nicht hatte (also ich hab mich zwar dazu belesen aber egal) war es schwer für mich das zu verstehen (eher ich habs nicht verstanden). So könnt ihr mir einen Algorithmus/Rechnung vorschlagen die sehr viel Performance hat, da ich solch eine Rechnung mehr als 10000mal in der Sekunde machen muss.
vielen Dank schon mal 👍

Allgemeines Dreieck oder rechtwinkles Dreieck oder gleichschenkliges Dreieck?

sowas geht auch mit simpler geometrie.

@der-schlingel: Allgemeines Dreieck
@JAck30lena: Sehr produktiv" Es tut mir leid wenn ich nicht den Ansatz finde.

//passiert 👅

Was ist eigentlich deine Frage?

Hehe 👍. Stimmt die Frage ist ganz schön versteckt. Die frage ist wie man berechnen kann ob ein Punkt in einem allgemeinem Dreiecklieg? Dabei sind die Koordinaten der Eckpunkte des Dreiecks gegeben und die Koordinaten des Punktes. Gut wär auch wenn die Rechnug schnell wär wegen der Performance.

Hi,

da kannst du wirklich wie schon Jack30Lena beschrieben hat, das ganz einfach mit einer Berechnung feststellen. Die kriegst du schon alleine auf die Reihe.
Poste dann dein Ergebnis und hier wird dir dann sicherlich gesagt wie man die Performance verbessern kann oder was nicht so gut ist.

Denn gerade wenn man selbst soetwas macht lernt man viel dazu 🙂

Gruss
Michael

Ich hab ja auch schon Ideen gehabt, wie Gerade zwischen Punkt und Mittelpunkt des Dreiecks und dann schauen ob sich die Grade mit den "Kanten" des Dreiecks scheindet, aber ich glaub dass die Performance darunter leidet.

Ohne Trigonometrie:

        private bool IsPointInTriangle(Point p, Point a, Point b, Point c)
        {
            return new Region(
                new System.Drawing.Drawing2D.GraphicsPath(
                    new Point[] { a, b, c },
                    new byte[]{
                        (byte)PathPointType.Line,
                        (byte)PathPointType.Line,
                        (byte)PathPointType.Line
                    }
                )
             ).IsVisible(p);
        }

Lg XXX

Cool! Vielen Dank 👍

bääm... ich dachte es soll performant sein :S

Edit: bei vektoren gibt es eigentlich nich soviel zu verstehen (abgesehen von den berechnungen)... meistens wird es auch einem klar wenn man bissl oldschool denkt, sich ein blatt und stift in die hand nimmt, und anfängt zu zeichnen... (Nen "Vektor" hattest du bestimmt schon einmal irgendwo in der schule benutzt... z.b. lineare funktionen)

naja nicht ganz so cool.

1. sowohl graphicspath als auch region implementieren idisposable und müssen daher manuell wieder freigegeben werden, was im geposteten code nciht passiert.
2. schleppen diese klassen sehr viel overhead mit, was das ganze ineffektiv macht.
3. sind die klassen für diesen fall eigendlich nciht gedacht.

edit: und die gdi-handles die es verfrisst können sehr sehr schnell zu einer outofmemoryexception führen....

Also im Titel steht zwar [gelöst], also scheint es nicht mehr relevant zu sein, aber das kann ich nicht so stehen lassen... Nix gegen deine Lösung, xxxprod, das ist sehr elegant, aber hat nix mit Geometrie zu tun 🙂 Also nix für ungut.

Um zu prüfen, ob ein Punkt in einem Dreieck liegt, berechnet man seine Baryzentrischen Koordinaten und testet ob diese zwischen 0 und 1 liegen. Soweit zur Theorie.

Cnard, hast du schonmal probiert "point in triangle" bei Google einzugeben?

Das Forum ist nicht dazu da, daß wir hier deinen Code schreiben!

Bereits der erste Treffer hat zwei verschiedene, ausformulierte Algorithmen, unter anderem auch über die Baryzentrischen Koordinaten: http://www.blackpawn.com/texts/pointinpoly/default.html

Schöne Grüße,
Christian

xD cool... hab gerade auch mal ein bissl rumgetrixt..

/// <summary>Überprüft auf welcher Seite der Linie der angegebene Punkt liegt.</summary>
/// <param name="start">Startpunkt der Linie.</param>
/// <param name="end">Endpunkt der Linie.</param>
/// <param name="pos">Position des punktes der überprüft werden soll.</param>
/// <returns>Ein Wert unter 0 = "links" von der Linie; Über 0 "Rechts von der Linie.</returns>
private float orientation(PointF start, PointF end, PointF pos) {
	float determinant =
		(end.X - start.X) * (pos.Y - start.Y) -
		(pos.X - start.X) * (end.Y - start.Y);

	if (determinant < 0) {
		return -1;
	}
	return 1;
}

//benutzt wird es so...
bool isInside =
	(orientation(a, b, pos) == orientation(a, b, c)) &&
	(orientation(b, c, pos) == orientation(b, c, a)) &&
	(orientation(c, a, pos) == orientation(c, a, b));

is aber total das gleiche.. funzt wie ne 1

umständlicher aber funktioniert trotzdem:

        public bool IsPointInTriangle(Point a, Point b, Point c, Point p)
        {
            return IsPointInTriangle(p.X, p.Y, a.X, a.Y, b.X, b.Y, c.X, c.Y);
        }
        public bool IsPointInTriangle(double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3)
        {
            double divisor = 0.0;
            double m1;
            double m2;
            double m3;

            divisor = (x3 - x1);
            m1 = divisor == 0.0 ? 0.0 : (y3 - y1) / divisor;
            divisor = (x2 - x1);
            m2 = divisor == 0.0 ? 0.0 : (y2 - y1) / divisor;
            divisor = (x3 - x2);
            m3 = divisor == 0.0 ? 0.0 : (y3 - y2) / divisor;

            double b1 = y1 - m1 * x1;
            double b2 = y2 - m2 * x2;
            double b3 = y3 - m3 * x3;            

            double y10 = m1 * x0 + b1;
            double y20 = m2 * x0 + b2;
            double y30 = m3 * x0 + b3;
            
            double x10 = m1 == 0.0 ? 0.0 : (y0 - b1) / m1;            
            double x20 = m2 == 0.0 ? 0.0 : (y0 - b2) / m2;            
            double x30 = m3 == 0.0 ? 0.0 : (y0 - b3) / m3;  

            return !
                (
                    (x0 < x10 && x0 < x20 && x0 < x30) ||
                    (x0 > x10 && x0 > x20 && x0 > x30) ||
                    (y0 < y10 && y0 < y20 && y0 < y30) ||
                    (y0 > y10 && y0 > y20 && y0 > x30)
                );
        }

Hi,
sorry hab mir das Thema nicht mehr angeschaut, halt wegen "[gelöst]".
Vielen Dank werde das jetzt mal alles nachvollziehen, weil ich jetzt Vektoren habe ^^ und in meinem Programm mit einbauen.

@MrSparkle

Das Forum ist nicht dazu da, daß wir hier deinen Code schreiben!

Das hatte ich auch nicht erwartet - war aber zufrieden als ich dann eine so einfache Lösung bekam (schäm), aber wenn das so rüber kam tut es mir leid.

Also Danke nochmal!
Grüße Cnard