Theory Affine_Arithmetic.Ex_Inter

section ‹Examples: Intersection of Zonotopes with Hyperplanes›
theory Ex_Inter
  imports
    Intersection
    Affine_Code
    Print
begin

subsection ‹Example›

definition zono1::"(real*real*real) aform"
  where "zono1 = msum_aform 53 (aform_of_ivl ((0,0,0)::real*real*real) ((1,2,0)::real*real*real))
    (0, pdevs_of_list [(5, 10, 20)])"

definition interzono1::"(real*real*real) aform"
  where "interzono1 = the (inter_aform_plane_ortho 53 zono1 (0, 0, 1) 3)"

text ‹10-dimensional zonotope with 50 generators›

definition random_zono::"(real*real*real*real*real*real*real*real*real*real) aform" where
  "random_zono =
    (0, pdevs_of_list
      [(5, 9, 27, 12, 23, 3, 9, 10, 18, 2),
      (26, 4, 14, 15, 11, 7, 27, 5, 21, 16),
      (10, 17, 11, 27, 13, 14, 27, 14, 25, 23),
      (7, 6, 5, 30, 14, 10, 2, 1, 18, 25),
      (17, 5, 28, 6, 10, 22, 5, 18, 8, 11),
      (5, 7, 14, 14, 5, 11, 5, 17, 1, 22),
      (3, 6, 11, 20, 28, 13, 12, 10, 2, 23),
      (3, 1, 26, 15, 1, 3, 25, 23, 6, 18),
      (30, 8, 24, 16, 8, 20, 27, 25, 21, 17),
      (30, 4, 8, 12, 8, 4, 22, 27, 23, 2),
      (24, 21, 19, 15, 24, 22, 16, 15, 25, 6),
      (20, 4, 1, 24, 2, 9, 19, 4, 21, 17),
      (1, 12, 13, 7, 8, 8, 2, 11, 28, 6),
      (26, 25, 19, 8, 6, 26, 27, 17, 27, 25),
      (8, 8, 1, 4, 6, 2, 28, 13, 18, 28),
      (14, 14, 12, 7, 26, 19, 9, 25, 21, 17),
      (25, 14, 30, 17, 24, 17, 7, 25, 25, 5),
      (27, 21, 29, 22, 30, 10, 13, 15, 23, 19),
      (27, 5, 10, 4, 11, 12, 3, 20, 8, 23),
      (29, 11, 19, 12, 2, 28, 30, 27, 27, 1),
      (18, 7, 23, 1, 14, 6, 23, 22, 23, 19),
      (7, 17, 3, 15, 28, 15, 9, 16, 23, 7),
      (18, 25, 10, 13, 17, 14, 3, 24, 14, 7),
      (28, 13, 6, 27, 8, 14, 7, 14, 5, 24),
      (17, 5, 18, 9, 2, 11, 24, 17, 3, 2),
      (13, 17, 15, 30, 27, 29, 29, 16, 27, 13),
      (25, 21, 21, 17, 19, 3, 26, 27, 26, 2),
      (5, 16, 21, 18, 23, 1, 19, 13, 10, 2),
      (8, 27, 14, 16, 2, 11, 27, 27, 29, 2),
      (10, 22, 1, 23, 2, 22, 17, 22, 19, 15),
      (16, 8, 9, 27, 19, 23, 24, 30, 1, 3),
      (2, 20, 9, 12, 19, 21, 30, 9, 19, 13),
      (23, 21, 28, 26, 27, 17, 22, 9, 17, 13),
      (24, 1, 19, 19, 28, 21, 4, 8, 10, 20),
      (27, 19, 7, 23, 11, 30, 12, 10, 27, 20),
      (4, 3, 23, 21, 17, 13, 25, 8, 13, 26),
      (11, 25, 7, 2, 27, 10, 15, 14, 17, 23),
      (25, 27, 28, 15, 11, 4, 30, 25, 16, 1),
      (27, 26, 11, 21, 9, 14, 15, 11, 30, 18),
      (3, 19, 13, 17, 13, 9, 22, 4, 20, 30),
      (21, 26, 20, 8, 19, 1, 22, 9, 28, 15),
      (22, 12, 5, 25, 29, 27, 13, 9, 2, 10),
      (9, 24, 30, 6, 23, 13, 18, 15, 30, 20),
      (13, 5, 7, 6, 21, 30, 7, 22, 26, 15),
      (9, 3, 3, 1, 29, 16, 10, 2, 21, 25),
      (3, 14, 22, 18, 21, 15, 16, 22, 27, 26),
      (16, 25, 16, 22, 27, 18, 4, 15, 9, 21),
      (30, 23, 29, 24, 20, 14, 15, 25, 3, 22),
      (6, 18, 17, 14, 19, 25, 9, 22, 7, 26),
      (24, 7, 30, 27, 9, 2, 8, 23, 24, 1)])"

