\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.12 - 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 <CGAL/Cartesian.h>
#include <CGAL/Arr_linear_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <cstdlib>
typedef Traits_2::Point_2 Point_2;
typedef Traits_2::Line_2 Line_2;
typedef Traits_2::X_monotone_curve_2 X_monotone_curve_2;
typedef CGAL::Arrangement_2<Traits_2> Arrangement_2;
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 << "!" << std::endl;
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_2> points;
std::list<X_monotone_curve_2> dual_lines;
size_t n;
in_file >> n;
points.resize(n);
unsigned int k;
for (k = 0; k < n; ++k) {
int px, py;
in_file >> px >> py;
points[k] = Point_2(px, py);
// The line dual to the point (p_x, p_y) is y = p_x*x - p_y,
// or: p_x*x - y - p_y = 0:
dual_lines.push_back(Line_2(CGAL::Exact_rational(px),
}
in_file.close();
// Construct the dual arrangement by aggregately inserting the lines.
Arrangement_2 arr;
insert(arr, dual_lines.begin(), dual_lines.end());
std::cout << "The dual arrangement size:" << std::endl
<< "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)" << std::endl;
// Look for a vertex whose degree is greater than 4.
Arrangement_2::Vertex_const_iterator vit;
bool found_collinear = false;
for (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."
<< std::endl;
else
std::cout << "No three collinear points are found in the input set."
<< std::endl;
// Pick two points from the input set, compute their midpoint and insert
// its dual line into the arrangement.
Kernel ker;
const int k1 = std::rand() % n, k2 = (k1 + 1) % n;
Point_2 p_mid = ker.construct_midpoint_2_object()(points[k1], points[k2]);
X_monotone_curve_2 dual_p_mid = Line_2(CGAL::Exact_rational(p_mid.x()),
CGAL::Exact_rational(-p_mid.y()));
insert(arr, dual_p_mid);
// Make sure that we now have three collinear points.
found_collinear = false;
for (vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit) {
if (vit->degree() > 4) {
found_collinear = true;
break;
}
}
CGAL_assertion(found_collinear);
return (0);
}