23511030556

Committed 24 Mar 2026 08:36PM UTC coverage: 91.163% (-0.05%) from 91.208%

Build # 23511030556

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #863 from eyal0/single_threaded_coverage

build: Disable multi-threading for coverage.

Run Details

7585 of 8671 branches covered (87.48%)

Branch coverage included in aggregate %.

4 of 4 new or added lines in 2 files covered. (100.0%)

4 existing lines in 2 files now uncovered.

6640 of 6933 relevant lines covered (95.77%)

40361588.65 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

71.34

/src/voronoi.cpp

/*
 * This file is part of pcb2gcode.
 *
 * Copyright (C) 2016 Nicola Corna <nicola@corna.info>
 *
 * pcb2gcode is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * pcb2gcode is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with pcb2gcode.  If not, see <http://www.gnu.org/licenses/>.
 */

 #include <iostream>

#include "voronoi.hpp"
#include "voronoi_visual_utils.hpp"
#include <list>
#include <map>
#include <algorithm>
using std::list;
using std::map;

#include <vector>
using std::vector;

// For use when we have to convert from float to long and back.
const double SCALE = 1000000.0;

multi_polygon_type_fp Voronoi::build_voronoi(
    const multi_polygon_type_fp& input,
    const box_type_fp& mask_bounding_box, coordinate_type_fp max_dist) {
  // We need to scale all the inputs and call the integer version.
  multi_polygon_type_fp scaled_input;
  bg::transform(input, scaled_input,
                bg::strategy::transform::scale_transformer<coordinate_type_fp, 2, 2>(
                    SCALE, SCALE));

  box_type_fp scaled_mask_bounding_box;
  bg::transform(mask_bounding_box, scaled_mask_bounding_box,
                bg::strategy::transform::scale_transformer<coordinate_type_fp, 2, 2>(
                    SCALE, SCALE));

  multi_polygon_type voronoi_input;
  bg::convert(scaled_input, voronoi_input);
  box_type voronoi_bounding_box;
  bg::convert(scaled_mask_bounding_box, voronoi_bounding_box);

  const multi_polygon_type_fp scaled_voronoi = build_voronoi(voronoi_input, voronoi_bounding_box, max_dist * SCALE);
  // Scale the result back down.
  multi_polygon_type_fp voronoi;
  bg::transform(scaled_voronoi, voronoi,
                bg::strategy::transform::scale_transformer<coordinate_type_fp, 2, 2>(
                    1.0/SCALE, 1.0/SCALE));
  return voronoi;
}