text ‹10-dimensional zonotope with 100 generators›

definition random_zono2::"(real*real*real*real*real*real*real*real*real*real) aform" where
  "random_zono2 =
    (0, pdevs_of_list
      [(17, 28, 12, 10, 18, 3, 14, 27, 21, 22),
      (7, 17, 16, 26, 25, 4, 12, 20, 18, 28),
      (11, 8, 30, 20, 11, 17, 8, 13, 28, 18),
      (18, 20, 26, 12, 25, 24, 23, 24, 22, 2),
      (14, 27, 20, 12, 16, 7, 21, 5, 5, 20),
      (4, 27, 8, 19, 11, 14, 9, 25, 8, 11),
      (14, 29, 12, 28, 29, 21, 20, 6, 18, 6),
      (20, 25, 8, 19, 30, 1, 21, 18, 7, 18),
      (5, 6, 7, 25, 30, 2, 19, 7, 13, 19),
      (11, 15, 16, 13, 17, 2, 9, 10, 29, 17),
      (29, 1, 30, 6, 6, 27, 19, 24, 11, 12),
      (27, 30, 8, 11, 30, 2, 19, 25, 5, 27),
      (3, 26, 16, 18, 12, 11, 4, 8, 2, 4),
      (16, 7, 11, 23, 29, 30, 22, 22, 5, 21),
      (6, 12, 28, 24, 12, 4, 11, 27, 6, 13),
      (30, 13, 16, 29, 22, 7, 10, 12, 3, 17),
      (26, 22, 6, 4, 8, 11, 29, 23, 13, 17),
      (30, 23, 20, 3, 4, 28, 25, 26, 25, 17),
      (30, 27, 8, 20, 4, 1, 9, 6, 23, 16),
      (10, 27, 15, 17, 14, 9, 19, 22, 7, 19),
      (29, 5, 14, 23, 23, 29, 13, 19, 1, 14),
      (7, 30, 29, 23, 27, 2, 3, 8, 10, 14),
      (7, 10, 10, 10, 30, 5, 7, 29, 7, 23),
      (2, 1, 11, 19, 23, 9, 14, 16, 13, 25),
      (5, 10, 2, 24, 16, 21, 21, 30, 14, 12),
      (25, 19, 9, 29, 21, 29, 10, 4, 19, 25),
      (30, 18, 3, 8, 9, 6, 13, 17, 1, 19),
      (7, 30, 18, 16, 25, 15, 10, 17, 18, 12),
      (21, 10, 13, 2, 12, 25, 25, 2, 27, 19),
      (17, 7, 18, 22, 24, 10, 8, 3, 26, 3),
      (3, 22, 19, 23, 30, 20, 1, 25, 18, 27),
      (8, 2, 15, 23, 28, 18, 4, 20, 7, 7),
      (4, 8, 29, 22, 20, 8, 18, 29, 13, 2),
      (20, 5, 8, 8, 20, 17, 2, 17, 29, 2),
      (4, 27, 8, 20, 18, 2, 18, 21, 6, 16),
      (8, 11, 24, 10, 20, 6, 16, 17, 13, 23),
      (22, 8, 21, 25, 17, 13, 9, 21, 4, 19),
      (18, 23, 22, 22, 2, 15, 25, 18, 30, 7),
      (2, 5, 5, 21, 18, 6, 27, 5, 30, 6),
      (28, 4, 17, 15, 27, 7, 27, 5, 9, 19),
      (8, 7, 4, 28, 22, 1, 28, 10, 14, 8),
      (6, 7, 30, 26, 5, 15, 21, 28, 1, 21),
      (20, 11, 8, 18, 17, 1, 24, 11, 22, 6),
      (23, 5, 29, 8, 10, 8, 28, 6, 5, 3),
      (8, 8, 17, 23, 23, 10, 9, 27, 10, 20),
      (3, 7, 29, 26, 1, 16, 1, 30, 5, 4),
      (23, 22, 17, 2, 15, 16, 17, 7, 20, 13),
      (1, 14, 3, 21, 14, 5, 24, 29, 5, 4),
      (6, 14, 26, 18, 29, 7, 2, 19, 19, 24),
      (24, 24, 10, 14, 22, 6, 17, 13, 3, 6),
      (5, 17, 2, 30, 26, 6, 21, 13, 11, 7),
      (11, 20, 15, 29, 20, 2, 23, 6, 28, 9),
      (27, 10, 3, 16, 21, 22, 8, 5, 19, 14),
      (21, 25, 23, 24, 7, 3, 30, 8, 21, 19),
      (10, 9, 17, 15, 14, 2, 5, 19, 28, 9),
      (1, 4, 3, 1, 22, 27, 15, 26, 1, 9),
      (8, 19, 18, 12, 26, 18, 1, 5, 19, 16),
      (6, 30, 11, 8, 22, 1, 24, 10, 30, 5),
      (10, 11, 12, 14, 24, 27, 22, 8, 11, 27),
      (8, 29, 17, 19, 20, 17, 4, 9, 3, 1),
      (17, 15, 1, 17, 22, 30, 1, 22, 3, 23),
      (1, 11, 15, 8, 6, 22, 4, 24, 18, 3),
      (23, 21, 24, 2, 17, 14, 14, 7, 18, 27),
      (30, 3, 25, 17, 25, 3, 5, 8, 4, 24),
      (4, 29, 30, 7, 14, 27, 25, 11, 18, 19),
      (2, 26, 15, 13, 16, 8, 7, 11, 21, 23),
      (9, 22, 28, 29, 18, 9, 22, 25, 26, 20),
      (21, 15, 29, 18, 24, 29, 20, 17, 2, 29),
      (12, 17, 11, 9, 4, 6, 2, 4, 22, 25),
      (17, 9, 9, 19, 3, 8, 6, 22, 12, 15),
      (28, 19, 25, 28, 1, 15, 8, 7, 6, 4),
      (17, 17, 22, 7, 1, 21, 25, 23, 22, 14),
      (19, 1, 7, 3, 11, 9, 7, 24, 2, 4),
      (17, 27, 18, 29, 8, 2, 17, 17, 13, 30),
      (8, 14, 14, 11, 26, 20, 28, 25, 13, 17),
      (10, 17, 7, 26, 24, 4, 10, 17, 2, 15),
      (21, 9, 29, 7, 13, 10, 13, 17, 2, 2),
      (16, 10, 18, 27, 26, 26, 3, 30, 14, 1),
      (9, 15, 11, 9, 2, 11, 3, 13, 29, 20),
      (18, 9, 22, 25, 15, 5, 21, 2, 13, 20),
      (9, 22, 15, 11, 24, 27, 22, 12, 16, 6),
      (4, 6, 20, 5, 25, 20, 3, 21, 26, 30),
      (24, 7, 19, 19, 27, 26, 3, 9, 13, 13),
      (27, 22, 8, 27, 13, 24, 23, 1, 26, 28),
      (12, 29, 7, 6, 25, 17, 22, 10, 6, 24),
      (2, 25, 30, 13, 10, 11, 20, 8, 10, 2),
      (28, 14, 11, 23, 28, 26, 2, 28, 28, 24),
      (8, 3, 24, 9, 10, 19, 11, 7, 5, 3),
      (25, 11, 27, 7, 4, 18, 14, 17, 3, 8),
      (2, 2, 20, 6, 26, 28, 7, 22, 2, 3),
      (29, 15, 23, 30, 23, 30, 1, 13, 12, 3),
      (18, 2, 4, 21, 23, 16, 17, 15, 9, 17),
      (28, 22, 12, 16, 8, 20, 14, 8, 2, 10),
      (28, 6, 18, 9, 4, 17, 11, 5, 19, 16),
      (27, 15, 27, 2, 4, 21, 21, 9, 10, 13),
      (5, 23, 13, 9, 28, 19, 5, 5, 14, 27),
      (7, 15, 2, 12, 9, 6, 12, 23, 25, 25),
      (7, 17, 17, 11, 20, 5, 13, 27, 27, 6),
      (7, 30, 14, 22, 16, 16, 11, 30, 29, 8)])"

