多个三角形与点的关系 点在多个三角形外部的算法
设平面上有多个三角形，三角形都不相交，可以一个三角形在另一个三角形内部，求在这些三角形外部的点的集合。写出算法
[解决办法]
我的方法
设三角形是由逆时针或顺时针线段构成,判断P点是否在各条线段的一侧,是则说明P点在其内,否则是外点,如P点在某一边上或角点上则需另做判断.
这个方法速度快!!
[解决办法]
考察每一个点,
从此点向任意一个方向(如向右)作射线,直到超出所有三角形,
统计此点与所有三角形的交点,则,
如果交点总数为奇数,此点在某三角形内
如果交点总数为偶数,此点在某三角形外
统计一下,就可得到结果.
注: 如果碰到顶点,在统计时交点要算2个.
这是一个基本算法,大概在任何一本计算机图形学书中都会谈到的.
