Offset distance violation on arcs

[olologin]

Its me again :)

Some of polygonized arc segments in the offset output are violating offset distance significantly.
Clipper1 on the same input was not violating it for more than 1.5 units of distance.
Clipper2 violates it on 14470.2 units of distance.

Red is input, green is output, blue points on arcs is where polygonization violates distance.
Somehow only subset of arcs has these problems.

Test (As always, add this to your unit tests please):

TEST(Clipper2Tests, OffsetDistanceViolationOnArcs)
{
	auto GetDistanceViolators = [](
		Clipper2Lib::Path64& distanceViolators,
		const Clipper2Lib::Path64& input,
		const Clipper2Lib::Path64& output,
		const double desiredDist,
		const double scaledTol)
	{
		const int stepsAlongSegment = 10;
		double maxDeviation = 0;

                // For each output point (and interpolated subpoints in output) find closest point on input
                // Put this (sub)point into distanceViolators vector if distance is too far away from desiredDist
		for (size_t resIdx = 0; resIdx + 1 < output.size(); ++resIdx)
		{
			const auto outPtA = output[resIdx];
			const auto outPtB = output[resIdx + 1];

			for (int step = 0; step <= stepsAlongSegment; ++step)
			{
				const auto outPt =
					outPtA + (outPtB - outPtA) * (static_cast<double>(step) / stepsAlongSegment);
				double minSqrDist = std::numeric_limits<double>::infinity();
				Clipper2Lib::Point64 sourcePt;

				for (size_t i = 0; i + 1 < input.size(); ++i)
				{
					const Clipper2Lib::Point64 a = input[i];
					const Clipper2Lib::Point64 b = input[i + 1];
					const auto closestPt = Clipper2Lib::GetClosestPointOnSegment(outPt, a, b);
					const double sqrDist = Clipper2Lib::DistanceSqr(outPt, closestPt);
					if (sqrDist < minSqrDist)
					{
						//sourcePt = closestPt;
						minSqrDist = sqrDist;
					}
				}

				if (!std::isinf(minSqrDist))
				{
					const double minDist = std::sqrt(minSqrDist);
					maxDeviation = std::max(maxDeviation, std::abs(minDist - desiredDist));
					if (std::abs(minDist - desiredDist) > scaledTol)
					{
						distanceViolators.push_back(outPt);
						//distanceViolators.push_back(sourcePt);
					}
				}
			}
		}
		return maxDeviation;
	};

	Clipper2Lib::Paths64 tmpSubject = {
		{{91759700, -49711991},    {83886095, -50331657},
		 {-872415388, -50331657},  {-880288993, -49711991},  {-887968725, -47868251},
		 {-895265482, -44845834},  {-901999593, -40719165},  {-908005244, -35589856},
		 {-913134553, -29584205},  {-917261224, -22850094},  {-920283639, -15553337},
		 {-922127379, -7873605},   {-922747045, 0},          {-922747045, 1434498600},
		 {-922160557, 1442159790}, {-920414763, 1449642437}, {-917550346, 1456772156},
		 {-913634061, 1463382794}, {-908757180, 1469320287}, {-903033355, 1474446264},
		 {-896595982, 1478641262}, {-889595081, 1481807519}, {-882193810, 1483871245},
		 {-876133965, 1484596521}, {-876145751, 1484713389}, {-875781839, 1485061090},
		 {-874690056, 1485191762}, {-874447580, 1485237014}, {-874341490, 1485264094},
		 {-874171960, 1485309394}, {-873612294, 1485570372}, {-873201878, 1485980788},
		 {-872941042, 1486540152}, {-872893274, 1486720070}, {-872835064, 1487162210},
		 {-872834788, 1487185500}, {-872769052, 1487406000}, {-872297948, 1487583168},
		 {-871995958, 1487180514}, {-871995958, 1486914040}, {-871908872, 1486364208},
		 {-871671308, 1485897962}, {-871301302, 1485527956}, {-870835066, 1485290396},
		 {-870285226, 1485203310}, {-868659019, 1485203310}, {-868548443, 1485188472},
		 {-868239649, 1484791011}, {-868239527, 1484783879}, {-838860950, 1484783879},
		 {-830987345, 1484164215}, {-823307613, 1482320475}, {-816010856, 1479298059},
		 {-809276745, 1475171390}, {-803271094, 1470042081}, {-752939437, 1419710424},
		 {-747810128, 1413704773}, {-743683459, 1406970662}, {-740661042, 1399673904},
		 {-738817302, 1391994173}, {-738197636, 1384120567}, {-738197636, 1244148246},
		 {-738622462, 1237622613}, {-739889768, 1231207140}, {-802710260, 995094494},
		 {-802599822, 995052810},  {-802411513, 994586048},  {-802820028, 993050638},
		 {-802879992, 992592029},  {-802827240, 992175479},  {-802662144, 991759637},
		 {-802578556, 991608039},  {-802511951, 991496499},  {-801973473, 990661435},
		 {-801899365, 990554757},  {-801842657, 990478841},  {-801770997, 990326371},
		 {-801946911, 989917545},  {-801636397, 989501855},  {-801546099, 989389271},
		 {-800888669, 988625013},  {-800790843, 988518907},  {-800082405, 987801675},
		 {-799977513, 987702547},  {-799221423, 987035738},  {-799109961, 986944060},
		 {-798309801, 986330832},  {-798192297, 986247036},  {-797351857, 985690294},
		 {-797228867, 985614778},  {-796352124, 985117160},  {-796224232, 985050280},
		 {-795315342, 984614140},  {-795183152, 984556216},  {-794246418, 984183618},
		 {-794110558, 984134924},  {-793150414, 983827634},  {-793011528, 983788398},
		 {-792032522, 983547874},  {-791891266, 983518284},  {-790898035, 983345662},
		 {-790755079, 983325856},  {-789752329, 983221956},  {-789608349, 983212030},
		 {-787698545, 983146276},  {-787626385, 983145034},  {-536871008, 983145034},
		 {-528997403, 982525368},  {-521317671, 980681627},  {-514020914, 977659211},
		 {-507286803, 973532542},  {-501281152, 968403233},  {-496151843, 962397582},
		 {-492025174, 955663471},  {-489002757, 948366714},  {-487159017, 940686982},
		 {-486539351, 932813377},  {-486539351, 667455555},  {-486537885, 667377141},
		 {-486460249, 665302309},  {-486448529, 665145917},  {-486325921, 664057737},
		 {-486302547, 663902657},  {-486098961, 662826683},  {-486064063, 662673784},
		 {-485780639, 661616030},  {-485734413, 661466168},  {-485372735, 660432552},
		 {-485315439, 660286564},  {-484877531, 659282866},  {-484809485, 659141568},
		 {-484297795, 658173402},  {-484219379, 658037584},  {-483636768, 657110363},
		 {-483548422, 656980785},  {-482898150, 656099697},  {-482800368, 655977081},
		 {-482086070, 655147053},  {-481979398, 655032087},  {-481205068, 654257759},
		 {-481090104, 654151087},  {-480260074, 653436789},  {-480137460, 653339007},
		 {-479256372, 652688735},  {-479126794, 652600389},  {-478199574, 652017779},
		 {-478063753, 651939363},  {-477095589, 651427672},  {-476954289, 651359626},
		 {-475950593, 650921718},  {-475804605, 650864422},  {-474770989, 650502744},
		 {-474621127, 650456518},  {-473563373, 650173094},  {-473410475, 650138196},
		 {-472334498, 649934610},  {-472179420, 649911236},  {-471091240, 649788626},
		 {-470934848, 649776906},  {-468860016, 649699272},  {-468781602, 649697806},
		 {-385876037, 649697806},  {-378002432, 649078140},  {-370322700, 647234400},
		 {-363025943, 644211983},  {-356291832, 640085314},  {-350286181, 634956006},
		 {-345156872, 628950354},  {-341030203, 622216243},  {-338007786, 614919486},
		 {-336164046, 607239755},  {-335544380, 599366149},  {-335544380, 571247184},
		 {-335426942, 571236100},  {-335124952, 570833446},  {-335124952, 569200164},
		 {-335037864, 568650330},  {-334800300, 568184084},  {-334430294, 567814078},
		 {-333964058, 567576517},  {-333414218, 567489431},  {-331787995, 567489431},
		 {-331677419, 567474593},  {-331368625, 567077133},  {-331368503, 567070001},
		 {-142068459, 567070001},  {-136247086, 566711605},  {-136220070, 566848475},
		 {-135783414, 567098791},  {-135024220, 567004957},  {-134451560, 566929159},
		 {-134217752, 566913755},  {-133983942, 566929159},  {-133411282, 567004957},
		 {-132665482, 567097135},  {-132530294, 567091859},  {-132196038, 566715561},
		 {-132195672, 566711157},  {-126367045, 567070001},  {-33554438, 567070001},
		 {-27048611, 566647761},   {-20651940, 565388127},   {-14471751, 563312231},
		 {-8611738, 560454902},    {36793963, 534548454},    {43059832, 530319881},
		 {48621743, 525200596},    {53354240, 519306071},    {57150572, 512769270},
		 {59925109, 505737634},    {61615265, 498369779},    {62182919, 490831896},
		 {62182919, 474237629},    {62300359, 474226543},    {62602349, 473823889},
		 {62602349, 472190590},    {62689435, 471640752},    {62926995, 471174516},
		 {63297005, 470804506},    {63763241, 470566946},    {64313081, 470479860},
		 {65939308, 470479860},    {66049884, 470465022},    {66358678, 470067562},
		 {66358800, 470060430},    {134217752, 470060430},   {134217752, 0},
		 {133598086, -7873605},    {131754346, -15553337},   {128731929, -22850094},
		 {124605260, -29584205},   {119475951, -35589856},   {113470300, -40719165},
		 {106736189, -44845834},   {99439432, -47868251},    {91759700, -49711991}}};

	const double offset = -50329979.277800001;

	Clipper2Lib::Paths64 pathsC2;

	Clipper2Lib::ClipperOffset offseter(2, 0.25);
	offseter.AddPaths(tmpSubject, Clipper2Lib::JoinType::Round, Clipper2Lib::EndType::Polygon);

	offseter.Execute(offset, pathsC2);
	
	/*
        // Uncomment if you want to check Clipper1 results
        ClipperLib::Paths tmpSubjectOld = {{}};
	for (const auto& pt : tmpSubject[0])
	{
		tmpSubjectOld[0].emplace_back(pt.x, pt.y);
	}

	ClipperLib::ClipperOffset offsetterOld(2, 0.25);
	offsetterOld.AddPaths(
		tmpSubjectOld, ClipperLib::JoinType::jtRound, ClipperLib::EndType::etClosedPolygon);
	ClipperLib::Paths pathsOld;
	offsetterOld.Execute(pathsOld, offset);

	pathsC2 = {{}};
	for (const auto& pt : pathsOld[0])
	{
		pathsC2[0].emplace_back(pt.X, pt.Y);
	}
        */

	pathsC2[0].push_back(pathsC2[0].front());
	Clipper2Lib::Path64 distanceViolators;
	auto maxDeviation =
		GetDistanceViolators(distanceViolators, tmpSubject[0], pathsC2[0], std::abs(offset), 2);
	std::cout << "Max offset deviation from desired offset value: " << maxDeviation << std::endl;
	ASSERT_TRUE(maxDeviation < 2);
}

