Lines Matching defs:hull
251 /* Given a facet "facet" of the convex hull of "set" and a facet "ridge"
252 * of that facet, compute the other facet of the convex hull that contains
270 * Since the ridge contains the origin, the cone of the convex hull
278 * convex hull to 1 and minimizing x_2.
279 * Now, each element in the cone of the convex hull is the sum
380 * If the affine hull of this intersection has only one equality,
443 /* Given the bounding constraint "c" of a facet of the convex hull of "set",
524 * in the resulting convex hull. That is, we compute the ridges
525 * of the resulting convex hull contained in the facet.
527 * of the convex hull. There is no need to wrap around the ridges
532 * the facets of the basic sets are also facets of the convex hull and
539 static __isl_give isl_basic_set *extend(__isl_take isl_basic_set *hull,
549 if (dim < 0 || !hull)
550 return isl_basic_set_free(hull);
554 for (i = 0; i < hull->n_ineq; ++i) {
555 facet = compute_facet(set, hull->ineq[i]);
556 facet = isl_basic_set_add_eq(facet, hull->ineq[i]);
559 hull_facet = isl_basic_set_copy(hull);
560 hull_facet = isl_basic_set_add_eq(hull_facet, hull->ineq[i]);
565 hull = isl_basic_set_cow(hull);
566 hull = isl_basic_set_extend(hull, 0, 0, facet->n_ineq);
567 if (!hull)
576 k = isl_basic_set_alloc_inequality(hull);
579 isl_seq_cpy(hull->ineq[k], hull->ineq[i], 1+dim);
580 if (!isl_set_wrap_facet(set, hull->ineq[k], facet->ineq[j]))
586 hull = isl_basic_set_simplify(hull);
587 hull = isl_basic_set_finalize(hull);
588 return hull;
592 isl_basic_set_free(hull);
596 /* Special case for computing the convex hull of a one dimensional set.
607 struct isl_basic_set *hull;
698 hull = isl_basic_set_alloc(set->ctx, 0, 1, 0, 0, 2);
699 hull = isl_basic_set_set_rational(hull);
700 if (!hull)
703 k = isl_basic_set_alloc_inequality(hull);
704 isl_seq_cpy(hull->ineq[k], lower, 2);
707 k = isl_basic_set_alloc_inequality(hull);
708 isl_seq_cpy(hull->ineq[k], upper, 2);
710 hull = isl_basic_set_finalize(hull);
713 return hull;
735 /* Compute the convex hull of a pair of basic sets without any parameters or
737 * The convex hull is the set of all points that can be written as
742 * to the convex hull.
749 struct isl_basic_set *hull = NULL;
756 hull = isl_basic_set_alloc(bset1->ctx, 0, 2 + 3 * dim, 0,
763 k = isl_basic_set_alloc_equality(hull);
766 isl_seq_clr(hull->eq[k], (i+1) * (1+dim));
767 isl_seq_clr(hull->eq[k]+(i+2)*(1+dim), (1-i)*(1+dim));
768 isl_seq_cpy(hull->eq[k]+(i+1)*(1+dim), bset[i]->eq[j],
772 k = isl_basic_set_alloc_inequality(hull);
775 isl_seq_clr(hull->ineq[k], (i+1) * (1+dim));
776 isl_seq_clr(hull->ineq[k]+(i+2)*(1+dim), (1-i)*(1+dim));
777 isl_seq_cpy(hull->ineq[k]+(i+1)*(1+dim),
780 k = isl_basic_set_alloc_inequality(hull);
783 isl_seq_clr(hull->ineq[k], 1+2+3*dim);
784 isl_int_set_si(hull->ineq[k][(i+1)*(1+dim)], 1);
787 k = isl_basic_set_alloc_equality(hull);
790 isl_seq_clr(hull->eq[k], 1+2+3*dim);
791 isl_int_set_si(hull->eq[k][j], -1);
792 isl_int_set_si(hull->eq[k][1+dim+j], 1);
793 isl_int_set_si(hull->eq[k][2*(1+dim)+j], 1);
795 hull = isl_basic_set_set_rational(hull);
796 hull = isl_basic_set_remove_dims(hull, isl_dim_set, dim, 2*(1+dim));
797 hull = isl_basic_set_remove_redundancies(hull);
800 return hull;
804 isl_basic_set_free(hull);
865 /* Compute the lineality space of the convex hull of bset1 and bset2.
869 * the linear hull of the resulting cone.
930 * project the linear space from the set, compute the convex hull
945 * After computing the convex hull in x'_1, i.e., A' x'_1 >= b',
946 * we transform the hull back to the original space as A' Q_1 x >= b',
954 struct isl_basic_set *hull;
974 hull = uset_convex_hull(set);
975 hull = isl_basic_set_preimage(hull, Q);
977 return hull;
1164 /* Compute the convex hull of a pair of basic sets without any parameters or
1165 * integer divisions, where the convex hull is known to be pointed,
1168 * We turn this problem into the computation of a convex hull of a pair
1215 * Then we compute the convex hull of the polytopes b_i' + A_i' x' >= 0
1221 * The polyhedron b + A x >= 0 is then the convex hull of the input polyhedra.
1230 struct isl_basic_set *hull;
1252 hull = uset_convex_hull(set);
1253 hull = isl_basic_set_preimage(hull, T);
1257 return hull;
1269 /* Compute the convex hull of a pair of basic sets without any parameters or
1273 * means that the complete convex hull is unbounded. Some pairs
1276 * case they need to be handled inside their affine hull since
1279 * If the convex hull of the two basic sets would have a non-trivial
1394 /* Compute the (linear) hull of the lineality spaces of the basic sets in the
1419 /* Compute the convex hull of a set without any parameters or
1482 /* Compute an initial hull for wrapping containing a single initial
1486 static __isl_give isl_basic_set *initial_hull(__isl_take isl_basic_set *hull,
1493 if (!hull)
1498 k = isl_basic_set_alloc_inequality(hull);
1505 isl_seq_cpy(hull->ineq[k], bounds->row[0], bounds->n_col);
1508 return hull;
1510 isl_basic_set_free(hull);
1608 * constraints of the convex hull.
1612 * all other basic sets and is therefore the convex hull of set.
1616 __isl_take isl_basic_set *hull, __isl_keep isl_set *set, int *is_hull)
1630 return isl_basic_set_free(hull);
1635 return hull;
1641 return isl_basic_set_free(hull);
1649 constraints = isl_calloc_array(hull->ctx, struct max_constraint,
1652 return hull;
1653 table = isl_alloc_type(hull->ctx, struct isl_hash_table);
1654 if (isl_hash_table_init(hull->ctx, table, min_constraints))
1661 constraints[i].c = isl_mat_sub_alloc6(hull->ctx,
1671 entry = isl_hash_table_find(hull->ctx, table, c_hash,
1675 isl_assert(hull->ctx, !entry->data, goto error);
1688 if (update_constraint(hull->ctx, table,
1695 if (update_constraint(hull->ctx, table, ineq, total, n,
1707 j = isl_basic_set_alloc_inequality(hull);
1710 isl_seq_cpy(hull->ineq[j], constraints[i].c->row[0], 1 + total);
1716 if (set->p[s]->n_ineq != hull->n_ineq)
1721 has = has_constraint(hull->ctx, table, ineq, total, n);
1736 return hull;
1744 return hull;
1747 /* Create a template for the convex hull of "set" and fill it up
1749 * be the convex hull of "set" then *is_hull is set to 1.
1754 struct isl_basic_set *hull;
1763 hull = isl_basic_set_alloc_space(isl_space_copy(set->dim), 0, 0, n_ineq);
1764 hull = isl_basic_set_set_rational(hull);
1765 if (!hull)
1767 return common_constraints(hull, set, is_hull);
1772 struct isl_basic_set *hull;
1775 hull = proto_hull(set, &is_hull);
1776 if (hull && !is_hull) {
1777 if (hull->n_ineq == 0)
1778 hull = initial_hull(hull, set);
1779 hull = extend(hull, set);
1783 return hull;
1786 /* Compute the convex hull of a set without any parameters or
1788 * we pass control to the wrapping based convex hull or
1789 * the Fourier-Motzkin elimination based convex hull.
1843 * without parameters or divs and where the convex hull of set is
1882 /* Compute the convex hull of set "set" with affine hull "affine_hull",
1884 * convex hull of the transformed set and then add the equalities back
1925 /* Compute the convex hull of a map.
1982 isl_basic_map *hull;
1984 hull = isl_map_convex_hull(map);
1985 return isl_basic_map_remove_divs(hull);
1998 /* Holds the data needed during the simple hull computation.
2002 * in the simple hull
2201 * to "hull". Relaxation is only allowed if "shift" is set.
2203 * We first check if "hull" already contains a translate of the inequality.
2220 static __isl_give isl_basic_set *add_bound(__isl_take isl_basic_set *hull,
2230 total = isl_basic_set_dim(hull, isl_dim_all);
2232 return isl_basic_set_free(hull);
2238 entry = isl_hash_table_find(hull->ctx, data->hull_table, c_hash,
2241 return isl_basic_set_free(hull);
2243 return hull;
2246 entry = isl_hash_table_find(hull->ctx, data->p[j].table,
2249 return isl_basic_set_free(hull);
2254 return hull;
2256 k = isl_basic_set_alloc_inequality(hull);
2259 isl_seq_cpy(hull->ineq[k], ineq, 1 + v.len);
2261 if (set_max_constant_term(data, set, i, hull->ineq[k], c_hash, &v) < 0)
2265 bound = is_bound(data, set, j, hull->ineq[k], shift);
2272 return isl_basic_set_free_inequality(hull, 1);
2276 entry = isl_hash_table_find(hull->ctx, data->p[j].table,
2279 return isl_basic_set_free(hull);
2282 bound = is_bound(data, set, j, hull->ineq[k], shift);
2289 return isl_basic_set_free_inequality(hull, 1);
2291 entry = isl_hash_table_find(hull->ctx, data->hull_table, c_hash,
2295 entry->data = hull->ineq[k];
2297 return hull;
2299 isl_basic_set_free(hull);
2305 * to "hull". Relaxation is only allowed if "shift" is set.
2328 /* Compute a superset of the convex hull of set that is described
2336 struct isl_basic_set *hull = NULL;
2350 hull = isl_basic_set_alloc_space(isl_space_copy(set->dim), 0, 0, n_ineq);
2351 if (!hull)
2359 hull = add_bounds(hull, data, set, i, shift);
2364 return hull;
2367 isl_basic_set_free(hull);
2372 /* Compute a superset of the convex hull of map that is described
2379 isl_basic_map *hull;
2386 hull = isl_basic_map_copy(map->p[0]);
2388 return hull;
2391 /* Return a copy of the simple hull cached inside "map".
2393 * simple hull.
2398 isl_basic_map *hull;
2400 hull = isl_basic_map_copy(map->cached_simple_hull[shift]);
2403 return hull;
2406 /* Compute a superset of the convex hull of map that is described
2430 struct isl_basic_map *hull;
2453 hull = isl_basic_map_overlying_set(bset, model);
2455 hull = isl_basic_map_intersect(hull, affine_hull);
2456 hull = isl_basic_map_remove_redundancies(hull);
2458 if (hull) {
2459 ISL_F_SET(hull, ISL_BASIC_MAP_NO_IMPLICIT);
2460 ISL_F_SET(hull, ISL_BASIC_MAP_ALL_EQUALITIES);
2463 hull = isl_basic_map_finalize(hull);
2465 input->cached_simple_hull[shift] = isl_basic_map_copy(hull);
2468 return hull;
2471 /* Compute a superset of the convex hull of map that is described
2484 /* Compute a superset of the convex hull of map that is described
2639 /* Compute a superset of the convex hull of "map" that is described
2648 * The hull is initialized from the first basic map and then
2655 isl_basic_map *hull;
2662 hull = isl_basic_map_copy(map->p[0]);
2667 hull = isl_basic_map_plain_unshifted_simple_hull(hull, bmap_i);
2671 return hull;
2674 /* Compute a superset of the convex hull of "set" that is described
2685 /* Check if "ineq" is a bound on "set" and, if so, add it to "hull".
2695 __isl_take isl_basic_set *hull, struct sh_data *data,
2704 total = isl_basic_set_dim(hull, isl_dim_all);
2706 return isl_basic_set_free(hull);
2712 ctx = isl_basic_set_get_ctx(hull);
2720 return isl_basic_set_free(hull);
2738 return isl_basic_set_free(hull);
2743 return hull;
2745 k = isl_basic_set_alloc_inequality(hull);
2747 return isl_basic_set_free(hull);
2748 isl_seq_cpy(hull->ineq[k], ineq, 1 + v.len);
2750 return hull;
2753 /* Compute a superset of the convex hull of "set" that is described
2763 * but we do not need the hull table since we will not consider the
2777 isl_basic_set *hull = NULL;
2780 hull = isl_basic_set_alloc_space(isl_set_get_space(set), 0, 0, n_ineq);
2781 if (!hull)
2792 int hull_n_ineq = hull->n_ineq;
2800 hull = add_bound_from_constraint(hull, data, set, ineq[i]);
2801 if (!hull)
2803 last_added = hull->n_ineq > hull_n_ineq;
2808 return hull;
2812 isl_basic_set_free(hull);
2872 /* Compute a superset of the convex hull of "set" that is described
2890 isl_basic_set *hull;
2924 hull = uset_unshifted_simple_hull_from_constraints(set, n_ineq, ineq);
2929 return hull;
2938 /* Compute a superset of the convex hull of "map" that is described
2946 * as regular variables, computing the unshifted simple hull in
2954 isl_basic_map *hull;
2985 hull = uset_unshifted_simple_hull_from_basic_set_list(set, bset_list);
2986 hull = isl_basic_map_overlying_set(hull, model);
2988 return hull;
3028 /* Compute a superset of the convex hull of "map" that is described
3031 * If "map" is the universe, then the convex hull (and therefore
3055 /* Compute a superset of the convex hull of "set" that is described
3077 /* Computes a "simple hull" and then check if each dimension in the
3078 * resulting hull is bounded by a symbolic constant. If not, the
3079 * hull is intersected with the corresponding bounds on the whole set.
3084 struct isl_basic_set *hull;
3089 hull = isl_set_simple_hull(isl_set_copy(set));
3090 nparam = isl_basic_set_dim(hull, isl_dim_param);
3091 dim = isl_basic_set_dim(hull, isl_dim_set);
3092 total = isl_basic_set_dim(hull, isl_dim_all);
3101 for (j = 0; j < hull->n_eq; ++j) {
3102 if (isl_int_is_zero(hull->eq[j][1 + nparam + i]))
3104 if (isl_seq_first_non_zero(hull->eq[j]+1+nparam+i+1,
3108 if (j < hull->n_eq)
3111 for (j = 0; j < hull->n_ineq; ++j) {
3112 if (isl_int_is_zero(hull->ineq[j][1 + nparam + i]))
3114 if (isl_seq_first_non_zero(hull->ineq[j]+1+nparam+i+1,
3116 isl_seq_first_non_zero(hull->ineq[j]+1+nparam,
3119 if (isl_int_is_pos(hull->ineq[j][1 + nparam + i]))
3137 hull = isl_basic_set_intersect(hull, bounds);
3138 if (!hull)
3143 return hull;
3146 isl_basic_set_free(hull);