Skip to content

Add an assertion to ClipperOffset::Group::Group checking that the lowest path has non-zero area #965

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
wants to merge 1 commit into from
Closed

Add an assertion to ClipperOffset::Group::Group checking that the lowest path has non-zero area #965

wants to merge 1 commit into from

Conversation

reunanen
Copy link
Contributor

@reunanen reunanen commented May 1, 2025

I am using InflatePaths, and I had the following problem that took a long time to figure out:

Background

The Group constructor currently needs to figure out if exteriors are clockwise and holes are counter-clockwise, or the other way around. It accomplishes this by finding the lowest path (=the one having the highest y coordinate), because that must be an outer path, and by checking if its area is positive or negative.

Problem

Now if the lowest path contains only 1 or 2 points, or otherwise has zero area, and the paths are indeed "reversed", then the above logic does not work as intended.

It wouldn't be a problem to simply drop such degenerate paths, but the issue is that if the same group contains also non-degenerate, large, significant paths, they may effectively be dropped as well. This is exactly what was sometimes happening in my use case. (Just for the record, my workaround was to weed such degenerate paths from the input, before calling InflatePaths. Very easy once I knew what exactly the problem was, but to get to that point took quite a while...)

(Where would such degenerate paths come from? I think for example from calling OpenCV's findContours for 1- or 2-pixel regions.)

What this PR does

This PR just adds an assert that should detect if the input data is such that the logic can't really work as intended. Having this available would have saved me a lot of time, so I thought it might help others who may be providing similar input data. Generally asserts are no-op in Release builds, so Release builds should remain unaffected. Alternatively, one could throw a std::logic_error or similar, but I guess that doing so would be more intrusive and might break applications that are currently working (although they would be "working" only if the paths are not reversed).

Alternative solutions

For clarity, I think it might be best to let the user explicitly provide the orientation also in the offset case (similar to the "main" clipping functionality, such as intersection), instead of trying to figure it out from the input data. (Should be a tad faster, too?)

Another alternative would be to find the lowest path that has non-zero area (instead of just the lowest path).

Angus, if you like either of the above suggestions, I can try and prepare an alternative PR.

Unrelated remark

(There is also a cosmetic spaces vs tabs issue here in this location, but I tried to keep the diff minimal and not start fixing that, at least for the time being.)

@AngusJohnson
Copy link
Owner

AngusJohnson commented May 3, 2025 •
edited
Loading

Hi again Juha. Thanks for not only identifying a bug, but also proposing a sensible fix.
I think I'd prefer to fix the GetLowestClosedPathIdx function so that it ignores paths with 0 areas.

std::optional<size_t> GetLowestClosedPathIdx(const Paths64& paths)
{
    std::optional<size_t> result;
	Point64 botPt = Point64(INT64_MAX, INT64_MIN);
	for (size_t i = 0; i < paths.size(); ++i)
	{
		for (const Point64& pt : paths[i])
		{
			if ((pt.y < botPt.y) || 
				((pt.y == botPt.y) && (pt.x >= botPt.x))) continue;
			if (Area(paths[i]) == 0) break; // break from inner loop
                        result = i;
			botPt.x = pt.x;
			botPt.y = pt.y;
		}
	}
	return result;
}

@reunanen
Copy link
Contributor Author

reunanen commented May 4, 2025

Hi Angus, thank you for your answer.

I think I'd prefer to fix the GetLowestClosedPathIdx function so that it ignores paths with 0 areas.

Yea, works for me.

However, maybe you don't want to keep evaluating Area(paths[i]) in the inner loop again and again?

Maybe just an if (Area(paths[i]) == 0) continue; at the top of the outer loop?

AngusJohnson added a commit that referenced this pull request May 4, 2025
@AngusJohnson
Fixed incorrect Polytree ownership following clipping op. (#957)
e8ebdef 
Fixed obscure clipper offset bug (PR #965)
@AngusJohnson
Copy link
Owner

AngusJohnson commented May 4, 2025 •
edited
Loading

However, maybe you don't want to keep evaluating Area(paths[i]) in the inner loop again and again?
Maybe just an if (Area(paths[i]) == 0) continue; at the top of the outer loop?

I really do want to avoid evaluating the area of every path, just paths that meet the current lowest criteria in the outer loop.
But in composing my reply to you now, I can now see the mistake you are alluding too. OOPS!

@AngusJohnson AngusJohnson reopened this May 4, 2025
AngusJohnson added a commit that referenced this pull request May 4, 2025
@AngusJohnson
Fixed a performance bug introduced in very recent commit (PR #965)
f8dced5
@AngusJohnson
Copy link
Owner

Hopefully all fixed now 🤞.

@reunanen
Copy link
Contributor Author

reunanen commented May 4, 2025

Thank you Angus! I tested the updated version, and as far I can tell it fixes the problem (and I can now remove my workaround).

@reunanen reunanen deleted the add-assertion-to-offset-group-constructor-checking-that-lowest-path-has-non-zero-area branch May 4, 2025 17:14
reunanen added a commit to reunanen/Clipper2 that referenced this pull request May 4, 2025
@reunanen
Add regression test for AngusJohnson#965
6a13cb8
@reunanen reunanen mentioned this pull request May 4, 2025
Merged
AngusJohnson pushed a commit that referenced this pull request May 4, 2025
@reunanen
Add regression test for #965 (#972)
1ef1da4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@reunanen @AngusJohnson