package canvas import ( "math" "sort" "github.com/tfriedel6/canvas/backend/backendbase" ) // Go port of https://github.com/mapbox/earcut.hpp type node struct { i int x, y float64 // previous and next vertice nodes in a polygon ring prev *node next *node // z-order curve value z int // previous and next nodes in z-order prevZ *node nextZ *node // indicates whether this is a steiner point 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]) } //estimate size of nodes and indices 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) } // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox 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 } } // minX, minY and size are later used to transform coords into integers for z-order calculation 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] } // create a circular doubly linked list from polygon points in the specified winding order func (ec *earcut) linkedList(points []backendbase.Vec, clockwise bool) *node { var sum float64 ln := len(points) var i, j int var last *node // calculate original winding order of a polygon ring 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++ } // link points into circular doubly-linked list in the specified winding order 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 } // eliminate colinear or duplicate points 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 } // main ear slicing loop which triangulates a polygon (given as a linked list) func (ec *earcut) earcutLinked(ear *node, pass int) { if ear == nil { return } // interlink polygon nodes in z-order if pass == 0 && ec.hashing { ec.indexCurve(ear) } stop := ear var prev, next *node iterations := 0 // iterate through ears, slicing them one by one 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 { // cut off the triangle ec.indices = append(ec.indices, prev.i, ear.i, next.i) ec.removeNode(ear) // skipping the next vertice leads to less sliver triangles ear = next.next stop = next.next continue } ear = next // if we looped through the whole remaining polygon and can't find any more ears if ear == stop { // try filtering points and slicing again if pass == 0 { ec.earcutLinked(ec.filterPoints(ear, nil), 1) } else if pass == 1 { // if this didn't work, try curing all small self-intersections locally ear = ec.cureLocalIntersections(ec.filterPoints(ear, nil)) ec.earcutLinked(ear, 2) } else if pass == 2 { // as a last resort, try splitting the remaining polygon into two ec.splitEarcut(ear) } break } } } // check whether a polygon node forms a valid ear with adjacent nodes func (ec *earcut) isEar(ear *node) bool { a := ear.prev b := ear c := ear.next if ec.area(a, b, c) >= 0 { return false // reflex, can't be an ear } // now make sure we don't have other points inside the potential ear 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 // reflex, can't be an ear } // triangle bbox; min & max are calculated like this for speed 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)) // z-order range for the current triangle bbox; minZ := ec.zOrder(minTX, minTY) maxZ := ec.zOrder(maxTX, maxTY) // first look for points inside the triangle in increasing z-order 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 } // then look for points in decreasing z-order 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 } // go through all polygon nodes and cure small local self-intersections func (ec *earcut) cureLocalIntersections(start *node) *node { p := start for { a := p.prev b := p.next.next // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2]) 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) // remove two nodes involved ec.removeNode(p) ec.removeNode(p.next) p, start = b, b } p = p.next if p == start { break } } return ec.filterPoints(p, nil) } // try splitting polygon into two and triangulate them independently func (ec *earcut) splitEarcut(start *node) { // look for a valid diagonal that divides the polygon into two a := start for { b := a.next.next for b != a.prev { if a.i != b.i && ec.isValidDiagonal(a, b) { // split the polygon in two by the diagonal c := ec.splitPolygon(a, b) // filter colinear points around the cuts a = ec.filterPoints(a, a.next) c = ec.filterPoints(c, c.next) // run earcut on each half ec.earcutLinked(a, 0) ec.earcutLinked(c, 0) return } b = b.next } a = a.next if a == start { break } } } // link every hole into the outer loop, producing a single-ring polygon without holes 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 }) // process holes from left to right for i := 0; i < len(queue); i++ { ec.eliminateHole(queue[i], outerNode) outerNode = ec.filterPoints(outerNode, outerNode.next) } return outerNode } // find a bridge between vertices that connects hole with an outer ring and and link it func (ec *earcut) eliminateHole(hole, outerNode *node) { outerNode = ec.findHoleBridge(hole, outerNode) if outerNode != nil { b := ec.splitPolygon(outerNode, hole) // filter out colinear points around cuts ec.filterPoints(outerNode, outerNode.next) ec.filterPoints(b, b.next) } } // David Eberly's algorithm for finding a bridge between hole and outer polygon func (ec *earcut) findHoleBridge(hole, outerNode *node) *node { p := outerNode hx := hole.x hy := hole.y qx := math.Inf(-1) var m *node // find a segment intersected by a ray from the hole's leftmost Vertex to the left; // segment's endpoint with lesser x will be potential connection Vertex 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 // hole touches outer segment; pick leftmost endpoint } // look for points inside the triangle of hole Vertex, segment intersection and endpoint; // if there are no points found, we have a valid connection; // otherwise choose the Vertex of the minimum angle with the ray as connection Vertex 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) // tangential 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 } // whether sector in vertex m contains sector in vertex p in the same coordinates 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 } // interlink polygon nodes in z-order 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) } // Simon Tatham's linked list merge sort algorithm // http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html 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 } } // z-order of a Vertex given coords and size of the data bounding box func (ec *earcut) zOrder(x, y float64) int { // coords are transformed into non-negative 15-bit integer range 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) } // find the leftmost node of a polygon ring 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 } // check if a point lies within a convex triangle 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 } // check if a diagonal between two polygon nodes is valid (lies in polygon interior) func (ec *earcut) isValidDiagonal(a, b *node) bool { return a.next.i != b.i && a.prev.i != b.i && !ec.intersectsPolygon(a, b) && // dones't intersect other edges ((ec.locallyInside(a, b) && ec.locallyInside(b, a) && ec.middleInside(a, b) && // locally visible (ec.area(a.prev, a, b.prev) != 0.0 || ec.area(a, b.prev, b) != 0.0)) || // does not create opposite-facing sectors (ec.equals(a, b) && ec.area(a.prev, a, a.next) > 0 && ec.area(b.prev, b, b.next) > 0)) // special zero-length case } // signed area of a triangle 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) } // check if two points are equal func (ec *earcut) equals(p1, p2 *node) bool { return p1.x == p2.x && p1.y == p2.y } // check if two segments intersect 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 // general case } if o1 == 0 && ec.onSegment(p1, p2, q1) { // p1, q1 and p2 are collinear and p2 lies on p1q1 return true } if o2 == 0 && ec.onSegment(p1, q2, q1) { // p1, q1 and q2 are collinear and q2 lies on p1q1 return true } if o3 == 0 && ec.onSegment(p2, p1, q2) { // p2, q2 and p1 are collinear and p1 lies on p2q2 return true } if o4 == 0 && ec.onSegment(p2, q1, q2) { // p2, q2 and q1 are collinear and q1 lies on p2q2 return true } return false } // for collinear points p, q, r, check if point q lies on segment pr 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 } // check if a polygon diagonal intersects any polygon segments 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 } // check if a polygon diagonal is locally inside the polygon 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 the middle Vertex of a polygon diagonal is inside the polygon func (ec *earcut) middleInside(a, b *node) bool { p := a inside := false px := (a.x + b.x) / 2 py := (a.y + b.y) / 2 for { if ((p.y > py) != (p.next.y > py)) && p.next.y != p.y && (px < (p.next.x-p.x)*(py-p.y)/(p.next.y-p.y)+p.x) { inside = !inside } p = p.next if p == a { break } } return inside } // link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits // polygon into two; if one belongs to the outer ring and another to a hole, it merges it into a // single ring func (ec *earcut) splitPolygon(a, b *node) *node { ec.nodes = append(ec.nodes, node{i: a.i, x: a.x, y: a.y}) a2 := &ec.nodes[len(ec.nodes)-1] ec.nodes = append(ec.nodes, node{i: b.i, x: b.x, y: b.y}) b2 := &ec.nodes[len(ec.nodes)-1] an := a.next bp := b.prev a.next = b b.prev = a a2.next = an an.prev = a2 b2.next = a2 a2.prev = b2 bp.next = b2 b2.prev = bp return b2 } // create a node and util::optionally link it with previous one (in a circular doubly linked list) func (ec *earcut) insertNode(i int, pt backendbase.Vec, last *node) *node { ec.nodes = append(ec.nodes, node{i: i, x: pt[0], y: pt[1]}) p := &ec.nodes[len(ec.nodes)-1] if last == nil { p.prev = p p.next = p } else { if last == nil { panic("last must not be nil") } p.next = last.next p.prev = last last.next.prev = p last.next = p } return p } func (ec *earcut) removeNode(p *node) { p.next.prev = p.prev p.prev.next = p.next if p.prevZ != nil { p.prevZ.nextZ = p.nextZ } if p.nextZ != nil { p.nextZ.prevZ = p.prevZ } } // sortFontContours takes the contours of a font glyph // and checks whether each contour is the outside or a // hole, and returns an array that is sorted so that // it contains an index of an outer contour followed by // any number of indices of hole contours followed by // a terminating -1 func sortFontContours(contours [][]backendbase.Vec) []int { type cut struct { idx int count int } type info struct { cuts []cut cutTotal int outer bool } cutBuf := make([]cut, len(contours)*len(contours)) cinf := make([]info, len(contours)) for i := range contours { cinf[i].cuts = cutBuf[i*len(contours) : i*len(contours)] } // go through each contour, pick one point on it, and // project that point to the right. count the number of // other contours that it cuts for i, p1 := range contours { pt := p1[0] for j, p2 := range contours { if i == j { continue } for k := range p2 { a, b := p2[k], p2[(k+1)%len(p2)] if a == b { continue } minY := math.Min(a[1], b[1]) maxY := math.Max(a[1], b[1]) if pt[1] <= minY || pt[1] > maxY { continue } r := (pt[1] - a[1]) / (b[1] - a[1]) x := (b[0]-a[0])*r + a[0] if x <= pt[0] { continue } found := false for l := range cinf[i].cuts { if cinf[i].cuts[l].idx == j { cinf[i].cuts[l].count++ found = true break } } if !found { cinf[i].cuts = append(cinf[i].cuts, cut{idx: j, count: 1}) } cinf[i].cutTotal++ } } } // any contour with an even number of cuts is outer, // odd number of cuts means it is a hole for i := range cinf { cinf[i].outer = cinf[i].cutTotal%2 == 0 } // go through them again, pick any outer contour, then // find any hole where the first outer contour it cuts // an odd number of times is the picked contour and add // it to the list of its holes result := make([]int, 0, len(contours)*2) for i := range cinf { if !cinf[i].outer { continue } result = append(result, i) for j := range cinf { if cinf[j].outer { continue } for _, cut := range cinf[j].cuts { if cut.count%2 == 0 { continue } if cut.idx == i { result = append(result, j) break } } } result = append(result, -1) } return result }