Opened 10 years ago

Closed 10 years ago

#13763 closed defect (fixed)

Minkowski subtraction

Reported by: Volker Braun Owned by: mhampton
Priority: major Milestone: sage-5.7
Component: geometry Keywords:
Cc: Dima Pasechnik Merged in: sage-5.7.beta2
Authors: Volker Braun Reviewers: Dmitrii Pasechnik
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11763, #12193 Stopgaps:

Status badges

Description (last modified by Volker Braun)

This patch implements the Minkowski difference and some misc. bugfixes (Did you know that CartesianProduct with generators silently gives the wrong answer? #13764)

Apply trac_13763_minkowski_difference.patch, trac_13763_minkowski_sum_decompositions.patch

Attachments (2)

trac_13763_minkowski_difference.patch (14.4 KB) - added by Volker Braun 10 years ago.
Updated patch
trac_13763_minkowski_sum_decompositions.patch (10.3 KB) - added by Volker Braun 10 years ago.
Updated patch

Download all attachments as: .zip

Change History (12)

comment:1 Changed 10 years ago by Volker Braun

Dependencies: #11763
Status: newneeds_review

comment:2 Changed 10 years ago by Volker Braun

Cc: Dima Pasechnik added
Description: modified (diff)

comment:3 Changed 10 years ago by Dima Pasechnik

I get

patching file sage/geometry/polyhedron/base.py
Hunk #4 succeeded at 1453 with fuzz 2 (offset -20 lines).

any idea why? Seems you might want to rebase it, perhaps adding #13638 as a dependency (hunk 4 fuzz happens with and without #13638 - although with different offsets.)

comment:4 Changed 10 years ago by Volker Braun

Dependencies: #11763#11763, #12193

Patch doesn't commute with #12193, added to the dependencies even though its functionally independent.

Changed 10 years ago by Volker Braun

Updated patch

comment:5 Changed 10 years ago by Volker Braun

Description: modified (diff)

While we are at it, I added some code to list all decompositions of a polygon into the Minkowski sum of two smaller polygons.

comment:6 Changed 10 years ago by Dima Pasechnik

Status: needs_reviewneeds_work
sage -t -long "devel/sage-main/sage/geometry/polyhedron/base_ZZ.py"
**********************************************************************
File "/usr/local/src/sage/sage-5.6.beta2/devel/sage-main/sage/geometry/polyhedron/base_ZZ.py", line 402:
    sage: [ len(square.dilation(i).Minkowski_decompositions())
        for i in range(Integer(6)) ]
Exception raised:
    Traceback (most recent call last):
      File "/usr/local/src/sage/sage-5.6.beta2/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/usr/local/src/sage/sage-5.6.beta2/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/usr/local/src/sage/sage-5.6.beta2/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_12[7]>", line 2, in <module>
        for i in range(Integer(6)) ]
      File "/usr/local/src/sage/sage-5.6.beta2/local/lib/python/site-packages/sage/geometry/polyhedron/base.py", line 2402, in dilation
        base_ring=self.parent()._coerce_base_ring(scalar.parent()))
    AttributeError: 'int' object has no attribute 'parent'

looks like there is int somewhere where one should have ZZ instead...

Changed 10 years ago by Volker Braun

Updated patch

comment:7 Changed 10 years ago by Volker Braun

Thanks, fixed. It should have just been _coerce_base_ring(scalar), the method is smart enough to deal with ZZ and int.

comment:8 Changed 10 years ago by Dima Pasechnik

Status: needs_workpositive_review

comment:9 Changed 10 years ago by Jeroen Demeyer

Reviewers: Dmitrii Pasechnik

comment:10 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.7.beta2
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.