edge_loops.swift

//: A UIKit based Playground for presenting user interface
  
import UIKit
import PlaygroundSupport
import simd

// -------------

let floorVertices = [
    // main island
    simd_float2(0,0),
    simd_float2(2,0),
    simd_float2(6,0),
    simd_float2(11,0),
    simd_float2(11,3),
    simd_float2(11,6),
    simd_float2(7,6),
    simd_float2(7,5),
    simd_float2(6,5),
    simd_float2(4,7),
    simd_float2(4,9),
    simd_float2(0,9),
    simd_float2(0,7),
    simd_float2(0,4),

    // north west island
    simd_float2(0,11),
    simd_float2(3,11),
    simd_float2(3,12),
    simd_float2(4,12),
    simd_float2(4,13),
    simd_float2(0,13),

    // north island
    simd_float2(6,8),
    simd_float2(7,8),
    simd_float2(8,9),
    simd_float2(8,10),
    simd_float2(6,10),
]

let floorTriangles = [
    // main island
    [12,11,10],
    [12,10,9],
    [13,12,9],
    [0,13,9],
    [0,9,1],
    [1,9,8],
    [1,8,2],
    [2,8,7],
    [2,7,3],
    [3,7,4],
    [4,7,5],
    [7,6,5],

    // north west island
    [14,19,16],
    [14,16,15],
    [16,18,17],
    [16,19,18],

    // north island
    [20,24,21],
    [21,24,22],
    [22,24,23],
]

// --------

public struct CountedSet<T: Hashable> {
    public typealias Element = T

    fileprivate var backingDictionary = [Element: Int]()

    public var count: Int {
        return backingDictionary.count
    }

    public var isEmpty: Bool {
        return count == 0
    }

    public init() {}

    public func count(for object: Element) -> Int {
            return backingDictionary[object] ?? 0
        }

    public func contains(_ member: CountedSet.Element) -> Bool {
        return backingDictionary[member] != nil
    }

    public mutating func clear() {
        backingDictionary.removeAll()
    }

    public mutating func insert(_ newMember: T) {
        if let count = backingDictionary[newMember] {
            backingDictionary[newMember] = count + 1
        } else {
            backingDictionary[newMember] = 1
        }
    }

    public func first() -> Element? {
        return backingDictionary.keys.first
    }
}

func keyForTriangleEdge(index0: Int, index1: Int) -> simd_int2 {
    if index0 < index1 {
        return simd_int2(Int32(index0), Int32(index1))
    } else {
        return simd_int2(Int32(index1), Int32(index0))
    }
}

func clockwise(hull:[simd_float2]) -> Bool {
    // shoelace formula
    // https://www.geeksforgeeks.org/area-of-a-polygon-with-given-n-ordered-vertices/
    var area:Float = 0
    let n = hull.count
    var j = n - 1
    for i in 0 ..< n {
        area += (hull[j].x + hull[i].x) * (hull[j].y - hull[i].y)
        j = i
    }

    return area * 0.5 > 0
}

struct LineSegment {
    let start: simd_float2
    let end: simd_float2
    let dir: simd_float2
    let length: Float

    init(start: simd_float2, end: simd_float2) {
        self.start = start
        self.end = end
        self.length = simd.length(end-start)
        self.dir = (end - start) / self.length
    }

    func distance(to point: simd_float2) -> Float {
        let toPoint = point - start
        let projectedLength = dot(toPoint, dir)

        // early exit condition, get distance from point to endpoints
        if projectedLength < 0 {
            return simd.length(start - point)
        } else if projectedLength > length {
            return simd.length(end - point)
        }

        // project point to segment body, and compute distance to there
        let projectedToSegment = start + (projectedLength * dir)
        return simd.distance(point, projectedToSegment)
    }
}

