search

xjiang4 / ellipsoids

Automatically exported from code.google.com/p/ellipsoids
Other
0 stars 1 forks source link

isinside for ellipsoid and polytope relies on "polytope.extreme" which is too slow #93

Closed GoogleCodeExporter closed 8 years ago

GoogleCodeExporter commented 8 years ago 
nDims = 20;
ell20D = ellipsoid(eye(nDims ));
poly20D = 
polytope(struct('H',[eye(nDims);-eye(nDims)],'K',(1/sqrt(nDims))*ones(nDims*2,1)
);
isInside = isinside(ell20D ,poly20D);

Original issue reported on code.google.com by heartofm...@gmail.com on 8 Apr 2013 at 2:25

GoogleCodeExporter commented 8 years ago

Original comment by heartofm...@gmail.com on 12 Apr 2013 at 10:11

GoogleCodeExporter commented 8 years ago 
Please study the code in 

D:\SVN_Local\EllToolBoxTrunk\mpt\extras\geometry\hull.m (lines 472 - 532) - it 
does basically what you need to do. 

tic;p=hull([eye(10);-eye(10)],struct('extreme_solver',4,'noReduce',1));toc

Once you have the polytope you can call 

getInnerEllipsoid(Pset,yourEllipsoid,Options)

to check weather it belongs to the polytope.

% DESCRIPTION
% ---------------------------------------------------------------------------
% This function computes he largest ellipsoid inscribed in a polytope. 
% It is also possible to pass an ellipsoid (x-x0) E (x - x0) <= rho and 
% to compute the maximum rho such that the scaled ellipsoid is still contained
% in the polytope.
%
% ----------------------

The problem is that hull works too slow comparing to your code (for 20 
dimensional case it never finishes while according to your reports your code 
finishes in 17 minutes). Thus 

1) Make sure that your implementation handles all the cases represented in hull 
function
2) Prepare a patch for hull function that speed things up and send this patch 
to MPT developers.

Original comment by heartofm...@gmail.com on 14 Apr 2013 at 12:52

GoogleCodeExporter commented 8 years ago 
Guys from MPT told me that are about to roll out a new version of the toolbox: 
MPT 3.0, located at 
http://control.ee.ethz.ch/~mpt/redmine/projects/mpt3/wiki/Installation

Please check if this version works faster (extreme and hull methods).

Original comment by heartofm...@gmail.com on 15 Apr 2013 at 9:18

GoogleCodeExporter commented 8 years ago

Original comment by justente...@gmail.com on 12 May 2013 at 10:14

GoogleCodeExporter commented 8 years ago

Original comment by justente...@gmail.com on 15 May 2013 at 10:09

GoogleCodeExporter commented 8 years ago 
1) Given that E1.contains(E2) checks if E1 contains E2 I think it would be more 
logical to rename
 isContainedinIntersection into doesIntersectionContain? I remember asking you to call the method as
 isContainedinIntersection but now it is obvious that the name was chosen incorrectly.
Also, can you please rename contains into doesContain to make things 100% 
consistent?

2) isInside expects a polytope object as second input while "contains" does not 
which is not very consistent.

We could call doesIntersectionContain from contains when the second input is 
polytope. However this is not a good solution as
 doesIntersectionContain calls doesContain and doesContain calls doesIntersectionContain. 
This kind of cross-dependency is a very bad style in OOP which can indicates a 
bad class design..
We need to move the common logic into one or more private methods which would 
be used by
 doesContain and doesIntersectionContain. Neither the new private methods nor
doesIntersectionContain and doesContain should have cross-dependencies

3) Do we have tets for intersection_ia and intersection_ea when ellipsoid is 
intersected with a hyperplane.

4) What is the difference betwee hpintersection and intersection_ia/ea? 
hpintersection's help header doesn't say anything about what kind of estimate 
is used

