Ближайшая пара из четырех точек c программой

Question

Мне нужно найти ближайшую пару из четырех пунктов программы C.Этот код на три пункта.Мне нужно это решение для четырех пунктов.

Я пробовал это.Это решение на три входа.

Когда я введу три точки, я получу самую близкую, но мне нужна ближайшая точка из четырех точек.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct Point
{
    int x, y ;
};
double getDistanceAB(struct Point a, struct Point b)
{
    double distanceAB;
    distanceAB = sqrt((a.x - b.x) * (a.x - b.x) + (a.y-b.y) *(a.y-b.y));
    return distanceAB;
}
double getDistanceBC(struct Point b, struct Point c)
{
    double distanceBC;
    distanceBC = sqrt((b.x - c.x) * (b.x - c.x) + (b.y-c.y) *(b.y-c.y));
    return distanceBC;
}
double getDistanceAC(struct Point a, struct Point c)
{
    double distanceAC;
    distanceAC = sqrt((a.x - c.x) * (a.x - c.x) + (a.y-c.y) *(a.y-c.y));
    return distanceAC;
}
int main()
{
    struct Point a, b, c;
    printf("Enter coordinate of points a: ");
    scanf("%d %d", &a.x, &a.y);
    printf("Enter coordinate of points b: ");
    scanf("%d %d", &b.x, &b.y);
    printf("Enter coordinate of points c: ");
    scanf("%d %d", &c.x, &c.y);
    if((getDistanceAB(a,b))>(getDistanceBC(b,c)) && (getDistanceAB(a,b))>(getDistanceBC(a,c)))
    {
        printf("Point A and B are closest.");
    }
    else if((getDistanceBC(b,c))>(getDistanceAC(a,c)) && (getDistanceBC(b,c))>(getDistanceAC(a,b)))
    {
        printf("Point B and C are closest.");
    }
    else if((getDistanceBC(a,c))>(getDistanceAC(a,b)) && (getDistanceBC(a,c))>(getDistanceAC(b,c)))
    {
        printf("Point A and C are closest.");
    }
    else
    {
        printf("All point are same.");
    }
}

Answer 1

Вот как я это решу,

#include <stdio.h>

typedef struct
{
    int x;
    int y;
} Point;

int square(int x) { return x * x; }

int distanceSq(Point *a, Point *b)
{
    return square(a->x - b->x) + square(a->y - b->y);
}

int main(int argc, char const *argv[])
{
    int n = 4;
    Point a[4];
    for (int i = 0; i < n; i++)
    {
        printf("Enter Point %d <as x y>: ", i + 1);
        scanf("%d %d", &a[i].x, &a[i].y);
    }

    int distance = __INT_MAX__;
    int p1 = -1, p2 = -1;

    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
        {
            int current = distanceSq(&a[i], &a[j]);
            if (current < distance)
            {
                p1 = i;
                p2 = j;
                distance = current;
            }
        }

    printf("The closest points are [%d %d] and [%d %d]", a[p1].x, a[p1].y, a[p2].x, a[p2].y);

    return 0;
}

Примечание:

1. Это можно продлить на n пунктов
2. Дает нампервая пара ближайших точек
3. нам не нужно брать квадратные корни, так как если квадрат большой, квадратный корень будет пропорционально большим (в случае большого количества (n) точек это может сэкономить время вычислений)

Answer 2

Во-первых, измените это:

double getDistanceAB(struct Point a, struct Point b)
{
    double distanceAB;
    distanceAB = sqrt((a.x - b.x) * (a.x - b.x) + (a.y-b.y) *(a.y-b.y));
    return distanceAB;
}
double getDistanceBC(struct Point b, struct Point c)
{
    double distanceBC;
    distanceBC = sqrt((b.x - c.x) * (b.x - c.x) + (b.y-c.y) *(b.y-c.y));
    return distanceBC;
}
double getDistanceAC(struct Point a, struct Point c)
{
    double distanceAC;
    distanceAC = sqrt((a.x - c.x) * (a.x - c.x) + (a.y-c.y) *(a.y-c.y));
    return distanceAC;
}

на следующее:

   double getDistance(struct Point a, struct Point b)
{
    double distance;
    distance = sqrt((a.x - b.x) * (a.x - b.x) + (a.y-b.y) * (a.y-b.y));
    return distance;
}

Одним из основных пунктов функций является то, что вам не нужно повторять код.

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

Имейте в виду это для дерева решений, которое вы приняли ... Если вы проверяете, не является ли точка 'a' ближайшей, используя ту же логику, которую вы использовали в исходном сообщении, вам не нужно сравниватьснова укажите точку «а».

Answer 3

Итак, решение для любого количества точек.

Просто измените MAX_POINTS на все, что вам может понадобиться.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

#define MAX_POINTS (4U)

struct Point
{
    int x;
    int y;
};

struct PointPair
{
    struct Point a;
    struct Point b;
};

double getDistance(const struct PointPair pair)
{
    return sqrt((pair.a.x - pair.b.x) * (pair.a.x - pair.b.x) +
                (pair.a.y - pair.b.y) * (pair.a.y - pair.b.y));
}

void readPoints(struct Point points[const])
{
    for (unsigned i = 0; i < MAX_POINTS; i++)
    {
        printf("Enter coordinate of point %u: ", i);
        scanf("%d %d", &(points[i].x), &(points[i].y));
    }
}

bool checkForShorterDistance(const struct PointPair pair, double *const p_minDistance)
{
    double tempDistance = getDistance(pair);

    if (tempDistance < *p_minDistance)
    {
        *p_minDistance = tempDistance;
        return true;
    }

    return false;
}

struct PointPair getClosestPair(const struct Point points[const])
{
    struct PointPair result =
    {
        .a = points[0],
        .b = points[1]
    };
    double minDistance = getDistance(result);

    struct PointPair tempPair;

    unsigned i, j;

    for (i = 0; i < MAX_POINTS; i++)
    {
        tempPair.a = points[i];

        for (j = 0; j < MAX_POINTS; j++)
        {
            if (i == j)
            {
                continue;
            }

            tempPair.b = points[j];

            if (checkForShorterDistance(tempPair, &minDistance))
            {
                result = tempPair;
            }
        }
    }

    return result;
}

int main(void)
{
    struct Point points[MAX_POINTS];

    readPoints(points);

    struct PointPair pair = getClosestPair(points);

    printf("Closest pair is (%d, %d) and (%d, %d)\n",
           pair.a.x,
           pair.a.y,
           pair.b.x,
           pair.b.y);

    return 0;
}

Answer 4

Я бы сократил количество функций до double getDistance(struct Point p, struct Point o) и сохранил бы ваши точки в списке, чтобы вы могли позволить программе динамически проходить через точки вместо программирования каждого условия.

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

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

Я не привык к синтаксису C, но для проверки точек в списке вам понадобится двойной цикл for, в котором первый проходит через каждую точку в списке, а второйпроверяет расстояние от / до этой первой точки до всех точек позже в списке.

for i = 0, i++, length(listOfPoints) {
    for j = i+1, j++, length(listOfPoints) {
        getDistance(listOfPoints[i], listOfPoints[j]
    }
}

Надеюсь, это поможет некоторым.