Thread Subject: How to get pixels from a triangle?

Hello,
I have an image that has multiple triangular regions, and I
know the coordinates of vertices to those triangles with the
help of delaunay function.

How can I extract all the pixels located inside those
triangle regions so that I can save each of those triangle
region into separated matrix format. Later, I can add all
those triangles back to compose the original image. Like a
jigsaw puzzle.

Thanks
Kev

"Kev L" <kevinl99_99@hotmail.com> wrote in message <g34mck$f1t
$1@fred.mathworks.com>...
> I have an image that has multiple triangular regions, and I ......

  If (x1,y1), (x2,y2), and (x3,y3) are the triangle's vertices, then an arbitrary point
(x,y) will lie within the triangle if and only if the three quantities

 det([1 x1 y1;1 x2 y2;1 x y]),
 det([1 x y;1 x2 y2;1 x3 y3]), and
 det([1 x1 y1;1 x y;1 x3 y3]),

all have the same sign as

 det([1 x1 y1;1 x2 y2;1 x3 y3]).

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message <g34qp8$g8v$1@fred.mathworks.com>...
> If (x1,y1), (x2,y2), and (x3,y3) are the triangle's vertices, then .......

  The answer I gave you, Kev, does not lend itself to an efficient vectorization.
You would probably prefer the following for processing the numerous points
of an image. Again let (x1,y1), (x2,y2), and (x3,y3) be the triangle's vertices
and suppose that x and y are vectors containing all the points' coordinates
you wish to test for lying inside the triangle. Then do this:

 % Set up nine coefficients
 s = sign(x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-y3*x1);
 c12 = s*(y1-y2); c23 = s*(y2-y3); c31 = s*(y3-y1);
 d12 = s*(x1-x2); d23 = s*(x2-x3); d31 = s*(x3-x1);
 e12 = s*(x1*y2-y1*x2);
 e23 = s*(x2*y3-y2*x3);
 e31 = s*(x3*y1-y3*x1);

 % Then check (x,y) vectors for being inside triangle
 t = (c12*x-d12*y+e12>=0) & ...
     (c23*x-d23*y+e23>=0) & ...
     (c31*x-d31*y+e31>=0);
 X = x(t); Y = y(t);

Then X and Y give all the points in x and y which lie inside the triangle.

Roger Stafford

"Roger Stafford"
<ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message <g34qp8$g8v$1@fred.mathworks.com>...
> "Kev L" <kevinl99_99@hotmail.com> wrote in message
<g34mck$f1t
> $1@fred.mathworks.com>...
> > I have an image that has multiple triangular regions,
and I ......
>
> If (x1,y1), (x2,y2), and (x3,y3) are the triangle's
vertices, then an arbitrary point
> (x,y) will lie within the triangle if and only if the
three quantities
>
> det([1 x1 y1;1 x2 y2;1 x y]),
> det([1 x y;1 x2 y2;1 x3 y3]), and
> det([1 x1 y1;1 x y;1 x3 y3]),
>
> all have the same sign as
>
> det([1 x1 y1;1 x2 y2;1 x3 y3]).
>
> Roger Stafford
>

Good answer, didnt know that.

It wouldnt be the fastest way though, since you would need
to do that for every point.

I think it would be more efficient to find the line
equations of the borders and then use various whiles to
extract all the points inbetween, kind of as you were
integrating.

Greetings

Hi Roger,
appreciate for the help, I put in the code and it is able to
find the points within the triangle. Sorry to bother you
again as I am not quite clear on why does this code works,
which theorem is based here? Can you explain it for me to
understand?

Thanks again,

Kev
>
> % Set up nine coefficients
> s = sign(x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-y3*x1);
> c12 = s*(y1-y2); c23 = s*(y2-y3); c31 = s*(y3-y1);
> d12 = s*(x1-x2); d23 = s*(x2-x3); d31 = s*(x3-x1);
> e12 = s*(x1*y2-y1*x2);
> e23 = s*(x2*y3-y2*x3);
> e31 = s*(x3*y1-y3*x1);
>
> % Then check (x,y) vectors for being inside triangle
> t = (c12*x-d12*y+e12>=0) & ...
> (c23*x-d23*y+e23>=0) & ...
> (c31*x-d31*y+e31>=0);
> X = x(t); Y = y(t);
>
> Then X and Y give all the points in x and y which lie
inside the triangle.
>
> Roger Stafford

