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

ddd · 发表于 2010-1-13 21:58:51

请问这样的图形算不算有效？
未命名2.JPG

这样的呢？

疯人￠衰人 · 发表于 2010-1-13 22:35:19

不需要全部使用
注意……
当构成一个封闭图形后
就不能再放置标记了……
也就是说
在上一次放置时
所有的有效连接不是一个封闭图形
所以第一个图不可能出现
第二个会出现

ddd · 发表于 2010-1-13 22:41:58

其实第一个图也会出现，比如按照左下，右上，右下，左上的顺序放置。
我只是想清楚地理解题意……

疯人￠衰人 · 发表于 2010-1-14 08:57:04

这个确实……
似乎理解错有效的路径了……
不过应该不影响解题

这个问题要分步做
第一步就是判断是否生成闭合图形

方法很简单，就是判断当前最后放置那个标记的有效半径内存在几个标记（除了自己）

不会是0，否则无法放置，当为一时，那么绝对不会产生闭合的图形，如果大于1，必然会产生闭合图形。

活宝 · 发表于 2010-1-14 11:24:15

对于技能B，孔明大人有什么想法呢？

疯人￠衰人 · 发表于 2010-1-14 14:35:58

原先的想法错误……
总之，可以证明，当形成闭合图形后
从最后放置的标记开始，遍历全部图案，记录连接到开始点的情况
最终获得的全部边（也就是回到开始点的路径）围成的闭合图形叠加起来，肯定包括了全部面积
那么将目标点依次对每个获得的闭合图形做判断内部即可

任意多边形的内部判断我还没想出来

活宝 · 发表于 2010-1-14 19:10:58

您看这样行么？

foodszhu · 发表于 2010-1-14 19:31:16

包括是包括了全部面积。。。但就从最简单的Σ形图形来说（不知道叫什么名字。。将右边两点再相连。。）。。如果用遍历的想法的话。。会有几条边不在原先的面积里。。。也就是按照楼主做的这样的闭合图形。。。最后仍然是凸多边形。。。而不是我们所想的。。任意多边形。。。
而且我说的。。点集上的所有点都会在一个任意多边形的边界上好像没人懂呢。。。。。
附图吧

这两个点集都是符合题意的的的点集。。且两个点集完全相同。。。他可以由一个任意多边形围起来且使得每个点都在任意多边形的边线上。。。
且这样的任意多边形不唯一

活宝 · 发表于 2010-1-14 19:35:06

引用第31楼foodszhu于2010-01-14 19:31发表的 :
包括是包括了全部面积。。。但就从最简单的Σ形图形来说（不知道叫什么名字。。将右边两点再相连。。）。。如果用遍历的想法的话。。会有几条边不在原先的面积里。。。也就是按照楼主做的这样的闭合图形。。。最后仍然是凸多边形。。。而不是我们所想的。。任意多边形。。。
而且我说的。。点集上的所有点都会在一个任意多边形的边界上好像没人懂呢。。。。。
附图吧

这两个点集都是符合题意的的的点集。。且两个点集完全相同。。。他可以由一个任意多边形围起来且使得每个点都在任意多边形的边线上。。。
.......

您说的是哈密顿圈么？

ddd · 发表于 2010-1-14 19:53:46

引用第32楼活宝于2010-01-14 19:35发表的 :

您说的是哈密顿圈么？

不过题目的要求似乎是在标记和有效线段形成的图形中找出一个子图，使得它为哈密顿图，并且找出其中一个哈密顿圈。这样的话孔明大人的问题就包含了著名的哈密顿问题，而哈密顿问题是NPC问题，并不存在有效算法，所以貌似孔明大人的问题也是没有有效算法的……

疯人￠衰人 · 发表于 2010-1-14 20:57:21

引用第31楼foodszhu于2010-01-14 19:31发表的 :
包括是包括了全部面积。。。但就从最简单的Σ形图形来说（不知道叫什么名字。。将右边两点再相连。。）。。如果用遍历的想法的话。。会有几条边不在原先的面积里。。。也就是按照楼主做的这样的闭合图形。。。最后仍然是凸多边形。。。而不是我们所想的。。任意多边形。。。
而且我说的。。点集上的所有点都会在一个任意多边形的边界上好像没人懂呢。。。。。
附图吧

这两个点集都是符合题意的的的点集。。且两个点集完全相同。。。他可以由一个任意多边形围起来且使得每个点都在任意多边形的边线上。。。
.......

阁下忘记了放置的问题
这个问题不是给你一堆点求解
而是一个个的放置
如果阁下给的图时不可能出现的
因为不存在一个点，去掉连接此点的边之后是一个非闭合图形

问题的特点在于
每次放置都会检查
检查后如果闭合，那么不可以放置
这种方式的放置会有一些限制
只少我没有发现出现不确定结果的状态。

foodszhu · 发表于 2010-1-15 18:39:51

其实还是有很多组解得。。。如图

