Re: How to get pixels from a triangle?

"Kev L" <kevinl99_99@xxxxxxxxxxx> wrote in message <g38g4q$8pb
$1@xxxxxxxxxxxxxxxxxx>...
appreciate for the help, I put in the code and it is able to .......

Those three inequalities each represent the condition that a point (x,y) lies
to the same side of the infinite line along one of the triangle's three sides as
the triangle does. If they all hold true, then (x,y) must lie inside the triangle.

For example, in analytic geometry we learned that for the two points P1 =
(x1,y1) and P2 = (x2,y2), the equation of the line running through them is:

(y-y1)/(x-x1) = (y2-y1)/(x2-x1),

which is equivalent to

(y1-y2)*x-(x1-x2)*y+x1*y2-y1*x2 = 0.

If you convert this to the inequality

(y1-y2)*x-(x1-x2)*y+x1*y2-y1*x2 >= 0,

these are the points (x,y) that lie on or to the left of the line P1P2 as one
moves from P1 to P2. It would be the opposite inequality for points off to the
right. If you substitute in x = x3 and y = y3, you get:

(y1-y2)*x3-(x1-x2)*y3+x1*y2-y1*x2 =
x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-y3*x1

and the sign of this therefore tells us which side of the line the triangle lies
on. For an arbitrary point (x,y) to be on the same side as the triangle, we
therefore want

(y1-y2)*x-(x1-x2)*y+x1*y2-y1*x2 and

x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-y3*x1

to have the same sign. That is accomplished by the single inequality

c12*x-d12*y+e12 >= 0

where

s = sign(x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-y3*x1)
c12 = s*(y1-y2)
d12 = s*(x1-x2)
e12 = s*(x1*y2-y1*x2)

A similar argument applies to the other two inequalities.

It should be noted here that these arguments break down if the area in the
triangle is zero - that is, if (x1,y1), (x2,y2), and (x3,y3) all lie along the same
line. If you have any degenerate triangles of this kind, they must be handled
in a rather different manner from the above. I have made the assumption
that this doesn't occur for you. Was that justified?

Roger Stafford

.

Relevant Pages

  • Re: Inequality help
    ... sides to get the inequality. ... lies within the circle of radius |a-b|/sqrtcentered at, ... closed set, set containing it's accumulation points is closed, etc. ...
    (sci.math)
  • Re: Inequality help
    ... TTroy wrote: ... But I can't seem to manipulate that inequality to extra x> y. ... lies within the circle of radius |a-b|/sqrtcentered at, ...
    (sci.math)
  • Re: help me with an inequality of geometry
    ... the components of which is zero, ... This inequality is alway wrong, if x lies in T but not on H. ...
    (sci.math)
  • Re: programming with triangle.
    ... triangle. ... I can fix QPR by computer) ... we can't guarantee that z lies on the boundary of given triangle. ... A picky anomaly is that if A, B and C lie in a straight line then this ...
    (sci.math)
  • Re: Closest point on 2D triangle from 2D point
    ... > My scheme works well. ... point lies outside two triangle edges forming an obtuse-angled ... of either edge and not the Voronoi region of the vertex. ...
    (comp.graphics.algorithms)
Loading