Text background with round corner like Instagram does

Question

I want to create text with background color and round corners like Instagram does. I am able to achieve the background color but could not create the round corners.

What I have till now:

Below is the source code of above screenshot:

-(void)createBackgroundColor{
    [self.txtView.layoutManager enumerateLineFragmentsForGlyphRange:NSMakeRange(0, self.txtView.text.length) usingBlock:^(CGRect rect, CGRect usedRect, NSTextContainer *textContainer, NSRange glyphRange, BOOL *stop) {
        [textArray addObject:[NSNumber numberWithInteger:glyphRange.length]];
        if (glyphRange.length == 1){
            return ;
        }
        UIImageView *highlightBackView = [[UIImageView alloc] initWithFrame:CGRectMake(usedRect.origin.x, usedRect.origin.y  , usedRect.size.width, usedRect.size.height + 2)];
        highlightBackView.layer.borderWidth = 1;
        highlightBackView.backgroundColor = [UIColor orangeColor];
        highlightBackView.layer.borderColor = [[UIColor clearColor] CGColor];
        [self.txtView insertSubview:highlightBackView atIndex:0];
        highlightBackView.layer.cornerRadius = 5;
    }];
}

I call this function in shouldChangeTextInRange delegate.

What I want:

See the inner radius marked with arrows, Any help would be appreciated!

Answer 1

UPDATE

I have rewritten my implementation of this code and made it available as a SwiftPM package: the RectangleContour package. The package includes an explanation of how to use its API and demo apps for macOS and iOS.

ORIGINAL

So, you want this:

Here's an answer that I spent way too long on, and that you probably won't even like, because your question is tagged objective-c but I wrote this answer in Swift. You can use Swift code from Objective-C, but not everyone wants to.

You can find my entire test project, including iOS and macOS test apps, in this github repo.

Anyway, what we need to do is compute the contour of the union of all of the line rects. I found a 1980 paper describing the necessary algorithm:

Lipski, W. and F. Preparata. “Finding the Contour of a Union of Iso-Oriented Rectangles.” J. Algorithms 1 (1980): 235-246. doi:10.1016/0196-6774(80)90011-5

This algorithm is probably more general than actually required for your problem, since it can handle rectangle arrangements that create holes:

So it might be overkill for you, but it gets the job done.

Anyway, once we have the contour, we can convert it to a CGPath with rounded corners for stroking or filling.

The algorithm is somewhat involved, but I implemented it (in Swift) as an extension method on CGPath:

import CoreGraphics

extension CGPath {
    static func makeUnion(of rects: [CGRect], cornerRadius: CGFloat) -> CGPath {
        let phase2 = AlgorithmPhase2(cornerRadius: cornerRadius)
        _ = AlgorithmPhase1(rects: rects, phase2: phase2)
        return phase2.makePath()
    }
}

fileprivate func swapped<A, B>(_ pair: (A, B)) -> (B, A) { return (pair.1, pair.0) }