[AngusJohnson]

Firstly, the purpose of the arc tolerance parameter (with offsetting) is to allow users to specify what they consider a sensible compromise between achieving curve quality (with rounded offsets) while avoiding generating excessive numbers of vertices. And in your example above you are generating a huge (and arguably excessive) numbers of vertices. These will seriously degrade performance (eg in offsetting, in rendering, an in storage), and almost certainly won't achieve any detectable improvement in arc quality.

Further, arc precision is premised on the assumption that arcs will be starting exactly where they're meant to start. And that's not the case here, so the imprecision that you are seeing is unrelated to arc quality. The offset imprecision is very small - less than 0.03% of the offset delta. And setting join_type = JoinType::Bevel, where offsetting should always be less than or equal delta, still somehow causes some offsetting to exceed delta (though again by about 0.03%).

So I am still investigating why there is even this small amount of offsetting imprecision, and it's unlikely just due to rounding errors.

More info on arc tolerance here.

[olologin]

Thanks for your explanation,
I understand that this may look wrong to you, but I am not trying to nitpick issues in this library.

Just to give you some context:
In our case, with our scaling we see a difference between:
~8e-8 mm deviation with Clipper1
~8e-4 mm deviation with Clipper2

This difference is significant for us.

[mmassing]

I had a similiar observation with an older version of Clipper2, where Clipper2 would tesselate the offset using DoSquare if the angle was small enough - leading to high error. I suspect something similar might be happening, although the logic has changed in the meantime.

