Как найти наименьший прямоугольник, который содержит все точки или точку, симметричную оси y = x?

Question

У меня есть набор точек (x, y). Как найти самый маленький прямоугольник (края перпендикулярны оси системы координат), который содержит эти точки или точки, симметричные оси y = x? Не все точки должны быть зеркальными изображениями одновременно, поэтому можно иметь некоторые нормальные и некоторые симметричные точки к оригинальным.

Answer 1

Вы могли решить эту проблему с помощью грубой силы O(n*2^n) подход: определить ваши очки в какой-то класс/структуру, которая, в дополнение к (x,y) координат вашей точки, также имеет логическое mirrored состояние. Для n количество точек, петля над всем 2^n Возможный набор состояний этого набора точек. Для каждого набора состояний вычислите окружность (2x+2y) ограничивающего прямоугольника.

Ниже следует это решение, реализованное в Swift. Если вы решите использовать этот подход грубой силы, мы надеемся, вы сможете перевести его на ваш язык выбора.

---

Точечные контейнеров и сервисных функций:

struct Point { 
    private var xOrig : Double 
    private var yOrig : Double 
    private var mirrored = false 
    var x : Double { return mirrored ? yOrig : xOrig } 
    var y : Double { return mirrored ? xOrig : yOrig } 

    init(_ x: Double, _ y: Double) { 
     xOrig = x 
     yOrig = y 
    } 

    mutating func setState(state: Bool) { 
     mirrored = state 
    } 
} 

func boundingBoxCircumference(points: [Point]) -> Double { 
    let xMax = points.maxElement { $0.x < $1.x }?.x ?? 0.0 
    let xMin = points.minElement { $0.x < $1.x }?.x ?? 0.0 
    let yMax = points.maxElement { $0.y < $1.y }?.y ?? 0.0 
    let yMin = points.minElement { $0.y < $1.y }?.y ?? 0.0 

    return 2*((xMax - xMin) + (yMax - yMin)) 
} 

func setMirroredStates(inout points: [Point], states: [Bool]) { 
    for i in 0..<points.count { 
     points[i].setState(states[i]) 
    } 
} 

Основные функции и пример

func findSmallestBox(var points: [Point]) -> Double { 
    var smallestBox = Double.infinity 
    for i in 0..<Int(pow(2,Double(points.count))) { 
     smallestBox = min(smallestBox, boundingBoxCircumference(points)) 

     var binString = String(i, radix: 2) 
     if let a = Optional(points.count - binString.characters.count) where a > 0 { 
      binString = "".stringByPaddingToLength(a, withString: "0", startingAtIndex: 0) + binString 
     } 
     let pointStates = Array(binString.characters).map { String($0) == "1" } 

     setMirroredStates(&points, states: pointStates) 
    } 
    return smallestBox 
} 

var myPoints : [Point] = [Point(1,2), Point(-4,3), Point(7,-5), Point(5,4), Point(-5, -1)] 
print(findSmallestBox(myPoints)) // 34