func (ec *earcut) locallyInside(a, b *node) bool {
	if ec.area(a.prev, a, a.next) < 0 {
		return ec.area(a, b, a.next) >= 0 && ec.area(a, a.prev, b) >= 0
	}
	return ec.area(a, b, a.prev) < 0 || ec.area(a, a.next, b) < 0
}
check if a polygon diagonal is locally inside the polygon
package canvas
import (
	"math"
	"sort"
	"github.com/tfriedel6/canvas/backend/backendbase"
)
type node struct {
	i    int
	x, y float64
	prev *node
	next *node
	z int
	prevZ *node
	nextZ *node
	steiner bool
}
type earcut struct {
	indices    []int
	vertices   int
	hashing    bool
	minX, minY float64
	maxX, maxY float64
	invSize    float64
	nodes      []node
}
func (ec *earcut) run(points [][]backendbase.Vec) {
	if len(points) == 0 {
		return
	}
	var x, y float64
	threshold := 80
	ln := 0
	for i := 0; threshold >= 0 && i < len(points); i++ {
		threshold -= len(points[i])
		ln += len(points[i])
	}
	ec.nodes = make([]node, 0, ln*3/2)
	ec.indices = make([]int, 0, ln+len(points[0]))
	ec.vertices = 0
	outerNode := ec.linkedList(points[0], true)
	if outerNode == nil || outerNode.prev == outerNode.next {
		return
	}
	if len(points) > 1 {
		outerNode = ec.eliminateHoles(points, outerNode)
	}
	ec.hashing = threshold < 0
	if ec.hashing {
		p := outerNode.next
		ec.minX, ec.maxX = outerNode.x, outerNode.x
		ec.minY, ec.maxY = outerNode.y, outerNode.y
		for {
			x = p.x
			y = p.y
			ec.minX = math.Min(ec.minX, x)
			ec.minY = math.Min(ec.minY, y)
			ec.maxX = math.Min(ec.maxX, x)
			ec.maxY = math.Min(ec.maxY, y)
			p = p.next
			if p != outerNode {
				break
			}
		}
		ec.invSize = math.Max(ec.maxX-ec.minX, ec.maxY-ec.minY)
		if ec.invSize != 0 {
			ec.invSize = 1 / ec.invSize
		}
	}
	ec.earcutLinked(outerNode, 0)
	ec.nodes = ec.nodes[:0]
}
func (ec *earcut) linkedList(points []backendbase.Vec, clockwise bool) *node {
	var sum float64
	ln := len(points)
	var i, j int
	var last *node
	if ln > 0 {
		j = ln - 1
	}
	for i < ln {
		p1 := points[i]
		p2 := points[j]
		p20 := p2[0]
		p10 := p1[0]
		p11 := p1[1]
		p21 := p2[1]
		sum += (p20 - p10) * (p11 + p21)
		j = i
		i++
	}
	if clockwise == (sum > 0) {
		for i := 0; i < ln; i++ {
			last = ec.insertNode(ec.vertices+i, points[i], last)
		}
	} else {
		for i = ln - 1; i >= 0; i-- {
			last = ec.insertNode(ec.vertices+i, points[i], last)
		}
	}
	if last != nil && ec.equals(last, last.next) {
		ec.removeNode(last)
		last = last.next
	}
	ec.vertices += ln
	return last
}
func (ec *earcut) filterPoints(start, end *node) *node {
	if end == nil {
		end = start
	}
	p := start
	var again bool
	for {
		again = false
		if !p.steiner && (ec.equals(p, p.next) || ec.area(p.prev, p, p.next) == 0) {
			ec.removeNode(p)
			p, end = p.prev, p.prev
			if p == p.next {
				break
			}
			again = true
		} else {
			p = p.next
		}
		if !again && p == end {
			break
		}
	}
	return end
}
func (ec *earcut) earcutLinked(ear *node, pass int) {
	if ear == nil {
		return
	}
	if pass == 0 && ec.hashing {
		ec.indexCurve(ear)
	}
	stop := ear
	var prev, next *node
	iterations := 0
	for ear.prev != ear.next {
		iterations++
		prev = ear.prev
		next = ear.next
		var e bool
		if ec.hashing {
			e = ec.isEarHashed(ear)
		} else {
			e = ec.isEar(ear)
		}
		if e {
			ec.indices = append(ec.indices, prev.i, ear.i, next.i)
			ec.removeNode(ear)
			ear = next.next
			stop = next.next
			continue
		}
		ear = next
		if ear == stop {
			if pass == 0 {
				ec.earcutLinked(ec.filterPoints(ear, nil), 1)
			} else if pass == 1 {
				ear = ec.cureLocalIntersections(ec.filterPoints(ear, nil))
				ec.earcutLinked(ear, 2)
			} else if pass == 2 {
				ec.splitEarcut(ear)
			}
			break
		}
	}
}
func (ec *earcut) isEar(ear *node) bool {
	a := ear.prev
	b := ear
	c := ear.next
	if ec.area(a, b, c) >= 0 {
		return false  
	}
	p := ear.next.next
	for p != ear.prev {
		if ec.pointInTriangle(a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y) &&
			ec.area(p.prev, p, p.next) >= 0 {
			return false
		}
		p = p.next
	}
	return true
}
func (ec *earcut) isEarHashed(ear *node) bool {
	a := ear.prev
	b := ear
	c := ear.next
	if ec.area(a, b, c) >= 0 {
		return false  
	}
	minTX := math.Min(a.x, math.Min(b.x, c.x))
	minTY := math.Min(a.y, math.Min(b.y, c.y))
	maxTX := math.Max(a.x, math.Max(b.x, c.x))
	maxTY := math.Max(a.y, math.Max(b.y, c.y))
	minZ := ec.zOrder(minTX, minTY)
	maxZ := ec.zOrder(maxTX, maxTY)
	p := ear.nextZ
	for p != nil && p.z <= maxZ {
		if p != ear.prev && p != ear.next &&
			ec.pointInTriangle(a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y) &&
			ec.area(p.prev, p, p.next) >= 0 {
			return false
		}
		p = p.nextZ
	}
	p = ear.prevZ
	for p != nil && p.z >= minZ {
		if p != ear.prev && p != ear.next &&
			ec.pointInTriangle(a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y) &&
			ec.area(p.prev, p, p.next) >= 0 {
			return false
		}
		p = p.prevZ
	}
	return true
}
func (ec *earcut) cureLocalIntersections(start *node) *node {
	p := start
	for {
		a := p.prev
		b := p.next.next
		if !ec.equals(a, b) && ec.intersects(a, p, p.next, b) && ec.locallyInside(a, b) && ec.locallyInside(b, a) {
			ec.indices = append(ec.indices, a.i, p.i, b.i)
			ec.removeNode(p)
			ec.removeNode(p.next)
			p, start = b, b
		}
		p = p.next
		if p == start {
			break
		}
	}
	return ec.filterPoints(p, nil)
}
func (ec *earcut) splitEarcut(start *node) {
	a := start
	for {
		b := a.next.next
		for b != a.prev {
			if a.i != b.i && ec.isValidDiagonal(a, b) {
				c := ec.splitPolygon(a, b)
				a = ec.filterPoints(a, a.next)
				c = ec.filterPoints(c, c.next)
				ec.earcutLinked(a, 0)
				ec.earcutLinked(c, 0)
				return
			}
			b = b.next
		}
		a = a.next
		if a == start {
			break
		}
	}
}
func (ec *earcut) eliminateHoles(points [][]backendbase.Vec, outerNode *node) *node {
	ln := len(points)
	queue := make([]*node, 0, ln)
	for i := 1; i < ln; i++ {
		list := ec.linkedList(points[i], false)
		if list != nil {
			if list == list.next {
				list.steiner = true
			}
			queue = append(queue, ec.getLeftmost(list))
		}
	}
	sort.Slice(queue, func(a, b int) bool {
		return queue[a].x < queue[b].x
	})
	for i := 0; i < len(queue); i++ {
		ec.eliminateHole(queue[i], outerNode)
		outerNode = ec.filterPoints(outerNode, outerNode.next)
	}
	return outerNode
}
func (ec *earcut) eliminateHole(hole, outerNode *node) {
	outerNode = ec.findHoleBridge(hole, outerNode)
	if outerNode != nil {
		b := ec.splitPolygon(outerNode, hole)
		ec.filterPoints(outerNode, outerNode.next)
		ec.filterPoints(b, b.next)
	}
}
func (ec *earcut) findHoleBridge(hole, outerNode *node) *node {
	p := outerNode
	hx := hole.x
	hy := hole.y
	qx := math.Inf(-1)
	var m *node
	for {
		if hy <= p.y && hy >= p.next.y && p.next.y != p.y {
			x := p.x + (hy-p.y)*(p.next.x-p.x)/(p.next.y-p.y)
			if x <= hx && x > qx {
				qx = x
				if x == hx {
					if hy == p.y {
						return p
					}
					if hy == p.next.y {
						return p.next
					}
				}
				if p.x < p.next.x {
					m = p
				} else {
					m = p.next
				}
			}
		}
		p = p.next
		if p == outerNode {
			break
		}
	}
	if m == nil {
		return nil
	}
	if hx == qx {
		return m  
	}
	stop := m
	tanMin := math.Inf(1)
	tanCur := 0.0
	p = m
	mx := m.x
	my := m.y
	for {
		var pt1, pt2 float64
		if hy < my {
			pt1 = hx
			pt2 = qx
		} else {
			pt1 = qx
			pt2 = hx
		}
		if hx >= p.x && p.x >= mx && hx != p.x &&
			ec.pointInTriangle(pt1, hy, mx, my, pt2, hy, p.x, p.y) {
			tanCur = math.Abs(hy-p.y) / (hx - p.x)  
			if ec.locallyInside(p, hole) &&
				(tanCur < tanMin || (tanCur == tanMin && (p.x > m.x || ec.sectorContainsSector(m, p)))) {
				m = p
				tanMin = tanCur
			}
		}
		p = p.next
		if p == stop {
			break
		}
	}
	return m
}
func (ec *earcut) sectorContainsSector(m, p *node) bool {
	return ec.area(m.prev, m, p.prev) < 0 && ec.area(p.next, m, m.next) < 0
}
func (ec *earcut) indexCurve(start *node) {
	if start == nil {
		panic("start must not be nil")
	}
	p := start
	for {
		if p.z <= 0 {
			p.z = ec.zOrder(p.x, p.y)
		}
		p.prevZ = p.prev
		p.nextZ = p.next
		p = p.next
		if p == start {
			break
		}
	}
	p.prevZ.nextZ = nil
	p.prevZ = nil
	ec.sortLinked(p)
}
func (ec *earcut) sortLinked(list *node) *node {
	if list == nil {
		panic("list must not be nil")
	}
	var p, q, e, tail *node
	var i, numMerges, pSize, qSize int
	inSize := 1
	for {
		p = list
		list = nil
		tail = nil
		numMerges = 0
		for p != nil {
			numMerges++
			q = p
			pSize = 0
			for i = 0; i < inSize; i++ {
				pSize++
				q = q.nextZ
				if q == nil {
					break
				}
			}
			qSize = inSize
			for pSize > 0 || (qSize > 0 && q != nil) {
				if pSize == 0 {
					e = q
					q = q.nextZ
					qSize--
				} else if qSize == 0 || q == nil {
					e = p
					p = p.nextZ
					pSize--
				} else if p.z <= q.z {
					e = p
					p = p.nextZ
					pSize--
				} else {
					e = q
					q = q.nextZ
					qSize--
				}
				if tail != nil {
					tail.nextZ = e
				} else {
					list = e
				}
				e.prevZ = tail
				tail = e
			}
			p = q
		}
		tail.nextZ = nil
		if numMerges <= 1 {
			return list
		}
		inSize *= 2
	}
}
func (ec *earcut) zOrder(x, y float64) int {
	x2 := int(32767.0 * (x - ec.minX) * ec.invSize)
	y2 := int(32767.0 * (y - ec.minY) * ec.invSize)
	x2 = (x2 | (x2 << 8)) & 0x00FF00FF
	x2 = (x2 | (x2 << 4)) & 0x0F0F0F0F
	x2 = (x2 | (x2 << 2)) & 0x33333333
	x2 = (x2 | (x2 << 1)) & 0x55555555
	y2 = (y2 | (y2 << 8)) & 0x00FF00FF
	y2 = (y2 | (y2 << 4)) & 0x0F0F0F0F
	y2 = (y2 | (y2 << 2)) & 0x33333333
	y2 = (y2 | (y2 << 1)) & 0x55555555
	return x2 | (y2 << 1)
}
func (ec *earcut) getLeftmost(start *node) *node {
	p := start
	leftmost := start
	for {
		if p.x < leftmost.x || (p.x == leftmost.x && p.y < leftmost.y) {
			leftmost = p
		}
		p = p.next
		if p == start {
			break
		}
	}
	return leftmost
}
func (ec *earcut) pointInTriangle(ax, ay, bx, by, cx, cy, px, py float64) bool {
	return (cx-px)*(ay-py)-(ax-px)*(cy-py) >= 0 &&
		(ax-px)*(by-py)-(bx-px)*(ay-py) >= 0 &&
		(bx-px)*(cy-py)-(cx-px)*(by-py) >= 0
}
func (ec *earcut) isValidDiagonal(a, b *node) bool {
	return a.next.i != b.i && a.prev.i != b.i && !ec.intersectsPolygon(a, b) &&  
		((ec.locallyInside(a, b) && ec.locallyInside(b, a) && ec.middleInside(a, b) &&  
			(ec.area(a.prev, a, b.prev) != 0.0 || ec.area(a, b.prev, b) != 0.0)) ||  
			(ec.equals(a, b) && ec.area(a.prev, a, a.next) > 0 && ec.area(b.prev, b, b.next) > 0))  
}
func (ec *earcut) area(p, q, r *node) float64 {
	return (q.y-p.y)*(r.x-q.x) - (q.x-p.x)*(r.y-q.y)
}
func (ec *earcut) equals(p1, p2 *node) bool {
	return p1.x == p2.x && p1.y == p2.y
}
func (ec *earcut) intersects(p1, q1, p2, q2 *node) bool {
	o1 := ec.sign(ec.area(p1, q1, p2))
	o2 := ec.sign(ec.area(p1, q1, q2))
	o3 := ec.sign(ec.area(p2, q2, p1))
	o4 := ec.sign(ec.area(p2, q2, q1))
	if o1 != o2 && o3 != o4 {
		return true  
	}
	if o1 == 0 && ec.onSegment(p1, p2, q1) {
		return true
	}
	if o2 == 0 && ec.onSegment(p1, q2, q1) {
		return true
	}
	if o3 == 0 && ec.onSegment(p2, p1, q2) {
		return true
	}
	if o4 == 0 && ec.onSegment(p2, q1, q2) {
		return true
	}
	return false
}
func (ec *earcut) onSegment(p, q, r *node) bool {
	return q.x <= math.Max(p.x, r.x) &&
		q.x >= math.Min(p.x, r.x) &&
		q.y <= math.Max(p.y, r.y) &&
		q.y >= math.Min(p.y, r.y)
}
func (ec *earcut) sign(val float64) int {
	if val < 0 {
		return -1
	} else if val > 0 {
		return 1
	}
	return 0
}
func (ec *earcut) intersectsPolygon(a, b *node) bool {
	p := a
	for {
		if p.i != a.i && p.next.i != a.i && p.i != b.i && p.next.i != b.i &&
			ec.intersects(p, p.next, a, b) {
			return true
		}
		p = p.next
		if p == a {
			break
		}
	}
	return false
}