multi_polygon_type_fp Voronoi::build_voronoi(
    const multi_polygon_type& input,
    const box_type& mask_bounding_box, coordinate_type max_dist) {
    if (input.empty()) {
        return multi_polygon_type_fp();
    }

    // Bounding_box is a box that is big enough to hold all milling.
    box_type_fp bounding_box = bg::return_envelope<box_type_fp>(input);
    // Expand that bounding box by the provided bounding_box.
    bg::expand(bounding_box, mask_bounding_box);
    // Make it large enough so that any voronoi edges between it and
    // the input will surely line outside mask_bounding_box.
    const auto bounding_box_width = bounding_box.max_corner().x() - bounding_box.min_corner().x();
    const auto bounding_box_height = bounding_box.max_corner().y() - bounding_box.min_corner().y();
    bounding_box.max_corner().x(bounding_box.max_corner().x() + 2*bounding_box_width);
    bounding_box.min_corner().x(bounding_box.min_corner().x() - 2*bounding_box_width);
    bounding_box.max_corner().y(bounding_box.max_corner().y() + 2*bounding_box_height);
    bounding_box.min_corner().y(bounding_box.min_corner().y() - 2*bounding_box_height);
    // Each line segment from all the inputs.
    vector<segment_type_p> segments;
    // From which polygon each segment is sourced.
    std::vector<size_t> segments_to_poly;
    for (const auto& polygon : input) {
        copy_ring(polygon.outer(), segments);
        for (const ring_type& ring : polygon.inners()) {
            copy_ring(ring, segments);
        }
        segments_to_poly.push_back(segments.size());
    }

    // Add the bounding box but without putting it in segments_to_poly
    // so that we won't put voronoi cells from it into the output.
    ring_type bounding_box_ring;
    bg::convert(bounding_box, bounding_box_ring);
    copy_ring(bounding_box_ring, segments);

    voronoi_builder_type voronoi_builder;
    boost::polygon::insert(segments.begin(), segments.end(), &voronoi_builder);
    voronoi_diagram_type voronoi_diagram;
    voronoi_builder.construct(&voronoi_diagram);

    // The output polygons which are voronoi shapes.  The outputs
    // match the inputs in number and position but the number of inner
    // rings for each output polygon might not match.
    multi_polygon_type_fp output;
    // Pre-allocate because we are going to add elements out of order.
    output.resize(input.size());

    // To keep it simply, we first mark each edge as used if it won't
    // be part of the output.
    const int VISITED = 1;
    for (const edge_type& edge : voronoi_diagram.edges()) {
        if (!edge.is_primary() || // Not a real voronoi edge.
            same_poly(edge, *edge.twin(), segments_to_poly) || // This edge doesn't divide different shapes.
            // The edge belongs to the boundary.
            std::upper_bound(segments_to_poly.cbegin(), segments_to_poly.cend(), edge.twin()->cell()->source_index()) == segments_to_poly.cend()) {
            edge.color(edge.color() | VISITED);
        }
    }
    for (const edge_type& edge : voronoi_diagram.edges()) {
        if ((edge.color() & VISITED) == VISITED) {
            continue;  // Used already.
        }

        const edge_type* current_edge = &edge;
        const edge_type* const start_edge = current_edge;
        ring_type_fp ring;
        do {
            linestring_type_fp discrete_edge = edge_to_linestring(*current_edge, segments, bounding_box, max_dist);
            // Don't push the last one because we'll put it at the end.
            for(std::size_t i=0; i<discrete_edge.size()-1; ++i)
            {
              bg::append(ring, discrete_edge.at(i));
            }

            current_edge->color(current_edge->color() | VISITED);  // Mark used
            current_edge = current_edge->next();

            // Check that we are still circling the same polygon for
            // our ring, and that we are on edge that is between
            // different traces, and that it's a primary edge.
            while (current_edge != start_edge &&
                   ((current_edge->color() & VISITED) == VISITED ||
                    // Still circling the same twin.  We look at twin because we need clockwise outer loops.
                    !same_poly(*current_edge->twin(), *start_edge->twin(), segments_to_poly))) {
                current_edge = current_edge->rot_next();
            }
        } while (current_edge != start_edge);

        if(!ring.empty())
        {
          ring.push_back(ring.front());  // Close the ring.
          size_t poly_index = std::distance(segments_to_poly.cbegin(), std::upper_bound(segments_to_poly.cbegin(), segments_to_poly.cend(), edge.twin()->cell()->source_index()));
          if (bg::area(ring) > 0) {
              // This is the outer ring of the poly.
              output[poly_index].outer().swap(ring);
          } else {
              // This has negative area, it must be a hole in the outer.
              output[poly_index].inners().push_back(ring);
          }
        }
    }

    return output;
}

bool Voronoi::same_poly(const edge_type& edge0, const edge_type& edge1, const std::vector<size_t>& segments_to_poly) {
    return (std::upper_bound(segments_to_poly.cbegin(), segments_to_poly.cend(), edge0.cell()->source_index()) ==
            std::upper_bound(segments_to_poly.cbegin(), segments_to_poly.cend(), edge1.cell()->source_index()));
}

linestring_type_fp Voronoi::edge_to_linestring(const edge_type& edge, const vector<segment_type_p>& segments, const box_type_fp& bounding_box, coordinate_type max_dist) {
    linestring_type_fp new_voronoi_edge;
    if (edge.is_finite()) {
        if (edge.is_linear()) {
            new_voronoi_edge.push_back(point_type_fp(edge.vertex0()->x(),
                                                     edge.vertex0()->y()));
            new_voronoi_edge.push_back(point_type_fp(edge.vertex1()->x(),
                                                     edge.vertex1()->y()));
        } else {
            // It's a curve, it needs sampling.
            vector<point_type_fp_p> sampled_edge;
            sample_curved_edge(&edge, segments, sampled_edge, max_dist);
            for (const auto& point : sampled_edge) {
                new_voronoi_edge.push_back(point_type_fp(point.x(), point.y()));
            }
        }
    } else {
        // Infinite edge, only make it if it is inside the bounding_box.
        if ((edge.vertex0() == NULL ||
             bg::covered_by(point_type(edge.vertex0()->x(), edge.vertex0()->y()),
                            bounding_box)) &&
            (edge.vertex1() == NULL ||
             bg::covered_by(point_type(edge.vertex1()->x(), edge.vertex1()->y()),
                            bounding_box))) {
            vector<point_type_fp_p> clipped_edge;
            clip_infinite_edge(
                edge, segments, &clipped_edge, bounding_box);
            for (const auto& point : clipped_edge) {
                new_voronoi_edge.push_back(point_type_fp(point.x(), point.y()));
            }
        }
    }
    return new_voronoi_edge;
}

