c++ - 点同时共线和不共线

Question

假设我有以下图表 -- https://www.desmos.com/calculator/eabskyo0hk

我需要做以下事情:

1. 判断apex(endpoint1)、dest(newvertex)和endpoint1是否 共线。

2. 如果它们不共线，找到它们的交点。

我写了下面的代码来做到这一点 -- http://coliru.stacked-crooked.com/a/c08cbe113e706a9c

不幸的是，它不能正常工作。它表示这些点不共线，但随后又表示它们的交点是 dest (newvertex)，因此第一个语句无效。

我想这一定是由于与浮点相关的问题，但我想知道如何在不更改坐标的情况下修复它？

提前致谢。

Answer 1

您的坐标值具有非常大的量级，因此将叉积量级与 std::numeric_limits<T>::epsilon() 进行比较给出错误的结果。

编辑:std::numeric_limits<T>::epsilon()不适合作为“这里的小值”。

您可以尝试根据坐标缩放“小值”。示例:

my_eps = 1.0E-9;
eps =  my_eps * Max(abs(x1), abs(y1)....

请注意，两个大值的微小差异已经包含了较大的相对误差，因此下一种方法是错误的:

eps = my_eps * Max(abs(y1 - y2), abs(x1 - x3), abs(y1 - y3), abs(x1 - x2)); 

描述的方法应该改进结果，但不会提供“ Elixir ”——有一些特殊的计算方法可用于稳健、容易出错的交集计算(问题是全局性的)。 Example - orientation test