标签: line-intersection

如何确定两条线是否相交,如果它们相交,在x,y点处是什么？

我已经尝试搜索一个javascript函数,它将检测两条线是否相互交叉.

该函数将获取每一行的两个起始端点的x,y值(我们称之为A行和B行).

如果相交则返回true,否则返回false.

功能示例.如果答案使用矢量对象,我很高兴.

Function isIntersect (lineAp1x, lineAp1y, lineAp2x, lineAp2y, lineBp1x, lineBp1y, lineBp2x, lineBp2y) 
{

    // JavaScript line intersecting test here. 

}

一些背景信息:这段代码是我想在html5画布中制作的游戏,也是我碰撞检测的一部分.

我如何使用numpy来计算两个线段之间的交点？

在代码中我有segment1 =((x1,y1),(x2,y2))和segment2 =((x1,y1),(x2,y2)).注意段1不等于segment2.所以在我的代码中我也一直在计算斜率和y截距,如果可以避免这种情况会很好但我不知道如何.

我一直在使用Cramer的规则和我在Python中编写的函数,但我想找到一种更快的方法.

给定一个线段列表,找到交叉点的最简单方法是遍历线段列表,检查它们是否相交并记录它们的交点.

但是这种方法的运行时O(n^2)效率非常低.还有其他算法可以加快这个过程吗？

我正在使用以下代码绘制线条,它的工作效果令人惊叹,

http://www.merowing.info/2012/04/drawing-smooth-lines-with-cocos2d-ios-inspired-by-paper/

现在我想......

1>检测线是否与自身相交.2)检测CCSprite是否在此闭合线内.

在搜索时,我遇到了LineIntersection的许多逻辑,但没有一个是准确的.我给它们中的一个检测交叉点,但是当没有交叉线时它也检测到它.

1. 第一种方法

   - (BOOL) lineIntersectOccured:(CGPoint)t1 pointEnd:(CGPoint)t2
   {
       BOOL result = NO;
       int pointsCount = [arrlinePoints count];
   
       CGPoint cp1;
       CGPoint cp2;
   
       for(int i = 0, j = 1; j < pointsCount; i++,j++)
       {
           [[arrlinePoints objectAtIndex:i] getValue:&cp1];
           [[arrlinePoints objectAtIndex:j] getValue:&cp2];
   
           // lines connected do not need to be included.
           if((cp2.x == t1.x && cp2.y == t1.y) || (cp1.x == t2.x && cp1.y == t2.y))
           {
               continue;
           }
   
           CGPoint diffLA = CGPointMake(cp2.x - cp1.x,cp2.y - cp1.y);
           CGPoint diffLB = …

   Run Code Online (Sandbox Code Playgroud)

我已经设置线段(未线),(A1, B1),(A2, B2),(A3, B3),其中A,B被结束的线段的点.每个A并B有(x,y)坐标.

问: 我想知道之间的最短距离point O,并line segments如所示所示图中的代码行实施.我真正理解的代码是伪代码或Python.

代码:我尝试使用此代码解决问题,遗憾的是,它无法正常工作.

def dist(A, B, O):
    A_ = complex(*A)
    B_ = complex(*B)
    O_= complex(*O)
    OA = O_ - A_
    OB = O_ - B_
    return min(OA, OB)
# coordinates are given
A1, B1 = [1, 8], [6,4]
A2, B2 = [3,1], [5,2]
A3, B3 = [2,3], [2, 1] …

我有两条位于同一平面上的3D线.line1由point(x1, y1, z1)及其方向向量(a1, b1, c1)line2定义,而由point(x2, y2, z2)及其方向向量(a2, b2, c2)定义.然后两条线的参数方程是

x = x1 + a1*t;         x = x2 + a2*s;
y = y1 + b1*t;         y = y2 + b2*s;
z = z1 + c1*t;         z = z2 + c2*s;

如果两个方向向量都是非零,我们可以通过将上面的等式的右侧等于t并且s从三个中的任何两个求解来容易地找出交叉点节点的位置.但是,有可能a1 b1 c1 a2 b2 c2并非全为非零,因此我无法以相同的方式解决这些方程.我目前的想法是逐案处理这个问题,比如

case1: a1 = 0, others are nonzero
case2: a2 = 0, others are nonzero
case3: b1 = …

在C#或Java中是否存在任何现有的Bentley-Ottmann算法实现/库？

Bentley-Ottmann算法用于寻找直线组的交点.但我有很多折线:

有没有办法找到折线组的交点？

我正在搞清楚,但与此同时,如果有人可以给出一些指示或想法,那将会有所帮助.谢谢阅读.顺便说一下,我正在使用WPF/C#,所有折线都是PathGeometry.

图片来源:http://www.sitepen.com/blog/wp-content/uploads/2007/07/gfx-curve-1.png

有N条线段，它们要么是水平的，要么是垂直的。现在我需要找出每条线段的交点总数和交点总数。N可以达到100000。我试着检查每一对线。答案是正确的，但我需要减少它所花费的时间。

这是我的代码：

using namespace std;

typedef struct Point
{
     long long int x;
     long long int y;
} ;


bool fun(Point p0, Point p1, Point p2, Point p3)
{
    double s1_x, s1_y, s2_x, s2_y;
    s1_x = p1.x - p0.x;     s1_y = p1.y - p0.y;
    s2_x = p3.x - p2.x;     s2_y = p3.y - p2.y;

    double s, t;
    s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y)) / (-s2_x * s1_y …