// Make segments from the ring and put them in segments.
void Voronoi::copy_ring(const ring_type& ring, vector<segment_type_p> &segments)
{
  for (auto iter = ring.begin(); iter + 1 != ring.end(); iter++) {
    segments.push_back(segment_type_p(point_type_p(iter->x(), iter->y()),
                                      point_type_p((iter + 1)->x(), (iter + 1)->y())));
  }
}

point_type_p Voronoi::retrieve_point(const cell_type& cell, const vector<segment_type_p> &segments) {
    source_index_type index = cell.source_index();
    source_category_type category = cell.source_category();

    if (category == boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT)
        return boost::polygon::low(segments[index]);
    else
       return boost::polygon::high(segments[index]);
}

const segment_type_p& Voronoi::retrieve_segment(const cell_type& cell, const vector<segment_type_p> &segments) {
    source_index_type index = cell.source_index();
    return segments[index];
}

void Voronoi::sample_curved_edge(const edge_type *edge, const vector<segment_type_p> &segments,
                         vector<point_type_fp_p>& sampled_edge, coordinate_type_fp max_dist) {

    point_type_p point = edge->cell()->contains_point() ?
        retrieve_point(*(edge->cell()), segments) :
        retrieve_point(*(edge->twin()->cell()), segments);

    const segment_type_p& segment = edge->cell()->contains_point() ?
        retrieve_segment(*(edge->twin()->cell()), segments) :
        retrieve_segment(*(edge->cell()), segments);

    sampled_edge.push_back(point_type_fp_p(edge->vertex0()->x(), edge->vertex0()->y()));
    sampled_edge.push_back(point_type_fp_p(edge->vertex1()->x(), edge->vertex1()->y()));
    boost::polygon::voronoi_visual_utils<coordinate_type_fp>::discretize(point, segment, max_dist, &sampled_edge);
}

void Voronoi::clip_infinite_edge(
    const edge_type& edge, const vector<segment_type_p>& segments, std::vector<point_type_fp_p>* clipped_edge, const box_type_fp& bounding_box) {
    const cell_type& cell1 = *edge.cell();
    const cell_type& cell2 = *edge.twin()->cell();
    point_type_p origin, direction;
    // Infinite edges could not be created by two segment sites.
    if (cell1.contains_point() && cell2.contains_point()) {
        point_type_p p1 = retrieve_point(cell1, segments);
        point_type_p p2 = retrieve_point(cell2, segments);
        origin.x((p1.x() + p2.x()) * 0.5);
        origin.y((p1.y() + p2.y()) * 0.5);
        direction.x(p1.y() - p2.y());
        direction.y(p2.x() - p1.x());
    } else {
        origin = cell1.contains_segment() ?
            retrieve_point(cell2, segments) :
            retrieve_point(cell1, segments);
        segment_type_p segment = cell1.contains_segment() ?
            retrieve_segment(cell1, segments) :
            retrieve_segment(cell2, segments);
        coordinate_type dx = high(segment).x() - low(segment).x();
        coordinate_type dy = high(segment).y() - low(segment).y();
        if ((low(segment) == origin) ^ cell1.contains_point()) {
            direction.x(dy);
            direction.y(-dx);
        } else {
            direction.x(-dy);
            direction.y(dx);
        }
    }
    coordinate_type side = bounding_box.max_corner().x() - bounding_box.min_corner().x();
    coordinate_type koef =
        side / std::max(std::abs(direction.x()), std::abs(direction.y()));
    if (edge.vertex0() == NULL) {
        clipped_edge->push_back(point_type_fp_p(
                                    origin.x() - direction.x() * koef,
                                    origin.y() - direction.y() * koef));
    } else {
        clipped_edge->push_back(
            point_type_fp_p(edge.vertex0()->x(), edge.vertex0()->y()));
    }
    if (edge.vertex1() == NULL) {
        clipped_edge->push_back(point_type_fp_p(
                                    origin.x() + direction.x() * koef,
                                    origin.y() + direction.y() * koef));
    } else {
        clipped_edge->push_back(
            point_type_fp_p(edge.vertex1()->x(), edge.vertex1()->y()));
    }
}

