1

Здравствуйте!

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

(100,100),(200,100),(150,200),(100,200).

Если соединить эти точки линиями, выйдет прямоугольная трапеция, и мне отсюда нужно найти правую нижнюю (150,200) точку. Раньше, когда имел дело только с прямоугольниками (а не трапециями, как в этом случае), в цикле у всех точек искал максимальную координату, и потом искал точку с такими координатами, но в данном случае максимальными будут координаты (200,200), и точки с такими - нету...

4
  • мне кажется или (150,200) - это права верхняя точка?
    – Spectre
    30 авг 2012 в 11:40
  • 4
    потому что Вы математик, а @metalurgus - начинающий программист и у него ось у направлена сверху вниз.:)
    – KoVadim
    30 авг 2012 в 12:00
  • 1
    Я так понимаю, что единственный интерес вопроса в том, что будет правильным ответом в случае набора, состоящего из двух точек {(150, 200), (200, 150)}. А дальше уже вариации на тему сортировки в coordinatewise порядке. 30 авг 2012 в 12:07
  • 2
    - Самый универсальный вариант (поскольку у вас написано "к примеру", а значит, возможно, подразумевается какая-либо дополнительная логика) - придумать метрику "хорошести" относительно исходных условий и выбрать из последовательности точек точку с наибольшим значением этой метрики. - Разумеется, такую метрику можно придумать не всегда, да и не каждый из придуманных вариантов, строго говоря, будет метрикой. 30 авг 2012 в 12:15

4 ответа 4

5

Предлагаю(for @iranda начал с большой буквы) следующую идею сортировки подобного массива с помощью js:

var array = [{x: 100, y: 100}, {x: 200, y: 100}, {x: 150, y: 200}, {x: 100, y: 200}];
array.sort(function(a,b){ return a.y - b.y || a.x - b.x });

Результат:

[{x: 100, y: 100}, {x: 200, y: 100}, {x: 100, y: 200}, {x: 150, y: 200}]

Т.о. получаем :

array[0] - левая нижняя
array[1] - правая нижняя
array[2] - левая верхняя
array[3] - правая верхняя

P.S. для сильно кривых трапеций алгоритм недееспособен

1
  • Спасибо, ваш и предыдущий ответ решили мою задачу! 30 авг 2012 в 13:51
4

Нужно последовательно пройти по всем точкам, проверяя их на "правость" и "нижнесть" одновременно. Очередную точку следует считать "более лучшим" кандидатом на роль самой правой и нижней в том случае, если у неё хотя бы одна из координат имеет более правое или более нижнее значение, чем у наилучшего на данный момент кандидата, при условии, что другая координата не ухудшает положение (т.е. меньше или равна соответствующей координате у лучшего). Та точка, которая окажется наилучшей в самом конце, как раз и будет самой правой и нижней.

2
  • Спасибо, то что нужно! 30 авг 2012 в 13:51
  • правда, если взять такой вариант (100,100) (100,200) (101,101) (200,100) - то я даже не знаю, какой угол будет правым нижним. Правда в этом случае не будет пересечения.
    – KoVadim
    30 авг 2012 в 14:07
4

Предлагаю алгоритм. Есть четыре точки. Значит можно соединить их попарно двумя отрезками тремя способами (1-2, 3-4; 1-3,2-4; 1-4,2-3). В одном случае из трех эти отрезки будут пересекаться. Найдя точку пересечения (которая будет неким центром), сравниваем координаты с ней. Если обе координаты нужной точки больше координат точки пересечение, то это и будет ниже-правее (в системе координат с осью у вниз).

Если же для точки одна с координат будет совпадать с координатами центральной точки - у нас ромб.

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

Нахождение пересечения двух отрезков - классическая задача и много раз разобрана, например: 1 и 2.

0

Можно пройтись по всем точкам проверяя их на максимально правый и нижний, но может случится так что 2 точки которые проверяются на правость могут быть равны и это надо учесть.

const arr = [{x: 100, y: 100}, {x: 200, y: 100}, {x: 150, y: 200}, {x: 100, y: 200}];
let index = 0;
let minX = arr[0].x;
let maxY = arr[0].y;
arr.forEach((item, i) => {
  if (item.y > maxY || (item.y === maxY && item.x < minX)) {
    maxY = item.y;
    minX = item.x
    index = i;
  }
});

index будет равен индексу самому правому и нижнему углу, но учтите что именно самому правому нижнему, т.е может оказаться точка ниже но не правее

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.