Нахождение минимальной ограничительной рамки выпуклой оболочки

Допустим, у меня есть выпуклая боковая оболочка, теперь как получить правый / левый верхний / нижний углы выпуклой оболочки, теперь давайте скажем, что возможно N равно 3, а координаты треугольника 0,0 50,0 0,50 или что-то еще, мы знаем, что такое углы и что 0,50 считается как правым верхним, так и левым, поэтому есть какой-то способ получить это, а не то, что у меня здесь, где Left_Bottom и т. д. являются векторами, а значения — это векторный массив

    Left_Bottom = values[0];
Left_Top = values[0];
Right_Bottom = values[0];
Right_Top = values[0];
for (int i = 1; i < values.length; i++) {
if (!Left_Bottom.XisLess(values[i])) {
if (Left_Bottom.YisLess(values[i])) {
Left_Bottom = values[i];
}
}

if (!Left_Top.XisLess(values[i])) {
if (!Left_Top.YisLess(values[i])) {
Left_Top = values[i];
}
}

if (Right_Bottom.XisLess(values[i])) {
if (Right_Bottom.YisLess(values[i])) {
Right_Bottom = values[i];
}
}

if (Right_Top.XisLess(values[i])) {
if (!Right_Top.YisLess(values[i])) {
Right_Top = values[i];
}
}
}

1

Решение

  1. Если вы ищете задача нахождения выпуклой оболочки конечного множества точек, Взгляни на Вот. Вы можете найти несколько решений для этого в O (n * log n)

введите описание изображения здесь

  1. Если вы просто ищете четыре угла ограничивающего прямоугольника этого выпуклого корпуса, на самом деле вы ищете минимальная ограничительная рамка для выпуклой оболочки.

    • Если ограничивающая рамка параллельна координатным осям, просто найдите min_x, min_y, max_x а также max_y среди всех этих выпуклых точек корпуса. Тогда четыре угла (по часовой стрелке):

      1. (min_x, min_y)

      2. (max_x, min_y)

      3. (max_x, max_y)

      4. (min_x, max_y)

введите описание изображения здесь

  • Если ограничивающая рамка не параллельна координатным осям, это становится сложным. Проверьте ссылки, представленные в Вот а также Вот для реализации.

введите описание изображения здесь

1

Другие решения

Других решений пока нет …