BorlandTalk.com

John Smith · Guest

I got this pascal code for determining whether a point is in a triangle,
from the newsgroups.
Does anybody know how this code could be modifed in order to
cater for the instance where the line between 2 of the triangle vertices is
vertical or horizontal. This code doesnt seem to give the correct output
with these lines.

If anybody has alternate code that may be better would appreciate your
posting it .
many thanks.

type
Point = record
x,y : real
end;

function Det ( p,q : Point ) : real;
begin
Det := p.x*q.y - p.y*q.x
end;

function Cross ( p,q,r : Point ) : real;
begin
Cross := Det(q,r) - Det(p,r) + Det(p,q)
end;

function Sign ( t : real ) : integer;
begin
if (t > 0) then Sign := 1
else if (t < 0) then Sign := -1
else Sign := 0
end;

function SameSide ( a,b,p,q : Point ) : boolean;
{ returns true if p and q are on the same
side of the line through a and b }
begin
if Sign(Cross(a,b,p))*Sign(Cross(a,p,q)) = 1
then SameSide := TRUE
else SameSide := FALSE
end;

function InTriangle ( a,b,c,p : Point ) : boolean;
{ returns true if p is inside triangle abc }
begin
InTriangle :=
Sameside(a,b,c,p) and SameSide(b,c,a,p) and SameSide(c,a,b,p)
end;

However, since Cross(a,b,c) = Cross(b,c,a) = Cross(c,a,b),
there is redundancy in the above routine (there are also
other redundancies, too). Better, then, is the following:

function IsInTriangle ( a,b,c,p : Point ) : boolean;
var
abc : integer;
bc,ca,abap,bp,cp : real;
begin
bc := Det(b,c);
ca := Det(c,a);
ab := Det(a,b);
ap := Det(a,p);
bp := Det(b,p);
cp := Det(c,p);
abc := Sign(bc + ca + ab);
IsInTriangle :=
(abc*(bc-bp+cp)>0) and (abc*(ca-cp+ap)>0) and (abc*(ab-ap+bp)>0)
end;

Pavel Vymazal · Guest

Two lines, AB and CD, have a 90 degree angle (i.e., are orthogonal) between
them, if their scalar multiplication equals to 0.
In computing, care has to be taken for "almost 0" - due to rounding errors
(underflow etc.), two lines may be misinterpreted as orthogonal when they
are not, and vice-versa.

For more information on scalar multiplication, check any Algebra book. Also,
since you seem to be working on a project that will do more than just
determining orthogonals, check stuff like Determinants, Vector
multiplication, Theorems about inner/outer angle of a polygon etc.
True programmers aren't afraid of Math :-)

"John Smith" <JSmith (AT) Hotmail (DOT) com> pí¹e v diskusním pøíspìvku
news:41384e51 (AT) newsgroups (DOT) borland.com...

hu zhenghui · Guest

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Math;

type
TTriangle = record
P1 : TPoint;
P2 : TPoint;
P3 : TPoint;
end;

type
TForm1 = class(TForm)
procedure FormCreate(Sender: TObject);
procedure FormPaint(Sender: TObject);
private
{ Private declarations }
Triangle : TTriangle;
public
{ Public declarations }
end;

var
Form1: TForm1;

implementation

{$R *.dfm}
function PointInTriangle(P : TPoint; Triangle : TTriangle) : Boolean;
var
S : Integer;
begin
S := Sign((Triangle.P1.X - P.X) * (Triangle.P2.Y - P.Y) - (Triangle.P2.X -
P.X) * (Triangle.P1.Y - P.Y)) +
Sign((Triangle.P2.X - P.X) * (Triangle.P3.Y - P.Y) - (Triangle.P3.X -
P.X) * (Triangle.P2.Y - P.Y)) +
Sign((Triangle.P3.X - P.X) * (Triangle.P1.Y - P.Y) - (Triangle.P1.X -
P.X) * (Triangle.P3.Y - P.Y));
Result := (S = 3) or (S = -3);
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
randomize;
Triangle.P1.X := random(100);
Triangle.P1.Y := random(100);
Triangle.P2.X := random(100);
Triangle.P2.Y := random(100);
Triangle.P3.X := random(100);
Triangle.P3.Y := random(100);
end;

procedure TForm1.FormPaint(Sender: TObject);
var
X : Integer;
Y : Integer;
begin
for x := 0 to 100 do
begin
for y := 0 to 100 do
begin
if PointInTriangle(Point(X, Y), Triangle) then
begin
Canvas.Pixels[x, y] := clWhite;
end
else
begin
Canvas.Pixels[x, y] := clBlack;
end;
end;
end;
Canvas.Pen.Color := clYellow;
Canvas.MoveTo(Triangle.P1.X, Triangle.P1.Y);
Canvas.LineTo(Triangle.P2.X, Triangle.P2.Y);
Canvas.LineTo(Triangle.P3.X, Triangle.P3.Y);
Canvas.LineTo(Triangle.P1.X, Triangle.P1.Y);
end;

end.

--
Hu Zhenghui
IBM Certified Solutions Expert - IBM WebSphere Studio
IBM Certified Database Associate - DB2 Universal Database V8.1 Family
IBM eServer Certified Specialist - pSeries AIX System Administration
IBM Certified Database Administrator - DB2 Universal Database V8.1 for
Linux, UNIX and Windows
<New Intranet Series - Intranet DIY> ISBN
7-5606-1163-X
<Flash MX Tutorial for Training> ISBN
7-900107-51-7
<Introduction to Conversancy Referring Flash MX> ISBN
7-03-012281-X TP391.41
<Macromedia Studio MX Five In One> ISBN
7-302-07057-1
<Delphi 7 Cross Platform Component Using and Writing> ISBN
7-113-05527-3/TP.1046
<Delphi 7 Graphics and Multimedia Advanced Component Using and Writing> ISBN
7-113-05491-9/TP.1034
<Top Sites - Business Economy Science Education> ISBN
7-113-05530-31
<Top Sites - Life Culture Sports entertainment> ISBN
7-113-05530-32
mailto:webmaster (AT) huzhenghui (DOT) 51.net
http://huzhenghui.51.net
----------------------------------------------------------------------------
----
"John Smith" <JSmith (AT) Hotmail (DOT) com> Ð´ÈëÏûÏ¢
news:41384e51 (AT) newsgroups (DOT) borland.com...