Обрезка перед запуском алгоритма выпуклой оболочки - PullRequest
Новая
       72

Обрезка перед запуском алгоритма выпуклой оболочки

1 голос
/ 02 мая 2019

Я должен сформировать выпуклый корпус из большого количества точек, и я наткнулся на эту статью.Весь процесс сокращения описан и хорошо объяснен, за исключением одной части.

Я не знаю, что означает эта часть и как преобразовать ее в код:

Так как пробелявляется двумерным, каждая точка имеет две координаты, x> и y.Каждый раз, когда мы читаем новую точку, мы вычисляем следующие 4> точки:

A = (Ax, Ay), который максимизирует xy B = (Bx, Xy), который максимизирует x + y C = (Cx, Cy), который минимизирует xy D = (Dx, Dy), который минимизирует x + y

Может ли кто-нибудь помочь мне вычислить точки A, B, C, D?

1 Ответ

1 голос
/ 03 мая 2019

Вы не так много вычисляя точек, вы выбираете их из своих входных данных:

  • A - это точка во ваших входных данных, гдезначение x-y больше, чем любая другая точка входных данных.
  • B - это точка во ваших входных данных, где значение x+y больше, чем любая другая точка входных данных.
  • C - это точка во ваших входных данных, где значение x-y меньше, чем любая другая точка входных данных.
  • D - это точка во ваших входных данных, где значение x+y меньше, чем любая другая точка входных данных.
...