(function(r,i){typeof exports=="object"&&typeof module<"u"?module.exports=i():typeof define=="function"&&define.amd?define(i):(r=typeof globalThis<"u"?globalThis:r||self,r.GrahamScan=i())})(this,function(){"use strict";var N=Object.defineProperty;var T=(r,i,y)=>i in r?N(r,i,{enumerable:!0,configurable:!0,writable:!0,value:y}):r[i]=y;var m=(r,i,y)=>(T(r,typeof i!="symbol"?i+"":i,y),y);const r=Number.parseFloat("0.000005");class i{constructor(){m(this,"vertices",[])}setVertices(e){this.vertices=e}static isValid(e){return e!=null&&isFinite(e)&&!isNaN(e)}getStartingHullPoint(){let e=-1;for(let c=0;c<this.vertices.length;c++)i.isValid(this.vertices[c].x)&&i.isValid(this.vertices[c].y)&&(e===-1||this.vertices[c].y<this.vertices[e].y||this.vertices[c].y===this.vertices[e].y&&this.vertices[c].x<this.vertices[e].x)&&(e=c);return e===-1?void 0:this.vertices[e]}static ccw(e,c,f){return(c.x-e.x)*(f.y-e.y)-(f.x-e.x)*(c.y-e.y)}generateHull(e){if(this.vertices.length===0)return[];if(this.vertices.length===1)return[this.vertices[0]];const c=(e==null?void 0:e.numericalErrorTolerance)??r,f=Number((e==null?void 0:e.includeCollinearVerts)??!1)*-2+1,h=+((e==null?void 0:e.walkDirection)==="cw")*-2+1,t=this.getStartingHullPoint();if(!t)return[];const x=[t],d=this.vertices.filter(n=>!(n.x===t.x&&n.y===t.y)&&i.isValid(n.x)&&i.isValid(n.y));d.sort((n,s)=>h*(s.x-t.x)*(n.y-t.y)-h*(n.x-t.x)*(s.y-t.y));const p=n=>{let s=x.length;for(;s>1&&h*i.ccw(x[s-2],x[s-1],n)<f*c;)s--;x.splice(s,1/0,n)};let l,V=!0;const b=n=>{let s;V?(s=1,V=!1):n?s=-1:s=0,f===-1&&s!==0?l.sort((o,u)=>s*((o.x-t.x)**2+(o.y-t.y)**2)-s*((u.x-t.x)**2+(u.y-t.y)**2)):f!==-1&&(l=[l.reduce((o,u)=>(o.x-t.x)**2+(o.y-t.y)**2>(u.x-t.x)**2+(u.y-t.y)**2?o:u)])};for(let n=0;n<d.length;n++){const s=d[n];if(l!==void 0){const o=l[0],u=s;if(Math.abs((u.x-t.x)*(o.y-t.y)-(o.x-t.x)*(u.y-t.y))<c){l.push(s);continue}b(),l.forEach(a=>p(a))}l=[s]}return b(!0),l==null||l.forEach(n=>p(n)),x}}return i});