diff --git a/CPP/Clipper2Lib/src/clipper.offset.cpp b/CPP/Clipper2Lib/src/clipper.offset.cpp
index 0cae6d8..ae0fb41 100644
--- a/CPP/Clipper2Lib/src/clipper.offset.cpp
+++ b/CPP/Clipper2Lib/src/clipper.offset.cpp
@@ -320,7 +320,7 @@ void ClipperOffset::OffsetPoint(Group& group, Path64& path, size_t j, size_t& k)
        else if (cos_a > 0.9998) 
                // almost straight - less than 1 degree (#424) 
                DoMiter(group, path, j, k, cos_a);
-       else if (cos_a > 0.99 || join_type_ == JoinType::Square)
+       else if (join_type_ == JoinType::Square)
                //angle less than 8 degrees or squared joins
                DoSquare(group, path, j, k);
        else
-- 
2.39.2

[AngusJohnson]

Replace:

Clipper2/CPP/Clipper2Lib/src/clipper.offset.cpp

Lines 412 to 415 in 9299eb6

	else if (cos_a > 0.999) // almost straight - less than 2.5 degree (#424, #526)
	{
	DoMiter(path, j, k, cos_a);
	}

with:

	else if (cos_a > 0.999) // almost straight - less than 2.5 degree (#424, #526) 
	{
		path_out.push_back(GetPerpendic(path[j], norms[k], group_delta_));
		path_out.push_back(GetPerpendic(path[j], norms[j], group_delta_));
		//DoMiter(path, j, k, cos_a);
	}

