Расчет самой дальней точки из набора других точек

Question

Я разрабатываю симуляцию, в которой у меня есть двумерное поле с заданной высотой и длиной (скажем, 100 х 100 м).Теперь у меня есть несколько точек в этом поле с координатами x и y (немного, около 6 или 7).Теперь я должен вычислить (или просто приблизить) точку, которая находится дальше всего от всех этих точек.

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

Может кто-нибудь намекнуть мне на возможное, более простое решение или предложить пример кода?Я стремлюсь реализовать его в методе C ++ с выводом x- и y-координат точки.

Answer 1

Этот веб-сайт содержит описание алгоритма вычисления диаграммы Вороного для ваших точек, а также реализацию C ++ в zipfile.Если моя математическая интуиция верна, самая дальняя точка из любой из ваших точек в вашем пространстве 100x100 должна быть вершиной на диаграмме Вороного (если вы включите ребра по краям вашего пространства).Поэтому, если вы вычислили диаграмму, а затем проверили каждую вершину диаграммы, вы должны найти самую дальнюю точку.

Answer 2

Мой подход:

Подготовьте матрицу расстояний, для набора из 7 точек у вас будет 49 значений расстояния.Затем напишите сумму значений для каждой строки, или вы можете вычислить суммы для каждого столбца.Контрольная точка строки (или столбца), имеющая наибольшую сумму, является точкой, которая является наиболее удаленной от всех других точек в наборе данных.Это можно сделать быстро только за ограниченное количество очков.

Бабу V Басса.

Answer 3

Вы можете сравнить каждую точку с центром тяжести x- и y-координат ваших точек, которые вы хотите сравнить.

Чтобы получить точку, представляющую все точки, которые вы хотите сравнить, вы можете сделать это:

#include <iostream>

using namespace std;

int main()
{
    int a, sumx = 0, sumy = 0 ;

       /* or use this
            int a,sum;
            sum = 0;
        */


    int arrayx[] = {1, 2, 3, 4, 5};
    int arrayy[] = {5, 5, 7, 9, 14};
    int length = 5;

    for (a=0; a<length; a++)
    {
        sumx+=arrayx[a];
        sumy+=arrayy[a];
    }

int gravx = sumx/length;
int gravy = sumy/length;

cout << "Grav of x = " << gravx << endl;
cout << "Grav of y = " << gravy << endl;

return 0;
}

Вы можете попробовать код здесь: https://www.onlinegdb.com/online_c++_compiler