当在计算机程序中完成类似的事情时,您可能需要处理的问题之一是仅使用整数算术(或尽可能多)来执行这些计算,假设输入是整数。尽可能以整数进行此操作是一个单独的问题,我不会在这里讨论。
以下是一个“数学”解决方案,如果按字面实现,则需要浮点计算。我不知道这对于你的情况是否可以接受。您可以根据自己的喜好自行优化。
(1)代表您的线路L
by
A * x + B * y + C = 0
方程。注意向量(A, B)
是这条线的法向量。
例如,如果直线由两点定义X1(x1, y1)
and X2(x2, y2)
, then
A = y2 - y1
B = -(x2 - x1)
C = -A * x1 - B * y1
(2)通过将所有系数除以向量的长度来标准化方程(A, B)
。 IE。计算长度
M = sqrt(A * A + B * B)
然后计算值
A' = A / M
B' = B / M
C' = C / M
等式
A' * x + B' * y + C' = 0
仍然是你的直线的等价方程L
除了现在法向量(A', B')
是单位向量。
(3)说出你的观点P(px, py)
并计算值
D = A' * px + B' * py + C'
这将为您提供signed距离D
从你的观点来看P
到你的线路L
。换句话说,这是距离P
到最近的点L
(我们并不真正关心最近点本身,我们只需要距离)。
标志上写着哪个side线的L
重点P
位于。如果P
位于向量的同一侧(A', B')
指向(“正”侧),距离为正。如果P
位于另一侧(“负”侧),距离为负。
(4)为了找到你的镜像点P'(px', py')
你需要改变你的观点P
按绝对距离|2 * D|
跨过这条线L
到另一边。
“越过线”的真正意思是如果点P
位于“积极”的一面L
,那么我们必须逆着向量的方向移动它(A', B')
到“消极”的一面。反之亦然,如果点P
位于“消极”的一面L
,那么我们必须将其沿向量方向移动(A', B')
到“积极”的一面。
这可以简单地表示为将点移动距离-2 * D
(注意负号)向量方向(A', B')
.
这意味着
px' = px - 2 * A' * D
py' = py - 2 * B' * D
给你你的镜像点P'(px', py')
.
或者,您可以使用基于查找实际最近点的方法N
在线的L
然后反映你的观点P
与N
。这已经在其他答案中建议过,我只会描述我会如何做。
(1)建立一个方程
A*x + B*y + C = 0
为您的线路L
完全按照上面步骤 1 中的描述。无需标准化该方程。
(2)建立穿过的垂直线的方程P
。假设垂直线表示为
D*x + E*y + F = 0
The D
and E
系数立即已知
D = B
E = -A
while F
可以通过代入点计算P
代入方程
F = -D*px - E*py
(3)通过求解两个线性方程组找到这两条线的交点
A*x + B*y = -C
D*x + E*y = -F
克莱默法则在这种情况下效果很好。给出的公式为线相交维基百科中的文章无非是克莱默规则在该系统中的应用。
该解决方案为您提供最近的点N(nx, ny)
我们正在寻找。
(4)现在只要计算一下
px' = nx + (nx - px)
py' = ny + (ny - py)
找到你的观点P'(px', py')
.
请注意,这种方法几乎可以完全用整数来实现。唯一可能失去精度的步骤是第 3 步中克莱默规则内的除法。当然,像往常一样,您必须为“几乎积分”解决方案付出的代价是需要进行大量算术。偶系数C
and F
可能会溢出,更不用说克莱默规则公式中的计算了。