4) elltool.core.test.mlunit.MPTIntegrationTestCase('testIntersectionIA')  
failed again
5) The teses you wrote (though I'm not sure that you are an author of 
'elltool.reach.test.mlunit.
ContinuousReachFirstTestCase('testIntersect')') take significant time to run 
(see below).

    '167.24753752139'
'elltool.core.test.mlunit.EllSecTCMultiDim('testIsContainedInIntersection')'
    '161.375587635779'
'elltool.reach.test.mlunit.ContinuousReachTestCase('testCut')'
    '135.077004667557'
'elltool.reach.test.mlunit.ContinuousReachFirstTestCase('testIntersect')'
    '133.204762011854'    'gras.ode.test.mlunit.SuiteBasic('testPosSame')'
    '131.342801883379'
'gras.ellapx.uncertcalc.test.regr.mlunit.SuiteRegression[advanced]('testRegressi
on')'
    '126.079382811206'
'elltool.core.test.mlunit.MPTIntegrationTestCase('testIsContainedInIntersection'
)'
    '105.853073165945'
'gras.ellapx.uncertcalc.test.regr.mlunit.SuiteSupportFunction[demo3firstTest]('t
estSupportCompare')'
    '101.877866621961'
'gras.ellapx.uncertcalc.test.comp.mlunit.SuiteCompare[basic3]('testCompare')'

Can we do something about it?

Original comment by heartofm...@gmail.com on 16 May 2013 at 8:55

GoogleCodeExporter commented 8 years ago 
About 5-th par. How did you decided which tests i've written? I think, that of 
listed test only 
'elltool.core.test.mlunit.MPTIntegrationTestCase('testIsContainedInIntersection'
)' is mine.

Original comment by justente...@gmail.com on 16 May 2013 at 9:42

GoogleCodeExporter commented 8 years ago 
1),2) - i'll fix it.
3) no, we don't have tests for intersection_ia and intersection_ea for anythig, 
except polytope. I prefer someone else, but not me do it.
4)Am i right, that it failed on this test
sh7Mat = [1.1954 0.3180 1.3183; 0.3180 0.2167 0.5039;...
                1.3183 0.5039 1.6320];
ell7 = ellipsoid(sh7Mat);
poly7 = polytope([1 1 1], 0.2);
ellPolyIA7 = intersection_ia(ell7,poly7);
mlunit.assert(isContainedInIntersection(ell7,ellPolyIA7) &&...
                isInside(ellPolyIA7,poly7));
I tried to reproduce error here in loop with hundred iterations without 
success. But i'll try again.

Original comment by justente...@gmail.com on 16 May 2013 at 10:06

GoogleCodeExporter commented 8 years ago 
4) What is the difference betwee hpintersection and intersection_ia/ea? 
hpintersection's help header doesn't say anything about what kind of estimate 
is used...

5) 
'elltool.core.test.mlunit.MPTIntegrationTestCase('testIsContainedInIntersection'
)'  - is there any way to speed it up?

Original comment by heartofm...@gmail.com on 16 May 2013 at 10:27

GoogleCodeExporter commented 8 years ago 
3) no problem, I'll ask someone else.

Original comment by heartofm...@gmail.com on 16 May 2013 at 10:33

GoogleCodeExporter commented 8 years ago 
4)The difference between hpintersection and interesection_ia/ea is that 
hpintersection calculates exact intersection ellipsoid with HYPERPLANE, while 
intersection_ia/ea computes internal or external approximation of intersection 
ellipsoid with HALFSPACE that is bounded with the hypeplane.
5)I don't see any ways for speeding up this test significantly. We can remove 
test for high dimensions, it will free about 30 seconds. Furthemore, i think 
now i'll even slow down it, because both polar and extreme methods will be 
tested, and i'll also add test for flag 'auto'.

Original comment by justente...@gmail.com on 16 May 2013 at 10:49

GoogleCodeExporter commented 8 years ago 
5) Ok, once you implement this test - please let me know how much slowly the 
test runs.
6) One more thing - you fixed a problem in intersection_ia related to absTol 
being added as many times as many ellipsoids we have. Can you please describe 
this problem in more details?

Original comment by heartofm...@gmail.com on 16 May 2013 at 10:56

GoogleCodeExporter commented 8 years ago 
Problem was with intersection_ea with polytopes. In intersection_ea we 
transfrorm each facet with number i of polytope into hyperplane hyp(i), and 
intersect ellipsoid consequently with all halfspaces, bounded by this 
hyperplanes using ellEA = intersection_ea(ellEA,hyp(i)). Before i fixed it, in 
intersection_ea, when we intersect ellipsoid with hyperplane, we counted the 
right result ellipsoid, with center qCenterVec and matrix shQMat, and then 
multiplied shQMat by (1+absTol), so we got difference with expected result 
about absTol*(number of constraints in polytope).