fileprivate class AlgorithmPhase1 {

    init(rects: [CGRect], phase2: AlgorithmPhase2) {
        self.phase2 = phase2
        xs = Array(Set(rects.map({ $0.origin.x})).union(rects.map({ $0.origin.x + $0.size.width }))).sorted()
        indexOfX = [CGFloat:Int](uniqueKeysWithValues: xs.enumerated().map(swapped))
        ys = Array(Set(rects.map({ $0.origin.y})).union(rects.map({ $0.origin.y + $0.size.height }))).sorted()
        indexOfY = [CGFloat:Int](uniqueKeysWithValues: ys.enumerated().map(swapped))
        segments.reserveCapacity(2 * ys.count)
        _ = makeSegment(y0: 0, y1: ys.count - 1)

        let sides = (rects.map({ makeSide(direction: .down, rect: $0) }) + rects.map({ makeSide(direction: .up, rect: $0)})).sorted()
        var priorX = 0
        var priorDirection = VerticalDirection.down
        for side in sides {
            if side.x != priorX || side.direction != priorDirection {
                convertStackToPhase2Sides(atX: priorX, direction: priorDirection)
                priorX = side.x
                priorDirection = side.direction
            }
            switch priorDirection {
            case .down:
                pushEmptySegmentsOfSegmentTree(atIndex: 0, thatOverlap: side)
                adjustInsertionCountsOfSegmentTree(atIndex: 0, by: 1, for: side)
            case .up:
                adjustInsertionCountsOfSegmentTree(atIndex: 0, by: -1, for: side)
                pushEmptySegmentsOfSegmentTree(atIndex: 0, thatOverlap: side)
            }
        }
        convertStackToPhase2Sides(atX: priorX, direction: priorDirection)

    }

    private let phase2: AlgorithmPhase2
    private let xs: [CGFloat]
    private let indexOfX: [CGFloat: Int]
    private let ys: [CGFloat]
    private let indexOfY: [CGFloat: Int]
    private var segments: [Segment] = []
    private var stack: [(Int, Int)] = []

    private struct Segment {
        var y0: Int
        var y1: Int
        var insertions = 0
        var status  = Status.empty
        var leftChildIndex: Int?
        var rightChildIndex: Int?

        var mid: Int { return (y0 + y1 + 1) / 2 }

        func withChildrenThatOverlap(_ side: Side, do body: (_ childIndex: Int) -> ()) {
            if side.y0 < mid, let l = leftChildIndex { body(l) }
            if mid < side.y1, let r = rightChildIndex { body(r) }
        }

        init(y0: Int, y1: Int) {
            self.y0 = y0
            self.y1 = y1
        }

        enum Status {
            case empty
            case partial
            case full
        }
    }

    private struct /*Vertical*/Side: Comparable {
        var x: Int
        var direction: VerticalDirection
        var y0: Int
        var y1: Int

        func fullyContains(_ segment: Segment) -> Bool {
            return y0 <= segment.y0 && segment.y1 <= y1
        }

        static func ==(lhs: Side, rhs: Side) -> Bool {
            return lhs.x == rhs.x && lhs.direction == rhs.direction && lhs.y0 == rhs.y0 && lhs.y1 == rhs.y1
        }

        static func <(lhs: Side, rhs: Side) -> Bool {
            if lhs.x < rhs.x { return true }
            if lhs.x > rhs.x { return false }
            if lhs.direction.rawValue < rhs.direction.rawValue { return true }
            if lhs.direction.rawValue > rhs.direction.rawValue { return false }
            if lhs.y0 < rhs.y0 { return true }
            if lhs.y0 > rhs.y0 { return false }
            return lhs.y1 < rhs.y1
        }
    }

    private func makeSegment(y0: Int, y1: Int) -> Int {
        let index = segments.count
        let segment: Segment = Segment(y0: y0, y1: y1)
        segments.append(segment)
        if y1 - y0 > 1 {
            let mid = segment.mid
            segments[index].leftChildIndex = makeSegment(y0: y0, y1: mid)
            segments[index].rightChildIndex = makeSegment(y0: mid, y1: y1)
        }
        return index
    }

    private func adjustInsertionCountsOfSegmentTree(atIndex i: Int, by delta: Int, for side: Side) {
        var segment = segments[i]
        if side.fullyContains(segment) {
            segment.insertions += delta
        } else {
            segment.withChildrenThatOverlap(side) { adjustInsertionCountsOfSegmentTree(atIndex: $0, by: delta, for: side) }
        }

        segment.status = uncachedStatus(of: segment)
        segments[i] = segment
    }

    private func uncachedStatus(of segment: Segment) -> Segment.Status {
        if segment.insertions > 0 { return .full }
        if let l = segment.leftChildIndex, let r = segment.rightChildIndex {
            return segments[l].status == .empty && segments[r].status == .empty ? .empty : .partial
        }
        return .empty
    }

    private func pushEmptySegmentsOfSegmentTree(atIndex i: Int, thatOverlap side: Side) {
        let segment = segments[i]
        switch segment.status {
        case .empty where side.fullyContains(segment):
            if let top = stack.last, segment.y0 == top.1 {
                // segment.y0 == prior segment.y1, so merge.
                stack[stack.count - 1] = (top.0, segment.y1)
            } else {
                stack.append((segment.y0, segment.y1))
            }
        case .partial, .empty:
            segment.withChildrenThatOverlap(side) { pushEmptySegmentsOfSegmentTree(atIndex: $0, thatOverlap: side) }
        case .full: break
        }
    }

    private func makeSide(direction: VerticalDirection, rect: CGRect) -> Side {
        let x: Int
        switch direction {
        case .down: x = indexOfX[rect.minX]!
        case .up: x = indexOfX[rect.maxX]!
        }
        return Side(x: x, direction: direction, y0: indexOfY[rect.minY]!, y1: indexOfY[rect.maxY]!)
    }

    private func convertStackToPhase2Sides(atX x: Int, direction: VerticalDirection) {
        guard stack.count > 0 else { return }
        let gx = xs[x]
        switch direction {
        case .up:
            for (y0, y1) in stack {
                phase2.addVerticalSide(atX: gx, fromY: ys[y0], toY: ys[y1])
            }
        case .down:
            for (y0, y1) in stack {
                phase2.addVerticalSide(atX: gx, fromY: ys[y1], toY: ys[y0])
            }
        }
        stack.removeAll(keepingCapacity: true)
    }

}

