NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/graphics/11955

Internet Message Format | 1992-11-17 | 2.2 KB

Path: sparky!uunet!wupost!gumby!yale!yale.edu!spool.mu.edu!sgiblab!munnari.oz.au!uniwa!watson
From: [e-mail] (David Watson)
Newsgroups: comp.graphics
Subject: Re: Point inside a triangle
Date: 17 Nov 1992 02:05:00 GMT
Organization: The University of Western Australia
Lines: 34
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
NNTP-Posting-Host: madvax.maths.uwa.oz.au

[e-mail] (David Watson) writes:

>A fail-proof method is to compute the barycentric coordinates.  For a
>triangle {(x1,y1), (x2,y2), (x3,y3)} and some point (x0,y0), calculate

>b0 = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
>b1 = ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) / b0
>b2 = ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) / b0
>b3 = ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) / b0

>Then if b1, b2, and b3 are all > 0, (x0,y0) is strictly inside the
>triangle; if bi = 0 and the other two coordinates are positive, (x0,y0)
>lies on the edge opposite (xi,yi); if bi and bj = 0, (x0,y0) lies on
>(xk,yk); if bi < 0, (x0,y0) lies outside the edge opposite (xi,yi);
>if all three coordinates are negative, something else is wrong.  This
>method does not depend on the cyclic order of the vertices.

and if b0 == 0 => (x1 == x2 && x1 == x3 && y1 == y2 && y1 == y3)

that is, if b0 = 0 then you have an empty triangle because all
three vertices are coincident.  That is because
fabs(b0) / 2 is the area of the triangle and b1, b2, and b3,
before division by b0, are similarly related to the areas of the
subtriangles defined by (x0,y0) and each pair of the other three
points.  Notice that b1 + b2 + b3 = 1 always so if bi is > 0 the
others will compensate, and not all three can be negative.
If b1 = b2 = b3 then (x0,y0) is at the centroid (center of gravity)
of the triangle, x0 = (x1 + x2 + x3) /3, and y0 = (y1 + y2 + y3) /3.

--
Dave Watson                          Internet: [e-mail]
Department of Mathematics
The University of Western Australia               Tel: [phone]
Nedlands, WA 6009  Australia.                     FAX: [phone]