Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Question about the code vectorization

Subject: Question about the code vectorization

From: Liana

Date: 31 Oct, 2011 05:00:27

Message: 1 of 11

Hi,

I'm thinking how to vectorize the following code:

s = struct('tess', {}); % structure that contains Delaunay traingulations of different polyhedrons

<...>

% This function is used to determine if a point is located inside any tetrahedron.
% The MATLAB built-in function 'pointLocation' is used.
function out = ToBeVectorized(s,point)
nrtess = length(s(:));
for i = 1:nrtess
    tetids = pointLocation(s(i).tess,point(1,1),point(1,2),point(1,3));
    if ~isnan(tetids)
        break
    end
end
out = isnan(tetids);

Is there any way to use MATLAB function 'pointLocation' in the vectorized code?

Subject: Question about the code vectorization

From: Matt J

Date: 31 Oct, 2011 13:25:14

Message: 2 of 11

"Liana" wrote in message <j8la1b$3d6$1@newscl01ah.mathworks.com>...
>
> % This function is used to determine if a point is located inside any tetrahedron.
> % The MATLAB built-in function 'pointLocation' is used.
> function out = ToBeVectorized(s,point)
> nrtess = length(s(:));
> for i = 1:nrtess
> tetids = pointLocation(s(i).tess,point(1,1),point(1,2),point(1,3));
> if ~isnan(tetids)
> break
> end
> end
> out = isnan(tetids);
>
> Is there any way to use MATLAB function 'pointLocation' in the vectorized code?
==============

pointLocation is already vectorized with respect to 'point'. You should see if there' a way to pass all the points you want to query at once.

I don't see why it be gainful to vectorize with respect to 's' unless s is a really really long struct, and if it is, you're probably making a mistake by working with structs that large (they are highly inefficient memory-wise).

Subject: Question about the code vectorization

From: Liana

Date: 31 Oct, 2011 18:55:23

Message: 3 of 11

The problem is that each s(i) is defined as follows:
s(1).tess = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3));
s(2).tess = DelaunayTri(pts2(:,1),pts2(:,2),pts2(:,3));

I vectorized the code with respect to points, it's very easy. But I don't know how to do this with respect to 's'. I assume it is impossible.

"Matt J" wrote in message <j8m7jq$rrt$1@newscl01ah.mathworks.com>...
> "Liana" wrote in message <j8la1b$3d6$1@newscl01ah.mathworks.com>...
> >
> > % This function is used to determine if a point is located inside any tetrahedron.
> > % The MATLAB built-in function 'pointLocation' is used.
> > function out = ToBeVectorized(s,point)
> > nrtess = length(s(:));
> > for i = 1:nrtess
> > tetids = pointLocation(s(i).tess,point(1,1),point(1,2),point(1,3));
> > if ~isnan(tetids)
> > break
> > end
> > end
> > out = isnan(tetids);
> >
> > Is there any way to use MATLAB function 'pointLocation' in the vectorized code?
> ==============
>
> pointLocation is already vectorized with respect to 'point'. You should see if there' a way to pass all the points you want to query at once.
>
> I don't see why it be gainful to vectorize with respect to 's' unless s is a really really long struct, and if it is, you're probably making a mistake by working with structs that large (they are highly inefficient memory-wise).

Subject: Question about the code vectorization

From: Matt J

Date: 31 Oct, 2011 19:25:29

Message: 4 of 11

"Liana" wrote in message <j8mqur$9vj$1@newscl01ah.mathworks.com>...
> The problem is that each s(i) is defined as follows:
> s(1).tess = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3));
> s(2).tess = DelaunayTri(pts2(:,1),pts2(:,2),pts2(:,3));
================

Is there a reason why you bury the DelaunayTri objects inside a struct? Why not just do

DT(1) = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3));
DT(2) = DelaunayTri(pts2(:,1),pts2(:,2),pts2(:,3));
etc...


> I vectorized the code with respect to points, it's very easy. But I don't know how to do this with respect to 's'. I assume it is impossible.
=============

Even if it were possible, why would you want to? How big is nrtess?

Subject: Question about the code vectorization

From: Liana

Date: 31 Oct, 2011 19:46:26

Message: 5 of 11

nrtess might be up to 1000. I just assumed that the vectorization could improve the time-efficiency of the code. The thing is that I used Matlab Profiler, which indicated that this particular piece of the code takes relatively long time.

"Matt J" wrote in message <j8msn9$frn$1@newscl01ah.mathworks.com>...
> "Liana" wrote in message <j8mqur$9vj$1@newscl01ah.mathworks.com>...
> > The problem is that each s(i) is defined as follows:
> > s(1).tess = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3));
> > s(2).tess = DelaunayTri(pts2(:,1),pts2(:,2),pts2(:,3));
> ================
>
> Is there a reason why you bury the DelaunayTri objects inside a struct? Why not just do
>
> DT(1) = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3));
> DT(2) = DelaunayTri(pts2(:,1),pts2(:,2),pts2(:,3));
> etc...
>
>
> > I vectorized the code with respect to points, it's very easy. But I don't know how to do this with respect to 's'. I assume it is impossible.
> =============
>
> Even if it were possible, why would you want to? How big is nrtess?

