Ultimaker / CuraEngine

Powerful, fast and robust engine for converting 3D models into g-code instructions for 3D printers. It is part of the larger open source project Cura.

https://ultimaker.com/en/products/cura-software

GNU Affero General Public License v3.0

1.66k stars 874 forks source link

Fix some convex hull related issues #2011

Closed casperlamboo closed 5 months ago

casperlamboo commented 5 months ago

Description

Previously we tried to be cheeky and cut some corners by implementing “Andrew’s Monotone Chain Convex Hull Algorithm” without sorting points. However, turns out we need to sort as we did run into some edge cases where this wouldn't work.

CURA-11395

Type of change

[x] Bug fix (non-breaking change which fixes an issue)
[ ] New feature (non-breaking change which adds functionality)

How Has This Been Tested?

yes

Test Configuration:

Operating System: MacOS 13.3

Checklist:

[x] My code follows the style guidelines of this project as described in UltiMaker Meta
[x] I have read the Contribution guide
[x] I have commented my code, particularly in hard-to-understand areas
[x] I have uploaded any files required to test this change