fileprivate class AlgorithmPhase2 {

    init(cornerRadius: CGFloat) {
        self.cornerRadius = cornerRadius
    }

    let cornerRadius: CGFloat

    func addVerticalSide(atX x: CGFloat, fromY y0: CGFloat, toY y1: CGFloat) {
        verticalSides.append(VerticalSide(x: x, y0: y0, y1: y1))
    }

    func makePath() -> CGPath {
        verticalSides.sort(by: { (a, b) in
            if a.x < b.x { return true }
            if a.x > b.x { return false }
            return a.y0 < b.y0
        })


        var vertexes: [Vertex] = []
        for (i, side) in verticalSides.enumerated() {
            vertexes.append(Vertex(x: side.x, y0: side.y0, y1: side.y1, sideIndex: i, representsEnd: false))
            vertexes.append(Vertex(x: side.x, y0: side.y1, y1: side.y0, sideIndex: i, representsEnd: true))
        }
        vertexes.sort(by: { (a, b) in
            if a.y0 < b.y0 { return true }
            if a.y0 > b.y0 { return false }
            return a.x < b.x
        })

        for i in stride(from: 0, to: vertexes.count, by: 2) {
            let v0 = vertexes[i]
            let v1 = vertexes[i+1]
            let startSideIndex: Int
            let endSideIndex: Int
            if v0.representsEnd {
                startSideIndex = v0.sideIndex
                endSideIndex = v1.sideIndex
            } else {
                startSideIndex = v1.sideIndex
                endSideIndex = v0.sideIndex
            }
            precondition(verticalSides[startSideIndex].nextIndex == -1)
            verticalSides[startSideIndex].nextIndex = endSideIndex
        }

        let path = CGMutablePath()
        for i in verticalSides.indices where !verticalSides[i].emitted {
            addLoop(startingAtSideIndex: i, to: path)
        }
        return path.copy()!
    }

    private var verticalSides: [VerticalSide] = []

    private struct VerticalSide {
        var x: CGFloat
        var y0: CGFloat
        var y1: CGFloat
        var nextIndex = -1
        var emitted = false

        var isDown: Bool { return y1 < y0 }

        var startPoint: CGPoint { return CGPoint(x: x, y: y0) }
        var midPoint: CGPoint { return CGPoint(x: x, y: 0.5 * (y0 + y1)) }
        var endPoint: CGPoint { return CGPoint(x: x, y: y1) }

        init(x: CGFloat, y0: CGFloat, y1: CGFloat) {
            self.x = x
            self.y0 = y0
            self.y1 = y1
        }
    }

    private struct Vertex {
        var x: CGFloat
        var y0: CGFloat
        var y1: CGFloat
        var sideIndex: Int
        var representsEnd: Bool
    }

    private func addLoop(startingAtSideIndex startIndex: Int, to path: CGMutablePath) {
        var point = verticalSides[startIndex].midPoint
        path.move(to: point)
        var fromIndex = startIndex
        repeat {
            let toIndex = verticalSides[fromIndex].nextIndex
            let horizontalMidpoint = CGPoint(x: 0.5 * (verticalSides[fromIndex].x + verticalSides[toIndex].x), y: verticalSides[fromIndex].y1)
            path.addCorner(from: point, toward: verticalSides[fromIndex].endPoint, to: horizontalMidpoint, maxRadius: cornerRadius)
            let nextPoint = verticalSides[toIndex].midPoint
            path.addCorner(from: horizontalMidpoint, toward: verticalSides[toIndex].startPoint, to: nextPoint, maxRadius: cornerRadius)
            verticalSides[fromIndex].emitted = true
            fromIndex = toIndex
            point = nextPoint
        } while fromIndex != startIndex
        path.closeSubpath()
    }

}