Subject: Question about the code vectorization

From: Liana

Date: 31 Oct, 2011 19:51:26

Message: 6 of 11

I checked your solution regarding DT(i). Maybe, I did something incorrectly, but I received an error message:
>> DT(1) = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3));
>> DT(2) = DelaunayTri(pts2(:,1),pts2(:,2),pts2(:,3));
Error using DelaunayTri/subsasgn
Invalid arguments in indexing operation.

>> DT(1)
Error using DelaunayTri/subsref
Invalid indexing into the triangulation, use the size method to check the dimensions.


"Matt J" wrote in message <j8msn9$frn$1@newscl01ah.mathworks.com>...
> "Liana" wrote in message <j8mqur$9vj$1@newscl01ah.mathworks.com>...
> > The problem is that each s(i) is defined as follows:
> > s(1).tess = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3));
> > s(2).tess = DelaunayTri(pts2(:,1),pts2(:,2),pts2(:,3));
> ================
>
> Is there a reason why you bury the DelaunayTri objects inside a struct? Why not just do
>
> DT(1) = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3));
> DT(2) = DelaunayTri(pts2(:,1),pts2(:,2),pts2(:,3));
> etc...
>
>
> > I vectorized the code with respect to points, it's very easy. But I don't know how to do this with respect to 's'. I assume it is impossible.
> =============
>
> Even if it were possible, why would you want to? How big is nrtess?

Subject: Question about the code vectorization

From: Matt J

Date: 31 Oct, 2011 20:35:26

Message: 7 of 11

"Liana" wrote in message <j8mu7u$lep$1@newscl01ah.mathworks.com>...
> I checked your solution regarding DT(i). Maybe, I did something incorrectly, but I received an error message:
> >> DT(1) = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3));
> >> DT(2) = DelaunayTri(pts2(:,1),pts2(:,2),pts2(:,3));
> Error using DelaunayTri/subsasgn
> Invalid arguments in indexing operation.
>
> >> DT(1)
> Error using DelaunayTri/subsref
> Invalid indexing into the triangulation, use the size method to check the dimensions.
======================


OK. I guess DelaunayTri isn't implemented as a new-style class...

Subject: Question about the code vectorization

From: Steven_Lord

Date: 31 Oct, 2011 21:03:55

Message: 8 of 11



"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message
news:j8n0qd$11i$1@newscl01ah.mathworks.com...
> "Liana" wrote in message <j8mu7u$lep$1@newscl01ah.mathworks.com>...
>> I checked your solution regarding DT(i). Maybe, I did something
>> incorrectly, but I received an error message:
>> >> DT(1) = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3)); DT(2) =
>> >> DelaunayTri(pts2(:,1),pts2(:,2),pts2(:,3));
>> Error using DelaunayTri/subsasgn
>> Invalid arguments in indexing operation.
>>
>> >> DT(1)
>> Error using DelaunayTri/subsref
>> Invalid indexing into the triangulation, use the size method to check the
>> dimensions.
> ======================
>
>
> OK. I guess DelaunayTri isn't implemented as a new-style class...

DelaunayTri objects aren't intended to be stored as elements of an array;
they're more like function handles, whose ()-indexing is intended to be
"evaluation" rather than "indexing into the object". In the case of the
DelaunayTri object, "evaluation" means "give me the appropriate piece of the
triangulation."


rng default
x = rand(20,1);
y = rand(20,1);
dt = DelaunayTri(x,y)
firstTriangle = dt(1, :); % first triangle
fprintf('The first triangle consists of points %d, %d, and %d.\n',
firstTriangle)
triplot(dt);
hold on
plot(x(firstTriangle), y(firstTriangle), 'ro')


If you look at the appropriate elements of x and y and use a data cursor on
the circled points on the plot, you should see the correspondence.
DelaunayTri inherits this behavior from the TriRep object, of which it is a
subclass.

http://www.mathworks.com/help/techdoc/ref/trirepclass.html

If you want to collect a group of DelaunayTri's together into one container,
I would use a cell array, though an array of structs (where each DelaunayTri
has some additional information associated with it that is stored in other
fields in the same element of the array of structs) could also be an
appropriate choice.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Subject: Question about the code vectorization

From: Matt J

Date: 31 Oct, 2011 21:29:28

Message: 9 of 11

"Liana" wrote in message <j8mtui$kct$1@newscl01ah.mathworks.com>...
> nrtess might be up to 1000. I just assumed that the vectorization could improve the time-efficiency of the code. The thing is that I used Matlab Profiler, which indicated that this particular piece of the code takes relatively long time.
=============