"Kev L" <kevinl99_99@hotmail.com> wrote in message
<g38g4q$8pb$1@fred.mathworks.com>...

If you have the image processing toolbox you could ...

1) connect the pixels with a line
2) fill with imfill
3) use bwlabel to find the regions

Probably less efficient, but may be sufficient.

~Adam

"Kev L" <kevinl99_99@hotmail.com> wrote in message <g38g4q$8pb
$1@fred.mathworks.com>...
> 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

Hi Roger,
it is a very detailed explanation, and I can see the
function expressions are from the method of determining a
point lies on the interior of a polygon or not. Thanks again
for your help.

Best, Kev

Hi Adam,
thanks for your suggestion. This method wwill also works by
locating the section of interested with bwlabel, then need
to use find function to locate the coordinate of those
pixels and achieve the objective.

Best,
Kev

"Adam " <not.real@email.com> wrote in message
<g38k4s$p0j$1@fred.mathworks.com>...
> "Kev L" <kevinl99_99@hotmail.com> wrote in message
> <g38g4q$8pb$1@fred.mathworks.com>...
>
> If you have the image processing toolbox you could ...
>
> 1) connect the pixels with a line
> 2) fill with imfill
> 3) use bwlabel to find the regions
>
> Probably less efficient, but may be sufficient.
>
> ~Adam

Hello Mr. Kev,

I came across this mail chain of yours regarding triangulation.

I am very new to Matlab and using it for the first time.

I have a x,y plane containting points[Points falling on
edges of a given image]. As is see some examples like
/*******************/
rand('state',0);
x = rand(1,10);
y = rand(1,10);
TRI = delaunay(x,y);
subplot(1,2,1),...
triplot(TRI,x,y)
axis([0 1 0 1]);
hold on;
plot(x,y,'or');
hold off
/******************/ output of "delaunay()" will be TRI,
which is used to plot the graph.

