CGAL 5.5.2 - 2D Arrangements
Arrangement_on_surface_2/dual_lines.cpp
// Checking whether there are three collinear points in a given input set
// using the arrangement of the dual lines.
#include <cstdlib>
#include <cassert>
#include "arr_linear.h"
#include "read_objects.h"
int main(int argc, char* argv[]) {
// Get the name of the input file from the command line, or use the default
// points.dat file if no command-line parameters are given.
const char* filename = (argc > 1) ? argv[1] : "points.dat";
// Open the input file.
std::ifstream in_file(filename);
if (! in_file.is_open()) {
std::cerr << "Failed to open " << filename << "!\n";
return 1;
}
// Read the points from the file, and construct their dual lines.
// The input file format should be (all coordinate values are integers):
// <n> // number of point.
// <x_1> <y_1> // point #1.
// <x_2> <y_2> // point #2.
// : : : :
// <x_n> <y_n> // point #n.
std::vector<Point> points;
read_objects<Point>(filename, std::back_inserter(points));
std::list<X_monotone_curve> dual_lines;
for (const auto& p : points) dual_lines.push_back(Line(p.x(), -1, -p.y()));
// Construct the dual arrangement by aggregately inserting the lines.
Arrangement arr;
insert(arr, dual_lines.begin(), dual_lines.end());
std::cout << "The dual arrangement size:\n"
<< "V = " << arr.number_of_vertices()
<< " (+ " << arr.number_of_vertices_at_infinity()
<< " at infinity)"
<< ", E = " << arr.number_of_edges()
<< ", F = " << arr.number_of_faces()
<< " (" << arr.number_of_unbounded_faces()
<< " unbounded)\n";
// Look for a vertex whose degree is greater than 4.
bool found_collinear = false;
for (auto vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit) {
if (vit->degree() > 4) {
found_collinear = true;
break;
}
}
if (found_collinear)
std::cout << "Found at least three collinear points in the input set.\n";
else
std::cout << "No three collinear points are found in the input set.\n";
// Pick two points from the input set, compute their midpoint and insert
// its dual line into the arrangement.
Kernel ker;
const auto n = points.size();
const auto k1 = std::rand() % n, k2 = (k1 + 1) % n;
Point p_mid = ker.construct_midpoint_2_object()(points[k1], points[k2]);
X_monotone_curve dual_p_mid = Line(p_mid.x(), -1, -p_mid.y());
insert(arr, dual_p_mid);
// Make sure that we now have three collinear points.
found_collinear = false;
for (auto vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit) {
if (vit->degree() > 4) {
found_collinear = true;
break;
}
}
assert(found_collinear);
return (0);
}