如何在 IR 中表示数学域？

Question

我想从约束列表中定义一个表示数学域的对象，但我不清楚该怎么做。

例如，我从 IR 开始，我有以下约束：

x > 0
x 不在 ]3,5]
x 不在 [7,12[

那么，我的域是 ]0,3] U ]5,7[ U [12,+oo .

我怎样才能很好地将它存储在 C++ 结构中？你以前做过吗？此外，我希望能够轻松检查域是否为空。

Answer 1

除非您想使用评论中提到的“第 3 方”工具，否则您必须编写自己的间隔 class。为此，您可以这样做：

class Interval{
  struct Range{
     bool leftInclusive, rightInclusive;
     double left, right;
     bool operator<(Range other){return left<other.left;}
  }
  std::Set<Range> trueRanges;
  void addTrueRange(Range r){
    //check for overlaps
    //merge if overlapping
    //otherwise add to trueRanges
  }
  bool trueAt(double at){
   //find the range with the highest left-bound lower than at
   auto candidate = truethRanges.upper_bound(at); 

   if(candidate == trueRanged.end()) return false; // no range found

   //on-point checking here
   if(at <= candidate->left) return false;
   if(at >= candidate->right) return false;
   return true;
 }
}

这里省略了点检查，因为你不能简单地说 doubleOne == doubleTwo，因为这可能会导致漏报。所以你必须说ABS(doubleOne-doubleTwo) < tinyValue。

要查找重叠，您可以查看 this。

Answer 2

回答我自己的问题。

实际上，我遵循了 sbabbi 的想法，使用来自 boost/numeric/interval 的区间列表，表示区间的并集。

这是一个例子：

typedef boost::numeric::interval_lib::rounded_math<double> RoundedPolicy;
typedef boost::numeric::interval_lib::checking_base<double> CheckingPolicy;
typedef boost::numeric::interval_lib::policies<RoundedPolicy,CheckingPolicy> IntervalPolicies;
typedef boost::numeric::interval<double,IntervalPolicies> interval;

//...

bool is_interval_empty(const interval& inter)
{
  return boost::numeric::empty(inter);
}

void restrict(interval& domain, const interval& inter)
{
  for(std::list<interval>::iterator it = domain.begin(); it != domain.end(); ++it)
    *it = boost::numeric::intersect(*it, inter);
  domain.remove_if(is_interval_empty);
}

void restrict(interval& domain, const interval& inter1, const interval& inter2)
{
  for(std::list<interval>::iterator it = domain.begin(); it != domain.end(); ++it)
  {
    domain.push_front(boost::numeric::intersect(*it, inter1));
    *it = boost::numeric::intersect(*it, inter2);
  }
  domain.remove_if(is_interval_empty);
}

//...

std::list<interval> domain;
for(unsigned long int i = 0; i < constraints.size(); ++i)
{
  if(constraints[i].is_lower_bound())
  {
    interval restriction(constraints[i].get_lower_bound(), std::numeric_limits<double>::infinity());
    restrict(domain, restriction);
  }
  else if(constraints[i].is_upper_bound())
  {
    interval restriction(-std::numeric_limits<double>::infinity(), constraints[i].get_upper_bound());
    restrict(domain, restriction);
  }
  else if(constraints[i].is_forbidden_range())
  {
    interval restriction1(-std::numeric_limits<double>::infinity(), constraints[i].get_lower_bound());
    interval restriction2(constraints[i].get_upper_bound(), std::numeric_limits<double>::infinity());
    restrict(domain, restriction1, restriction2);
  }
}

if(domain.size() == 0)
  std::cout << "empty domain" << std::endl;
else
  std::cout << "the domain exists" << std::endl;

如何在 IR 中表示数学域？

How to represent a mathematical domain in IR?

c++

math

mathematical-morphology