多个三角形与点的关系 点在多个三角形外部的算法

设平面上有多个三角形，三角形都不相交，可以一个三角形在另一个三角形内部，求在这些三角形外部的点的集合。写出算法

9 个解决方案

#1

问题好像描述的不是很清楚，帮顶一下

#2

怎么又开了一个贴，原来回答的不行吗？

判断点不在所有三角形内部或边上就可以了。判断方法可以用下面的：

定义：平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量：
S(P1,P2,P3) = (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)

已知：三角形的三个顶点A,B,C，及平面上的一点P，
1、 若abs( S(A,B,C) ) = abs( S(P,B,C) ) + abs( S(A,P,C) ) + abs( S(A,B,P) ) ，则P在三角形ABC的内部或边上；如果还有abs( S(P,B,C) )、abs( S(A,P,C) ) 和abs( S(A,B,P) )全都大于0，则说明P在三角形ABC的内部，否则P在三角形ABC的边上；
2、 若abs( S(A,B,C) ) < abs( S(P,B,C) ) + abs( S(A,P,C) ) + abs( S(A,B,P) ) ，则P在三角形ABC的外部；
3、 对abs( S(A,B,C) ) > abs( S(P,B,C) ) + abs( S(A,P,C) ) + abs( S(A,B,P) ) 的情况在理论上是不存在的；

#3

谢谢  会给你给分的

#4

判断一点o和三角形ABC的关系：
从o点分别作平行于三角形三条边的直线l1,l2,l3。
如果o点在三角形内部，那么这三条直线中任一条必然与三角形的两边都相交。
否则，至少有一条直线与三边都不相交。
如此点与三角形的位置关系与直线相交构成充要条件。

#5

我的方法
设三角形是由逆时针或顺时针线段构成,判断P点是否在各条线段的一侧,是则说明P点在其内,否则是外点,如P点在某一边上或角点上则需另做判断.
这个方法速度快!!

#6

考察每一个点,
从此点向任意一个方向(如向右)作射线,直到超出所有三角形,
统计此点与所有三角形的交点,则,

如果交点总数为奇数,此点在某三角形内
如果交点总数为偶数,此点在某三角形外

统计一下,就可得到结果.

注: 如果碰到顶点,在统计时交点要算2个.


这是一个基本算法,大概在任何一本计算机图形学书中都会谈到的.

#7

以上的注有错,应该是:

注: 如果射线碰到三角形的顶点,则要进一步考察与此顶点关联的2边,
    如果2边均在射线同侧,交点要算2个.
    如果2边分在射线两侧,交点要算1个.

#8

还有,
 如果射线通过三角形的一边,则要进一步考察三角形另外的2边,
    如果2边均在射线同侧,交点要算2个.
    如果2边分在射线两侧,交点要算1个.

#9

抱歉,我把问题看复杂了,

如果是任意多边形(包括凸与凹),才要像最后一次的回复那样进行考虑

如果三角形,不与射线重合的另外2边总是在同一侧的,因此,
射线通过后,不影响该点是否在某个三角形内,可以不考虑.