1	/*
2	* This file is part of pcb2gcode.
3	*
4	* Copyright (C) 2016 Nicola Corna <nicola@corna.info>
5	*
6	* pcb2gcode is free software: you can redistribute it and/or modify
7	* it under the terms of the GNU General Public License as published by
8	* the Free Software Foundation, either version 3 of the License, or
9	* (at your option) any later version.
10	*
11	* pcb2gcode is distributed in the hope that it will be useful,
12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	* GNU General Public License for more details.
15	*
16	* You should have received a copy of the GNU General Public License
17	* along with pcb2gcode. If not, see <http://www.gnu.org/licenses/>.
18	*/
19
20	#include <iostream>
21
22	#include "voronoi.hpp"
23	#include "voronoi_visual_utils.hpp"
24	#include <list>
25	#include <map>
26	#include <algorithm>
27	using std::list;
28	using std::map;
29
30	#include <vector>
31	using std::vector;
32
33	// For use when we have to convert from float to long and back.
34	const double SCALE = 1000000.0;
35
36	multi_polygon_type_fp Voronoi::build_voronoi(	294✔
37	const multi_polygon_type_fp& input,
38	const box_type_fp& mask_bounding_box, coordinate_type_fp max_dist) {	5,586✔
39	// We need to scale all the inputs and call the integer version.
40	multi_polygon_type_fp scaled_input;	5,880✔
41	bg::transform(input, scaled_input,	6,174✔
42	bg::strategy::transform::scale_transformer<coordinate_type_fp, 2, 2>(	5,880✔
43	SCALE, SCALE));	5,586✔
44
45	box_type_fp scaled_mask_bounding_box;	5,880✔
46	bg::transform(mask_bounding_box, scaled_mask_bounding_box,	6,174✔
47	bg::strategy::transform::scale_transformer<coordinate_type_fp, 2, 2>(	5,880✔
48	SCALE, SCALE));	5,586✔
49
50	multi_polygon_type voronoi_input;	5,880✔
51	bg::convert(scaled_input, voronoi_input);	5,880✔
52	box_type voronoi_bounding_box;	5,880✔
53	bg::convert(scaled_mask_bounding_box, voronoi_bounding_box);	5,880✔
54
55	const multi_polygon_type_fp scaled_voronoi = build_voronoi(voronoi_input, voronoi_bounding_box, max_dist * SCALE);	5,880✔
56	// Scale the result back down.
57	multi_polygon_type_fp voronoi;	5,880✔
58	bg::transform(scaled_voronoi, voronoi,	6,174✔
59	bg::strategy::transform::scale_transformer<coordinate_type_fp, 2, 2>(	5,880✔
60	1.0/SCALE, 1.0/SCALE));	5,880✔
61	return voronoi;	5,880✔
62	}	5,880✔
63
64	multi_polygon_type_fp Voronoi::build_voronoi(	302✔
65	const multi_polygon_type& input,
66	const box_type& mask_bounding_box, coordinate_type max_dist) {	5,738✔
67	if (input.empty()) {	6,040✔
68	return multi_polygon_type_fp();	120✔
69	}	114✔
70
71	// Bounding_box is a box that is big enough to hold all milling.
72	box_type_fp bounding_box = bg::return_envelope<box_type_fp>(input);	5,920✔
73	// Expand that bounding box by the provided bounding_box.
74	bg::expand(bounding_box, mask_bounding_box);	5,920✔
75	// Make it large enough so that any voronoi edges between it and
76	// the input will surely line outside mask_bounding_box.
77	const auto bounding_box_width = bounding_box.max_corner().x() - bounding_box.min_corner().x();	5,920✔
78	const auto bounding_box_height = bounding_box.max_corner().y() - bounding_box.min_corner().y();	5,920✔
79	bounding_box.max_corner().x(bounding_box.max_corner().x() + 2*bounding_box_width);	5,920✔
80	bounding_box.min_corner().x(bounding_box.min_corner().x() - 2*bounding_box_width);	5,920✔
81	bounding_box.max_corner().y(bounding_box.max_corner().y() + 2*bounding_box_height);	5,920✔
82	bounding_box.min_corner().y(bounding_box.min_corner().y() - 2*bounding_box_height);	5,920✔
83	// Each line segment from all the inputs.
84	vector<segment_type_p> segments;	5,920✔
85	// From which polygon each segment is sourced.
86	std::vector<size_t> segments_to_poly;	5,920✔
87	for (const auto& polygon : input) {	47,136✔
88	copy_ring(polygon.outer(), segments);	46,840✔
89	for (const ring_type& ring : polygon.inners()) {	47,932✔
90	copy_ring(ring, segments);	21,840✔
91	}	20,748✔
92	segments_to_poly.push_back(segments.size());	46,840✔
93	}	44,498✔
94
95	// Add the bounding box but without putting it in segments_to_poly
96	// so that we won't put voronoi cells from it into the output.
97	ring_type bounding_box_ring;	5,920✔
98	bg::convert(bounding_box, bounding_box_ring);	5,920✔
99	copy_ring(bounding_box_ring, segments);	5,920✔
100
101	voronoi_builder_type voronoi_builder;	5,920✔
102	boost::polygon::insert(segments.begin(), segments.end(), &voronoi_builder);	5,920✔
103	voronoi_diagram_type voronoi_diagram;	5,920✔
104	voronoi_builder.construct(&voronoi_diagram);	5,920✔
105
106	// The output polygons which are voronoi shapes. The outputs
107	// match the inputs in number and position but the number of inner
108	// rings for each output polygon might not match.
109	multi_polygon_type_fp output;	5,920✔
110	// Pre-allocate because we are going to add elements out of order.
111	output.resize(input.size());	5,920✔
112
113	// To keep it simply, we first mark each edge as used if it won't
114	// be part of the output.
115	const int VISITED = 1;	5,920✔
116	for (const edge_type& edge : voronoi_diagram.edges()) {	58,207,336✔
117	if (!edge.is_primary() \|\| // Not a real voronoi edge.	60,130,656✔
118	same_poly(edge, *edge.twin(), segments_to_poly) \|\| // This edge doesn't divide different shapes.	58,207,040✔
119	// The edge belongs to the boundary.
120	std::upper_bound(segments_to_poly.cbegin(), segments_to_poly.cend(), edge.twin()->cell()->source_index()) == segments_to_poly.cend()) {	55,992,844✔
121	edge.color(edge.color() \| VISITED);	44,951,880✔
122	}	42,704,286✔
123	}	55,296,688✔
124	for (const edge_type& edge : voronoi_diagram.edges()) {	58,207,336✔
125	if ((edge.color() & VISITED) == VISITED) {	58,207,040✔
126	continue; // Used already.	58,156,200✔
127	}	55,248,390✔
128
129	const edge_type* current_edge = &edge;	50,840✔
130	const edge_type* const start_edge = current_edge;	50,840✔
131	ring_type_fp ring;	50,840✔
132	do {	13,255,160✔
133	linestring_type_fp discrete_edge = edge_to_linestring(*current_edge, segments, bounding_box, max_dist);	13,255,160✔
134	// Don't push the last one because we'll put it at the end.
135	for(std::size_t i=0; i<discrete_edge.size()-1; ++i)	27,732,920✔
136	{	13,753,872✔
137	bg::append(ring, discrete_edge.at(i));	14,477,760✔
138	}	13,753,872✔
139
140	current_edge->color(current_edge->color() \| VISITED); // Mark used	13,255,160✔
141	current_edge = current_edge->next();	13,255,160✔
142
143	// Check that we are still circling the same polygon for
144	// our ring, and that we are on edge that is between
145	// different traces, and that it's a primary edge.
146	while (current_edge != start_edge &&	27,363,560✔
147	((current_edge->color() & VISITED) == VISITED \|\|	28,214,992✔
148	// Still circling the same twin. We look at twin because we need clockwise outer loops.
149	!same_poly(current_edge->twin(), start_edge->twin(), segments_to_poly))) {	26,801,058✔
150	current_edge = current_edge->rot_next();	14,108,400✔
151	}	13,402,980✔
152	} while (current_edge != start_edge);	13,255,160✔
153
154	if(!ring.empty())	50,840✔
155	{	48,298✔
156	ring.push_back(ring.front()); // Close the ring.	50,840✔
157	size_t poly_index = std::distance(segments_to_poly.cbegin(), std::upper_bound(segments_to_poly.cbegin(), segments_to_poly.cend(), edge.twin()->cell()->source_index()));	50,840✔
158	if (bg::area(ring) > 0) {	50,840✔
159	// This is the outer ring of the poly.
160	output[poly_index].outer().swap(ring);	46,840✔
161	} else {	44,498✔
162	// This has negative area, it must be a hole in the outer.
163	output[poly_index].inners().push_back(ring);	4,000✔
164	}	3,800✔
165	}	48,298✔
166	}	50,840✔
167
168	return output;	5,920✔
169	}	6,034✔
170
171	bool Voronoi::same_poly(const edge_type& edge0, const edge_type& edge1, const std::vector<size_t>& segments_to_poly) {	55,551,800✔
172	return (std::upper_bound(segments_to_poly.cbegin(), segments_to_poly.cend(), edge0.cell()->source_index()) ==	58,329,390✔
173	std::upper_bound(segments_to_poly.cbegin(), segments_to_poly.cend(), edge1.cell()->source_index()));	55,551,800✔
174	}	52,774,210✔
175
176	linestring_type_fp Voronoi::edge_to_linestring(const edge_type& edge, const vector<segment_type_p>& segments, const box_type_fp& bounding_box, coordinate_type max_dist) {	13,255,160✔
177	linestring_type_fp new_voronoi_edge;	13,255,160!
178	if (edge.is_finite()) {	13,255,160✔
179	if (edge.is_linear()) {	13,255,160✔
180	new_voronoi_edge.push_back(point_type_fp(edge.vertex0()->x(),	7,343,952✔
181	edge.vertex0()->y()));	6,994,240✔
182	new_voronoi_edge.push_back(point_type_fp(edge.vertex1()->x(),	6,994,240✔
183	edge.vertex1()->y()));	6,994,240✔
184	} else {	6,644,528✔
185	// It's a curve, it needs sampling.
186	vector<point_type_fp_p> sampled_edge;	6,260,920✔
187	sample_curved_edge(&edge, segments, sampled_edge, max_dist);	6,260,920✔
188	for (const auto& point : sampled_edge) {	14,057,486✔
189	new_voronoi_edge.push_back(point_type_fp(point.x(), point.y()));	13,744,440✔
190	}	13,057,218✔
191	}	6,260,920✔
192	} else {	12,592,402✔
193	// Infinite edge, only make it if it is inside the bounding_box.
UNCOV 194	if ((edge.vertex0() == NULL \|\|	×
UNCOV 195	bg::covered_by(point_type(edge.vertex0()->x(), edge.vertex0()->y()),	×
196	bounding_box)) &&	×
UNCOV 197	(edge.vertex1() == NULL \|\|	×
198	bg::covered_by(point_type(edge.vertex1()->x(), edge.vertex1()->y()),	×
199	bounding_box))) {
200	vector<point_type_fp_p> clipped_edge;	×
201	clip_infinite_edge(	×
202	edge, segments, &clipped_edge, bounding_box);
203	for (const auto& point : clipped_edge) {	×
204	new_voronoi_edge.push_back(point_type_fp(point.x(), point.y()));	×
205	}
206	}	×
207	}
208	return new_voronoi_edge;	13,255,160✔
209	}	12,592,402✔
210
211	// Make segments from the ring and put them in segments.
212	void Voronoi::copy_ring(const ring_type& ring, vector<segment_type_p> &segments)	3,730✔
213	{	70,870✔
214	for (auto iter = ring.begin(); iter + 1 != ring.end(); iter++) {	5,008,360✔
215	segments.push_back(segment_type_p(point_type_p(iter->x(), iter->y()),	4,933,760✔
216	point_type_p((iter + 1)->x(), (iter + 1)->y())));	5,180,448✔
217	}	4,687,072✔
218	}	74,600✔
219
220	point_type_p Voronoi::retrieve_point(const cell_type& cell, const vector<segment_type_p> &segments) {	6,260,920✔
221	source_index_type index = cell.source_index();	6,260,920✔
222	source_category_type category = cell.source_category();	6,260,920✔
223
224	if (category == boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT)	6,260,920✔
225	return boost::polygon::low(segments[index]);	3,058,120✔
226	else	3,042,660✔
227	return boost::polygon::high(segments[index]);	3,202,800✔
228	}	5,947,874✔
229
230	const segment_type_p& Voronoi::retrieve_segment(const cell_type& cell, const vector<segment_type_p> &segments) {	6,260,920✔
231	source_index_type index = cell.source_index();	6,095,498✔
232	return segments[index];	6,260,920✔
233	}	5,947,874✔
234
235	void Voronoi::sample_curved_edge(const edge_type *edge, const vector<segment_type_p> &segments,	313,046✔
236	vector<point_type_fp_p>& sampled_edge, coordinate_type_fp max_dist) {	5,947,874✔
237
238	point_type_p point = edge->cell()->contains_point() ?	6,260,920✔
239	retrieve_point(*(edge->cell()), segments) :	2,952,480✔
240	retrieve_point(*(edge->twin()->cell()), segments);	6,113,296✔
241
242	const segment_type_p& segment = edge->cell()->contains_point() ?	6,260,920✔
243	retrieve_segment(*(edge->twin()->cell()), segments) :	2,952,480✔
244	retrieve_segment(*(edge->cell()), segments);	6,113,296✔
245
246	sampled_edge.push_back(point_type_fp_p(edge->vertex0()->x(), edge->vertex0()->y()));	6,260,920✔
247	sampled_edge.push_back(point_type_fp_p(edge->vertex1()->x(), edge->vertex1()->y()));	6,260,920✔
248	boost::polygon::voronoi_visual_utils<coordinate_type_fp>::discretize(point, segment, max_dist, &sampled_edge);	6,260,920✔
249	}	6,260,920✔
250
251	void Voronoi::clip_infinite_edge(
252	const edge_type& edge, const vector<segment_type_p>& segments, std::vector<point_type_fp_p>* clipped_edge, const box_type_fp& bounding_box) {
253	const cell_type& cell1 = *edge.cell();	×
254	const cell_type& cell2 = *edge.twin()->cell();	×
255	point_type_p origin, direction;	×
256	// Infinite edges could not be created by two segment sites.
257	if (cell1.contains_point() && cell2.contains_point()) {	×
258	point_type_p p1 = retrieve_point(cell1, segments);	×
259	point_type_p p2 = retrieve_point(cell2, segments);	×
260	origin.x((p1.x() + p2.x()) * 0.5);	×
261	origin.y((p1.y() + p2.y()) * 0.5);	×
262	direction.x(p1.y() - p2.y());	×
263	direction.y(p2.x() - p1.x());	×
264	} else {
265	origin = cell1.contains_segment() ?	×
266	retrieve_point(cell2, segments) :
267	retrieve_point(cell1, segments);	×
268	segment_type_p segment = cell1.contains_segment() ?	×
269	retrieve_segment(cell1, segments) :	×
270	retrieve_segment(cell2, segments);	×
271	coordinate_type dx = high(segment).x() - low(segment).x();	×
272	coordinate_type dy = high(segment).y() - low(segment).y();	×
273	if ((low(segment) == origin) ^ cell1.contains_point()) {	×
274	direction.x(dy);	×
275	direction.y(-dx);	×
276	} else {
277	direction.x(-dy);	×
278	direction.y(dx);	×
279	}
280	}
281	coordinate_type side = bounding_box.max_corner().x() - bounding_box.min_corner().x();	×
282	coordinate_type koef =	×
283	side / std::max(std::abs(direction.x()), std::abs(direction.y()));	×
284	if (edge.vertex0() == NULL) {	×
285	clipped_edge->push_back(point_type_fp_p(	×
286	origin.x() - direction.x() * koef,	×
287	origin.y() - direction.y() * koef));	×
288	} else {
289	clipped_edge->push_back(	×
290	point_type_fp_p(edge.vertex0()->x(), edge.vertex0()->y()));	×
291	}
292	if (edge.vertex1() == NULL) {	×
293	clipped_edge->push_back(point_type_fp_p(	×
294	origin.x() + direction.x() * koef,	×
295	origin.y() + direction.y() * koef));	×
296	} else {
297	clipped_edge->push_back(	×
298	point_type_fp_p(edge.vertex1()->x(), edge.vertex1()->y()));	×
299	}
300	}	×

pcb2gcode / pcb2gcode / 23511030556

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous