Authors: Shahar Shamai and Efi Fogel

Introduction

Movable Separability of Sets [2] is a class of problems that deal with moving sets of objects, such as polygons in the plane; the challenge is to avoid collisions between the objects while considering different kinds of motions and various definitions of separation. The Moving sofa problem or sofa problem is a classic member of this class. It is a two-dimensional idealization of real-life furniture-moving problems; it asks for the rigid two-dimensional shape of largest area \(A\) that can be maneuvered through an L-shaped planar region with legs of unit width [3]. The area \(A\) thus obtained is referred to as the sofa constant. The exact value of the sofa constant is an open problem; see Figure 25.1. These problems become progressively more challenging as the allowable set of separation motions becomes more complex (have more degrees of freedom), the number of objects involved grows, or the shape of the objects becomes more complicated.

Figure 25.1 The Hammersley sofa has area 2.2074 but is not the largest solution.

At this point this package provides solutions to one subclass of problems related to 2D castings. In particular, each of these solutions handles a single moving polygon and a single stationary polygon, and considers a single translation of the moving polygon.

Casting

Casting is a manufacturing process where liquid material is poured into a cavity inside a mold, which has the shape of a desired product. (The mold can take any shape and form as long as it has a cavity of the desired shape.) After the material solidifies, the product is pulled out of the mold. Typically a mold is used to manufacture numerous copies of a product. The challenge is designing a proper mold, such that the solidified product can be separated from its mold without breaking it.

This package provides a function called CGAL::Set_movable_separability_2::Single_mold_translational_casting::top_edges() that, given a simple closed polygon \(P\), determines whether a cavity (of a mold in the plane) that has the shape of \(P\) can be used so that the polygon \(P\) could be pulled out of the mold without colliding into the mold (but possibly sliding along the mold boundary); see Figure 25.2 for an illustration. In reality, the mold of a castable polygon must be rotated before the polygon is casted, such that one edge becomes parallel to the \(x\)-axis and is located above all other edges; such an edge is referred to as a top edge. A polygon may have up to four edges that can serve as top edges. If the polygon is castable, the function computes the set of top edges of such cavities and the corresponding closed ranges of pullout directions in the plane.

Figure 25.2 Two castable polygons (light grey) in their molds (darker grey) and valid pullout directions on the left. Two non-castable polygons on the right.

The input polygon must satisfy two conditions as follows. First, it has to be simple. Essentially, a simple polygon is topologically equivalent to a disk; see Chapter 2D Regularized Boolean Set-Operations for the precise definition of simple polygons. Secondly, any consecutive three vertices cannot be collinear. If you suspect that the input polygon may not satisfy the latter condition, pre-process the polygon to eliminate this ill-condition.

The implementation is based on an algorithm developed by Shamai and Halperin; see [1] for the generalization of the algorithm to 3D. The time and space complexities are in \(O(n)\) and \(O(1)\), respectively. In order to ensure robustness and correctness you must use a kernel that guarantees exact constructions as well as exact predicates, e,g,. Exact_predicates_exact_constructions_kernel.

The following example computes the top edges and their pullout directions of an input polygon read from a file and reports the results.

File Set_movable_separability_2/top_edges_single_mold_trans_cast.cpp

#include <list>
#include <fstream>
 
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Set_movable_separability_2/Single_mold_translational_casting/top_edges.h>
 
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Polygon_2<Kernel>                           Polygon_2;
typedef Kernel::Direction_2                               Direction_2;
typedef Kernel::Vector_2                                        Vector_2;
typedef Kernel::Point_2                                        Point_2;
 
// A direction range is a closed range of directions on the unit circle.
typedef std::pair<Direction_2, Direction_2>               Direction_range;
typedef Polygon_2::Edge_const_iterator                    Edge_iter;
 
// A top edge is identified by the index to an edge of a polygon and the
// corresponding range of pullout directions.
typedef std::pair<Edge_iter, Direction_range>             Top_edge;
 
namespace SMS = CGAL::Set_movable_separability_2;
namespace casting = SMS::Single_mold_translational_casting;
 
// The main program:
int main(int  argc, char* argv[])
{
  Polygon_2 polygon;
 
  const char* filename = (argc > 1) ? argv[1] : "polygon.dat";
  std::ifstream input_file(filename);
  if (! input_file.is_open()) {
    std::cerr << "Failed to open the " << filename << std::endl;
    return -1;
  }
  input_file >> polygon;
  input_file.close();
 
  std::list<Top_edge> top_edges;
 
  // Example for top_edges_single_mold_translational_casting_2
  casting::top_edges(polygon, std::back_inserter(top_edges));
  if (top_edges.empty())
    std::cout << "The polygon is not castable!" << std::endl;
  else {
    std::cout << "There are " << top_edges.size() << " top edges:" << std::endl;
    for (const auto& top_edge : top_edges) {
      std::cout
        << "\tEdge: " << *top_edge.first<< std::endl
        << "\tPullout directions from: " << top_edge.second.first
        << " to " << top_edge.second.second
        << std::endl << std::endl;
    }
  }
 
  return 0;
}

This package provides two additional functions, namely, CGAL::Set_movable_separability_2::Single_mold_translational_casting::pullout_directions() and CGAL::Set_movable_separability_2::Single_mold_translational_casting::is_pullout_direction(). The former accepts a simple closed polygon \(P\) and an edge \(e\) of the polygon \(P\); it determines whether \(e\) is a top edge of \(P\), and if so, it computes the range of pullout directions of \(e\). The latter is overloaded with two versions: The first version accepts a simple closed polygon \(P\) and a direction \(d\); it determines whether \(d\) is a pullout direction of some top edge of \(P\). The other version accepts, in addition, an edge \(e\) of the polygon \(P\); it determines whether \(d\) is a pullout direction of \(e\).

Overloads of each of the functions above that accept (i) an additional argument that indicates the orientation of the input polygon or (ii) an additional traits argument, or (iii) both, are also provided by the package.