【跟风出题】关于区域范围内判断的技能[悬赏6威望]

疯人￠衰人 · 发表于 2010-1-8 20:21:22

题目描述：
设三个技能A、B、C各自效果如下：
技能A：点目标技能，效果为放置一个标记。放置标记需满足：如放置时可用地图上没有释法单位C的标记，那么可以任意释放，否则在释放点的一定范围（n）内存在D放置的标记才可以释放。设当两个标记的距离小于n时，我们认为这两个标记之间的线段有效，否则认为无效。那么当此施法单位放置的全部标记相互之间连接构成的有效线段可以组成一个封闭图形E时，设置技能B有效。技能A无效，并将有效范围用闪电特效连接起来（仅围多边形的边）。
无标题.png

技能B：无目标技能。效果为检查某一给定的点F是否再E的范围内。给出检查结果（可以显示在屏幕上）并执行技能C的效果
技能C：无目标技能。效果为清除地图上所有属于释法单位的标记，如A技能无效、B技能有效，那么重设为A技能有效，B技能无效。
题目要求：制作一个演示图，以一个单位的位置为被检查是否再范围内的点，技能A、B、C多人使用无冲突，可以选择标记对玩家共享（一个玩家的多个单位的标记一起判断）还是施放单位各自区分（每个单位只检查自己的）。地图大小、技能CD什么的任意。
只要求结果，不要求权限（演示图不要加密），作者可以将制作的成品发到j区或者技能区，获得奖励，与此奖励无关。

如有其它问题请留在此帖，成品不发表在此帖也请留下连接。我会烤烟两日。之后回复。

疯人￠衰人 · 发表于 2010-1-8 20:25:17

~~忘记设置悬赏时间了……~~
怎么设置悬赏时间？

hjistc · 发表于 2010-1-8 20:28:36

咱沙包无望阿题都没看懂 = =
话说咱要是遇到不会写的技能出个技能题是不是特伸手党囧

疯人￠衰人 · 发表于 2010-1-8 20:48:17

实际问题是2个
1、在有放置限制（放置位置指定范围内存在已经放置的标记）中，选出部分或全部点组成一个边长小于定值的多边形
2、判断一个点是否再某个给定的多边形内

a62123 · 发表于 2010-1-9 09:31:35

题目看不懂。

jpg · 发表于 2010-1-9 12:59:00

似懂非懂。

达子 · 发表于 2010-1-9 14:42:15

有个bug~~假设你所设的那个有效距离m=1000~~此时你在一个直径1000的圆周内所作的所有的点之间的距离必然都符合条件，那么你所画的那个五角星例图就会同时出现多个有效区域~~~~

alexries · 发表于 2010-1-9 16:52:45

KW的头像亮点在于下面的格子

疯人￠衰人 · 发表于 2010-1-9 18:18:20

引用第6楼达子于2010-01-09 14:42发表的 :
有个bug~~假设你所设的那个有效距离m=1000~~此时你在一个直径1000的圆周内所作的所有的点之间的距离必然都符合条件，那么你所画的那个五角星例图就会同时出现多个有效区域~~~~

有个参数打错了
判断的距离和放置的距离是一样的
而且，允许多个区域存在，判断的点在任何一个区域内都成立。
当然实际最多能够成立的区域（闭合多边形）最多只有4个
原因不解释

foodszhu · 发表于 2010-1-10 01:42:30

有没有规定是不是一定是凸多边形。。。能不能是凹的？？

foodszhu · 发表于 2010-1-10 02:40:46

