Cura polygon.cpp, 4.13 vs 5.0
64 removals
| Words removed | 411 |
| Total words | 865 |
| Words removed (%) | 47.51 |
130 lines
86 additions
| Words added | 505 |
| Total words | 959 |
| Words added (%) | 52.66 |
147 lines
void PolygonRef::simplify(const coord_t smallest_line_segment_squared, const coord_t allowed_error_distance_squared)
void PolygonRef::_simplify(const coord_t smallest_line_segment_squared, const coord_t allowed_error_distance_squared, bool processing_polylines)
{
{
if (size() < 3)
const size_t min_poly_length = processing_polylines ? 2 : 3;
if (size() < min_poly_length)
{
{
clear();
clear();
return;
return;
}
}
if (size() == 3)
if (size() == min_poly_length)
{
{
return;
return;
}
}
ClipperLib::Path new_path;
ClipperLib::Path new_path;
Point previous = path->back();
Point previous = path->back();
Point previous_previous = path->at(path->size() - 2);
Point previous_previous = path->at(path->size() - 2);
Point current = path->at(0);
Point current = path->at(0);
/* When removing a vertex, we check the height of the triangle of the area
/* When removing a vertex, we check the height of the triangle of the area
being removed from the original polygon by the simplification. However,
being removed from the original polygon by the simplification. However,
when consecutively removing multiple vertices the height of the previously
when consecutively removing multiple vertices the height of the previously
removed vertices w.r.t. the shortcut path changes.
removed vertices w.r.t. the shortcut path changes.
In order to not recompute the new height value of previously removed
In order to not recompute the new height value of previously removed
vertices we compute the height of a representative triangle, which covers
vertices we compute the height of a representative triangle, which covers
the same amount of area as the area being cut off. We use the Shoelace
the same amount of area as the area being cut off. We use the Shoelace
formula to accumulate the area under the removed segments. This works by
formula to accumulate the area under the removed segments. This works by
computing the area in a 'fan' where each of the blades of the fan go from
computing the area in a 'fan' where each of the blades of the fan go from
the origin to one of the segments. While removing vertices the area in
the origin to one of the segments. While removing vertices the area in
this fan accumulates. By subtracting the area of the blade connected to
this fan accumulates. By subtracting the area of the blade connected to
the short-cutting segment we obtain the total area of the cutoff region.
the short-cutting segment we obtain the total area of the cutoff region.
From this area we compute the height of the representative triangle using
From this area we compute the height of the representative triangle using
the standard formula for a triangle area: A = .5*b*h
the standard formula for a triangle area: A = .5*b*h
*/
*/
coord_t accumulated_area_removed = previous.X * current.Y - previous.Y * current.X; // Twice the Shoelace formula for area of polygon per line segment.
coord_t accumulated_area_removed = previous.X * current.Y - previous.Y * current.X; // Twice the Shoelace formula for area of polygon per line segment.
for (size_t point_idx = 0; point_idx < size(); point_idx++)
for (size_t point_idx = 0; point_idx < size(); point_idx++)
{
{
current = path->at(point_idx % size());
current = path->at(point_idx % size());
//Check if the accumulated area doesn't exceed the maximum.
//Check if the accumulated area doesn't exceed the maximum.
Point next;
Point next;
if (point_idx + 1 < size())
if (point_idx + 1 < size())
{
{
next = path->at(point_idx + 1);
next = path->at(point_idx + 1);
}
}
else if (point_idx + 1 == size() && new_path.size() > 1)
else if (point_idx + 1 == size() && new_path.size() > 1)
{ // don't spill over if the [next] vertex will then be equal to [previous]
{ // don't spill over if the [next] vertex will then be equal to [previous]
next = new_path[0]; //Spill over to new polygon for checking removed area.
next = new_path[0]; //Spill over to new polygon for checking removed area.
}
}
else
else
{
{
next = path->at((point_idx + 1) % size());
next = path->at((point_idx + 1) % size());
}
}
const coord_t removed_area_next = current.X * next.Y - current.Y * next.X; // Twice the Shoelace formula for area of polygon per line segment.
const coord_t removed_area_next = current.X * next.Y - current.Y * next.X; // Twice the Shoelace formula for area of polygon per line segment.
const coord_t negative_area_closing = next.X * previous.Y - next.Y * previous.X; // area between the origin and the short-cutting segment
const coord_t negative_area_closing = next.X * previous.Y - next.Y * previous.X; // area between the origin and the short-cutting segment
accumulated_area_removed += removed_area_next;
accumulated_area_removed += removed_area_next;
const coord_t length2 = vSize2(current - previous);
if (length2 < 25)
{
// We're allowed to always delete segments of less than 5 micron.
continue;
}
const coord_t area_removed_so_far = accumulated_area_removed + negative_area_closing; // close the shortcut area polygon
if (!processing_polylines || (point_idx != 0 && point_idx + 1 != size()))
const coord_t base_length_2 = vSize2(next - previous);
{ // bypass all checks for deleting a vertex when processing the start or end of a polyline
const coord_t length2 = vSize2(current - previous);
if (length2 < 25)
{
// We're allowed to always delete segments of less than 5 micron.
continue;
}
if (base_length_2 == 0) //Two line segments form a line back and forth with no area.
const coord_t area_removed_so_far = accumulated_area_removed + negative_area_closing; // close the shortcut area polygon
{
const coord_t base_length_2 = vSize2(next - previous);
continue; //Remove the vertex.
}
//We want to check if the height of the triangle formed by previous, current and next vertices is less than allowed_error_distance_squared.
//1/2 L = A [actual area is half of the computed shoelace value] // Shoelace formula is .5*(...) , but we simplify the computation and take out the .5
//A = 1/2 * b * h [triangle area formula]
//L = b * h [apply above two and take out the 1/2]
//h = L / b [divide by b]
//h^2 = (L / b)^2 [square it]
//h^2 = L^2 / b^2 [factor the divisor]
const coord_t height_2 = area_removed_so_far * area_removed_so_far / base_length_2;
if ((height_2 <= 1 //Almost exactly colinear (barring rounding errors).
&& LinearAlg2D::getDistFromLine(current, previous, next) <= 1)) // make sure that height_2 is not small because of cancellation of positive and negative areas
{
continue;
}
if (length2 < smallest_line_segment_squared
if (base_length_2 == 0) //Two line segments form a line back and forth with no area.
&& height_2 <= allowed_error_distance_squared) // removing the vertex doesn't introduce too much error.)
{
const coord_t next_length2 = vSize2(current - next);
if (next_length2 > smallest_line_segment_squared)
{
{
// Special case; The next line is long. If we were to remove this, it could happen that we get quite noticeable artifacts.
continue; //Remove the vertex.
// We should instead move this point to a location where both edges are kept and then remove the previous point that we wanted to keep.
}
// By taking the intersection of these two lines, we get a point that preserves the direction (so it makes the corner a bit more pointy).
//We want to check if the height of the triangle formed by previous, current and next vertices is less than allowed_error_distance_squared.
// We just need to be sure that the intersection point does not introduce an artifact itself.
//1/2 L = A [actual area is half of the computed shoelace value] // Shoelace formula is .5*(...) , but we simplify the computation and take out the .5
Point intersection_point;
//A = 1/2 * b * h [triangle area formula]
bool has_intersection = LinearAlg2D::lineLineIntersection(previous_previous, previous, current, next, intersection_point);
//L = b * h [apply above two and take out the 1/2]
if (!has_intersection
//h = L / b [divide by b]
|| LinearAlg2D::getDist2FromLine(intersection_point, previous, current) > allowed_error_distance_squared
//h^2 = (L / b)^2 [square it]
|| vSize2(intersection_point - previous) > smallest_line_segment_squared // The intersection point is way too far from the 'previous'
//h^2 = L^2 / b^2 [factor the divisor]
|| vSize2(intersection_point - next) > smallest_line_segment_squared) // and 'next' points, so it shouldn't replace 'current'
const coord_t height_2 = area_removed_so_far * area_removed_so_far / base_length_2;
if ((height_2 <= 5 * 5 //Almost exactly colinear (barring rounding errors).
&& LinearAlg2D::getDistFromLine(current, previous, next) <= 5)) // make sure that height_2 is not small because of cancellation of positive and negative areas
{
continue;
}
if (length2 < smallest_line_segment_squared
&& height_2 <= allowed_error_distance_squared) // removing the vertex doesn't introduce too much error.)
{
const coord_t next_length2 = vSize2(current - next);
if (next_length2 > 4 * smallest_line_segment_squared)
{
{
// We can't find a better spot for it, but the size of the line is more than 5 micron.
// Special case; The next line is long. If we were to remove this, it could happen that we get quite noticeable artifacts.
// So the only thing we can do here is leave it in...
// We should instead move this point to a location where both edges are kept and then remove the previous point that we wanted to keep.
// By taking the intersection of these two lines, we get a point that preserves the direction (so it makes the corner a bit more pointy).
// We just need to be sure that the intersection point does not introduce an artifact itself.
Point intersection_point;
bool has_intersection = LinearAlg2D::lineLineIntersection(previous_previous, previous, current, next, intersection_point);
if (!has_intersection
|| LinearAlg2D::getDist2FromLine(intersection_point, previous, current) > allowed_error_distance_squared
|| vSize2(intersection_point - previous) > smallest_line_segment_squared // The intersection point is way too far from the 'previous'
|| vSize2(intersection_point - next) > smallest_line_segment_squared) // and 'next' points, so it shouldn't replace 'current'
{
// We can't find a better spot for it, but the size of the line is more than 5 micron.
// So the only thing we can do here is leave it in...
}
else
{
// New point seems like a valid one.
current = intersection_point;
// If there was a previous point added, remove it.
if (!new_path.empty()
&& (!processing_polylines || new_path.size() > 1) // never delete the first point of a polyline
)
{
new_path.pop_back();
previous = previous_previous;
}
}
}
}
else
else
{
{
// New point seems like a valid one.
continue; //Remove the vertex.
current = intersection_point;
// If there was a previous point added, remove it.
if(!new_path.empty())
{
new_path.pop_back();
previous = previous_previous;
}
}
}
}
}
else
{
continue; //Remove the vertex.
}
}
}
//Don't remove the vertex.
//Don't remove the vertex.
accumulated_area_removed = removed_area_next; // so that in the next iteration it's the area between the origin, [previous] and [current]
accumulated_area_removed = removed_area_next; // so that in the next iteration it's the area between the origin, [previous] and [current]
previous_previous = previous;
previous_previous = previous;
previous = current; //Note that "previous" is only updated if we don't remove the vertex.
previous = current; //Note that "previous" is only updated if we don't remove the vertex.
new_path.push_back(current);
new_path.push_back(current);
}
}
if (processing_polylines)
{ // make sure the last segment is not 5u short
size_t second_to_last_idx = new_path.size() - 2;
if (vSize2(new_path.back() - new_path[second_to_last_idx]) < 25)
{
new_path.erase(new_path.begin() + second_to_last_idx);
}
}
*path = new_path;
*path = new_path;
}
}