Skip to content
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.

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

Add test suite for approximation code, fix edge cases #138

Closed
hannobraun opened this issue Feb 7, 2022 · 1 comment · Fixed by #159
Closed

Add test suite for approximation code, fix edge cases #138

hannobraun opened this issue Feb 7, 2022 · 1 comment · Fixed by #159
Assignees
Labels
topic: core Issues relating to core geometry, operations, algorithms type: bug Something isn't working type: development Work to ease development or maintenance, without direct effect on features or bugs

Comments

@hannobraun
Copy link
Owner

The approximation code queries the geometry for approximate points, then processes and aggregates these points, depending on the type of edges.

I've cleaned this up recently, but I suspect there's at least one unaddressed edge case in there. We should have a comprehensive test suite for this code, possibly move it to a dedicated module, and make sure we cover edge cases as best as possible.


Here's the unaddressed edge case that I suspect needs addressing.

Point de-duplication depends on consistent edge direction

When approximating an edge, the approximation will include the two points that bound the edge. When approximating a whole cycle of connected edges, this will lead to duplicated points that need to be filtered out.

Currently, the points are in a Vec and Vec::dedup is called to filter out duplicates. However, this won't work if the direction of edges is inconsistent. For example, if you have the straight edges a -> b, b -> c, then the duplicate b will be correctly filtered. If the edges are a -> b, c -> b, on the other hand, then one of the bs must still be filtered, but that won't happen.

@hannobraun hannobraun added type: bug Something isn't working type: development Work to ease development or maintenance, without direct effect on features or bugs topic: core Issues relating to core geometry, operations, algorithms labels Feb 7, 2022
@hannobraun hannobraun self-assigned this Feb 7, 2022
hannobraun added a commit that referenced this issue Feb 9, 2022
This is the edge case being tracked in #138.
hannobraun added a commit that referenced this issue Feb 9, 2022
This is the edge case being tracked in #138.
@hannobraun
Copy link
Owner Author

Turns out the edge case I mentioned here was worse than I thought: The problem would even show up when edge direction was perfectly consistent, as the first vertex and the last vertex weren't recognized as duplicates (even though, the edges forming a cycle, those were identical).

It's been fixed in #158.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
topic: core Issues relating to core geometry, operations, algorithms type: bug Something isn't working type: development Work to ease development or maintenance, without direct effect on features or bugs
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant