RFR: 8274066: Polygon filled outside its area when very large coordinates are used [v2]

[Johan Vos]

On Mon, 10 Jan 2022 00:04:00 GMT, Laurent Bourgès <lbourges at openjdk.org> wrote:

>> Changelog for this MarlinFX 0.9.4.5 release:
>> 
>> The Marlin-renderer 0.9.4.5 release provides bug fixes on Marlin's path clipper:
>> - improved Stroker to handle huge coordinates, up to 1E15
>> - improved PathClipFilter (filler) to handle huge coordinates, up to 1E15
>> 
>> 
>> This is the Marlin-renderer 0.9.4.3 release providing few bug / enhancement fixes in the MarlinRenderingEngine:
>> - Update DPQS to latest OpenJDK 14 patch
>> - Improve cubic curve offset computation
>> 
>> 
>> The Marlin-renderer 0.9.4.2 release provides a single long-standing bug fix in the MarlinRenderingEngine: 
>> - JDK-8230728, https://bugs.openjdk.java.net/browse/JDK-8230728.
>> 
>> 
>> Marlin-renderer 0.9.4.1 provides only a single bug fix in the path clipper, reported first against JavaFX 11: 
>> - JDK-8226789, https://bugs.openjdk.java.net/browse/JDK-8226789.
>> 
>> 
>> This is the Marlin-renderer 0.9.4 release providing an updated Dual Pivot Quick Sort (19.05) as its internal sorter faster than the Marlin's optimized MergeSort (x-position + edge indices) for arrays larger than 256.
>> 
>> Special Thanks to Vladimir Yaroslavskiy that provided me up-to-date DPQS 19.05 with many variants, improving almost-sorted datasets. We are collaborating to provide a complete Sort framework (15 algorithms, many various datasets, JMH benchmarks) publicly on github:
>> see https://github.com/bourgesl/nearly-optimal-mergesort-code
>
> Laurent Bourgès has updated the pull request incrementally with one additional commit since the last revision:
> 
>   added test for huge polygon coords

Building and testing works, I am looking into the diffs as well now. 
The DualPivotQuicksort20191112Ext seems to be an improved version of what is in java.util. Ideally, we can somehow extend or leverage the version in java.util without duplicating the original code.
For testing: one of the tests I would like to do is to see if the complexity increases as expected when increasing coordinates. Since the original Dual-Pivot quicksort has O(n log(n)) time complexity, it should be possible to have an upper bound on the number of invocations.

-------------

PR: https://git.openjdk.java.net/jfx/pull/674