c - 如何找到两条线段(不是两条直线)是否相交

标签 c algorithm computational-geometry xlib x11

我想找到一种方法来检查两条线段是否相交。我正在使用 Xlib 编程来实现这个。

我在网上查过,但我只找到了找到两条线的交点的方法,但没有找到两条线段的交点。

我如何使用 X lib 编程实现它?

最佳答案

为此您不需要 Xlib。设两段为

  • A1 = (x1, y1) -> B1 = (x1 + dx1, y1 + dy1)
  • A2 = (x2, y2) -> B2 = (x2 + dx2, y2 + dy2)

  • vp = dx1 * dy2 - dx2 * dy1

如果 vp == 0 线段平行且没有交点。

否则,令v = (vx, vy)A1A2 之间的 vector

  • vx = x2 - x1
  • vy = y2 - y1

计算

  • k1 = (vx * dy2 - vy * dx2)/vp
  • k2 = (vx * dy1 - vy * dx1)/vp

如果 k1k2 落在 [0, 1] 区间之外,则线段不相交(但底层线相交)。否则,路口在

(x1 + k1 * dx1, y1 + k1 * dy1)

顺便说一句,如果你想知道对称性,那将是同一个点

(x2 + k2 * dx2, y2 + k2 * dy2)

这些公式与How do you detect where two line segments intersect?上的答案基本相似除了从那里编码对于新手或匆忙的人来说不一定是微不足道的(就像我自己很多次一样)。

关于c - 如何找到两条线段(不是两条直线)是否相交,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18928803/

相关文章:

c - 如何编写 Windows 应用程序?

algorithm - 将一个文件复制到另一个文件并返回复制的字节数

python - 在 python 中使用枢轴算法在 3d 格中 self 避免随机游走

c - 使用 crypt 加密单词列表

C 在 ubuntu DNS 中使用 dig

c# - C# 中的 Liang-Barsky?

algorithm - 如何加粗折线?

algorithm - 找到覆盖所有点的最小面积的两个矩形

C程序判断一个数是否为素数

performance - 在小于 O(n^2) 的时间内在 2D 平面中找到距离最小的给定点集中的两个点