Circles that are tangents of each other. How do I detect which circle is tapped?

Question

I created a UIView subclass that looks like this:

It is 21 circles packed in a triangular shape. The circles are tangents of each other.

I want to know which circle is touched when a tap gesture is recognised. Specifically, I want to know the row number (0 refers to the top row, 5 refers to the bottom row) and the index (0 refers to the leftmost circle) of the touched circle.

This is how I draw the circles. There's nothing wrong with this code AFAIK. I provided this code so that you can reproduce my custom UIView.

// This is the frame that I actually draw the circles in, because the view's
// bounds is not always the perfect size. This frame is supposed to be centered in the view's bounds
var actualBoardFrame: CGRect {
    if bounds.width < bounds.height {
        return CGRect(x: 0,
                      y: (bounds.height - bounds.width) / 2,
                      width: bounds.width,
                      height: bounds.width)
            .insetBy(dx: 3, dy: 3)
    } else {
        return CGRect(x: (bounds.width - bounds.height) / 2,
                      y: 0,
                      width: bounds.height,
                      height: bounds.height)
            .insetBy(dx: 3, dy: 3)
    }
}

var circleDiameter: CGFloat {
    return actualBoardFrame.height / 6
}

override func draw(_ rect: CGRect) {
    for row in 0..<board.rowCount {
        for index in 0...row {
            let path = UIBezierPath(ovalIn: CGRect(origin: pointInViewFrame(forCircleInRow: row, atIndex: index), size: size))
            path.lineWidth = 3
            UIColor.black.setStroke()
            path.stroke()
        }
    }

}

// Sorry for the short variable names. I worked this formula out on paper with maths,
// so I didn't bother to write long names
func pointInBoardFrame(forCircleInRow row: Int, atIndex index: Int) -> CGPoint {
    let n = CGFloat(board.rowCount)
    let c = CGFloat(board.rowCount - row - 1)
    let w = actualBoardFrame.width
    let h = actualBoardFrame.height
    let x = (2 * w * CGFloat(index) + w * c) / (2 * n)
    let y = (n - c - 1) * h / n + (c * (circleDiameter / 2) * tan(.pi / 8))
    return CGPoint(x: x, y: y)
}

// This converts the point in the actualBoardFrame's coordinate space
// to a point in the view.bounds coordinate space
func pointInViewFrame(forCircleInRow row: Int, atIndex index: Int) -> CGPoint {
    let point = pointInBoardFrame(forCircleInRow: row, atIndex: index)
    return CGPoint(x: point.x + actualBoardFrame.origin.x, y: point.y + actualBoardFrame.origin.y)
}

One way I tried to detect which circle is touched is this:

override func touchesBegan(_ touches: Set<UITouch>, with event: UIEvent?) {
    guard let point = touches.first?.location(in: self) else { return }
    let pointInBoardFrame = CGPoint(x: point.x - actualBoardFrame.origin.x, y: point.y - actualBoardFrame.origin.y)
    guard pointInBoardFrame.y >= 0 else { return }

    // This line below makes an incorrect assumption
    let touchedRow = Int(pointInBoardFrame.y / circleDiameter)
    let rowStart = self.pointInBoardFrame(forCircleInRow: touchedRow, atIndex: 0).x
    let rowEnd = self.pointInBoardFrame(forCircleInRow: touchedRow, atIndex: touchedRow).x + circleDiameter
    guard pointInBoardFrame.x >= rowStart && pointInBoardFrame.x <= rowEnd else { return }
    let touchedIndex = Int((pointInBoardFrame.x - rowStart) / circleDiameter)


    print("touched circle: \(touchedRow) \(touchedIndex)")
}

The above does not work because it makes an incorrect assumption that the y coordinate of the tap can be used to unambiguously determine the row touched. This not true because there exist horizontal lines that pass through two rows.

How can I do this?

Answer 1

Both methods requires O(1) time, but the first one eats memory.

Simple solution: make hidden picture with the same circles, but draw every circle with specific color, for example: R component = row index, G component = index in the row. When tapping, translate coordinates to that picture and get color value in that point.

---

Math solution:

Represent tap coordinates in the basis of u-v vectors.

s3 = Sqrt(3)
u = (-R, R*s3)
v = (R, R*s3)

Every cartesian point (x,y) (relative to the center of top circle, OY axis is down!) might be represented as linear combination

x = a * ux + b * vx
y = a * uy + b * vy

We need to get a and b coefficients

multiply and subtract
x * uy = a * ux * uy + b * vx * uy
y * ux = a * uy * ux + b * vy * ux
x * uy - y * ux = b * (vx * uy - vy * ux)
b = (x * uy - y * ux) / (vx * uy - vy * ux)
x * vy - y * vx = a * (ux * vy - uy * vx)
a = (y * vx  - x * vy)/ (vx * uy - vy * ux)

Denominator is constant, so formulas are quite simple

denom = vx * uy - vy * ux = R * R * s3 + R * S3 * R =  2 * R^2 * s3 

a = (y * R - x * R*s3) / (2 * R^2 * s3) = - x / (2*R) + y / (2*R*s3)
b  = (x * R * s3 +  y * R ) / (2 * R^2 * s3) = x / (2*R) +  y / (2*R*s3)

After calculation of a and b round them to the closest integers and get row/index:

aa = round(a)
bb = round(b) 
row = a + b
index = b

Example:

R = 2
x = 2, y = 3.4 (near right center on my picture)
a = 0  b = 1
row = 1  index = 1

x = -2, y = 3.4  (near left center on my picture)
a = 1  b = 0 
row = 1  index = 0

Answer 2

Just iterate through your circles, and see what the distance between the hit point and the center is, and if less than the radius, then you know you tapped in that circle.

For example, based upon how you iterated in draw(_:), you could do something like:

func identifyCircle(for point: CGPoint) {
    let radius = size.width / 2

    for row in 0..<board.rowCount {
        for index in 0...row {
            let origin = pointInViewFrame(forCircleInRow: row, atIndex: index)
            let center = CGPoint(x: origin.x + size.width / 2, y: origin.y + size.height / 2)
            let distance = hypot(center.x - point.x, center.y - point.y)
            if distance <= radius {
                print(Date(), "tapped in \(row), \(index)")
            }
        }
    }
}

e.g.

override func touchesBegan(_ touches: Set<UITouch>, with event: UIEvent?) {
    guard let touch = touches.first else { return }
    let point = touch.location(in: self)

    identifyCircle(for: point)
}

Whether you use the touches methods or gesture recognizer really isn't material. But this is one way to determine which circle the CGPoint fell within.

Note, this assumes we're dealing with circles. If not, you'd probably want to fall back on the contains method of the UIBezierPath.