fileprivate extension CGMutablePath {
    func addCorner(from start: CGPoint, toward corner: CGPoint, to end: CGPoint, maxRadius: CGFloat) {
        let radius = min(maxRadius, min(abs(start.x - end.x), abs(start.y - end.y)))
        addArc(tangent1End: corner, tangent2End: end, radius: radius)
    }
}

fileprivate enum VerticalDirection: Int {
    case down = 0
    case up = 1
}

With this, I can paint the rounded background you want in my view controller:

private func setHighlightPath() {
    let textLayer = textView.layer
    let textContainerInset = textView.textContainerInset
    let uiInset = CGFloat(insetSlider.value)
    let radius = CGFloat(radiusSlider.value)
    let highlightLayer = self.highlightLayer
    let layout = textView.layoutManager
    let range = NSMakeRange(0, layout.numberOfGlyphs)
    var rects = [CGRect]()
    layout.enumerateLineFragments(forGlyphRange: range) { (_, usedRect, _, _, _) in
        if usedRect.width > 0 && usedRect.height > 0 {
            var rect = usedRect
            rect.origin.x += textContainerInset.left
            rect.origin.y += textContainerInset.top
            rect = highlightLayer.convert(rect, from: textLayer)
            rect = rect.insetBy(dx: uiInset, dy: uiInset)
            rects.append(rect)
        }
    }
    highlightLayer.path = CGPath.makeUnion(of: rects, cornerRadius: radius)
}

Answer 2

Im pasting in the wrapper class I made for this. Thanks for the algorithm rob mayoff it works great.

Limitations that I'm aware of:

1. If you use dynamic colors, this class is not aware of traitcollection and userinterface style changes. Highlight is cgColor so it will not adopt. So your .label color for the highlight will stay either .white or .black for example after interface style changed. Handle it outside with an update.
2. Just wrote this quickly without testing too many scenarios. Insets and radius auto calculated if not specified to fit the font size but not aware or line spacing and other variables.
3. Generally not tested heavily so check if it fits your purpose.
4. This being a View and a textView on it, you need to lay it out with frame or constraints for width and height. No intrinsic content size. If you want to fiddle with that, please do and post the intrinsicContentSize function.
5. Editing and selection for the textView is turned off. textView is public; Turn editing back on if you need it.

convenience init / update signature:

init(text:String? = nil,
     font:UIFont? = nil,
     textColor:UIColor? = nil,
     highlightColor:UIColor? = nil,
     inset:CGFloat? = nil,
     radius:CGFloat? = nil)

usage examples:

let stamp = Stamp()
let stamp = Stamp(text: "Whatever\nneeds to be\nstamped.")
let stamp = Stamp(text: "Placeholder that has no line breaks but wraps anyway.")
stamp.update(text: "Smaller Version", 
             font: UIFont.systemFont(ofSize: 15, weight: .regular),
             textColor: .label, 
             highlightColor:.purple)

Just make a new file and paste in this class. Use as described.

import UIKit
import CoreGraphics

