Алгоритм дискретизации линии
Для некоторой заданной линии, ограниченной точками (x_1, y_1), (x_2, y_2)Какие алгоритмические методы и подходы доступны для дискретизации этой линии на четное число сегментов?
Математически, я полагаю, можно просто:
(1) найти длину,
(2) разделить на N количество сегментов, а затем
(3) вычислить точку сегмента из этих данных,
но мне интересно, есть ли лучший или более ориентированный на «компьютерные науки» подход к этому.
Я студент первого курса CS, поэтому я не знаю, что я ищу, и даже, где начать искать.
Решение
Нет необходимости рассчитывать и использовать длину.
Вы можете найти промежуточные точки (для N равных отрезков) с помощью простой линейной интерполяции:
for i = 1 to N - 1
Point[i].X = X1 + (X2 - X1) * i / N
Point[i].Y = Y1 + (Y2 - Y1) * i / N
Если вы обеспокоены эффективностью, предварительно вычислите X_coeff = (X2 - X1) / N и использовать это значение внутри цикла
Другие решения
Вот пример того, как прочитать две точки (и N) из std :: cin, затем вычислить сегменты и, наконец, вывести их в std :: cout.
#include <iostream>
#include <vector>
struct point
{
double x;
double y;
};
int main()
{
point P1;
point P2;
size_t N;
std::cin >> P1.x >> P1.y;
std::cin >> P2.x >> P2.y;
std::cin >> N;
std::vector<point> segments(N + 1);
double x_diff = (P2.x - P1.x) / N;
double y_diff = (P2.y - P1.y) / N;
for (size_t i = 1; i < segments.size(); ++i)
{
segments[i].x = P1.x + x_diff * i;
segments[i].y = P1.y + y_diff * i;
}
segments[0] = P1;
for (size_t i = 1; i < segments.size(); ++i)
{
std::cout << "(" << segments[i-1].x << "," << segments[i-1].y << ") - ";
std::cout << "(" << segments[i].x << "," << segments[i].y << ")" << std::endl;
}
}
detector