and replace:

Clipper2/CPP/Clipper2Lib/src/clipper.offset.cpp

Lines 422 to 424 in 9299eb6

	else if (cos_a > 0.99 || join_type_ == JoinType::Bevel)
	// ie > 2.5 deg (see above) but less than ~8 deg ( acos(0.99) )
	DoBevel(path, j, k);

with:

	else if (/*cos_a > 0.99 ||*/ join_type_ == JoinType::Bevel) 
	// cos_a > 0.99 here improves performance with extremely minor reduction in accuracy
	// acos(0.99) == 8.1 deg. still a small angle but not as small as cos_a > 0.999 (see above)
		DoBevel(path, j, k);

[AngusJohnson]

I'm confident that this is now fixed. Thank you for your patience and persistence.

[olologin]

I apologize for a bit of criticism, but I hope this will lead to some good result in the end:

Regarding your test: Your test is not fully correct because you are measuring distance from output points to the input segments. While in reality quality of result is measured by measuring distance from output segments to the input the segments.
I mean on your own picture here:
(https://www.angusj.com/clipper2/Docs/Trigonometry.htm)
You measure L (which is the desired maximal imprecision) from the middle of your output segment to the ideal circle representation, because this is the biggest imprecision and it is the correct way to measure it. You don't measure it from a or b to circle.
The same applies to offset, you have to measure distance from any point of output segment to any point of input segment, and the maximal difference of this value with offset is your error.
My test that measures distance from subpoints of the output to the input segments is much better approximation in this sense.

Regarding precision after your fix: It is 2 times better now, I think you had the same result couple of months ago. But it is still 8k of imprecision according to the original test (vs 1.5 of imprecision in Clipper1).
And in our product I still visually see 5e-4 mm difference between Clipper2 result and Clipper1/ideal offset.
By "ideal offset" I mean offset that doesnt polygonize arcs and saves as much precision as possible.

I just fail to understand why you dont consider this as a problem? From my point of view it is a problem because Clipper1 could produce much more precise result than Clipper2, and what is worse - this problem is not happening everywhere. Most of the time Clipper1 and Clipper2 results are almost identical, but from time to time we get into problems because some subsegments of result are having this bad precision.

[olologin]

In case you try to measure distance correctly, here is your modified code:

template <typename T>
struct OffsetQual
{
	double smallestDist;
	double largestDist;
	Clipper2Lib::Point<T> ptSmallestIn;
	Clipper2Lib::Point<T> ptSmallestOut;
	Clipper2Lib::Point<T> ptLargestIn;
	Clipper2Lib::Point<T> ptLargestOut;
	double standardDev;
};

template <typename T>
static OffsetQual<T> GetOffsetQuality(
	const Clipper2Lib::Path<T>& input, const Clipper2Lib::Path<T>& output, const double desiredDist)
{
	if (!input.size() || !output.size())
		return OffsetQual<T>();

	const double desiredDistSqr = desiredDist * desiredDist;
	const size_t stepsAlongSegment = 10;

	OffsetQual<T> oq{desiredDistSqr, desiredDistSqr, {0, 0}, {0, 0}, {0, 0}, {0, 0}, 0};

	double deviationsSqr = 0;
	for (size_t outPtIdx = 0; outPtIdx + 1 < output.size(); ++outPtIdx)
	{
		double closestDistSqr = std::numeric_limits<double>::infinity();

		Clipper2Lib::Point<T> in_prev = input[input.size() - 1];
		Clipper2Lib::Point<T> closestPtIn = {0, 0};
		Clipper2Lib::Point<T> closestPtOut = {0, 0};

		for (size_t step = 0; step < stepsAlongSegment; ++step)
		{
			const auto outPt = output[outPtIdx]
				+ (output[outPtIdx + 1] - output[outPtIdx]) * (static_cast<double>(step) / stepsAlongSegment);

			for (size_t i = 0; i < input.size(); ++i)
			{
				Clipper2Lib::Point<T> cp =
					Clipper2Lib::GetClosestPointOnSegment(outPt, input[i], in_prev);
				in_prev = input[i];
				const double sqrDist = Clipper2Lib::DistanceSqr(cp, outPt);
				if (sqrDist < closestDistSqr)
				{
					closestDistSqr = sqrDist;
					closestPtIn = cp;
					closestPtOut = outPt;
				};
			}

			if (closestDistSqr < oq.smallestDist)
			{
				oq.smallestDist = closestDistSqr;
				oq.ptSmallestIn = closestPtIn;
				oq.ptSmallestOut = closestPtOut;
			}
			if (closestDistSqr > oq.largestDist)
			{
				oq.largestDist = closestDistSqr;
				oq.ptLargestIn = closestPtIn;
				oq.ptLargestOut = closestPtOut;
			}
		}
		// we now have smallestDistSqr between outPt and the input path
		double offset_qual = std::sqrt(closestDistSqr) - desiredDist;
		deviationsSqr += offset_qual * offset_qual;
	}
	oq.smallestDist = std::sqrt(oq.smallestDist);
	oq.largestDist = std::sqrt(oq.largestDist);
	oq.standardDev = std::sqrt(deviationsSqr / (stepsAlongSegment  * input.size()));
	return oq;
}

[AngusJohnson]

I apologize for a bit of criticism, but I hope this will lead to some good result in the end:

I'm always happy for constructive criticism, though I do appreciate the warning 😜😁.

Regarding your test: Your test is not fully correct because you are measuring distance from output points to the input segments. While in reality quality of result is measured by measuring distance from output segments to the input the segments. I mean on your own picture here: (https://www.angusj.com/clipper2/Docs/Trigonometry.htm) You measure L (which is the desired maximal imprecision) from the middle of your output segment to the ideal circle representation, because this is the biggest imprecision and it is the correct way to measure it. You don't measure it from a or b to circle. The same applies to offset, you have to measure distance from any point of output segment to any point of input segment, and the maximal difference of this value with offset is your error. My test that measures distance from subpoints of the output to the input segments is much better approximation in this sense.

You are right that both input and output paths should be assessed for segment proximity rather than vertex proximity. And I agree that my GetOffsetQuality() function was only measuring output vertex distances from input segments, not output segments from input segments. And indeed this needs fixing as you've proposed.

I modified your original offset testing code because I was focusing on why there were these unexplained discrepancies in offsetting, though I was confident it wasn't coming from my arc approximation code. So my focus was on where rounding started and ended. And as it turned out the discrepancies I've found weren't coming from arcs but from where I tried to avoid creating segments of almost no length (and improve performance). I had assumed (incorrectly) that these tweaks would have no measurable effect on offset quality.

I'm keen, of course, to ensure that Clipper2 is at least as good as Clipper1 in offsetting precision. Until now I had assumed that it was (notwithstanding the various bugs I introduced and fixed while trying to improve performance). So could you please post examples where Clipper2 offsetting still isn't right?

[olologin]

So could you please post examples where Clipper2 offsetting still isn't right?

So far I only have my original problem. Here is its updated version that is just modified version of your test that you merged today (I added it to txt file to not take too much space here).
If you uncomment clipper1 code you will see the difference.

original_test_updated.txt

I will try to measure the distance between Clipper1 and Clipper2 on the rest of our inputs, maybe I will find other good samples. I noticed issue in this sample only because our algorithm that is based on Clipper2 now fails on one of our tests near those arcs.

[olologin]

In case you take that test from the txt file, last assertion has to be replaced by:

	ASSERT_TRUE(std::abs(std::abs(offset) - offset_qual.smallestDist) < 2);
	ASSERT_TRUE(std::abs(std::abs(offset) - offset_qual.largestDist) < 2);

[AngusJohnson]

Replace:

Clipper2/CPP/Clipper2Lib/src/clipper.offset.cpp

Lines 412 to 423 in 906bc1d

	else if (cos_a > 0.999) // almost straight - less than 2.5 degree (#424, #526)
	{
	// with ::Round, preserving near exact delta is more important than simpler paths
	// See also Issues #424, #526 #482
	if (join_type_ == JoinType::Round)
	{
	path_out.push_back(GetPerpendic(path[j], norms[k], group_delta_));
	path_out.push_back(GetPerpendic(path[j], norms[j], group_delta_));
	}
	else
	DoMiter(path, j, k, cos_a);
	}

with:

	else if (cos_a > 0.999 && join_type_ != JoinType::Round) 
	{
		// almost straight - less than 2.5 degree (#424, #482 & #526) 
		DoMiter(path, j, k, cos_a);
	}

[olologin]

Yes, it solves the issue :)

[olologin]

Thanks for your fix. This discussion can now be closed.