class Stamp: UIView, UITextViewDelegate {

var textView = UITextView()

private var text:String = "Place holder\nline\nbroken Stamp."

private var highlightLayer = CAShapeLayer()
private var highlightColor:CGColor = UIColor.systemOrange.cgColor

private var textColor:UIColor = UIColor.label
private var font:UIFont = UIFont.systemFont(ofSize: 35, weight: .bold)

private var inset:CGFloat = 1
private var radius:CGFloat = 1

override init(frame: CGRect) {
    super.init(frame: frame)
    
    textView.delegate = self
    textView.isEditable = false
    textView.isSelectable = false
    textView.font = self.font
    
    self.inset = -font.pointSize / 5
    self.radius = font.pointSize / 4
    
    self.textView.text = self.text
    self.textView.textAlignment = .center
    self.textView.backgroundColor = .clear
    
    highlightLayer.backgroundColor = nil
    highlightLayer.strokeColor = nil
    self.layer.insertSublayer(highlightLayer, at: 0)
    
    highlightLayer.fillColor = self.highlightColor
    
    addSubview(textView)
    textView.fillSuperview()
}

convenience init(text:String? = nil,
                 font:UIFont? = nil,
                 textColor:UIColor? = nil,
                 highlightColor:UIColor? = nil,
                 inset:CGFloat? = nil,
                 radius:CGFloat? = nil) {
    
    self.init(frame: .zero)
    
    self.update(text: text,
                font: font,
                textColor: textColor,
                highlightColor: highlightColor,
                inset: inset,
                radius: radius)
}

func update(text:String? = nil,
            font:UIFont? = nil,
            textColor:UIColor? = nil,
            highlightColor:UIColor? = nil,
            inset:CGFloat? = nil,
            radius:CGFloat? = nil){
    
    if let text = text { self.text = text }
    if let font = font { self.font = font }
    if let textColor = textColor { self.textColor = textColor }
    if let highlightColor = highlightColor { self.highlightColor = highlightColor.cgColor }
    
    self.inset = inset ?? -self.font.pointSize / 5
    self.radius = radius ?? self.font.pointSize / 4
    
    self.textView.text = text
    self.textView.textColor = self.textColor
    self.textView.font = self.font
    
    highlightLayer.fillColor = self.highlightColor
    
    // this will re-draw the highlight
    setHighlightPath()
}

override func layoutSubviews() {
    super.layoutSubviews()
    highlightLayer.frame = self.bounds
    self.setHighlightPath()
}

func textViewDidChange(_ textView: UITextView) {
    setHighlightPath()
}

private func setHighlightPath() {
    let textLayer = textView.layer
    let textContainerInset = textView.textContainerInset
    let uiInset = CGFloat(inset)
    let radius = CGFloat(radius)
    let highlightLayer = self.highlightLayer
    let layout = textView.layoutManager
    let range = NSMakeRange(0, layout.numberOfGlyphs)
    var rects = [CGRect]()
    layout.enumerateLineFragments(forGlyphRange: range) { (_, usedRect, _, _, _) in
        if usedRect.width > 0 && usedRect.height > 0 {
            var rect = usedRect
            rect.origin.x += textContainerInset.left
            rect.origin.y += textContainerInset.top
            rect = highlightLayer.convert(rect, from: textLayer)
            rect = rect.insetBy(dx: uiInset, dy: uiInset)
            rects.append(rect)
        }
    }
    highlightLayer.path = CGPath.makeUnion(of: rects, cornerRadius: radius)
}

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

extension CGPath {
    static func makeUnion(of rects: [CGRect], cornerRadius: CGFloat) -> CGPath {
        let phase2 = AlgorithmPhase2(cornerRadius: cornerRadius)
        _ = AlgorithmPhase1(rects: rects, phase2: phase2)
        return phase2.makePath()
    }
}

fileprivate func swapped<A, B>(_ pair: (A, B)) -> (B, A) { return (pair.1, pair.0) }

fileprivate class AlgorithmPhase1 {

init(rects: [CGRect], phase2: AlgorithmPhase2) {
    self.phase2 = phase2
    xs = Array(Set(rects.map({ $0.origin.x})).union(rects.map({ $0.origin.x + $0.size.width }))).sorted()
    indexOfX = [CGFloat:Int](uniqueKeysWithValues: xs.enumerated().map(swapped))
    ys = Array(Set(rects.map({ $0.origin.y})).union(rects.map({ $0.origin.y + $0.size.height }))).sorted()
    indexOfY = [CGFloat:Int](uniqueKeysWithValues: ys.enumerated().map(swapped))
    segments.reserveCapacity(2 * ys.count)
    _ = makeSegment(y0: 0, y1: ys.count - 1)

    let sides = (rects.map({ makeSide(direction: .down, rect: $0) }) + rects.map({ makeSide(direction: .up, rect: $0)})).sorted()
    var priorX = 0
    var priorDirection = VerticalDirection.down
    for side in sides {
        if side.x != priorX || side.direction != priorDirection {
            convertStackToPhase2Sides(atX: priorX, direction: priorDirection)
            priorX = side.x
            priorDirection = side.direction
        }
        switch priorDirection {
        case .down:
            pushEmptySegmentsOfSegmentTree(atIndex: 0, thatOverlap: side)
            adjustInsertionCountsOfSegmentTree(atIndex: 0, by: 1, for: side)
        case .up:
            adjustInsertionCountsOfSegmentTree(atIndex: 0, by: -1, for: side)
            pushEmptySegmentsOfSegmentTree(atIndex: 0, thatOverlap: side)
        }
    }
    convertStackToPhase2Sides(atX: priorX, direction: priorDirection)

}

private let phase2: AlgorithmPhase2
private let xs: [CGFloat]
private let indexOfX: [CGFloat: Int]
private let ys: [CGFloat]
private let indexOfY: [CGFloat: Int]
private var segments: [Segment] = []
private var stack: [(Int, Int)] = []

private struct Segment {
    var y0: Int
    var y1: Int
    var insertions = 0
    var status  = Status.empty
    var leftChildIndex: Int?
    var rightChildIndex: Int?

    var mid: Int { return (y0 + y1 + 1) / 2 }

    func withChildrenThatOverlap(_ side: Side, do body: (_ childIndex: Int) -> ()) {
        if side.y0 < mid, let l = leftChildIndex { body(l) }
        if mid < side.y1, let r = rightChildIndex { body(r) }
    }

    init(y0: Int, y1: Int) {
        self.y0 = y0
        self.y1 = y1
    }

    enum Status {
        case empty
        case partial
        case full
    }
}

private struct /*Vertical*/Side: Comparable {
    var x: Int
    var direction: VerticalDirection
    var y0: Int
    var y1: Int

    func fullyContains(_ segment: Segment) -> Bool {
        return y0 <= segment.y0 && segment.y1 <= y1
    }

    static func ==(lhs: Side, rhs: Side) -> Bool {
        return lhs.x == rhs.x && lhs.direction == rhs.direction && lhs.y0 == rhs.y0 && lhs.y1 == rhs.y1
    }

    static func <(lhs: Side, rhs: Side) -> Bool {
        if lhs.x < rhs.x { return true }
        if lhs.x > rhs.x { return false }
        if lhs.direction.rawValue < rhs.direction.rawValue { return true }
        if lhs.direction.rawValue > rhs.direction.rawValue { return false }
        if lhs.y0 < rhs.y0 { return true }
        if lhs.y0 > rhs.y0 { return false }
        return lhs.y1 < rhs.y1
    }
}

private func makeSegment(y0: Int, y1: Int) -> Int {
    let index = segments.count
    let segment: Segment = Segment(y0: y0, y1: y1)
    segments.append(segment)
    if y1 - y0 > 1 {
        let mid = segment.mid
        segments[index].leftChildIndex = makeSegment(y0: y0, y1: mid)
        segments[index].rightChildIndex = makeSegment(y0: mid, y1: y1)
    }
    return index
}

private func adjustInsertionCountsOfSegmentTree(atIndex i: Int, by delta: Int, for side: Side) {
    var segment = segments[i]
    if side.fullyContains(segment) {
        segment.insertions += delta
    } else {
        segment.withChildrenThatOverlap(side) { adjustInsertionCountsOfSegmentTree(atIndex: $0, by: delta, for: side) }
    }

    segment.status = uncachedStatus(of: segment)
    segments[i] = segment
}

private func uncachedStatus(of segment: Segment) -> Segment.Status {
    if segment.insertions > 0 { return .full }
    if let l = segment.leftChildIndex, let r = segment.rightChildIndex {
        return segments[l].status == .empty && segments[r].status == .empty ? .empty : .partial
    }
    return .empty
}

private func pushEmptySegmentsOfSegmentTree(atIndex i: Int, thatOverlap side: Side) {
    let segment = segments[i]
    switch segment.status {
    case .empty where side.fullyContains(segment):
        if let top = stack.last, segment.y0 == top.1 {
            // segment.y0 == prior segment.y1, so merge.
            stack[stack.count - 1] = (top.0, segment.y1)
        } else {
            stack.append((segment.y0, segment.y1))
        }
    case .partial, .empty:
        segment.withChildrenThatOverlap(side) { pushEmptySegmentsOfSegmentTree(atIndex: $0, thatOverlap: side) }
    case .full: break
    }
}

private func makeSide(direction: VerticalDirection, rect: CGRect) -> Side {
    let x: Int
    switch direction {
    case .down: x = indexOfX[rect.minX]!
    case .up: x = indexOfX[rect.maxX]!
    }
    return Side(x: x, direction: direction, y0: indexOfY[rect.minY]!, y1: indexOfY[rect.maxY]!)
}

private func convertStackToPhase2Sides(atX x: Int, direction: VerticalDirection) {
    guard stack.count > 0 else { return }
    let gx = xs[x]
    switch direction {
    case .up:
        for (y0, y1) in stack {
            phase2.addVerticalSide(atX: gx, fromY: ys[y0], toY: ys[y1])
        }
    case .down:
        for (y0, y1) in stack {
            phase2.addVerticalSide(atX: gx, fromY: ys[y1], toY: ys[y0])
        }
    }
    stack.removeAll(keepingCapacity: true)
}

}

fileprivate class AlgorithmPhase2 {

init(cornerRadius: CGFloat) {
    self.cornerRadius = cornerRadius
}

let cornerRadius: CGFloat

func addVerticalSide(atX x: CGFloat, fromY y0: CGFloat, toY y1: CGFloat) {
    verticalSides.append(VerticalSide(x: x, y0: y0, y1: y1))
}

func makePath() -> CGPath {
    verticalSides.sort(by: { (a, b) in
        if a.x < b.x { return true }
        if a.x > b.x { return false }
        return a.y0 < b.y0
    })


    var vertexes: [Vertex] = []
    for (i, side) in verticalSides.enumerated() {
        vertexes.append(Vertex(x: side.x, y0: side.y0, y1: side.y1, sideIndex: i, representsEnd: false))
        vertexes.append(Vertex(x: side.x, y0: side.y1, y1: side.y0, sideIndex: i, representsEnd: true))
    }
    vertexes.sort(by: { (a, b) in
        if a.y0 < b.y0 { return true }
        if a.y0 > b.y0 { return false }
        return a.x < b.x
    })

    for i in stride(from: 0, to: vertexes.count, by: 2) {
        let v0 = vertexes[i]
        let v1 = vertexes[i+1]
        let startSideIndex: Int
        let endSideIndex: Int
        if v0.representsEnd {
            startSideIndex = v0.sideIndex
            endSideIndex = v1.sideIndex
        } else {
            startSideIndex = v1.sideIndex
            endSideIndex = v0.sideIndex
        }
        precondition(verticalSides[startSideIndex].nextIndex == -1)
        verticalSides[startSideIndex].nextIndex = endSideIndex
    }

    let path = CGMutablePath()
    for i in verticalSides.indices where !verticalSides[i].emitted {
        addLoop(startingAtSideIndex: i, to: path)
    }
    return path.copy()!
}

private var verticalSides: [VerticalSide] = []

private struct VerticalSide {
    var x: CGFloat
    var y0: CGFloat
    var y1: CGFloat
    var nextIndex = -1
    var emitted = false

    var isDown: Bool { return y1 < y0 }

    var startPoint: CGPoint { return CGPoint(x: x, y: y0) }
    var midPoint: CGPoint { return CGPoint(x: x, y: 0.5 * (y0 + y1)) }
    var endPoint: CGPoint { return CGPoint(x: x, y: y1) }

    init(x: CGFloat, y0: CGFloat, y1: CGFloat) {
        self.x = x
        self.y0 = y0
        self.y1 = y1
    }
}

private struct Vertex {
    var x: CGFloat
    var y0: CGFloat
    var y1: CGFloat
    var sideIndex: Int
    var representsEnd: Bool
}

private func addLoop(startingAtSideIndex startIndex: Int, to path: CGMutablePath) {
    var point = verticalSides[startIndex].midPoint
    path.move(to: point)
    var fromIndex = startIndex
    repeat {
        let toIndex = verticalSides[fromIndex].nextIndex
        let horizontalMidpoint = CGPoint(x: 0.5 * (verticalSides[fromIndex].x + verticalSides[toIndex].x), y: verticalSides[fromIndex].y1)
        path.addCorner(from: point, toward: verticalSides[fromIndex].endPoint, to: horizontalMidpoint, maxRadius: cornerRadius)
        let nextPoint = verticalSides[toIndex].midPoint
        path.addCorner(from: horizontalMidpoint, toward: verticalSides[toIndex].startPoint, to: nextPoint, maxRadius: cornerRadius)
        verticalSides[fromIndex].emitted = true
        fromIndex = toIndex
        point = nextPoint
    } while fromIndex != startIndex
    path.closeSubpath()
}

}
    fileprivate extension CGMutablePath {
        func addCorner(from start: CGPoint, toward corner: CGPoint, to end: CGPoint, maxRadius: CGFloat) {
            let radius = min(maxRadius, min(abs(start.x - end.x), abs(start.y - end.y)))
            addArc(tangent1End: corner, tangent2End: end, radius: radius)
        }
    }
    
    fileprivate enum VerticalDirection: Int {
        case down = 0
        case up = 1
    }