Точка привязки к ближайшей линии

Question

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

Пример:

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

Point = (6, 6)

NearestPointOnLine = (4, 6) // magic here

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

Answer 1

Итерируя от сегмента к сегменту, для каждого сегмента найдите ближайшую точку от этого сегмента до точки (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);

Answer 2

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

Заметка (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;

Answer 3

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

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

2) Если y1 <= yp <= y2, ответ (x, yp). Если yp

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