But I actually wanted to know the vertices(x1,y1, x2,y2 and
x3,y3 of the resultant triangles once "delaunay()" is done.

Can you help me in this regard.

Thanks in advance
Joshi



"Kev L" <kevinl99_99@hotmail.com> wrote in message
<g34mck$f1t$1@fred.mathworks.com>...
> Hello,
> I have an image that has multiple triangular regions, and I
> know the coordinates of vertices to those triangles with the
> help of delaunay function.
>
> How can I extract all the pixels located inside those
> triangle regions so that I can save each of those triangle
> region into separated matrix format. Later, I can add all
> those triangles back to compose the original image. Like a
> jigsaw puzzle.
>
> Thanks
> Kev

"ChandraShekhar Joshi" <joshi_c_m@rediffmail.com> wrote in
message <g54l81$iag$1@fred.mathworks.com>...
> Hello Mr. Kev,
>
> I came across this mail chain of yours regarding
triangulation.
>
> I am very new to Matlab and using it for the first time.
>
> I have a x,y plane containting points[Points falling on
> edges of a given image]. As is see some examples like
> /*******************/
> rand('state',0);
> x = rand(1,10);
> y = rand(1,10);
> TRI = delaunay(x,y);
> subplot(1,2,1),...
> triplot(TRI,x,y)
> axis([0 1 0 1]);
> hold on;
> plot(x,y,'or');
> hold off
> /******************/ output of "delaunay()" will be TRI,
> which is used to plot the graph.
>
> But I actually wanted to know the vertices(x1,y1, x2,y2
and
> x3,y3 of the resultant triangles once "delaunay()" is
done.
>
> Can you help me in this regard.
>
> Thanks in advance
> Joshi
>
>
>
> "Kev L" <kevinl99_99@hotmail.com> wrote in message
> <g34mck$f1t$1@fred.mathworks.com>...
> > Hello,
> > I have an image that has multiple triangular regions,
and I
> > know the coordinates of vertices to those triangles
with the
> > help of delaunay function.
> >
> > How can I extract all the pixels located inside those
> > triangle regions so that I can save each of those
triangle
> > region into separated matrix format. Later, I can add
all
> > those triangles back to compose the original image.
Like a
> > jigsaw puzzle.
> >
> > Thanks
> > Kev
>

Hi,

Vertices are stored in array TRI.
Do you need to display it ????
if so Just type "disp(TRI)" or simply "TRI"(with no
semicolon) at the end of code, you will get the result.

with regards,
Nitin

"ChandraShekhar Joshi" <joshi_c_m@rediffmail.com> wrote in message
news:g54l81$iag$1@fred.mathworks.com...
> Hello Mr. Kev,
>
> I came across this mail chain of yours regarding triangulation.
>
> I am very new to Matlab and using it for the first time.
>
> I have a x,y plane containting points[Points falling on
> edges of a given image]. As is see some examples like
> /*******************/
> rand('state',0);
> x = rand(1,10);
> y = rand(1,10);
> TRI = delaunay(x,y);
> subplot(1,2,1),...
> triplot(TRI,x,y)
> axis([0 1 0 1]);
> hold on;
> plot(x,y,'or');
> hold off
> /******************/ output of "delaunay()" will be TRI,
> which is used to plot the graph.
>
> But I actually wanted to know the vertices(x1,y1, x2,y2 and
> x3,y3 of the resultant triangles once "delaunay()" is done.

DELAUNAY returns an N-by-3 matrix of indices into the x and y vectors. Each
row is one triangle.

http://www.mathworks.com/access/helpdesk/help/techdoc/ref/delaunay.html

What would happen if you asked for x(TRI(1, :)) and y(TRI(1, :))? Do those
look familiar, looking at the graph you created with TRIPLOT?

--
Steve Lord
slord@mathworks.com

Hi!

Just a proposition to improve the speed of Roger's method,
depending on the size of your triangles, with respect to the
global size of the image:

Considering that the triangle is small, and has points
coordinates (x1,y1) (x2,y2) and (x3,y3), you could narrow
your research to the points (x,y) so that:
(x > min(x1, x2, x3)) && (x < max(x1, x2, x3))

same for y. So you'll search only among the points contained
in the rectangle containing the triangle.

Regards,

Gavrilo



"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
wrote in message <g353ks$n40$1@fred.mathworks.com>...
> "Roger Stafford"
<ellieandrogerxyzzy@mindspring.com.invalid> wrote in
> message <g34qp8$g8v$1@fred.mathworks.com>...
> > If (x1,y1), (x2,y2), and (x3,y3) are the triangle's
vertices, then .......
>
> The answer I gave you, Kev, does not lend itself to an
efficient vectorization.
> You would probably prefer the following for processing the
numerous points
> of an image. Again let (x1,y1), (x2,y2), and (x3,y3) be
the triangle's vertices
> and suppose that x and y are vectors containing all the
points' coordinates
> you wish to test for lying inside the triangle. Then do this:
>
> % Set up nine coefficients
> s = sign(x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-y3*x1);
> c12 = s*(y1-y2); c23 = s*(y2-y3); c31 = s*(y3-y1);
> d12 = s*(x1-x2); d23 = s*(x2-x3); d31 = s*(x3-x1);
> e12 = s*(x1*y2-y1*x2);
> e23 = s*(x2*y3-y2*x3);
> e31 = s*(x3*y1-y3*x1);
>
> % Then check (x,y) vectors for being inside triangle
> t = (c12*x-d12*y+e12>=0) & ...
> (c23*x-d23*y+e23>=0) & ...
> (c31*x-d31*y+e31>=0);
> X = x(t); Y = y(t);
>
> Then X and Y give all the points in x and y which lie
inside the triangle.
>
> Roger Stafford
>
>