Function ForEachRect

libs/geometry/calipers_box.cpp:35–76

// containing the hull and with one side collinear to the facet.
template <typename Fn>
void ForEachRect(ConvexHull const & hull, Fn && fn)
{
  ASSERT_GREATER(hull.Size(), 2, ());

  size_t j = 0, k = 0, l = 0;
  for (size_t i = 0; i < hull.Size(); ++i)
  {
    auto const ab = hull.SegmentAt(i).Dir();

    j = std::max(j, i + 1);
    while (DotProduct(ab, hull.SegmentAt(j).Dir()) > CalipersBox::kEps)
      ++j;

    k = std::max(k, j);
    while (CrossProduct(ab, hull.SegmentAt(k).Dir()) > CalipersBox::kEps)
      ++k;

    l = std::max(l, k);
    while (DotProduct(ab, hull.SegmentAt(l).Dir()) < -CalipersBox::kEps)
      ++l;

    auto const oab = Ort(ab);
    std::array<Line2D, 4> const lines = {Line2D(hull.PointAt(i), ab), Line2D(hull.PointAt(j), oab),
                                         Line2D(hull.PointAt(k), ab), Line2D(hull.PointAt(l), oab)};
    std::vector<PointD> corners;
    for (size_t i = 0; i < lines.size(); ++i)
    {
      auto const j = (i + 1) % lines.size();
      auto result = Intersect(lines[i], lines[j], CalipersBox::kEps);
      if (result.m_type == IntersectionResult::Type::One)
        corners.push_back(result.m_point);
    }

    if (corners.size() != 4)
      continue;

    auto const it = std::min_element(corners.begin(), corners.end());
    std::rotate(corners.begin(), it, corners.end());

    fn(std::move(corners));
  }
}
}  // namespace

CalipersBox::CalipersBox(std::vector<PointD> const & points) : m_points({})