这是我的答案。我已经通过创建一个循环来测试它是否准确，该循环检查它给出的答案是否与 Boost 几何库给出的答案相同，并且他们同意每个测试，尽管我在下面写的那个比它快得多Boost中的那个。对于所有可能的线段对，该测试生成每个可能的线段，其中 x 是 [-3,2] 中的整数，y 是 [-3,2] 中的整数。
下面的代码认为在端点处相交的线段是相交的。T 形交叉口也被认为是交叉口。代码是 c++，但很容易适应任何语言。它基于不同的 stackoverflow 答案，但该答案没有正确处理端点。
它使用叉积方法，可以报告一个点是在给定射线的左边还是右边。
在数学上需要进行一些优化，但是这样做并没有显示出编译时g++ -O2的性能提升，有时甚至会降低性能！编译器能够进行这些优化，所以我更愿意让代码保持可读性。
// is_left(): tests if a point is Left|On|Right of an infinite line.
// Input: three points p0, p1, and p2
// Return: >0 for p2 left of the line through p0 and p1
// =0 for p2 on the line
// <0 for p2 right of the line
// See: Algorithm 1 "Area of Triangles and Polygons"
// This is p0p1 cross p0p2.
extern inline coordinate_type_fp is_left(point_type_fp p0, point_type_fp p1, point_type_fp p2) {
return ((p1.x() - p0.x()) * (p2.y() - p0.y()) -
(p2.x() - p0.x()) * (p1.y() - p0.y()));
}
// Is x between a and b, where a can be lesser or greater than b. If
// x == a or x == b, also returns true. */
extern inline coordinate_type_fp is_between(coordinate_type_fp a,
coordinate_type_fp x,
coordinate_type_fp b) {
return x == a || x == b || (a-x>0) == (x-b>0);
}
// https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
extern inline bool is_intersecting(const point_type_fp& p0, const point_type_fp& p1,
const point_type_fp& p2, const point_type_fp& p3) {
const coordinate_type_fp left012 = is_left(p0, p1, p2);
const coordinate_type_fp left013 = is_left(p0, p1, p3);
const coordinate_type_fp left230 = is_left(p2, p3, p0);
const coordinate_type_fp left231 = is_left(p2, p3, p1);
if (p0 != p1) {
if (left012 == 0) {
if (is_between(p0.x(), p2.x(), p1.x()) &&
is_between(p0.y(), p2.y(), p1.y())) {
return true; // p2 is on the line p0 to p1
}
}
if (left013 == 0) {
if (is_between(p0.x(), p3.x(), p1.x()) &&
is_between(p0.y(), p3.y(), p1.y())) {
return true; // p3 is on the line p0 to p1
}
}
}
if (p2 != p3) {
if (left230 == 0) {
if (is_between(p2.x(), p0.x(), p3.x()) &&
is_between(p2.y(), p0.y(), p3.y())) {
return true; // p0 is on the line p2 to p3
}
}
if (left231 == 0) {
if (is_between(p2.x(), p1.x(), p3.x()) &&
is_between(p2.y(), p1.y(), p3.y())) {
return true; // p1 is on the line p2 to p3
}
}
}
if ((left012 > 0) == (left013 > 0) ||
(left230 > 0) == (left231 > 0)) {
if (p1 == p2) {
return true;
}
return false;
} else {
return true;
}
}
测试代码：
BOOST_AUTO_TEST_CASE(small, *boost::unit_test::disabled()) {
for (double x0 = -3; x0 < 3; x0++) {
for (double y0 = -3; y0 < 3; y0++) {
for (double x1 = -3; x1 < 3; x1++) {
for (double y1 = -3; y1 < 3; y1++) {
for (double x2 = -3; x2 < 3; x2++) {
for (double y2 = -3; y2 < 3; y2++) {
for (double x3 = -3; x3 < 3; x3++) {
for (double y3 = -3; y3 < 3; y3++) {
point_type_fp p0{x0, y0};
point_type_fp p1{x1, y1};
point_type_fp p2{x2, y2};
point_type_fp p3{x3, y3};
linestring_type_fp ls0{p0,p1};
linestring_type_fp ls1{p2,p3};
BOOST_TEST_INFO("intersection: " << bg::wkt(ls0) << " " << bg::wkt(ls1));
BOOST_CHECK_EQUAL(
path_finding::is_intersecting(p0, p1, p2, p3),
bg::intersects(ls0, ls1));
}
}
}
}
}
}
}
}
}