Rigid Rotation / Reorientation

[carterbox]

I want to add a method to polytope which reorients the polytope.

I believe (with no proof) that it will be computationally less expensive to reorient an existing polytope and bounding sphere than to define a new polytope and calculate the bounding sphere from scratch. I also believe (because profiling shows a lot of time spent on cheby_ball and reduce) that the cost of computing bounding boxes and half-space representations is large compared to the intersection computation. My application involves computing intersections of the same set of polytopes at varying orientations.

Is this something y'all are interested in? Should the implementation be more general and accept non-rigid transformations? Should it automatically calculate the minimum number of rotations needed to reorient the polytope given an orientation matrix (after 3D, it is not guaranteed that there is a one step rotation between given orientations)?

[slivingston]

I am interested. It is not something for which I have an immediate application, so I do not have preferences about the alternatives that you mention.

[carterbox]

I've got a prototype for the rotation and translation methods on my branch called affine (carterbox/polytope@abb143ef). However, I'm not going to make a pull request until all my other pull requests are closed.

I think that the rotate function is thoroughly described in the code (https://github.com/carterbox/polytope/commit/abb143efedab7ee263f1854d8c2f92eb2f6a7a3a#diff-568a32ef43ad350e3dddd07731579142R476). Let me know if it is unclear. Also, the second option is unimplemented because I don't need it immediately and it is non-trivial.

[slivingston]

@carterbox I will finish reviewing your other PRs within 24 hours.

[slivingston]

@carterbox I briefly read your proposed functions translate and rotate at https://github.com/carterbox/polytope/blob/abb143efedab7ee263f1854d8c2f92eb2f6a7a3a/polytope/polytope.py#L455 and https://github.com/carterbox/polytope/blob/abb143efedab7ee263f1854d8c2f92eb2f6a7a3a/polytope/polytope.py#L476, respectively. Please open a pull request when you are ready to begin review. My initial comments:

1. The docstring of rotate has lines that are too long and should be folded.
2. Have you considered creating a second form of each function that returns new polytopes, rather than modifying the given one? Actually, I recommend that the default behavior is to return new objects (and not modify the arguments of the function), which is consistent with other functions in polytope, e.g., reduce.
3. Can you add some message to the NotImplementedError exception that suggests there is a corresponding TODO item in the code? Otherwise, it might be worth opening an issue about the need to implement something there eventually.

[slivingston]

More comments:

1. Docstrings should begin with command verb forms. E.g., "Rotate the polytope. Only simple rotations are implemented at this time." More about docstring style: PEP 257
2. If the function is going to modify the given Polytope objects, then the docstring should explicitly state it. As a matter of convention, functions are assumed to not modify arguments (also known as parameters) unless stated otherwise.

[carterbox]

@slivingston I've made changes to the docs strings for line breaks and added a message for the NotImplementedError.

However, I don't want to rewrite rotate and translate to return a new polyreg because, without proof, I believe that the overhead of making a new polyreg for every rotation/translation may be is significant. Would it be better/acceptable if I renamed the functions from rotate to _rotate? My intent is that users to only use these transformation functions through their public wrapper methods e.g. foo.rotate(Rmatrix) and not directly e.g. rotate(foo, Rmatrix).

[johnyf]

I strongly agree with returning new objects, as recommended above.

Standard library classes tend to use verbs for methods that modify the object, and nouns for methods that return a new object (which is described by the selected noun). For example, set.add vs set.union, set.difference. Modifications are emphasized, e.g., set.difference_update. The issue of choosing between the two has come up in polytope design a few years ago. We had decided that polytopes are to be immutable by default. Applying this naming convention to the proposed methods, they would become translation and rotation.

Are you concerned about the overhead of allocating memory for new objects? I don't expect that it will have a big effect. If the input polytope object is dereferenced after the call, then it will be automatically garbage collected (see weakref). The time overhead should be small.

Altering the algorithm without evidence from profiling measurements is premature optimization. There are several profiling tools for Python, for example line_profiler and pympler.

A middle solution is to offer an option for in-place operation via a keyword argument. Even so, it is simpler to implement a function that returns new objects, and use those new objects to modify an existing one within its method.

I agree that functions that are not intended as public API should better remain hidden.

[carterbox]

Seems reasonable, but by that logic, we should rename all of the following methods:

reduce -> reduction intersect -> intersection rotate -> rotation translate -> translation scale -> scaled_polyreg (also this method doesn't return a copy currently)

[johnyf]

Indeed, I renamed the methods to reduction and intersection more than 2 years ago. They are still on branch overhaul, because efficiency had been affected by some (other) change, and I have to identify by which commit.

scale is a verb, so it modifies the instance.

[carterbox]

I did testing over the weekend to see whether returning a copy instead of doing transformations in place was slower; it wasn't. I've created a pull request #39.

Also, I'm going to stop worrying about refactoring, style, and such until after y'all finish merging your overhaul branch. Thanks for being interactive with my questions and pulls.

[johnyf]

Thanks for doing the testing. I think that style and refactoring are important. For example, you could inspect the overhaul branch and raise issues about the design of the API, and you could consider the (old so maybe outdated) summary in the wiki.

I would have liked to have merged that branch, but I cannot without first finding which change degraded performance. This happened because I wasn't running any performance tests (there aren't any). So, having some (automated) unit benchmarks to avoid a similar situation would be useful. Unfortunately, it may take time before I return to the overhaul branch (though I am tempted to).

[johnyf]

Another way to express approximately the same convention about naming functions as described above is given here.

[johnyf]

A relevant package that implements 3 dimensional transformations and looks particularly instructive is transforms3d (it appears to be used by the neuroimaging community).

[slivingston]

@johnyf Good find! I skimmed the requirements.txt and setup.py of transforms3d, and the only dependency that I noticed is numpy, so including it does not incur the cost of more indirect dependencies

[johnyf]

Two other finds:

• pypolymake: wrappers for polymake
• pplpy: wrappers to the Parma Polyhedral library,