// Ramer-Douglas-Peucker simplification
func ramerDouglasPeuker(path: [simd_float2], threshold: Float) -> [simd_float2] {
    var path = path // make path mutable

    // remove front/end duplicates
    while path.count > 2 {
        if let first = path.first, let last = path.last {
            if distance_squared(first, last) < 1e-4 {
                path.removeLast()
            } else {
                break
            }
        }
    }

    // sanity check
    if path.count <= 2 {
        return path
    }

    if let first = path.first, let last = path.last {
        // find the vertex farthest from the line segment defined by the start and end of the path
        var maxDistance:Float = 0
        var maxDistanceIndex:Int? = nil
        let line = LineSegment(start: first, end: last)

        for i in 1 ..< path.count - 1 {
            let distance = line.distance(to: path[i])
            if distance > maxDistance {
                maxDistance = distance
                maxDistanceIndex = i
            }
        }

        if let maxDistanceIndex = maxDistanceIndex, maxDistance > threshold {

            // partition `path` to left and right subpaths and simplify them
            var left = Array(path.prefix(maxDistanceIndex + 1))
            var right = Array(path.suffix(path.count - maxDistanceIndex))

            left = ramerDouglasPeuker(path: left, threshold: threshold)
            right = ramerDouglasPeuker(path: right, threshold: threshold)
            left.append(contentsOf: right.suffix(right.count-1))
            return left
        } else {
            return [first, last]
        }
    } else {
        return path
    }
}

func simplify(path: [simd_float2], threshold: Float) -> [simd_float2] {
    let simplified = ramerDouglasPeuker(path: path, threshold: threshold)

    // ramer-douglas-peuker doesn't work on closed loops, but as a result
    // it can miss potential optimizations when the beginning and end of a loop
    // are colinear with neighbors
    var optimized:[simd_float2] = []
    let count = simplified.count
    for i in 0 ..< simplified.count {
        let previousPoint = simplified[(i + simplified.count - 1) % count]
        let currentPoint = simplified[i]
        let nextPoint = simplified[(i + 1) % count]

        let segment = LineSegment(start: previousPoint, end: nextPoint)
        if segment.distance(to: currentPoint) > threshold {
            optimized.append(currentPoint)
        }
    }

    return optimized
}

// ---------------

func findMeshPerimeters(vertices: [simd_float2], triangleIndices:[[Int]]) -> [[simd_float2]] {

    // compute edge counts
    var edgeCounts = CountedSet<simd_int2>()
    for triangle in triangleIndices {
        let edge0 = keyForTriangleEdge(index0: triangle[0], index1: triangle[1])
        let edge1 = keyForTriangleEdge(index0: triangle[1], index1: triangle[2])
        let edge2 = keyForTriangleEdge(index0: triangle[2], index1: triangle[0])
        edgeCounts.insert(edge0)
        edgeCounts.insert(edge1)
        edgeCounts.insert(edge2)
    }

    var unorderedEdges = Set<[Int]>()

    // now collect all edges with count of 1
    for triangle in triangleIndices {
        let edge0 = keyForTriangleEdge(index0: triangle[0], index1: triangle[1])
        let edge1 = keyForTriangleEdge(index0: triangle[1], index1: triangle[2])
        let edge2 = keyForTriangleEdge(index0: triangle[2], index1: triangle[0])

        if edgeCounts.count(for: edge0) == 1 {
            unorderedEdges.insert([Int(edge0.x), Int(edge0.y)])
        }

        if edgeCounts.count(for: edge1) == 1 {
            unorderedEdges.insert([Int(edge1.x), Int(edge1.y)])
        }

        if edgeCounts.count(for: edge2) == 1 {
            unorderedEdges.insert([Int(edge2.x), Int(edge2.y)])
        }
    }

    // now we have a list of all unique triangle edges; but they're unordered.
    // time for some O(n^2) searching.
    var indexedLoops:[[Int]] = []

    while !unorderedEdges.isEmpty {

        // pick a random point in unorderedEdges
        var loop: [Int] = []
        if let firstEdge = unorderedEdges.first {
            unorderedEdges.remove(firstEdge)
            loop.append(firstEdge[0])

            var tail = firstEdge[1]
            var foundEdge:[Int]? = nil

            repeat {
                foundEdge = nil
                for edge in unorderedEdges {
                    if edge[0] == tail {
                        loop.append(edge[0])
                        tail = edge[1]
                        foundEdge = edge
                        break
                    } else if edge[1] == tail {
                        loop.append(edge[1])
                        tail = edge[0]
                        foundEdge = edge
                        break
                    }
                }
                if let foundEdge = foundEdge {
                    unorderedEdges.remove(foundEdge)
                }
            } while foundEdge != nil
        }

        if !loop.isEmpty {
            indexedLoops.append(loop)
        }
    }

    // flatten from indices to actual vertices
    var loops:[[simd_float2]] = []
    for indexedLoop in indexedLoops {
        var loop:[simd_float2] = []
        for index in indexedLoop {
            loop.append(vertices[index])
        }
        loops.append(loop)
    }

    // normalize to ccw winding, and simplify
    for i in 0 ..< loops.count {
        if clockwise(hull: loops[i]) {
            loops[i] = loops[i].reversed()
        }

        loops[i] = simplify(path: loops[i], threshold: 1e-4)
    }

    return loops
}