I don't sure why it was done that way. I assume, that some test about 
intersection of resulting ellipsoid and some hyperplane failed, without this 
multiplication, because after fixing it i've got fails in hpintersection tests. 
Hpintersection was wrong too, it checked if distance between ellipsoid and 
hyperplane > 0, while better check if it > absTol. After fixing it, need in 
multiplication by  (1+absTol) disappeared, or i just think so, but all tests 
passed.

Original comment by justente...@gmail.com on 16 May 2013 at 12:24

GoogleCodeExporter commented 8 years ago 
elltool.core.test.mlunit.MPTIntegrationTestCase('testIsContainedInIntersection')
 now runs about 130 seconds on my computer.
Runned part of code, that failed in trunk with 300 iterations, still not any 
fails.
Fixed items 1) and 2) of the list.

Original comment by justente...@gmail.com on 16 May 2013 at 7:16

GoogleCodeExporter commented 8 years ago 
1) resArr output in doesContain is named incorrectly, please rename it into 
isPosArr.
The same problem presents in the tests, in EllipsoidIntUnionTC.m for instance, 
where 
the outputs of doesContain are named incorrectly
2) Please use true/false instead of 1/0 in assertions for logical results:

mlunit.assert_equals(0, any(testResVec(:))); should be replaced with

mlunit.assert_equals(false, any(testResVec(:)));
3) doesEllContainPoly should be renamed into doesContainPoly as "Ell" is not 
necessary
given that doesContainPoly is a method of ellipsoid class.

4) Please document inputs and outputs of doesContainPoly.
5) Please use parseparext in doesContainPoly for parsing the input arguments:

[~,~,compMode,isCompModeSpec] = 
modgen.common.parseparams(varargin,'computeMode');

6) Please rename lDFDoesContain into doesContainLowDim and hDFDoesContain into 
DoesContainHighDim
7) doesIntersectionContain for scalar inputs does the same as doesContain, 
right? 
Can we just call doesIntersectionContain from doesContain without having to 
worry about a performance degradation?

Original comment by heartofm...@gmail.com on 19 May 2013 at 1:14

GoogleCodeExporter commented 8 years ago 
7)I'll look more carefully, but, i think, that we call doesContain in some 
cases for ellipsoids from doesIntersectionContain, so, it is not very good 
idea, to call doesIntersectionContain from doesContain. We can make it work, 
but, in my opinion, it looks bad.

Original comment by justente...@gmail.com on 19 May 2013 at 8:29

GoogleCodeExporter commented 8 years ago

Original comment by justente...@gmail.com on 23 May 2013 at 2:17

GoogleCodeExporter commented 8 years ago 
Please reintegrate. Do not forget to run the tests on the reintegrated working 
copy.

Original comment by heartofm...@gmail.com on 23 May 2013 at 3:29

GoogleCodeExporter commented 8 years ago

Original comment by justente...@gmail.com on 24 May 2013 at 12:06

GoogleCodeExporter commented 8 years ago 
You haven't renamed the function calls in /doc/mcodesnippets. Please do so ASAP.

Original comment by heartofm...@gmail.com on 25 May 2013 at 10:48

GoogleCodeExporter commented 8 years ago 
i don't see any calls of contains and isContainedInIntersection in that folder

Original comment by justente...@gmail.com on 25 May 2013 at 3:57

GoogleCodeExporter commented 8 years ago 
done

Original comment by justente...@gmail.com on 25 May 2013 at 4:42

GoogleCodeExporter commented 8 years ago

Original comment by heartofm...@gmail.com on 25 May 2013 at 7:52

GoogleCodeExporter commented 8 years ago 
May i reintegrate without running tests, because functionality was nor changed?

Original comment by justente...@gmail.com on 25 May 2013 at 8:03

GoogleCodeExporter commented 8 years ago 
Ok, but please do one more thing - please move testIntersect test from 
MPTIntegrationTestCase into elltool.reach.test.mlunit package. This way we will 
have all Reach tests separated from ellipsoid/hyperplane tests. After that you 
can reintegrate.

Original comment by heartofm...@gmail.com on 25 May 2013 at 8:13

GoogleCodeExporter commented 8 years ago

Original comment by justente...@gmail.com on 27 May 2013 at 9:18

GoogleCodeExporter commented 8 years ago

Original comment by heartofm...@gmail.com on 28 May 2013 at 9:02