Generate a fan triangulation for convex polygons

csiro-coasts / emsarray

xarray extension that supports EMS model formats

BSD 3-Clause "New" or "Revised" License

13 stars 2 forks source link

Generate a fan triangulation for convex polygons #151

Closed mx-moth closed 1 week ago

mx-moth commented 1 month ago

The ear clipping method is correct for all polygons, but slow. For convex polygons a fan triangulation is much quicker. Most polygons will be convex. For an example dataset this sped up triangulation on my machine from around 6 seconds to 1 second.

david-sh-csiro commented 3 weeks ago

When tested with MoVE we saw the following improvements.

v0.7.0 time

Time elapsed during the process: 4.897634860997641

Time elapsed during the process: 4.988207356000203

Optimised Triangulation time

Time elapsed during the process: 1.4324180190014886

Time elapsed during the process: 1.7977412979998917

I haven't noticed any regressions in MoVE, however MoVE was previously using emsarray 0.4.1.

frizwi commented 3 weeks ago

I'm getting similar speed ups to David, so for the larger National model data, they go from ~5mins down to 1.5 mins