Yes, but you said you've already modified your code to vectorize with respect to points. So, you should have gained considerably from that assuming you have a lot more than 1000 points to check.

If you want to accelerate the loop over s(i) and if you have the Parallel Computing Toolbox, you could try converting to a parfor loop.

As a third option, I think you're familiar with this tool

http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities

If you use this to convert each i-th tetrahedron representation to linear inequalities

A(:,:,i)*x<=b(:,:,i) %for the i-th tetrahedron

then you can do a vectorized evaluation of all these inequalities using MTIMESX, which I think you're also familar with


http://www.mathworks.com/matlabcentral/fileexchange/25977-mtimesx-fast-matrix-multiply-with-multi-dimensional-support

Subject: Question about the code vectorization

From: Liana

Date: 31 Oct, 2011 23:40:27

Message: 10 of 11

Thanks. Could you please gave some working example of using cell array for collecting a group of DelaunayTri's? I tried DT{1} = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3)); but it does not work.

"Steven_Lord" <slord@mathworks.com> wrote in message <j8n2fr$6n5$1@newscl01ah.mathworks.com>...
>
>
> "Matt J " <mattjacREMOVE@THISieee.spam> wrote in message
> news:j8n0qd$11i$1@newscl01ah.mathworks.com...
> > "Liana" wrote in message <j8mu7u$lep$1@newscl01ah.mathworks.com>...
> >> I checked your solution regarding DT(i). Maybe, I did something
> >> incorrectly, but I received an error message:
> >> >> DT(1) = DelaunayTri(pts1(:,1),pts1(:,2),pts1(:,3)); DT(2) =
> >> >> DelaunayTri(pts2(:,1),pts2(:,2),pts2(:,3));
> >> Error using DelaunayTri/subsasgn
> >> Invalid arguments in indexing operation.
> >>
> >> >> DT(1)
> >> Error using DelaunayTri/subsref
> >> Invalid indexing into the triangulation, use the size method to check the
> >> dimensions.
> > ======================
> >
> >
> > OK. I guess DelaunayTri isn't implemented as a new-style class...
>
> DelaunayTri objects aren't intended to be stored as elements of an array;
> they're more like function handles, whose ()-indexing is intended to be
> "evaluation" rather than "indexing into the object". In the case of the
> DelaunayTri object, "evaluation" means "give me the appropriate piece of the
> triangulation."
>
>
> rng default
> x = rand(20,1);
> y = rand(20,1);
> dt = DelaunayTri(x,y)
> firstTriangle = dt(1, :); % first triangle
> fprintf('The first triangle consists of points %d, %d, and %d.\n',
> firstTriangle)
> triplot(dt);
> hold on
> plot(x(firstTriangle), y(firstTriangle), 'ro')
>
>
> If you look at the appropriate elements of x and y and use a data cursor on
> the circled points on the plot, you should see the correspondence.
> DelaunayTri inherits this behavior from the TriRep object, of which it is a
> subclass.
>
> http://www.mathworks.com/help/techdoc/ref/trirepclass.html
>
> If you want to collect a group of DelaunayTri's together into one container,
> I would use a cell array, though an array of structs (where each DelaunayTri
> has some additional information associated with it that is stored in other
> fields in the same element of the array of structs) could also be an
> appropriate choice.
>
> --
> Steve Lord
> slord@mathworks.com
> To contact Technical Support use the Contact Us link on
> http://www.mathworks.com

Subject: Question about the code vectorization

From: Liana

Date: 31 Oct, 2011 23:49:10

Message: 11 of 11

Thanks, I'll try out the 'parfor loop'.

"Matt J" wrote in message <j8n3vo$bah$1@newscl01ah.mathworks.com>...
> "Liana" wrote in message <j8mtui$kct$1@newscl01ah.mathworks.com>...
> > nrtess might be up to 1000. I just assumed that the vectorization could improve the time-efficiency of the code. The thing is that I used Matlab Profiler, which indicated that this particular piece of the code takes relatively long time.
> =============
>
> Yes, but you said you've already modified your code to vectorize with respect to points. So, you should have gained considerably from that assuming you have a lot more than 1000 points to check.
>
> If you want to accelerate the loop over s(i) and if you have the Parallel Computing Toolbox, you could try converting to a parfor loop.
>
> As a third option, I think you're familiar with this tool
>
> http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities
>
> If you use this to convert each i-th tetrahedron representation to linear inequalities
>
> A(:,:,i)*x<=b(:,:,i) %for the i-th tetrahedron
>
> then you can do a vectorized evaluation of all these inequalities using MTIMESX, which I think you're also familar with
>
>
> http://www.mathworks.com/matlabcentral/fileexchange/25977-mtimesx-fast-matrix-multiply-with-multi-dimensional-support

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us