text ‹a randomly generated 20-dimensional zonotope* with 50 generators›
definition random_zono3::
  "(real*real*real*real*real*real*real*real*real*real*
    real*real*real*real*real*real*real*real*real*real) aform"
where
  "random_zono3 =
    (0, pdevs_of_list
      [(30, 22, 14, 3, 15, 10, 9, 9, 18, 22, 24, 27, 24, 5, 24, 18, 16, 4, 13, 21),
      (30, 10, 25, 6, 5, 10, 7, 13, 14, 27, 30, 30, 6, 21, 12, 28, 1, 1, 24, 18),
      (25, 14, 10, 30, 9, 5, 2, 11, 11, 11, 26, 8, 12, 18, 5, 10, 17, 15, 30, 24),
      (30, 27, 21, 21, 27, 23, 7, 1, 22, 4, 13, 3, 20, 12, 4, 14, 13, 13, 4, 28),
      (9, 22, 4, 13, 19, 26, 8, 19, 28, 24, 14, 1, 30, 14, 9, 20, 12, 12, 14, 1),
      (7, 6, 13, 1, 21, 28, 23, 1, 26, 16, 6, 25, 12, 26, 17, 13, 30, 12, 28, 25),
      (12, 12, 30, 23, 15, 11, 7, 8, 11, 20, 8, 17, 16, 20, 18, 9, 9, 11, 9, 18),
      (9, 3, 13, 16, 28, 6, 28, 4, 1, 20, 23, 19, 12, 9, 11, 26, 2, 24, 8, 10),
      (3, 9, 11, 22, 29, 17, 1, 16, 27, 6, 16, 3, 24, 20, 20, 14, 4, 14, 21, 11),
      (16, 7, 9, 30, 14, 22, 1, 11, 7, 8, 18, 21, 24, 18, 27, 22, 17, 26, 21, 6),
      (4, 4, 4, 24, 24, 22, 28, 24, 25, 14, 2, 22, 6, 24, 19, 14, 13, 11, 8, 1),
      (30, 9, 12, 17, 23, 11, 18, 1, 19, 3, 18, 26, 19, 16, 21, 10, 23, 28, 17, 11),
      (5, 5, 25, 22, 15, 24, 4, 17, 18, 23, 29, 12, 18, 20, 27, 13, 4, 29, 6, 23),
      (29, 14, 14, 17, 20, 17, 1, 27, 5, 4, 3, 4, 7, 12, 12, 21, 14, 21, 13, 11),
      (3, 21, 14, 3, 14, 27, 5, 22, 22, 3, 4, 1, 24, 17, 1, 7, 7, 24, 16, 6),
      (14, 2, 24, 16, 10, 11, 23, 30, 14, 19, 16, 16, 22, 12, 28, 19, 12, 25, 17, 11),
      (8, 23, 19, 25, 5, 30, 22, 13, 28, 28, 23, 7, 24, 29, 3, 13, 2, 7, 6, 10),
      (4, 10, 13, 5, 15, 22, 11, 20, 4, 9, 11, 17, 16, 30, 1, 12, 29, 7, 20, 11),
      (19, 6, 22, 17, 9, 3, 6, 13, 18, 21, 21, 27, 4, 23, 18, 5, 23, 16, 21, 1),
      (2, 8, 16, 16, 8, 21, 19, 22, 10, 28, 7, 11, 21, 3, 18, 30, 15, 21, 3, 16),
      (7, 8, 8, 19, 21, 13, 7, 7, 29, 16, 10, 5, 21, 28, 16, 19, 11, 21, 13, 23),
      (26, 7, 26, 14, 9, 18, 10, 24, 20, 2, 5, 1, 15, 21, 29, 24, 27, 20, 24, 16),
      (4, 14, 10, 8, 22, 20, 1, 4, 1, 25, 17, 15, 16, 2, 30, 10, 29, 11, 29, 17),
      (21, 12, 16, 3, 28, 7, 3, 8, 12, 19, 24, 12, 6, 14, 18, 16, 24, 12, 21, 2),
      (7, 30, 25, 20, 23, 14, 17, 17, 18, 27, 24, 17, 3, 19, 7, 10, 19, 14, 24, 6),
      (12, 16, 26, 29, 27, 1, 18, 3, 14, 4, 27, 28, 24, 4, 18, 25, 25, 7, 12, 30),
      (19, 30, 30, 15, 16, 4, 12, 16, 27, 24, 22, 28, 13, 14, 22, 17, 18, 21, 7, 19),
      (9, 9, 23, 5, 1, 23, 9, 26, 23, 13, 19, 14, 29, 27, 23, 25, 2, 13, 18, 11),
      (12, 8, 20, 14, 14, 23, 24, 11, 8, 6, 25, 27, 28, 3, 4, 15, 1, 22, 19, 22),
      (19, 23, 28, 13, 2, 5, 17, 1, 17, 19, 30, 7, 6, 29, 7, 12, 11, 20, 30, 23),
      (27, 10, 21, 19, 24, 17, 10, 22, 22, 26, 2, 25, 8, 1, 5, 9, 22, 18, 28, 6),
      (9, 22, 9, 13, 20, 10, 6, 23, 7, 10, 29, 5, 28, 30, 22, 23, 8, 10, 14, 11),
      (14, 16, 20, 4, 25, 1, 10, 20, 13, 29, 17, 14, 21, 30, 21, 16, 10, 19, 6, 16),
      (25, 3, 6, 20, 18, 23, 3, 12, 14, 9, 2, 2, 30, 19, 12, 29, 23, 20, 29, 22),
      (20, 15, 11, 23, 5, 17, 13, 2, 4, 20, 16, 7, 7, 24, 7, 10, 13, 22, 9, 15),
      (8, 12, 30, 22, 11, 26, 25, 16, 27, 2, 9, 15, 15, 13, 30, 21, 4, 3, 1, 5),
      (23, 26, 23, 29, 26, 24, 8, 15, 22, 5, 26, 6, 2, 3, 17, 5, 14, 25, 28, 10),
      (20, 28, 25, 20, 9, 22, 1, 5, 24, 8, 10, 19, 3, 26, 21, 1, 13, 15, 3, 3),
      (9, 24, 1, 5, 22, 11, 11, 22, 25, 25, 16, 25, 24, 28, 15, 26, 22, 1, 23, 9),
      (13, 1, 11, 16, 6, 12, 11, 8, 29, 21, 23, 21, 21, 20, 5, 26, 2, 23, 2, 16),
      (12, 13, 5, 24, 25, 19, 26, 4, 17, 5, 18, 6, 2, 29, 21, 3, 10, 20, 7, 5),
      (26, 10, 13, 17, 29, 22, 3, 3, 28, 11, 5, 8, 11, 11, 17, 27, 19, 17, 23, 8),
      (2, 4, 11, 17, 18, 23, 14, 22, 4, 29, 2, 29, 25, 3, 4, 13, 2, 14, 5, 15),
      (12, 6, 16, 4, 25, 22, 29, 21, 2, 27, 17, 4, 11, 22, 2, 2, 5, 9, 28, 8),
      (3, 26, 17, 3, 29, 17, 16, 24, 10, 9, 16, 4, 23, 14, 10, 12, 16, 28, 28, 28),
      (7, 15, 28, 6, 25, 24, 11, 26, 22, 3, 28, 17, 10, 17, 19, 12, 20, 18, 29, 23),
      (24, 7, 7, 26, 17, 23, 19, 29, 1, 28, 11, 30, 23, 25, 30, 2, 6, 21, 1, 16),
      (6, 27, 22, 25, 9, 1, 16, 2, 12, 30, 23, 19, 12, 29, 20, 16, 16, 16, 6, 21),
      (25, 12, 5, 28, 19, 9, 25, 12, 10, 27, 10, 26, 27, 15, 2, 4, 23, 12, 20, 27)])"

fun random_inter1 where
  "random_inter1 () =
    the (inter_aform_plane_ortho 53 random_zono (1, 15, 26, 8, 15, 23, 5, 14, 8, 8) 12)"

fun random_inter2 where
  "random_inter2 () =
    the (inter_aform_plane_ortho 53 random_zono2 (13, 23, 22, 30, 27, 19, 17, 11, 24, 29) 12)"

fun random_inter3 where
  "random_inter3 () =
    the (inter_aform_plane_ortho 53 random_zono3
      (7, 10, 24, 12, 6, 14, 10, 14, 23, 13, 25, 27, 20, 2, 1, 9, 4, 17, 28, 19)
      12)"

ML val ri1 = @{code random_inter1}
val ri2 = @{code random_inter2}
val ri3 = @{code random_inter3}

text ‹Timings›

ML fun iter f 0 = f ()
| iter f i = let val _ = f () in iter f (i - 1) end
ML iter ri1 100 ― ‹0.7 s›
ML iter ri2 100 ― ‹1.3 s›
ML iter ri3 100 ― ‹1.3 s›

end