AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Punkt in Dreieck?

Ein Thema von BUG · begonnen am 25. Mai 2008 · letzter Beitrag vom 26. Mai 2008
Antwort Antwort
Seite 1 von 2  1 2   
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#1

Punkt in Dreieck?

  Alt 25. Mai 2008, 21:42
Da ich mich zur Zeit eh in Mathe mit Vektoren herumschlagen muss, wollte ich gleich was nützliches machen

Mit dem folgenden Code kann man herausfinden, ob ein Punkt in einem Dreieck liegt:

Delphi-Quellcode:
function pointInTriangle( x, y,
                          triangleX1, triangleY1,
                          triangleX2, triangleY2,
                          triangleX3, triangleY3: double): boolean;
var a, b: double;
begin
     // change points to vectors
     // (triangleX1|triangleY1) is position vectors
     // the rest are direction vectors
     triangleX3 := triangleX3 - triangleX2;
     triangleY3 := triangleY3 - triangleY2;

     triangleX2 := triangleX2 - triangleX1;
     triangleY2 := triangleY2 - triangleY1;

     x := x - triangleX1;
     y := y - triangleY1;

     // Check if (triangleY3*triangleX2-triangleX3*triangleY2) is 0 to prevent dividing by 0
     // If you are sure that your input is a triangle, you could remove it.
     if not (abs(triangleY3*triangleX2-triangleX3*triangleY2)>0) then
     begin
          result := false;
          exit;
     end;


     // calculate for which a and b
     //-> (x|y) = a*(triangleX2|triangleY2) + b(triangleX3|triangleY3) is true
     b := (y*triangleX2-x*triangleY2)
         /(triangleY3*triangleX2-triangleX3*triangleY2);

     if triangleX2 <> 0 then
     begin
          a := (x-b*triangleX3)/triangleX2;
     end else
     begin
          a := (y*triangleX3-x*triangleY3)
              /(triangleY2*triangleX3-triangleX2*triangleY3);
     end;

     // a will be smaller then 1 and
     // bigger than/equal to b being being bigger than/equal to 0
     // if the point is in the triangle.
     result := not((a>1) or (a<b) or (b<0));
end;
Wichtig:
Die Funktion kann sollte nur angewendet werden, wenn das "Dreieck" auch wirklich eines ist, d.h. die drei Dreiecks-Punkte dürfen nicht alle drei auf einer Geraden liegen., ansonsten ist eine Division durch Null vorprogrammiert. Aus Gründen der Übersicht wurde auf diese Überprüfung verzichtet!


Eine Demoanwendung (o.g. Fehler tritt noch auf) mit Source liegt bei, klicke um 3mal um das Dreieck festzulegen.

Viel Spaß damit!


MfG,
Bug
Angehängte Dateien
Dateityp: zip pointintriangle_123.zip (98,8 KB, 16x aufgerufen)
Intellekt ist das Verstehen von Wissen. Verstehen ist der wahre Pfad zu Einsicht. Einsicht ist der Schlüssel zu allem.
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.534 Beiträge
 
Delphi 11 Alexandria
 
#2

Re: Punkt in Dreieck?

  Alt 25. Mai 2008, 21:49
Ich will Deine Leistung nicht schmälern, aber wäre das mit einer Region nicht auch gegangen?
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#3

Re: Punkt in Dreieck?

  Alt 25. Mai 2008, 22:04
Bei den meisten Anwendungsfällen schon, aber IMHO gibt es Regionen nur mit Ganzzahlen.

MfG,
Bug
Intellekt ist das Verstehen von Wissen. Verstehen ist der wahre Pfad zu Einsicht. Einsicht ist der Schlüssel zu allem.
  Mit Zitat antworten Zitat
omata

Registriert seit: 26. Aug 2004
Ort: Nebel auf Amrum
3.154 Beiträge
 
Delphi 7 Enterprise
 
#4

Re: Punkt in Dreieck?

  Alt 25. Mai 2008, 22:07
Zitat von BUG:
...aber IMHO gibt es Regionen nur mit Ganzzahlen.
Ich wusste gar nicht, dass es halbe Bildpixel gibt

Verwunderte Grüsse
Thorsten
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#5

Re: Punkt in Dreieck?

  Alt 25. Mai 2008, 22:17
Zitat von omata:
Ich wusste gar nicht, dass es halbe Bildpixel gibt
Die sogenannten Subpixel?

Aber im Ernst, die angehängte Anwendung ist nur ein Beispiel, es sollte die Problematik nicht auf die Pixel festnageln. Es ist ja nicht so, als würde die ganze Welt aus Pixeln bestehen. (Oder doch )

MfG,
Bug
Intellekt ist das Verstehen von Wissen. Verstehen ist der wahre Pfad zu Einsicht. Einsicht ist der Schlüssel zu allem.
  Mit Zitat antworten Zitat
Benutzerbild von OldGrumpy
OldGrumpy

Registriert seit: 28. Sep 2006
Ort: Sandhausen
941 Beiträge
 
