11#ifndef UTILS_CRITICAL_POINTS_H_
12#define UTILS_CRITICAL_POINTS_H_
18#include "utils/Edge_contractor.h"
28 SkBlComplex filled_complex_;
29 const SkBlComplex& input_complex_;
31 std::ostream& stream_;
34 typedef typename SkBlComplex::Vertex_handle Vertex_handle;
35 typedef typename SkBlComplex::Edge_handle Edge_handle;
36 typedef typename std::pair<Vertex_handle, Vertex_handle> Edge;
41 Critical_points(
const SkBlComplex& input_complex, std::ostream& stream,
double max_length) :
42 input_complex_(input_complex), max_length_(max_length), stream_(stream) {
43 std::deque<Edge> edges;
44 auto vertices = input_complex.vertex_range();
45 for (
auto p = vertices.begin(); p != vertices.end(); ++p) {
46 filled_complex_.add_vertex(input_complex.point(*p));
47 for (
auto q = p; ++q != vertices.end(); )
48 if (squared_eucl_distance(input_complex.point(*p), input_complex.point(*q)) < max_length_ * max_length_)
49 edges.emplace_back(*p, *q);
52 std::sort(edges.begin(), edges.end(),
53 [&](Edge e1, Edge e2) {
54 return squared_edge_length(e1) < squared_edge_length(e2);
57 anti_collapse_edges(edges);
61 double squared_eucl_distance(
const Point& p1,
const Point& p2)
const {
62 return Geometry_trait::Squared_distance_d()(p1, p2);
65 void anti_collapse_edges(
const std::deque<Edge>& edges) {
67 for (Edge e : edges) {
68 std::clog <<
"edge " << pos++ <<
"/" << edges.size() <<
"\n";
69 auto eh = filled_complex_.add_edge_without_blockers(e.first, e.second);
70 int is_contractible(is_link_reducible(eh));
72 switch (is_contractible) {
74 stream_ <<
"alpha=" << std::sqrt(squared_edge_length(e)) <<
" topological change" << std::endl;
77 stream_ <<
"alpha=" << std::sqrt(squared_edge_length(e)) <<
" maybe a topological change" << std::endl;
89 int is_link_reducible(Edge_handle e) {
90 auto link = filled_complex_.link(e);
98 if (link.num_connected_components() > 1)
102 if (link.num_vertices() == 1)
110 double squared_edge_length(Edge_handle e)
const {
111 return squared_eucl_distance(input_complex_.point(input_complex_.first_vertex(e)),
112 input_complex_.point(input_complex_.second_vertex(e)));
115 double squared_edge_length(Edge e)
const {
116 return squared_eucl_distance(input_complex_.point(e.first), input_complex_.point(e.second));
Definition: Critical_points.h:26
Critical_points(const SkBlComplex &input_complex, std::ostream &stream, double max_length)
check all pair of points with length smaller than max_length
Definition: Critical_points.h:41
Definition: Edge_contractor.h:24