将一个点捕捉到一条线的最近部分？

Question

我有一个工单管理系统 Python 2.7.

在系统中，只能使用standard Python 2.7 library中包含的库（不能导入其他库）。

系统有线和点：

Line Vertex 1: 676561.00, 4860927.00
Line Vertex 2: 676557.00, 4860939.00

Point 100: 676551.00, 4860935.00
Point 200: 676558.00, 4860922.00

我想捕捉点到线的最近部分。

Snapping can be defined as:

Moving a point so that it coincides exactly with the closest part of a line.

似乎有两种不同的数学场景在起作用：

一个。线的最近部分是沿线的位置，其中 点垂直于线 .

乙。或者，线的最近部分只是 最近的顶点。

是否可以使用 Python 2.7（和标准 2.7 库）将点捕捉到直线的最近部分？

Answer 1

你可以计算线方程，然后计算每个点到线的距离。

例如：

import collections
import math

Point = collections.namedtuple('Point', "x, y")


def distance(pt, a, b, c):
    # line eq: ax + by + c = 0
    return math.fabs(a * pt.x + b * pt.y + c) / math.sqrt(a**2 + b**2)


l1 = Point(676561.00, 4860927.00)
l2 = Point(676557.00, 4860939.00)

# line equation
a = l2.y - l1.y
b = l1.x - l2.x
c = l2.x * l1.y - l2.y * l1.x

assert a * l1.x + b * l1.y + c == 0
assert a * l2.x + b * l2.y + c == 0

p100 = Point(676551.00, 4860935.00)
p200 = Point(676558.00, 4860922.00)

print(distance(p100, a, b, c))
print(distance(p200, a, b, c))

你得到：

6.957010852370434
4.427188724235731

Edit1：计算正交投影

你要的是p100和p200的orthographic projection在直线(l1,l2)上的坐标

你可以这样计算：

import collections
import math

Point = collections.namedtuple('Point', "x, y")


def snap(pt, pt1, pt2):
    # type: (Point, Point, Point) -> Point
    v = Point(pt2.x - pt1.x, pt2.y - pt1.y)
    dv = math.sqrt(v.x ** 2 + v.y ** 2)
    bh = ((pt.x - pt1.x) * v.x + (pt.y - pt1.y) * pt2.y) / dv
    h = Point(
        pt1.x + bh * v.x / dv,
        pt1.y + bh * v.y / dv
    )
    return h


l1 = Point(676561.00, 4860927.00)
l2 = Point(676557.00, 4860939.00)

p100 = Point(676551.00, 4860935.00)
p200 = Point(676558.00, 4860922.00)

s100 = snap(p100, l1, l2)
s200 = snap(p200, l1, l2)

print(s100)
print(p100)

你得到：

Point(x=-295627.7999999998, y=7777493.4)
Point(x=676551.0, y=4860935.0)

您可以检查捕捉点是否在线：

# line equation
a = l2.y - l1.y
b = l1.x - l2.x
c = l2.x * l1.y - l2.y * l1.x

assert math.fabs(a * s100.x + b * s100.y + c) < 1e-6
assert math.fabs(a * s200.x + b * s200.y + c) < 1e-6

Edit2：对齐线段

如果要捕捉到线段，需要检查正投影是否在线段内。

如果正投影在线段内：就是解，
如果它靠近线段的末端，则该末端就是解决方案。

您可以按照以下方式进行操作：

def distance_pts(pt1, pt2):
    v = Point(pt2.x - pt1.x, pt2.y - pt1.y)
    dv = math.sqrt(v.x ** 2 + v.y ** 2)
    return dv


def snap(pt, pt1, pt2):
    # type: (Point, Point, Point) -> Point
    v = Point(pt2.x - pt1.x, pt2.y - pt1.y)
    dv = distance_pts(pt1, pt2)
    bh = ((pt.x - pt1.x) * v.x + (pt.y - pt1.y) * pt2.y) / dv
    h = Point(pt1.x + bh * v.x / dv, pt1.y + bh * v.y / dv)
    if 0 <= (pt1.x - h.x) / (pt2.x - h.y) < 1:
        # in the line segment
        return h
    elif distance_pts(h, pt1) < distance_pts(h, pt2):
        # near pt1
        return pt1
    else:
        # near pt2
        return pt2

p100和p200的解法是：

Point(x=676557.0, y=4860939.0)
Point(x=676551.0, y=4860935.0)

Answer 2

这是一个 extremely helpful 资源。

import collections
import math

Line = collections.namedtuple('Line', 'x1 y1 x2 y2')
Point = collections.namedtuple('Point', 'x y')


def lineLength(line):
  dist = math.sqrt((line.x2 - line.x1)**2 + (line.y2 - line.y1)**2)
  return dist


## See http://paulbourke.net/geometry/pointlineplane/
## for helpful formulas

## Inputs
line = Line(0.0, 0.0, 100.0, 0.0)
point = Point(50.0, 1500)

## Calculations
print('Inputs:')
print('Line defined by: ({}, {}) and ({}, {})'.format(line.x1, line.y1, line.x2, line.y2))
print('Point "P": ({}, {})'.format(point.x, point.y))

len = lineLength(line)
if (len == 0):
  raise Exception('The points on input line must not be identical')

print('\nResults:')
print('Length of line (calculated): {}'.format(len))

u = ((point.x - line.x1) * (line.x2 - line.x1) + (point.y - line.y1) * (line.y2 - line.y1)) / (
    len**2)

# restrict to line boundary
if u > 1:
  u = 1
elif u < 0:
  u = 0

nearestPointOnLine = Point(line.x1 + u * (line.x2 - line.x1), line.y1 + u * (line.y2 - line.y1))
shortestLine = Line(nearestPointOnLine.x, nearestPointOnLine.y, point.x, point.y)

print('Nearest point "N" on line: ({}, {})'.format(nearestPointOnLine.x, nearestPointOnLine.y))
print('Length from "P" to "N": {}'.format(lineLength(shortestLine)))

Answer 3

另一个选项：

# snap a point to a 2d line
# parameters: 
#   A,B: the endpoints of the line
#   C: the point we want to snap to the line AB
# all parameters must be a tuple/list of float numbers
def snap_to_line(A,B,C):
    Ax,Ay = A
    Bx,By = B
    Cx,Cy = C

    # special case: A,B are the same point: just return A
    eps = 0.0000001
    if abs(Ax-Bx) < eps and abs(Ay-By) < eps: return [Ax,Ay] 

    # any point X on the line can be represented by the equation
    #   X = A + t * (B-A)
    # so for point C we compute its perpendicular D on the line 
    # and the parameter t for D
    # if t is between 0..1 then D is on the line so the snap point is D
    # if t < 0 then the snap point is A
    # if t > 1 then the snap point is B
    #
    # explanation of the formula for distance from point to line:
    #    http://paulbourke.net/geometry/pointlineplane/
    #
    dx = Bx-Ax
    dy = By-Ay
    d2 = dx*dx + dy*dy
    t = ((Cx-Ax)*dx + (Cy-Ay)*dy) / d2
    if t <= 0: return A
    if t >= 1: return B
    return [dx*t + Ax, dy*t + Ay]


if __name__=="__main__":
    A,B = [676561.00, 4860927.00],[676557.00, 4860939.00]
    C = [676551.00, 4860935.00]
    print(snap_to_line(A,B,C))
    C = [676558.00, 4860922.00]
    print(snap_to_line(A,B,C))

将一个点捕捉到一条线的最近部分？

Snap a point to the closest part of a line?

python

python-2.7

math

trigonometry

snapping