1 import functools
2 import math
3 import numbers
5 from . import islhelper
7 from .islhelper import mainctx, libisl
8 from .geometry import GeometricObject, Point, Vector
9 from .linexprs import Expression, Symbol, Rational
10 from .domains import Domain
13 __all__ = [
14 'Polyhedron',
15 'Lt', 'Le', 'Eq', 'Ne', 'Ge', 'Gt',
16 'Empty', 'Universe',
17 ]
20 class Polyhedron(Domain):
22 __slots__ = (
23 '_equalities',
24 '_inequalities',
25 '_constraints',
26 '_symbols',
27 '_dimension',
28 )
30 def __new__(cls, equalities=None, inequalities=None):
31 if isinstance(equalities, str):
32 if inequalities is not None:
33 raise TypeError('too many arguments')
34 return cls.fromstring(equalities)
35 elif isinstance(equalities, GeometricObject):
36 if inequalities is not None:
37 raise TypeError('too many arguments')
38 return equalities.aspolyhedron()
39 if equalities is None:
40 equalities = []
41 else:
42 for i, equality in enumerate(equalities):
43 if not isinstance(equality, Expression):
44 raise TypeError('equalities must be linear expressions')
45 equalities[i] = equality.scaleint()
46 if inequalities is None:
47 inequalities = []
48 else:
49 for i, inequality in enumerate(inequalities):
50 if not isinstance(inequality, Expression):
51 raise TypeError('inequalities must be linear expressions')
52 inequalities[i] = inequality.scaleint()
53 symbols = cls._xsymbols(equalities + inequalities)
54 islbset = cls._toislbasicset(equalities, inequalities, symbols)
55 return cls._fromislbasicset(islbset, symbols)
57 @property
58 def equalities(self):
59 return self._equalities
61 @property
62 def inequalities(self):
63 return self._inequalities
65 @property
66 def constraints(self):
67 return self._constraints
69 @property
70 def polyhedra(self):
71 return self,
73 def disjoint(self):
74 return self
76 def isuniverse(self):
77 islbset = self._toislbasicset(self.equalities, self.inequalities,
78 self.symbols)
79 universe = bool(libisl.isl_basic_set_is_universe(islbset))
80 libisl.isl_basic_set_free(islbset)
81 return universe
83 def aspolyhedron(self):
84 return self
86 def __contains__(self, point):
87 if not isinstance(point, Point):
88 raise TypeError('point must be a Point instance')
89 if self.symbols != point.symbols:
90 raise ValueError('arguments must belong to the same space')
91 for equality in self.equalities:
92 if equality.subs(point.coordinates()) != 0:
93 return False
94 for inequality in self.inequalities:
95 if inequality.subs(point.coordinates()) < 0:
96 return False
97 return True
99 def subs(self, symbol, expression=None):
100 equalities = [equality.subs(symbol, expression)
101 for equality in self.equalities]
102 inequalities = [inequality.subs(symbol, expression)
103 for inequality in self.inequalities]
104 return Polyhedron(equalities, inequalities)
106 @classmethod
107 def _fromislbasicset(cls, islbset, symbols):
108 islconstraints = islhelper.isl_basic_set_constraints(islbset)
109 equalities = []
110 inequalities = []
111 for islconstraint in islconstraints:
112 constant = libisl.isl_constraint_get_constant_val(islconstraint)
113 constant = islhelper.isl_val_to_int(constant)
114 coefficients = {}
115 for index, symbol in enumerate(symbols):
116 coefficient = libisl.isl_constraint_get_coefficient_val(islconstraint,
117 libisl.isl_dim_set, index)
118 coefficient = islhelper.isl_val_to_int(coefficient)
119 if coefficient != 0:
120 coefficients[symbol] = coefficient
121 expression = Expression(coefficients, constant)
122 if libisl.isl_constraint_is_equality(islconstraint):
123 equalities.append(expression)
124 else:
125 inequalities.append(expression)
126 libisl.isl_basic_set_free(islbset)
127 self = object().__new__(Polyhedron)
128 self._equalities = tuple(equalities)
129 self._inequalities = tuple(inequalities)
130 self._constraints = tuple(equalities + inequalities)
131 self._symbols = cls._xsymbols(self._constraints)
132 self._dimension = len(self._symbols)
133 return self
135 @classmethod
136 def _toislbasicset(cls, equalities, inequalities, symbols):
137 dimension = len(symbols)
138 indices = {symbol: index for index, symbol in enumerate(symbols)}
139 islsp = libisl.isl_space_set_alloc(mainctx, 0, dimension)
140 islbset = libisl.isl_basic_set_universe(libisl.isl_space_copy(islsp))
141 islls = libisl.isl_local_space_from_space(islsp)
142 for equality in equalities:
143 isleq = libisl.isl_equality_alloc(libisl.isl_local_space_copy(islls))
144 for symbol, coefficient in equality.coefficients():
145 islval = str(coefficient).encode()
147 index = indices[symbol]
148 isleq = libisl.isl_constraint_set_coefficient_val(isleq,
149 libisl.isl_dim_set, index, islval)
150 if equality.constant != 0:
151 islval = str(equality.constant).encode()
153 isleq = libisl.isl_constraint_set_constant_val(isleq, islval)
155 for inequality in inequalities:
156 islin = libisl.isl_inequality_alloc(libisl.isl_local_space_copy(islls))
157 for symbol, coefficient in inequality.coefficients():
158 islval = str(coefficient).encode()
160 index = indices[symbol]
161 islin = libisl.isl_constraint_set_coefficient_val(islin,
162 libisl.isl_dim_set, index, islval)
163 if inequality.constant != 0:
164 islval = str(inequality.constant).encode()
166 islin = libisl.isl_constraint_set_constant_val(islin, islval)
168 return islbset
170 @classmethod
171 def fromstring(cls, string):
172 domain = Domain.fromstring(string)
173 if not isinstance(domain, Polyhedron):
174 raise ValueError('non-polyhedral expression: {!r}'.format(string))
175 return domain
177 def __repr__(self):
178 if self.isempty():
179 return 'Empty'
180 elif self.isuniverse():
181 return 'Universe'
182 else:
183 strings = []
184 for equality in self.equalities:
185 strings.append('0 == {}'.format(equality))
186 for inequality in self.inequalities:
187 strings.append('0 <= {}'.format(inequality))
188 if len(strings) == 1:
189 return strings[0]
190 else:
191 return 'And({})'.format(', '.join(strings))
193 @classmethod
194 def fromsympy(cls, expr):
195 domain = Domain.fromsympy(expr)
196 if not isinstance(domain, Polyhedron):
197 raise ValueError('non-polyhedral expression: {!r}'.format(expr))
198 return domain
200 def tosympy(self):
201 import sympy
202 constraints = []
203 for equality in self.equalities:
204 constraints.append(sympy.Eq(equality.tosympy(), 0))
205 for inequality in self.inequalities:
206 constraints.append(sympy.Ge(inequality.tosympy(), 0))
207 return sympy.And(*constraints)
209 @classmethod
210 def _polygon_inner_point(cls, points):
211 symbols = points[0].symbols
212 coordinates = {symbol: 0 for symbol in symbols}
213 for point in points:
214 for symbol, coordinate in point.coordinates():
215 coordinates[symbol] += coordinate
216 for symbol in symbols:
217 coordinates[symbol] /= len(points)
218 return Point(coordinates)
220 @classmethod
221 def _sort_polygon_2d(cls, points):
222 if len(points) <= 3:
223 return points
224 o = cls._polygon_inner_point(points)
225 angles = {}
226 for m in points:
227 om = Vector(o, m)
228 dx, dy = (coordinate for symbol, coordinate in om.coordinates())
229 angle = math.atan2(dy, dx)
230 angles[m] = angle
231 return sorted(points, key=angles.get)
233 @classmethod
234 def _sort_polygon_3d(cls, points):
235 if len(points) <= 3:
236 return points
237 o = cls._polygon_inner_point(points)
238 a = points[0]
239 oa = Vector(o, a)
240 norm_oa = oa.norm()
241 for b in points[1:]:
242 ob = Vector(o, b)
243 u = oa.cross(ob)
244 if not u.isnull():
245 u = u.asunit()
246 break
247 else:
248 raise ValueError('degenerate polygon')
249 angles = {a: 0.}
250 for m in points[1:]:
251 om = Vector(o, m)
252 normprod = norm_oa * om.norm()
253 cosinus = oa.dot(om) / normprod
254 sinus = u.dot(oa.cross(om)) / normprod
255 angle = math.acos(cosinus)
256 angle = math.copysign(angle, sinus)
257 angles[m] = angle
258 return sorted(points, key=angles.get)
260 def faces(self):
261 vertices = self.vertices()
262 faces = []
263 for constraint in self.constraints:
264 face = []
265 for vertex in vertices:
266 if constraint.subs(vertex.coordinates()) == 0:
267 face.append(vertex)
268 faces.append(face)
269 return faces
271 def plot(self):
272 import matplotlib.pyplot as plt
273 from matplotlib.path import Path
274 import matplotlib.patches as patches
276 if len(self.symbols)> 3:
277 raise TypeError
279 elif len(self.symbols) == 2:
280 verts = self.vertices()
281 points = []
282 codes = [Path.MOVETO]
283 for vert in verts:
284 pairs = ()
285 for sym in sorted(vert, key=Symbol.sortkey):
286 num = vert.get(sym)
287 pairs = pairs + (num,)
288 points.append(pairs)
289 points.append((0.0, 0.0))
290 num = len(points)
291 while num > 2:
292 codes.append(Path.LINETO)
293 num = num - 1
294 else:
295 codes.append(Path.CLOSEPOLY)
296 path = Path(points, codes)
297 fig = plt.figure()
299 patch = patches.PathPatch(path, facecolor='blue', lw=2)
301 ax.set_xlim(-5,5)
302 ax.set_ylim(-5,5)
303 plt.show()
305 elif len(self.symbols)==3:
306 return 0
308 return points
311 def _polymorphic(func):
312 @functools.wraps(func)
313 def wrapper(left, right):
314 if isinstance(left, numbers.Rational):
315 left = Rational(left)
316 elif not isinstance(left, Expression):
317 raise TypeError('left must be a a rational number '
318 'or a linear expression')
319 if isinstance(right, numbers.Rational):
320 right = Rational(right)
321 elif not isinstance(right, Expression):
322 raise TypeError('right must be a a rational number '
323 'or a linear expression')
324 return func(left, right)
325 return wrapper
327 @_polymorphic
328 def Lt(left, right):
329 return Polyhedron([], [right - left - 1])
331 @_polymorphic
332 def Le(left, right):
333 return Polyhedron([], [right - left])
335 @_polymorphic
336 def Eq(left, right):
337 return Polyhedron([left - right], [])
339 @_polymorphic
340 def Ne(left, right):
341 return ~Eq(left, right)
343 @_polymorphic
344 def Gt(left, right):
345 return Polyhedron([], [left - right - 1])
347 @_polymorphic
348 def Ge(left, right):
349 return Polyhedron([], [left - right])
352 Empty = Eq(1, 0)
354 Universe = Polyhedron([])