有没有更好的方法来确定与垂直线相交的两条线段的顺序？顺序是根据交点的 y 坐标。天真的方法是计算交点并进行比较。
问问题
738 次
2 回答
0
I can give you some pointers to solve this problem:
- A more faster way to find the intersection between lines can be with the use of determinants as show this Wikipedia entry.
- An algorithm to solve the more general version this problem, is the Bentley–Ottmann algorithm, created for testing whether or not a set of line segments has any crossings.
I believe this entry in the Wikipedia about Line segment intersection encompasses your inquiries in this matter.
于 2012-06-11T04:20:58.897 回答
0
我假设这些线是使用端点指定的。
具有端点 ( x0, y0)/( x1, y1) 的线与具有 x 坐标的垂直线的交点x在：
y = (dy/dx)(x - x0) + y0
哪里dx = x1 - x0和dy = y1 - y0。
您有 2 行并且正在计算：
(day/dax)(x - ax0) + ay0 < (dby/dbx)(x - bx0) + by0
您可以将两边相乘dax * dbx以消除分歧：
(day * dbx)(x - ax0) + (ay0 * dax * dbx) < (dby * dax)(x - bx0) + (by0 * dax * dbx)
并简化一点：
(day * dbx)(x - ax0) - (dby * dax)(x - bx0) + (ay0 - by0)(dax * dbx) < 0
这不一定更好——这取决于具体情况：
dax如果坐标是整数，这可以让你精确地执行测试，但是如果/dbx/etc 很大，它也容易溢出- 如果坐标是浮点数，如果浮点除法很慢，它可能会更快
于 2012-06-11T04:24:53.420 回答