已知一些直线及一个点,怎样得到包围这个点的多边形。要求这个多边形是由已知的这些直接组成的。

解决方案 »

  1.   

    OpenGL高手 happy__888([顾问团]寻开心)同志, 帮我看看这个问题好不好?
    http://community.csdn.net/Expert/topic/4339/4339986.xml?temp=.3469049ok,我讲搂主问题
      

  2.   

    先声明2个问题:
    1、把你问题“已知一些直线及一个点“ 更改成“已知一些线段及一个点”
           (这样好讲点,如果你的确实直线的话,也根据思路也可解)
    2、你必须了解 “矢量的一些概念”,例如矢量叉积、线段的拐向判断等,
        若有不明白见网址:http://www.frontfree.net/view/article_748.html
      

  3.   

    假定点P在凸包的内部
       那么先去除那些位于凸包内部的线段,只保留那些有顶点位于凸包上面的线段。 
    此时凸包上的相邻点,要么属于一个线段,要么分别属于两个不同的线段上
       把那些不在凸包上面的点提取出来,再次连接成一个多边形L(只要不自交就可以)
    这个时候,你会发现,线段把凸包分解成为了多个不相交的区域,点P在不同区域的时候,可以给出不同的多边形连接方法,按照上面的说明画出图片就明白了。
       主要是两种情况,一个是P位于L内部,有一种连接方法,位于外部有另外的一类连接方法
      

  4.   

    我个人做法是这样,欢迎大家指正:(我的思路很清晰,但是不知道能不能完全表达出来)
    (你的条件还是“直线”,刚才考虑不周)1、直线互相折断,得到 线段的 线段列表  
       (每一条线段不能包含其他线段) (下面是处理方法);      循环:寻找每一条直线 与 其他所有直线的交点,由这些交点组成多条独立的线段;
        假设直线a 与 其他所有直线有多个不同的交点P1、P2、P3、P4,任意组合它们
        会得到很多条线段,但是如何得到独立的、互不包含的线段?
        (假设点P1不落在线段P3P4上,而点P2也不落在线段P3P4上,P3P4是我们要找的),
        那么由直线a 可以得到3条线段,把他们放入列表(例如P1P2、P2P3、P3P4)。
    (另外,直线与直线的交点好求吧,例如y=k1x + c1 , y=k2x + c2,只要k1<>k2,必有交点 ) 
    2、由线段列表,得到一个多边形列表,且每一个多边形都是最小的、独立的、不会互相包含的;      (这一步是最麻烦的,我也不太好讲,就举一个得到一个多边形的例子吧)
           线段列表中任取一线段 P1P2,如果能找到其他以P2为端点的线段(找不到这样的
           线段的话,就结束本次任务,找到就继续往下),如果仅找到1条这样的线段例如
           P2P3,那么,P1P2P3有可能会组成一个多边形的一部分,继续找到其他以P3为端点
           的线段......;否则,如果找到多条以P2为端点的线段,例如有P2P3、P2P4、P2P5,
           两两比较P2P3、P2P4、P2P5,找到最左边的一条线段(也可最右,但要统一),
           不妨假设P2P3是最左边的一条线段,那么,P1P2P3有可能会组成一个多边形的一部
           分,继续找到其他以P3为端点的线段......;一旦找到诸如 P1P2P3P7...P1这样的
           折线(首尾相同),这个就是你找到的一个封闭的多边形,这个多边形一定是最小
           的单元,其内部不会包含其他多边行,而且,由于你的条件是“直线”,所以,
        这个多边形就一定是个凸多边形(否则是线段的话,就不敢保证了,而凸多边形
        是下一步 判断点是否在多边行内的先决条件)    这是一个循环或者递归算法,它的出口是:不考虑方向的线段,它最多是属于2个
            多边形,例如线段P1P2,它最多附属于2个多边形;但,如果考虑线段方向,例如
            线段P1->P2最多属于1个多边形(也可能没有),线段P2->P1最多属于1个多边形。
            所以,在找多边形时,要记录好线段的使用次数和方向。3、最终,判断你条件中的那个点是否在 多边形列表中的某一个多边形内!        这个有现成的算法,我上面给出的网站,也有详细介绍麻烦不???嗬嗬,你先理解这个思路,思路中也许包含一些你未了解
    的算法,还得找找相关资料。如果你非得要实现这整个算法,中间还需要特别注意一些问题,
    我暂时不讲,怕把你给弄糊涂了,不过,你也可能会考虑到!
      

  5.   

    happy__888([顾问团]寻开心) ,我不是十分明白你的意思。多条直线的交点,如果能围成一个区域,不管这个大区域是什么形状,
    但,它肯定是由数个相互独立的凸多边形组成。(你说呢?)
    搂主最终要求解的,也是这些凸多边形!否则,去判断点是否在凹多边形内,那才是真正的无解!
      

  6.   

    首先感谢Gold2000(Gold2000)及happy__888([顾问团]寻开心)的热心帮助。其实我要解决的是一个在二维平面上进行填充的问题,但不能用扫描线法直接填充,必须取得要填充的多边形。因为我还要缩放、要保存这个多边形。首先这个平面有一个矩形范围(就是屏幕范围,鼠标点一定在这个范围之内),这些线段是任意的,可能完全位于屏幕内(或屏幕外,可不考虑),也可能与屏幕矩形相交。注意是“线段”,所以产生的最终结果有可能是凹多边形,也有可能是“回”字型,甚至更复杂的情况,这些线段在矩形范围内部围成了若干个“口”字形,鼠标点位于“口”外部,最终结果要取得“口”外面、屏幕矩形内部的形状。不知我的表述是否清楚?
      感觉Gold2000(Gold2000)描述的算法差不多,请继续...
      

  7.   

    哈哈,我不太需要你这个分!互相学习一下而已我也是最近才来到你们这个板块,你们这里研究算法的人多,
    特别是OpenGL高手多,happy__888([顾问团]寻开心)帮了我不少的忙,
    十分感谢!
      

  8.   

    Gold2000(Gold2000): 你的算法是假设“直线”的情况下的,如果换成“线段”,除了需要判断点是否在凹多边形内以外,其它还有什么改变吗?
      另外,你说“实现这个算法时,中间还需要特别注意一些问题”。不妨也说出来吧。
      

  9.   

    考虑到我上面提到的“复杂”情况,经过算法第2步,得到一个多边形列表后,在第3步中就不能只是简单地判断点是否在某个多边形内了。当判断出点在某个多边形内部后,是不是还需要进一步判断还有没有其它多边形也完全包含在这个多边形内?最后这个多边形要用Polypolygon()画出了。
      

  10.   

    1、我的意思是: 多边形列表中所有的多边形都是相互独立的、都不会相互包含!2、“实现这个算法时,中间还需要特别注意一些问题”:
      线段列表中任取一线段 P1P2,如果找到多条以P2为端点的线段,
      例如有P2P3、P2P4、P2P5,“应该先把位于线段 P1P2左边的线段过滤掉”,
      剩下的是位于线段 P1P2右边的,然后才两两比较这些线段,
      找到最左边的一条线段;如果所有的线段都是位于线段 P1P2左边,应该
      两两比较这些线段,找到最右边的一条线段。  这样,才能保证你找出来的多边形是 相互独立的、都不会相互包含!
      

  11.   

    To Gold2000(Gold2000): 如果考虑这些线都是线段,就可能会出现“回”字形的情况,这时通过第2步得到的多边形就不一定相互独立、互不包含了。
      

  12.   

    To I_Love_CPP(Climb,Never Stop!) :什么叫"点仅仅在其一侧"?
      

  13.   

    “回”里面还包含“回”字 其实也没所谓,大不了你就找到n个多边形,
    你用不同的Canvas颜色画Polypolygon()不就OK了!
      

  14.   

    我以前做过跟你这个问题相似的算法,我总觉得有点“笨”!I_Love_CPP(Climb,Never Stop!)  是不是有些好建议???
      

  15.   

    To Gold2000(Gold2000): 我在做的是对CAD图填色。
      

  16.   

    噢,你是在做CAD的二次开发?!