判断怪在任意三角形里面还外面或者在边上

zxczxc9898 · 发表于 2012-3-22 22:09:01

本来想问的是任意边形不过想想会了三角形其他的就知道了，之前找了很多方法，看见选取的怪分别到三角形的三个顶点的角度相加之和等于360度就是在里面不是就在外面不过我自己试了不行，其他的方法看起来好复杂看了鬼一那演示感觉好乱越看越糊涂可以帮我做个纯T的演示吗，问了很多人用什么方法不过用到魔兽里就纠结了。帮我做个T的演示自己看看就比较容易理解了要有判断怪在三角形里面外面还是在某条边上

okolek · 发表于 2012-3-22 22:47:24

你可以去wow8找一下任意区域的捕捉。

因为我没有做出来所以抱歉了。

lghdtc · 发表于 2012-3-23 10:21:09

OK了

三角形内外判断.w3x (19 KB, 下载次数: 14)

2012-3-23 10:19 上传
点击文件名下载附件

UI：Red_Wolf汉化V1.2.2

楼主是想做WOW里面旋云之颠最终BOSS的那个技能吧？

请无视这个渣渣吧，在楼下下给了最新的附件

lo · 发表于 2012-3-23 10:31:57

这是数学问题，直角坐标系里会介绍如何判断点在直线上和点在直线下，学好数学，任意区域什么的都是浮云……

lghdtc · 发表于 2012-3-23 11:50:35

好了，优化了一下~

多边形内外判断.w3x (19 KB, 下载次数: 27)
现在支持任意边形的内外判断了~
只要更改整数变量N的赋值就可以变成N边形的判断(默认为4)

需要说明的是，本演示的多边形是指突多边形
以N=4来说，如果有一个顶点位于其他三个顶点所围成的三角形内部，那么此时的多边形实际上是三角形
多边形.jpg

zxczxc9898 · 发表于 2012-3-23 17:38:19

嗯谢谢了

夜の星 · 发表于 2012-3-23 20:35:49

于是星给一个同时适合凹多边形和凸多边形的方法呢的说~

首先几何画板⑨一只，唔...因为时间比较少而且为了演示方便，所以画的很粗糙呢的说~
眉毛什么的忘掉了就不要吐槽了呐~

)(`E1XDP4H7L5VBHDNJJ~]P.jpg

然后我们要分别判断两个点是否在两个选定的多边形内~
MT0[AS42ON3)J8SWDV@5W2K.jpg

方法如图喵！~从该点开始，作一条水平向右的射线，计算与多边形的交点个数，奇数在形内，偶数在形外喵~>.<

不难呢的说~>.<

chyj4747 · 发表于 2012-3-23 20:58:31

奇数，形外……
虽然可能比较难遇到。。

zxczxc9898 · 发表于 2012-3-23 21:53:12

如果判断怪在直线上呢我自己做了发现单位移动老会跨过去 QQ截图20120323215040.png

x1y1 x2y2分别为线段2个端点有时候过去没效果

从该点起，做一条平行于x轴且水平向右的射线~
若射线与多边形的交点个数为奇数，则在形内~
否则在形外的说~（边上面自己拿捏的说）
若x1<x0且x2<x0 则该边在线段左端，不考虑~
若（y1>y0 且y2<y0）或（y2>y0 且y1<y0）则与这条边有交点的说~
这方法只会在现实里判断魔兽里就不会了

lghdtc · 发表于 2012-3-23 22:11:16

呃，7楼的情况应该算是偶数个交点。
看嘛，射线和四条边有交点，只是其中两个点重合了。

说实话，星的办法确实可以简单的判断任意多边形的。但是实在是懒得去做了，似乎记得有人做过现成的

夜の星 · 发表于 2012-3-23 22:54:48

chyj4747:奇数，形外……
虽然可能比较难遇到。。
 (2012-03-23 20:58) 

如果你对于一条边的顶点，判定为相交，那么另一条边也应等价判定为有交点的说~

如果你判定端点为不相交，则另一条边也不相交~

所以仍然素偶数的说~

chyj4747 · 发表于 2012-3-24 04:08:22

原来如此……

chyj4747 · 发表于 2012-3-24 08:21:19

zxczxc9898：这方法只会在现实里判断魔兽里就不会了

于是演示奉上~

多边形内外判断.w3x (23 KB, 下载次数: 25)
用的夜星那个方法~

测试方法什么的全部都写了~
进图就可以直接测~

算法：简单来说就是在随便哪条边上找一点（顶点不行，目标单位在形内时连顶点会得偶数），然后与目标单位连一条“射线”（实际计算时射线和边都是用直线处理），然后循环判断跟每一条边的交点，看该交点是否在边上以及在射线上

PS：
（1）本演示没有做任何容错处理，所以要是操作错误，会有什么样的BUG我也不知道……（比如顶点数小于3，比如某两边相交了）
（2）虽说是演示，但有些地方特殊化处理了，比如直接用了放在地图上的步兵，所以是没法移植的
（3）理论上来说是支持任意顶点数量的多边形（极限是2^31-1个），但是请不要做任何过于极端的事……电脑会卡死的。。绝对。。。
（4）本演示T写法并不是最简洁的，请不要效仿~

zxczxc9898 · 发表于 2012-3-24 17:58:52

谢谢各位那么帮忙

		自动登录	找回密码
密码			点一下

判断怪在任意三角形里面还外面或者在边上

回 chyj4747 的帖子