Delphi 2006 Professional
 
#6

Re: Punkt in Dreieck?

  Alt 25. Mai 2008, 22:35
Kann z.B. dann nützlich sein wenn man programmintern mit einer anderen Auflösung rechnet als letzten Endes auf dem Bildschirm erscheint. Davon einmal abgesehen: Optimal wäre der Code wenn noch ein kurzer Kommentar den mathematischen Hintergrund kurz erklärt. So in etwa "Der Punkt liegt innerhalb des Dreieck wenn ... und ... gegeben sind..." - nix wildes, aber eine ganz kurze Beschreibung. Darauf hat mich der Kommentar zu Hypot() in Math.pas gebracht. Dort steht zwar eine in Assembler geschriebene Funktion, aber auch die zugrundeliegende mathematische Formel und eine Pascal-Implementation dazu als Kommentar.
"Tja ja, das Ausrufezeichen... Der virtuelle Spoiler des 21. Jahrhunderts, der Breitreifen für die Datenautobahn, die k3wle Sonnenbrille fürs Usenet. " (Henning Richter)
  Mit Zitat antworten Zitat
grenzgaenger
(Gast)

n/a Beiträge
 
#7

Re: Punkt in Dreieck?

  Alt 25. Mai 2008, 23:20
zwei punkte fallen wir mal kurz auf, zum einen solltest du den typ TPunkt verwenden und damit die einzelkoordninaten zusammenliegen, zum zweiten, sollte deine routine solche kleinigkeiten wie 'n DIV/0 abfangen...
  Mit Zitat antworten Zitat
Benutzerbild von inherited
inherited

Registriert seit: 19. Dez 2005
Ort: Rosdorf
2.022 Beiträge
 
Turbo Delphi für Win32
 
#8

Re: Punkt in Dreieck?

  Alt 25. Mai 2008, 23:40
[quote="BUG"]
Zitat von omata:
Es ist ja nicht so, als würde die ganze Welt aus Pixeln bestehen. (Oder doch )
http://www.br-online.de/br-alpha/alp...7829151878.xml
Nikolai Wyderka

SWIM SWIM HUNGRY!
Neuer Blog: hier!
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
2.094 Beiträge
 
#9

Re: Punkt in Dreieck?

  Alt 25. Mai 2008, 23:54
Meinst du:
Delphi-Quellcode:
type TPoint = record
  X: Longint; // also nicht double
  Y: Longint; // also nicht double
end;
Dann wäre das Merkmal Gleitkommazahlen weg -> man könnte auch Regionen nehmen.
Und nur für einen Funktionsaufruf einen eigenen Typen zu basteln, finde ich eigentlich übertrieben.

Die Division durch Null tritt nur aus, wenn alle Dreieckspunkte auf einer Linie liegen, aber ok, ich werde noch eine Überprüfung einbauen.

@OldGrumpy
Jup, wäre schön ...
  • wenn a oder b größer als 1 sind, sind wir schon aus dem Dreieck heraus
  • wenn sie kleine als 0 sind auch.
  • wenn a = b, dann liegt der Punkt auf der Grade zwischen dem 3 und 1 Punkt des Dreieck (mit 2. Strahlensatz beweisbar)
  • wenn b>a, dann liegt der Punkt außerhalb des Dreiecks

Behauptungen 1 & 2 sind ja auch noch logisch, wenn die Beträge der Vektoren gleich der der Länge der entsprechenden Strecke ist. Aber bei Behauptung 4 war eine Vermutung meinerseits, die für die ich aber (heute/23:50) noch keine Begründung ausformulieren kann.

MfG,
Bug
Intellekt ist das Verstehen von Wissen. Verstehen ist der wahre Pfad zu Einsicht. Einsicht ist der Schlüssel zu allem.
  Mit Zitat antworten Zitat
grenzgaenger
(Gast)

n/a Beiträge
 
#10

Re: Punkt in Dreieck?

  Alt 26. Mai 2008, 00:14
Zitat von BUG:
Meinst du:
Delphi-Quellcode:
type TPoint = record
  X: Longint; // also nicht double
  Y: Longint; // also nicht double
end;
Dann wäre das Merkmal Gleitkommazahlen weg -> man könnte auch Regionen nehmen.
Und nur für einen Funktionsaufruf einen eigenen Typen zu basteln, finde ich eigentlich übertrieben.
ja, den datentyp meinte ich. weshalb willste denn den typ nicht nehmen? hast du angst, dass du je einen bildschirm mti mehr als 2'000'000'000 * 2'000'000'000 bildpunkten zu gesicht bekommst? in diesem falle solltest wohl eher auf INT64 ausweichen.

für die skalierung, ist ja sowieso der user resp. der programmierer zuständig. und IMHO ist mir eine schöne routine erheblich lieber, als eine, welche (aufgrund des datentyps) sowieso nicht genau sein kann.

noch 'n schönen abend GG
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 22:40 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz