Блог

Главная - Вопросы по программированию - Привязка точки к ближайшей строке

Привязка точки к ближайшей строке

#algorithm #2d #point #lines

#алгоритм #2d #точка #строки

Вопрос:

У меня есть начальная и конечная точки каждой строки. Каждая строка может быть только вертикальной или горизонтальной.

Пример:

введите описание изображения здесь

 Lines = [
  ((1, 1), (1, 7)), // (start, end)
  ((1, 1), (7, 1)),
  ((4, 1), (4, 7))
]

Point = (6, 6)

NearestPointOnLine = (4, 6) // magic here

Как мне вычислить ближайшую точку на линии для любой точки?

Комментарии:

1. Что должно произойти, если точка не находится на одном уровне с линией? например ((1, 1), (1, 5)) , точка линии (2, 6) . Следует ли учитывать эту строку?

2. Итак, мы говорим о сегментах, а не о строках.

3. уэтсон: Да, так и должно быть.

4. Что вы пробовали до сих пор?

Ответ №1:

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

Примечание ( line.x и line.y любая точка на line , начало или конец)

 var closestLine;
var closestDistance = maxvalue;
foreach line
{
   var distance = line.isHorizontal? line.x - point.x : line.y - point.y;
   distance = Math.Abs(distance);
   if (distance<closestDistance)
   {
      closestDistance = distance;
      closestLine = line;
   }
}
var snapX = closestLine.isHorizontal ? point.x : closestLine.x;
var snapY = closestLine.isHorizontal ? closestLine.y : point.y;

Ответ №2:

Переходя от сегмента к сегменту, для каждого сегмента найдите ближайшую точку из этого сегмента к точке (a, b).

Существует три случая:

  • Горизонтальная линия (x1, y) к (x2, y) и точка (a, b) имеет x1 <= a <= x2, поэтому ближайшая точка (a, y)

  • Вертикальная линия (x, y1) к (x, y2) и точка (a, b) имеют y1 <= b <= y2, поэтому ближайшая точка (x, b)

  • Ни в одном из этих двух приведенных выше случаев, в данном случае ближайшая точка не является ни начальной, ни конечной точкой сегмента. Вы можете легко определить, вычислив расстояние от (a, b) до начала и конца.

После получения всей точки просто верните точку, которая имеет наименьшее расстояние по сравнению с другими. Формула для вычисления расстояния от точки (a, b) до точки (c, d):

 int x = a - c;
int y = b - d;
double dist = sqrt(x*x   y*y);

Ответ №3:

Вам просто нужно рассмотреть несколько случаев (я покажу, как это сделать для вертикальной линии, для горизонтальной линии это почти то же самое):

1) Предположим, что ((x, y1); (x, y2)) — это строка, а (xp, yp) — точка.

2) Если y1 <= yp <= y2, ответ будет (x, yp). Если yp < y1, это (x, y1). В противном случае ближайшей точкой будет (x, y2).

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