如何判断自相交图形？

Question

图形自相交一定是基于外边线的相交。所以遍历所有边线，返回它们之间是否有交点，或者交点是否在线内即可，如果返回TRUE，则是该图形有自相交

Answer 1

计算跨度，即扫描过的点的最大的x范围XF，
从第三个点开始，看第n点的x值Xn是否在XF之内，
不是，肯定不相交
如果是，则计算是否有交点

Answer 2

在three.js中找到一个算法 但是没看懂 
测试下来应该是没错 但是算法复杂度 有点高
在处理大数据的时候效率不是很好

Answer 3

如果两线相交，它们必定有一个点是相同的。列出所有点，比较是否存在相同点即可。一个思路，希望对你有帮助：
1按顺序求出这条曲线经过的点，比如n1(x1,y1,),n2(x2,y2),n3(x3,y3)...,先求出n1(x1,y1)-n2(x2,y2)这条直线经过的所有点，可以用DDA画直线法。再求n2-n3,n3-n4因为计算机上是用离散点来表示直线的，所以画出这一条曲线的所有点的计算量并不大,时间复杂度是n。2如果有二点的坐标相同，则说明这条曲线是互交的。问题就转为成这曲线上面的所有点有没有相同的两个点.这里可以用一一对比的方法，时间复杂度是n的平方(这一步可以优化，将坐标通过这样的转换(x*1000+y),当作一个整数，利用位图法求相同点，时间复杂度可以减为n的)。综上，两步的时间复杂度其实是n而已。应该注意的问题：DDA画线法并不保证相交的二条直线一定存在重合的点，所以只要求出两个点的距离小于指定值则可以认为它们是可能相交的，再回归到它们所属的端点，重新计算这两条线段是否真的相交。

Answer 4

“100个点，按照顺序进行描画”
画成直线， 判直线 相交
“直线绘制和交点”0分
http://download.csdn.net/detail/schlafenhamster/5704889
“通过鼠标 画线，并计算直线的交点。可以 点击直线，即删除它”

Answer 5

深圳志和诚科技有专门的自相交判断和处理功能可高效处理。www.zhcdesign.com 

Answer 6

three.js。。楼主玩HTML5的啊？？
我这里有C++的判断点是否在多边形内的。PolygonAlgorithmRadialBOOL Delaunay::PolygonAlgorithmRadial(std::vector<vertex_d>& vecPolyon,int polyonNum,vertex_d &pt)
{
int n = vecPolyon.size() > polyonNum ? polyonNum : vecPolyon.size();
int count = 0; vertex_d pV1;
pV1.SetY(pt.GetY());
pV1.SetX(Delaunay_INFINITY*-1);
edge * line = new edge(&pt,&pV1);
for( int i = 0; i < n; i++ ){
// 得到多边形的一条边
vertex_d side_pt1 = vecPolyon[i];
vertex_d side_pt2 = vecPolyon[(i + 1) % n];
edge * side = new edge(&side_pt1,&side_pt2); if( IsOnline(&pt, side) ){
return TRUE ;
} // 如果side平行x轴则不作考虑
if( fabs((double)(side->m_pV0->GetY() - side->m_pV1->GetY())) < Delaunay_ESP ) {
continue;
} if( IsOnline((vertex_d *)side->m_pV0, line) ){
if( side->m_pV0->GetY() > side->m_pV1->GetY()) 
count++;
} 
else if( IsOnline((vertex_d *)side->m_pV1, line) ){
if( side->m_pV1->GetY() > side->m_pV0->GetY() ) 
count++; } else if( Intersect(line, side) ){
count++;
}
} if ( count % 2 == 1 ){
return TRUE;
}else { 
return FALSE;
}
}float Delaunay::Multiply(vertex_d * P0, vertex_d * P1, vertex_d * P2)
{
return ((P1->GetX() - P0->GetX()) * (P2->GetY() - P0->GetY())
- (P2->GetX() - P0->GetX()) * (P1->GetY() - P0->GetY()));
}bool Delaunay::IsOnline(vertex_d * point, edge * line)
{ return ((fabs(Multiply((vertex_d *)line->m_pV0, (vertex_d *)line->m_pV1, point)) < Delaunay_ESP ) && (( point->GetX() - line->m_pV0->GetX() ) * ( point->GetX() - line->m_pV1->GetX() ) <= 0 ) && (( point->GetY() - line->m_pV0->GetY() ) * ( point->GetY() - line->m_pV1->GetY() ) <= 0 ) 
);}
bool Delaunay::Intersect(edge * L1, edge * L2)
{ return ((max(L1->m_pV0->GetX(), L1->m_pV1->GetX()) >= min(L2->m_pV0->GetX(), L2->m_pV1->GetX())) && (max(L2->m_pV0->GetX(), L2->m_pV1->GetX()) >= min(L1->m_pV0->GetX(), L1->m_pV1->GetX())) && (max(L1->m_pV0->GetY(), L1->m_pV1->GetY()) >= min(L2->m_pV0->GetY(), L2->m_pV1->GetY())) && (max(L2->m_pV0->GetY(), L2->m_pV1->GetY()) >= min(L1->m_pV0->GetY(), L1->m_pV1->GetY())) && (Multiply((vertex_d *)L2->m_pV0, (vertex_d *)L1->m_pV1, (vertex_d *)L1->m_pV0) * Multiply((vertex_d *)L1->m_pV1, (vertex_d *)L2->m_pV1, (vertex_d *)L1->m_pV0) >= 0) && (Multiply((vertex_d *)L1->m_pV0, (vertex_d *)L2->m_pV1, (vertex_d *)L2->m_pV0) * Multiply((vertex_d *)L2->m_pV1, (vertex_d *)L1->m_pV1, (vertex_d *)L2->m_pV0) >= 0) );}

Answer 7

我这里有C++的判断点是否在多边形内的。PolygonAlgorithmRadial可能根本不懂图形算法，误人子弟

Answer 8

100个点，相邻两点连线，不就是99条线段吗(首尾不相连的话)
for循环
第一条与后面98条相交不？
第二条与后面97条相交不？
.....
完事
可以不？