diff options
| -rw-r--r-- | source/blender/blenlib/BLI_delaunay_2d.h | 6 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/delaunay_2d.cc | 155 | ||||
| -rw-r--r-- | source/blender/blenlib/tests/BLI_delaunay_2d_test.cc | 372 |
3 files changed, 518 insertions, 15 deletions
diff --git a/source/blender/blenlib/BLI_delaunay_2d.h b/source/blender/blenlib/BLI_delaunay_2d.h index e91726991ca..d42bd6af637 100644 --- a/source/blender/blenlib/BLI_delaunay_2d.h +++ b/source/blender/blenlib/BLI_delaunay_2d.h @@ -178,6 +178,8 @@ typedef enum CDT_output_type { CDT_FULL, /** All triangles fully enclosed by constraint edges or faces. */ CDT_INSIDE, + /** Like previous, but detect holes and omit those from output. */ + CDT_INSIDE_WITH_HOLES, /** Only point, edge, and face constraints, and their intersections. */ CDT_CONSTRAINTS, /** @@ -186,7 +188,9 @@ typedef enum CDT_output_type { * #BMesh faces in Blender: that is, * no vertex appears more than once and no isolated holes in faces. */ - CDT_CONSTRAINTS_VALID_BMESH + CDT_CONSTRAINTS_VALID_BMESH, + /** Like previous, but detect holes and omit those from output. */ + CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, } CDT_output_type; /** diff --git a/source/blender/blenlib/intern/delaunay_2d.cc b/source/blender/blenlib/intern/delaunay_2d.cc index 9444d1a29cb..eb3e64c49e6 100644 --- a/source/blender/blenlib/intern/delaunay_2d.cc +++ b/source/blender/blenlib/intern/delaunay_2d.cc @@ -226,6 +226,8 @@ template<typename Arith_t> struct CDTFace { int visit_index{0}; /** Marks this face no longer used. */ bool deleted{false}; + /** Marks this face as part of a hole. */ + bool hole{false}; CDTFace() = default; }; @@ -481,9 +483,9 @@ template<typename T> void cdt_draw(const std::string &label, const CDTArrangemen * This is just for developer debugging anyway, and should never be called in production Blender. */ # ifdef _WIN32 - const char *drawfile = "./debug_draw.html"; + const char *drawfile = "./cdt_debug_draw.html"; # else - const char *drawfile = "/tmp/debug_draw.html"; + const char *drawfile = "/tmp/cdt_debug_draw.html"; # endif constexpr int max_draw_width = 1800; constexpr int max_draw_height = 1600; @@ -2364,9 +2366,6 @@ template<typename T> void remove_non_constraint_edges_leave_valid_bmesh(CDT_stat template<typename T> void remove_outer_edges_until_constraints(CDT_state<T> *cdt_state) { - // LinkNode *fstack = NULL; - // SymEdge *se, *se_start; - // CDTFace *f, *fsym; int visit = ++cdt_state->visit_count; cdt_state->cdt.outer_face->visit_index = visit; @@ -2415,6 +2414,137 @@ template<typename T> void remove_outer_edges_until_constraints(CDT_state<T> *cdt } } +template<typename T> void remove_faces_in_holes(CDT_state<T> *cdt_state) +{ + CDTArrangement<T> *cdt = &cdt_state->cdt; + for (int i : cdt->faces.index_range()) { + CDTFace<T> *f = cdt->faces[i]; + if (!f->deleted && f->hole) { + f->deleted = true; + SymEdge<T> *se = f->symedge; + SymEdge<T> *se_start = se; + SymEdge<T> *se_next = nullptr; + do { + BLI_assert(se != nullptr); + se_next = se->next; /* In case we delete this edge. */ + if (se->edge && !is_constrained_edge(se->edge)) { + /* Invalidate one half of this edge. The other has will be or has been + * handled with the adjacent triangle is processed: it should be part of the same hole. + */ + se->next = nullptr; + } + se = se_next; + } while (se != se_start); + } + } +} + +/** + * Set the hole member of each CDTFace to true for each face that is detected to be part of a + * hole. A hole face is define as one for which, when a ray is shot from a point inside the face + * to infinity, it crosses an even number of constraint edges. We'll choose a ray direction that + * is extremely unlikely to exactly superimpose some edge, so avoiding the need to be careful + * about such overlaps. + * + * To improve performance, we gather together faces that should have the same winding number, and + * only shoot rays once. + */ +template<typename T> void detect_holes(CDT_state<T> *cdt_state) +{ + CDTArrangement<T> *cdt = &cdt_state->cdt; + + /* Make it so that each face with the same visit_index is connected through a path of + * non-constraint edges. */ + Vector<CDTFace<T> *> fstack; + Vector<CDTFace<T> *> region_rep_face; + for (int i : cdt->faces.index_range()) { + cdt->faces[i]->visit_index = -1; + } + int cur_region = -1; + cdt->outer_face->visit_index = -2; /* Don't visit this one. */ + for (int i : cdt->faces.index_range()) { + CDTFace<T> *f = cdt->faces[i]; + if (!f->deleted && f->symedge && f->visit_index == -1) { + fstack.append(f); + ++cur_region; + region_rep_face.append(f); + while (!fstack.is_empty()) { + CDTFace<T> *f = fstack.pop_last(); + if (f->visit_index != -1) { + continue; + } + f->visit_index = cur_region; + SymEdge<T> *se_start = f->symedge; + SymEdge<T> *se = se_start; + do { + if (se->edge && !is_constrained_edge(se->edge)) { + CDTFace<T> *fsym = sym(se)->face; + if (fsym && !fsym->deleted && fsym->visit_index == -1) { + fstack.append(fsym); + } + } + se = se->next; + } while (se != se_start); + } + } + } + cdt_state->visit_count = ++cur_region; /* Good start for next use of visit_count. */ + + /* Now get hole status for each region_rep_face. */ + + /* Pick a ray end almost certain to be outside everything and in direction + * that is unlikely to hit a vertex or overlap an edge exactly. */ + FatCo<T> ray_end; + ray_end.exact = vec2<T>(123456, 654321); + for (int i : region_rep_face.index_range()) { + CDTFace<T> *f = region_rep_face[i]; + FatCo<T> mid; + mid.exact[0] = (f->symedge->vert->co.exact[0] + f->symedge->next->vert->co.exact[0] + + f->symedge->next->next->vert->co.exact[0]) / + 3; + mid.exact[1] = (f->symedge->vert->co.exact[1] + f->symedge->next->vert->co.exact[1] + + f->symedge->next->next->vert->co.exact[1]) / + 3; + int hits = 0; + /* TODO: Use CDT data structure here to greatly reduce search for intersections! */ + for (const CDTEdge<T> *e : cdt->edges) { + if (!is_deleted_edge(e) && is_constrained_edge(e)) { + if (e->symedges[0].face->visit_index == e->symedges[1].face->visit_index) { + continue; /* Don't count hits on edges between faces in same region. */ + } + auto isect = vec2<T>::isect_seg_seg(ray_end.exact, + mid.exact, + e->symedges[0].vert->co.exact, + e->symedges[1].vert->co.exact); + switch (isect.kind) { + case vec2<T>::isect_result::LINE_LINE_CROSS: { + hits++; + break; + } + case vec2<T>::isect_result::LINE_LINE_EXACT: + case vec2<T>::isect_result::LINE_LINE_NONE: + case vec2<T>::isect_result::LINE_LINE_COLINEAR: + break; + } + } + } + f->hole = (hits % 2) == 0; + } + + /* Finally, propagate hole status to all holes of a region. */ + for (int i : cdt->faces.index_range()) { + CDTFace<T> *f = cdt->faces[i]; + int region = f->visit_index; + if (region < 0) { + continue; + } + CDTFace<T> *f_region_rep = region_rep_face[region]; + if (i >= 0) { + f->hole = f_region_rep->hole; + } + } +} + /** * Remove edges and merge faces to get desired output, as per options. * \note the cdt cannot be further changed after this. @@ -2439,6 +2569,13 @@ void prepare_cdt_for_output(CDT_state<T> *cdt_state, const CDT_output_type outpu } } + bool need_holes = output_type == CDT_INSIDE_WITH_HOLES || + output_type == CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES; + + if (need_holes) { + detect_holes(cdt_state); + } + if (output_type == CDT_CONSTRAINTS) { remove_non_constraint_edges(cdt_state); } @@ -2448,6 +2585,14 @@ void prepare_cdt_for_output(CDT_state<T> *cdt_state, const CDT_output_type outpu else if (output_type == CDT_INSIDE) { remove_outer_edges_until_constraints(cdt_state); } + else if (output_type == CDT_INSIDE_WITH_HOLES) { + remove_outer_edges_until_constraints(cdt_state); + remove_faces_in_holes(cdt_state); + } + else if (output_type == CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES) { + remove_non_constraint_edges_leave_valid_bmesh(cdt_state); + remove_faces_in_holes(cdt_state); + } } template<typename T> diff --git a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc index d00e8bf55fd..59c4be6d952 100644 --- a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc +++ b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc @@ -17,6 +17,7 @@ extern "C" { #define DO_CPP_TESTS 1 #define DO_C_TESTS 1 +#define DO_TEXT_TESTS 0 #define DO_RANDOM_TESTS 0 #include "BLI_array.hh" @@ -267,7 +268,7 @@ template<typename T> void graph_draw(const std::string &label, const Array<vec2<T>> &verts, const Array<std::pair<int, int>> &edges, - const Array<Vector<int>> &UNUSED(faces)) + const Array<Vector<int>> &faces) { /* Would like to use BKE_tempdir_base() here, but that brings in dependence on kernel library. * This is just for developer debugging anyway, and should never be called in production Blender. @@ -281,7 +282,7 @@ void graph_draw(const std::string &label, constexpr int max_draw_height = 1000; constexpr int thin_line = 1; constexpr int vert_radius = 3; - constexpr bool draw_vert_labels = true; + constexpr bool draw_vert_labels = false; constexpr bool draw_edge_labels = false; if (verts.size() == 0) { @@ -339,6 +340,15 @@ void graph_draw(const std::string &label, "xml:space=\"preserve\"\n" << "width=\"" << view_width << "\" height=\"" << view_height << "\">n"; + for (const Vector<int> &fverts : faces) { + f << "<polygon fill=\"azure\" stroke=\"none\"\n points=\""; + for (int vi : fverts) { + const vec2<T> &co = verts[vi]; + f << SX(co[0]) << "," << SY(co[1]) << " "; + } + f << "\"\n />\n"; + } + for (const std::pair<int, int> &e : edges) { const vec2<T> &uco = verts[e.first]; const vec2<T> &vco = verts[e.second]; @@ -642,6 +652,110 @@ template<typename T> void lineinsquare_test() if (DO_DRAW) { graph_draw<T>("LineInSquare - constraints", out2.vert, out2.edge, out2.face); } + CDT_result<T> out3 = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES); + EXPECT_EQ(out3.vert.size(), 6); + EXPECT_EQ(out3.face.size(), 6); + if (DO_DRAW) { + graph_draw<T>("LineInSquare - inside with holes", out3.vert, out3.edge, out3.face); + } + CDT_result<T> out4 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES); + EXPECT_EQ(out4.vert.size(), 6); + EXPECT_EQ(out4.face.size(), 2); + if (DO_DRAW) { + graph_draw<T>("LineInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face); + } +} + +template<typename T> void lineholeinsquare_test() +{ + const char *spec = R"(10 1 2 + -0.5 -0.5 + 0.5 -0.5 + -0.5 0.5 + 0.5 0.5 + -0.25 0.0 + 0.25 0.0 + -0.4 -0.4 + 0.4 -0.4 + 0.4 -0.3 + -0.4 -0.3 + 4 5 + 0 1 3 2 + 6 7 8 9 + )"; + + CDT_input<T> in = fill_input_from_string<T>(spec); + CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL); + EXPECT_EQ(out.vert.size(), 10); + EXPECT_EQ(out.face.size(), 14); + if (DO_DRAW) { + graph_draw<T>("LineHoleInSquare - full", out.vert, out.edge, out.face); + } + CDT_result<T> out2 = delaunay_2d_calc(in, CDT_CONSTRAINTS); + EXPECT_EQ(out2.vert.size(), 10); + EXPECT_EQ(out2.face.size(), 2); + if (DO_DRAW) { + graph_draw<T>("LineHoleInSquare - constraints", out2.vert, out2.edge, out2.face); + } + CDT_result<T> out3 = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES); + EXPECT_EQ(out3.vert.size(), 10); + EXPECT_EQ(out3.face.size(), 12); + if (DO_DRAW) { + graph_draw<T>("LineHoleInSquare - inside with holes", out3.vert, out3.edge, out3.face); + } + CDT_result<T> out4 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES); + EXPECT_EQ(out4.vert.size(), 10); + EXPECT_EQ(out4.face.size(), 2); + if (DO_DRAW) { + graph_draw<T>("LineHoleInSquare - valid bmesh with holes", out4.vert, out4.edge, out4.face); + } +} + +template<typename T> void nestedholes_test() +{ + const char *spec = R"(12 0 3 + -0.5 -0.5 + 0.5 -0.5 + -0.5 0.5 + 0.5 0.5 + -0.4 -0.4 + 0.4 -0.4 + 0.4 0.4 + -0.4 0.4 + -0.2 -0.2 + 0.2 -0.2 + 0.2 0.2 + -0.2 0.2 + 0 1 3 2 + 4 7 6 5 + 8 9 10 11 + )"; + + CDT_input<T> in = fill_input_from_string<T>(spec); + CDT_result<T> out = delaunay_2d_calc(in, CDT_FULL); + EXPECT_EQ(out.vert.size(), 12); + EXPECT_EQ(out.face.size(), 18); + if (DO_DRAW) { + graph_draw<T>("NestedHoles - full", out.vert, out.edge, out.face); + } + CDT_result<T> out2 = delaunay_2d_calc(in, CDT_CONSTRAINTS); + EXPECT_EQ(out2.vert.size(), 12); + EXPECT_EQ(out2.face.size(), 3); + if (DO_DRAW) { + graph_draw<T>("NestedHoles - constraints", out2.vert, out2.edge, out2.face); + } + CDT_result<T> out3 = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES); + EXPECT_EQ(out3.vert.size(), 12); + EXPECT_EQ(out3.face.size(), 10); + if (DO_DRAW) { + graph_draw<T>("NestedHoles - inside with holes", out3.vert, out3.edge, out3.face); + } + CDT_result<T> out4 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES); + EXPECT_EQ(out4.vert.size(), 12); + EXPECT_EQ(out4.face.size(), 3); + if (DO_DRAW) { + graph_draw<T>("NestedHoles - valid bmesh with holes", out4.vert, out4.edge, out4.face); + } } template<typename T> void crosssegs_test() @@ -1025,16 +1139,28 @@ template<typename T> void overlapfaces_test() graph_draw<T>("OverlapFaces - inside", out2.vert, out2.edge, out2.face); } - CDT_result<T> out3 = delaunay_2d_calc(in, CDT_CONSTRAINTS); - EXPECT_EQ(out3.face.size(), 4); + CDT_result<T> out3 = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES); + EXPECT_EQ(out3.face.size(), 14); + if (DO_DRAW) { + graph_draw<T>("OverlapFaces - inside with holes", out3.vert, out3.edge, out3.face); + } + + CDT_result<T> out4 = delaunay_2d_calc(in, CDT_CONSTRAINTS); + EXPECT_EQ(out4.face.size(), 4); if (DO_DRAW) { - graph_draw<T>("OverlapFaces - constraints", out3.vert, out3.edge, out3.face); + graph_draw<T>("OverlapFaces - constraints", out4.vert, out4.edge, out4.face); } - CDT_result<T> out4 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH); - EXPECT_EQ(out4.face.size(), 5); + CDT_result<T> out5 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH); + EXPECT_EQ(out5.face.size(), 5); if (DO_DRAW) { - graph_draw<T>("OverlapFaces - valid bmesh", out4.vert, out4.edge, out4.face); + graph_draw<T>("OverlapFaces - valid bmesh", out5.vert, out5.edge, out5.face); + } + + CDT_result<T> out6 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES); + EXPECT_EQ(out6.face.size(), 3); + if (DO_DRAW) { + graph_draw<T>("OverlapFaces - valid bmesh with holes", out6.vert, out6.edge, out6.face); } } @@ -1246,6 +1372,34 @@ template<typename T> void repeattri_test() } } +template<typename T> void square_o_test() +{ + const char *spec = R"(8 0 2 + 0.0 0.0 + 1.0 0.0 + 1.0 1.0 + 0.0 1.0 + 0.2 0.2 + 0.2 0.8 + 0.8 0.8 + 0.8 0.2 + 0 1 2 3 + 4 5 6 7 + )"; + CDT_input<T> in = fill_input_from_string<T>(spec); + CDT_result<T> out1 = delaunay_2d_calc(in, CDT_INSIDE_WITH_HOLES); + EXPECT_EQ(out1.face.size(), 8); + if (DO_DRAW) { + graph_draw<T>("Square O - inside with holes", out1.vert, out1.edge, out1.face); + } + + CDT_result<T> out2 = delaunay_2d_calc(in, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES); + EXPECT_EQ(out2.face.size(), 2); + if (DO_DRAW) { + graph_draw<T>("Square O - valid bmesh with holes", out2.vert, out2.edge, out2.face); + } +} + TEST(delaunay_d, Empty) { empty_test<double>(); @@ -1301,6 +1455,16 @@ TEST(delaunay_d, LineInSquare) lineinsquare_test<double>(); } +TEST(delaunay_d, LineHoleInSquare) +{ + lineholeinsquare_test<double>(); +} + +TEST(delaunay_d, NestedHoles) +{ + nestedholes_test<double>(); +} + TEST(delaunay_d, CrossSegs) { crosssegs_test<double>(); @@ -1371,6 +1535,11 @@ TEST(delaunay_d, RepeatTri) repeattri_test<double>(); } +TEST(delaunay_d, SquareO) +{ + square_o_test<double>(); +} + # ifdef WITH_GMP TEST(delaunay_m, Empty) { @@ -1426,6 +1595,16 @@ TEST(delaunay_m, LineInSquare) lineinsquare_test<mpq_class>(); } +TEST(delaunay_m, LineHoleInSquare) +{ + lineholeinsquare_test<mpq_class>(); +} + +TEST(delaunay_m, NestedHoles) +{ + nestedholes_test<mpq_class>(); +} + TEST(delaunay_m, CrossSegs) { crosssegs_test<mpq_class>(); @@ -1496,7 +1675,6 @@ TEST(delaunay_m, RepeatTri) repeattri_test<mpq_class>(); } # endif - #endif #if DO_C_TESTS @@ -1524,6 +1702,182 @@ TEST(delaunay_d, CintTwoFace) } #endif +#if DO_TEXT_TESTS +template<typename T> +void text_test(int num_arc_points, int num_lets_per_line, int num_lines, CDT_output_type otype) +{ + constexpr bool print_timing = true; + /* + * Make something like a letter B: + * + * 4------------3 + * | ) + * | 12--11 ) + * | | ) a3 ) a1 + * | 9---10 ) + * | ) + * | 2 + * | ) + * | 8----7 ) + * | | ) a2 ) a0 + * | 5----6 ) + * | ) + * 0------------1 + * + * Where the numbers are the first 13 vertices, and the rest of + * the vertices are in arcs a0, a1, a2, a3, each of which have + * num_arc_points per arc in them. + */ + + const char *b_before_arcs = R"(13 0 3 + 0.0 0.0 + 1.0 0.0 + 1.0 1.5 + 1.0 3.0 + 0.0 3.0 + 0.2 0.2 + 0.6 0.2 + 0.6 1.4 + 0.2 1.4 + 0.2 1.6 + 0.6 1.6 + 0.6 2.8 + 0.2 2.8 + 3 4 0 1 2 + 6 5 8 7 + 10 9 12 11 + )"; + + CDT_input<T> b_before_arcs_in = fill_input_from_string<T>(b_before_arcs); + constexpr int narcs = 4; + int b_npts = b_before_arcs_in.vert.size() + narcs * num_arc_points; + constexpr int b_nfaces = 3; + Array<vec2<T>> b_vert(b_npts); + Array<Vector<int>> b_face(b_nfaces); + std::copy(b_before_arcs_in.vert.begin(), b_before_arcs_in.vert.end(), b_vert.begin()); + std::copy(b_before_arcs_in.face.begin(), b_before_arcs_in.face.end(), b_face.begin()); + if (num_arc_points > 0) { + b_face[0].pop_last(); // We'll add center point back between arcs for outer face. + for (int arc = 0; arc < narcs; ++arc) { + int arc_origin_vert; + int arc_terminal_vert; + bool ccw; + switch (arc) { + case 0: + arc_origin_vert = 1; + arc_terminal_vert = 2; + ccw = true; + break; + case 1: + arc_origin_vert = 2; + arc_terminal_vert = 3; + ccw = true; + break; + case 2: + arc_origin_vert = 7; + arc_terminal_vert = 6; + ccw = false; + break; + case 3: + arc_origin_vert = 11; + arc_terminal_vert = 10; + ccw = false; + break; + default: + BLI_assert(false); + } + vec2<T> start_co = b_vert[arc_origin_vert]; + vec2<T> end_co = b_vert[arc_terminal_vert]; + vec2<T> center_co = 0.5 * (start_co + end_co); + BLI_assert(start_co[0] == end_co[2]); + double radius = abs(math_to_double<T>(end_co[1] - center_co[1])); + double angle_delta = M_PI / (num_arc_points + 1); + int start_vert = b_before_arcs_in.vert.size() + arc * num_arc_points; + Vector<int> &face = b_face[(arc <= 1) ? 0 : arc - 1]; + for (int i = 0; i < num_arc_points; ++i) { + vec2<T> delta; + float ang = ccw ? (-M_PI_2 + (i + 1) * angle_delta) : (M_PI_2 - (i + 1) * angle_delta); + delta[0] = T(radius * cos(ang)); + delta[1] = T(radius * sin(ang)); + b_vert[start_vert + i] = center_co + delta; + face.append(start_vert + i); + } + if (arc == 0) { + face.append(arc_terminal_vert); + } + } + } + + CDT_input<T> in; + int tot_instances = num_lets_per_line * num_lines; + if (tot_instances == 1) { + in.vert = b_vert; + in.face = b_face; + } + else { + in.vert = Array<vec2<T>>(tot_instances * b_vert.size()); + in.face = Array<Vector<int>>(tot_instances * b_face.size()); + T cur_x = T(0); + T cur_y = T(0); + T delta_x = T(2); + T delta_y = T(3.25); + int instance = 0; + for (int line = 0; line < num_lines; ++line) { + for (int let = 0; let < num_lets_per_line; ++let) { + vec2<T> co_offset(cur_x, cur_y); + int in_v_offset = instance * b_vert.size(); + for (int v = 0; v < b_vert.size(); ++v) { + in.vert[in_v_offset + v] = b_vert[v] + co_offset; + } + int in_f_offset = instance * b_face.size(); + for (int f : b_face.index_range()) { + for (int fv : b_face[f]) { + in.face[in_f_offset + f].append(in_v_offset + fv); + } + } + cur_x += delta_x; + ++instance; + } + cur_y += delta_y; + cur_x = T(0); + } + } + in.epsilon = b_before_arcs_in.epsilon; + double tstart = PIL_check_seconds_timer(); + CDT_result<T> out = delaunay_2d_calc(in, otype); + double tend = PIL_check_seconds_timer(); + if (print_timing) { + std::cout << "time = " << tend - tstart << "\n"; + } + if (DO_DRAW) { + std::string label = "Text arcpts=" + std::to_string(num_arc_points); + if (num_lets_per_line > 1) { + label += " linelen=" + std::to_string(num_lets_per_line); + } + if (num_lines > 1) { + label += " lines=" + std::to_string(num_lines); + } + graph_draw<T>(label, out.vert, out.edge, out.face); + } +} + +TEST(delaunay_d, TextB10) +{ + text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES); +} + +TEST(delaunay_d, TextB200) +{ + text_test<double>(200, 1, 1, CDT_INSIDE_WITH_HOLES); +} + +TEST(delaunay_d, TextB10_10_10) +{ + text_test<double>(10, 10, 10, CDT_INSIDE_WITH_HOLES); +} + +#endif + #if DO_RANDOM_TESTS enum { |