Cura polygon.cpp, 4.13 vs 5.0
बनाया गया Diff कभी समाप्त नहीं होता
6 हटाए गए
| लाइनें | |
|---|---|
| कुल | |
| हटाया गया | |
| अक्षर | |
| कुल | |
| हटाया गया | |
90 जोड़े गए
| लाइनें | |
|---|---|
| कुल | |
| जोड़ा गया | |
| अक्षर | |
| कुल | |
| जोड़ा गया | |
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;
if (!processing_polylines || (point_idx != 0 && point_idx + 1 != size()))
{ // bypass all checks for deleting a vertex when processing the start or end of a polyline
const coord_t length2 = vSize2(current - previous);
const coord_t length2 = vSize2(current - previous);
if (length2 < 25)
if (length2 < 25)
{
{
// We're allowed to always delete segments of less than 5 micron.
// We're allowed to always delete segments of less than 5 micron.
continue;
continue;
}
}
const coord_t area_removed_so_far = accumulated_area_removed + negative_area_closing; // close the shortcut area polygon
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);
const coord_t base_length_2 = vSize2(next - previous);
if (base_length_2 == 0) //Two line segments form a line back and forth with no area.
if (base_length_2 == 0) //Two line segments form a line back and forth with no area.
{
{
continue; //Remove the vertex.
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.
//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
//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]
//A = 1/2 * b * h [triangle area formula]
//L = b * h [apply above two and take out the 1/2]
//L = b * h [apply above two and take out the 1/2]
//h = L / b [divide by b]
//h = L / b [divide by b]
//h^2 = (L / b)^2 [square it]
//h^2 = (L / b)^2 [square it]
//h^2 = L^2 / b^2 [factor the divisor]
//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;
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).
if ((height_2 <= 5 * 5 //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
&& LinearAlg2D::getDistFromLine(current, previous, next) <= 5)) // make sure that height_2 is not small because of cancellation of positive and negative areas
{
{
continue;
continue;
}
}
if (length2 < smallest_line_segment_squared
if (length2 < smallest_line_segment_squared
&& height_2 <= allowed_error_distance_squared) // removing the vertex doesn't introduce too much error.)
&& height_2 <= allowed_error_distance_squared) // removing the vertex doesn't introduce too much error.)
{
{
const coord_t next_length2 = vSize2(current - next);
const coord_t next_length2 = vSize2(current - next);
if (next_length2 > smallest_line_segment_squared)
if (next_length2 > 4 * 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.
// Special case; The next line is long. If we were to remove this, it could happen that we get quite noticeable artifacts.
// 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.
// 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).
// 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.
// We just need to be sure that the intersection point does not introduce an artifact itself.
Point intersection_point;
Point intersection_point;
bool has_intersection = LinearAlg2D::lineLineIntersection(previous_previous, previous, current, next, intersection_point);
bool has_intersection = LinearAlg2D::lineLineIntersection(previous_previous, previous, current, next, intersection_point);
if (!has_intersection
if (!has_intersection
|| LinearAlg2D::getDist2FromLine(intersection_point, previous, current) > allowed_error_distance_squared
|| 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 - 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'
|| 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.
// 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...
// So the only thing we can do here is leave it in...
}
}
else
else
{
{
// New point seems like a valid one.
// New point seems like a valid one.
current = intersection_point;
current = intersection_point;
// If there was a previous point added, remove it.
// If there was a previous point added, remove it.
if(!new_path.empty())
if (!new_path.empty()
&& (!processing_polylines || new_path.size() > 1) // never delete the first point of a polyline
)
{
{
new_path.pop_back();
new_path.pop_back();
previous = previous_previous;
previous = previous_previous;
}
}
}
}
}
}
else
else
{
{
continue; //Remove the vertex.
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;
}
}