ABCDE分别表示点的出现顺序............若技能中判定的距离为n。。。。。有AB<n.. Ac<n.. BE<n.. CE<n.. AD<n..CD<n..DE<n....BC>BD>n。。。。这几个点满足大人的要求。。。且若去掉E点则无多边形。。。。
那么。。。连接时就有两种情况

图做的不好请见谅。。。。。。。因为要求的算法需要有普适性。。。。则这个么。。。不成立。。。
再说。。楼主大人也从未说过在同时凸多边形与凹多边形同时存在时（这个是一定的）。。。到底选哪个。。。。。。还是选面积最小的？？还是选区域内存在点最少的？？亦或者从最初点开始的遍历？？
真的很有意思的题。。。。发到网上真的会有很多人去做的。。。。

疯人￠衰人 · 发表于 2010-1-16 09:52:16

LS的图不可能出现的
当放置完d点
因AD、AC、DC都小于N
已经出现闭合图形
那么E点将不可放置

疯人￠衰人 · 发表于 2010-1-16 10:15:32

关于多边形的内外判断，我想到了一种方法
需要一些坐标转换的背景知识。
设ABCD……是多边形的依次顶点
AB为边，以AB为X轴做直角坐标系转换目标点坐标，如果转换后的点的坐标的Y值大于0设某个布尔值为1，否则为0，
若在直线上，则以BC为开始
然后循环
分别以BC为X轴做同类的判断，
当返回结果与AB的结果不同时，跳出（此时点在多边形外）
若在直线上或者相同，那么继续循环（这个自行选择，如果边界算在多变形内如此，否则在直线上跳出）
直至遍历全部边
如果全部在一侧，那么就在多边形内

至于每次的Y轴的正方向
需要根据此次判断的边和上次的边（相邻边的同一时针方向的旋转有关）
无标题.png

如图，箭头方向为正方向（也可以为负方向，一致即可）

活宝 · 发表于 2010-1-16 11:49:03

ummm……我原先是用斯托克斯公式来着，但是精度不是很好，看来还是孔明大人的方法比较简便啊……

不过如果碰上这样的情况，

这种方法就没有效果了，
比如取这样的回路：

即使找出它的哈密顿圈，也不行

因此非得找出它所有的没有扭结的圈

分别计算才行……然而这样的话复杂度会比较高……
目前还没找到更有效的算法……

foodszhu · 发表于 2010-1-16 12:34:01

楼主大人难道没有看到。。ABCD四点是不能组成一个多边形的么？？。。。还是说可以有点不在多边形组成的区域中。。。？？和题意不符吧。。。
。。大人。。再仔细看看。。。如果连这个的无法解决的话。。。整个算法的无精确解。。。。那么。。。。

疯人￠衰人 · 发表于 2010-1-16 13:08:33

ls误解
不是需要用全部点组成的
只要能够组成任意闭合即可
ACD组成了三角形

疯人￠衰人 · 发表于 2010-1-16 13:14:43

引用第38楼活宝于2010-01-16 11:49发表的 :
ummm……我原先是用斯托克斯公式来着，但是精度不是很好，看来还是孔明大人的方法比较简便啊……

不过如果碰上这样的情况，

这种方法就没有效果了，
.......

请给出放置的最后一个点
整个系统时一体的
而且组成多边形的点的数量也是任意的
不需要全部使用
从最后放置的点开始，遍历全部支路
回到最后放置的点，那么就是一个闭合图形了
如果产生了多个闭合图形
那么可以证明这样圈出的多边形叠加起来
会是全部闭合部分
因此，我们依次对每个闭合图形做判断
在任意一个之内
那么就是在了

foodszhu · 发表于 2010-1-16 14:05:51

。。。。我的意思是。。。B点并非在ACD三角形中。。且B比D出场顺序早。。。即技能释放后B先于D点。。
再因为ABC不能构成三角形。。。因而可以引入D。。又因ABCD无法组成符合的四边形。。。才引出E。。。
若无顺序一说。。岂不乱套。。
那大人的技能不就很混乱呢。。。
还有

引用第41楼疯人￠衰人于2010-01-16 13:14发表的  :

从最后放置的点开始，遍历全部支路
回到最后放置的点，那么就是一个闭合图形了
如果产生了多个闭合图形
那么可以证明这样圈出的多边形叠加起来
会是全部闭合部分
因此，我们依次对每个闭合图形做判断
在任意一个之内
那么就是在了
.......

如此遍历得到的多边形必然是凸多边形。。。
那么讨论的东西就大大简化了
但不符合大人的意思。。
否则这东西早都做出来了

foodszhu · 发表于 2010-1-16 14:11:03

还有。。。这个所有点都在多边形边界上。。。这个是因为一个问题还未解答。。。
楼主大人从未说过在同时凸多边形与凹多边形同时存在时（这个是一定的）。。。到底选哪个。。。。。。还是选面积最小的？？还是选区域内存在点最少的？？
这个问题并未解决。。。使得每个人的理解都不同。。。。或许楼主大人给大家一个比较精确的解释为妙。。。。别最后发现大家讨论的问题不同。。。。

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