（先不考虑非凸多边形的情况）分为两步。。先假设所有点已经取好。。取一个大圆。。使得大圆将所有点包括。。。（其实就是取最低处俩点。。做他们连线的中垂线。。
然后圆心在中垂线上移动。。。到两点距离为半径。。。。即可求出）且使其恰好包括所有点。。。即圆上三点公园。。①判断三点是否能围成三角形使得包括所有点。。是则为所求。。否进入②。。。②去掉这三个点。。再重新找另三个点做法同上。。。三点钟至少有一个不在上面3点围成区域内。。所以构成一个至少四边形。。再次重复①
②直至所有点被去完或找完。。
判断一个点是否再某个给定的多边形内。。。这个就是核心了。。。上面的也依赖于他。。。。即问题都纠结在这了。。。其实上就是判断一个点是否在三角形内。。。因为任多边形都可分为有限多个三角形（n-2个）而这个就不用我多说了吧。。。如果一个点p在三角形内部或者边线上，那么p与三角形的其中两个顶点组成的三个三角形面积与原三角形面积应该相等，这时候问题就转化为如何计算三角形的面积了。。。 s= |(t0.x * t1.y + t1.x * t2.y + t2.x * t0.y - t1.x * t0.y - t2.x * t1.y - t0.x * t2.y)*0.5|或海伦公式即可。。。。进一步我们可以知道如果一个点p在n边形内部或者边线上，那么p与n边形的其中任两个顶点组成的n个三角形面积与原n边形面积应该相等。。。。
两道题都非常类似都最后与三角形的面积有关。。。算法。。。末路了吗

疯人￠衰人 · 发表于 2010-1-10 18:39:27

要实际做出来的……
做跟说差很多……

foodszhu · 发表于 2010-1-10 18:47:47

其实上楼主大人的题就是一个求一个有限点集的凸包问题。。很多地方都有算法。。。后一个判断则和我说的一样。。求n个3角形的面积与圆面积相比。。不相等则在凸包外。。。
凸包的求取算法有很多。。最简单的额额是逼近法。。。但不适合算法。。。
而真正写出来是很复杂的。。。http://eastsun.javaeye.com/blog/92854。。
有兴趣自己看一下吧。。。我只是自己想了下算法。。。很简陋。。很被鄙视啊

疯人￠衰人 · 发表于 2010-1-10 19:10:52

首先这个不是凸多边形
其次这个多边形的边长是有特定限制的
另外有人也提到了，生成的多边形不唯一
最后我要的是最终结果
如果ls用其他编程方式做出来
那么我也认为你是最佳答案

不过最好是j

另外，多点组成多边形的算法我在很早之前就完成了
这个题就是那个的扩展

foodszhu · 发表于 2010-1-10 22:25:14

我只是讨论一下算法呀可行性和效率之类的。。楼主大人的智慧令人钦佩。。。。这么难的题都能想得出。。。。首先。。最后连出来要么是凸要么是凹多边形。。。
因为一个多边形（无论凹凸）必是一个欧拉图。。。（这个易证得）。。。
若还有一点在多边形内。。则必可以找到两点与其相连之后所形成的多边形内再无一点。。
所以多边形内再无点。。。即点集必在（凹）多边形的边界上。。。
这个算法么。。。貌似很复杂。。。没试过。。。但肯定有人做过欧拉回路的路径判断的算法。。。或者用A*算法算算路径或许也可以。。。再或者一个个点说不定也可以。。。。楼主以前的算法说不定也用得上
不过这样说来没有一个点在多边形内貌似与楼主的想法不太符合吧。。。
而凹多边形的区域问题还真没想过。。。下去再考虑考虑。。。实在不行就将多边形分为n个多边形再做不过可行性很低呢。。。
大人们果然是大人们。。。就是猛。。。。

疯人￠衰人 · 发表于 2010-1-11 18:35:45

这个……
我不是搞编程的……
看的不是很懂……
这个东西是某个计划的图中的东西
坑掉了

此方丽莎 · 发表于 2010-1-11 18:41:58

测试

活宝 · 发表于 2010-1-13 10:56:17

不知这样行么？

foodszhu · 发表于 2010-1-13 18:50:15

。。。。经过反复测试。。。貌似无解。。。。楼上的演示很好呢。。但跟楼主大人的要求有些许不附。。。若可以有凹多边形的话。。。再无限制条件下。。。有无数多组解。。。所以判断点是否在凹多边形区域内变得极为复杂。。所以还需要做一个统一的标准。。。。就很复杂了。。。再加上。。。点都会在凹多边形边界上。。。。。
这样没有什么意义了。。。所以估计不会有凹多边形的存在。。。所以大概或许maybe。。你那个计划的意思就是求凸包吧。。。.。。貌似你自己以前也做过。。。。
而且算法很普及。。。这东西也就结束后了吧。。。

ddd · 发表于 2010-1-13 19:17:29

是否所有的标记都要连到？还是只要其中某些标记组成封闭图形就可以了？

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