// --------

class HullView : UIView {

    var loops:[[simd_float2]] = [] {
        didSet {
            setNeedsDisplay()
        }
    }

    override init(frame: CGRect) {
        super.init(frame: frame)
        addGestureRecognizer(UITapGestureRecognizer(target: self, action: #selector(onTap)))
    }

    required init?(coder: NSCoder) {
        fatalError("init(coder:) has not been implemented")
    }

    @objc
    func onTap(_ gestureRecognizer: UITapGestureRecognizer) {
        loops = findMeshPerimeters(vertices: floorVertices, triangleIndices: floorTriangles)
    }

    override func draw(_ rect: CGRect) {
        let ctx = UIGraphicsGetCurrentContext()!
        ctx.setFillColor(UIColor.black.cgColor)
        let inset:CGFloat = 16
        let insetBounds = bounds.inset(by: UIEdgeInsets(top: inset, left: inset, bottom: inset, right: inset))
        let loopBounds = self.loopBounds
        var scale = insetBounds.width / loopBounds.width
        if loopBounds.height * scale > insetBounds.height {
            scale *= insetBounds.height / (loopBounds.height * scale)
        }

        let project:(simd_float2)->simd_float2 = { point in
            var projected = simd_float2(Float(inset), Float(inset)) + (point * Float(scale))
            projected.y = Float(self.bounds.size.height) - projected.y
            return projected
        }

        let colorFor:(Int,Int)->CGColor = { index, count in
            let hue = Float(index) / Float(count)
            return UIColor.init(hue: CGFloat(hue), saturation: 0.7, brightness: 0.8, alpha: 1).cgColor
        }

        for loop in loops {
            for (i,point) in loop.enumerated() {
                let screenPoint = project(point)

                if i == 0 {
                    ctx.setFillColor(UIColor.white.cgColor)
                    ctx.fillEllipse(in: CGRect(x: CGFloat(screenPoint.x - 5), y: CGFloat(screenPoint.y - 5), width: 10.0, height: 10.0))
                } else if i == 1 {
                    ctx.setStrokeColor(UIColor.white.cgColor)
                    ctx.setLineWidth(1)
                    ctx.strokeEllipse(in: CGRect(x: CGFloat(screenPoint.x - 5), y: CGFloat(screenPoint.y - 5), width: 10.0, height: 10.0))
                }

                ctx.setFillColor(colorFor(i, loop.count))
                ctx.fillEllipse(in: CGRect(x: CGFloat(screenPoint.x - 3), y: CGFloat(screenPoint.y - 3), width: 6.0, height: 6.0))

                let nextPoint = loop[(i+1) % loop.count]
                let nextScreenPoint = project(nextPoint)
                ctx.move(to: CGPoint(x: CGFloat(screenPoint.x), y: CGFloat(screenPoint.y)))
                ctx.addLine(to: CGPoint(x: CGFloat(nextScreenPoint.x), y: CGFloat(nextScreenPoint.y)))
                ctx.setLineWidth(2)
                ctx.setStrokeColor(colorFor(i, loop.count))
                ctx.strokePath()
            }
        }
    }

    var loopBounds:CGRect {
        var minEdge = simd_float2(Float.greatestFiniteMagnitude, Float.greatestFiniteMagnitude)
        var maxEdge = simd_float2(-Float.greatestFiniteMagnitude, -Float.greatestFiniteMagnitude)
        for loop in loops {
            for point in loop {
                minEdge.x = min(minEdge.x, point.x)
                minEdge.y = min(minEdge.y, point.y)
                maxEdge.x = max(maxEdge.x, point.x)
                maxEdge.y = max(maxEdge.y, point.y)
            }
        }
        return CGRect(x: CGFloat(minEdge.x), y: CGFloat(minEdge.y), width: CGFloat(max(maxEdge.x - minEdge.x, 0)), height: CGFloat(max(maxEdge.y - minEdge.y, 0)))
    }
}

class MyViewController : UIViewController {
    override func loadView() {
        let view = HullView()
        view.loops = findMeshPerimeters(vertices: floorVertices, triangleIndices: floorTriangles)
        self.view = view
    }
}

// Present the view controller in the Live View window
PlaygroundPage.current.liveView = MyViewController()