Algorithm 版 (精华区)

发信人: ssos (存在与虚无·戒酒戒网), 信区: Algorithm
标  题: [合集]请教：什么样的算法？
发信站: 哈工大紫丁香 (2001年08月06日08:06:31 星期一), 站内信件


────────────────────────────────────────
 toto (勿打扰逝者的长眠)              于 2001年08月04日14:51:03 星期六 说道:

    任给一块均匀铁板，该铁板是任意n边形，请编程给出该铁板的重心位置。
设输入数据放在input.dat中，第1行为整数n，表示铁板是n边形，以后共n行，每行两个
浮点数xi，yi依逆时针方向依次给出n个点的顶点坐标。
显然input.dat给出的多边形任意两边不会在非顶点位置相交，围成的区域是一个连通区
域。请编程在屏幕上给出重心坐标。
多谢！//Bow

────────────────────────────────────────
 psola (狂吻春天)                     于 2001年08月05日08:43:21 星期天 说道:

重心在几何上是如何定义的呢？

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月05日08:57:53 星期天 说道:

用一根小棍支在这个点上，可以平衡

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月05日08:58:49 星期天 说道:

                                   ~~~~~~~~~~~~~~~~~~~~~这个解释一下

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月05日09:21:25 星期天 说道:

其实就是说这是一个多边形

────────────────────────────────────────
 sino (茶水博士)                      于 2001年08月05日09:41:54 星期天 说道:

可以想象用一条线自下向上扫过整个多边形，经过顶点时停下。
这样多边形就被分割成了很多梯形（凸多边形）。
然后的计算就Easy了吧。

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月05日10:10:42 星期天 说道:

这不是计算面积吧

────────────────────────────────────────
 fobcaesar (企鹅)                     于 2001年08月05日10:11:49 星期天 说道:

这可行么?

────────────────────────────────────────
 sino (茶水博士)                      于 2001年08月05日10:19:28 星期天 说道:

目的不是求梯形的面积，而是求重心。
求出每个梯形的重心，再积分不是很简单吗？
我想这种方法判别梯形是否在多边形内比较方便。
复杂度 ~~ O(n:顶点)？     

────────────────────────────────────────
 sino (茶水博士)                      于 2001年08月05日10:20:48 星期天 说道:

应该没问题吧...

────────────────────────────────────────
 PowerBuilder (孙武空)                于 2001年08月05日10:31:09 星期天 说道:

要解决这个问题首先要知道形心计算公式，接下来就是把图形分为可计算的部分，代入
形心公式就可以了。此问题是任意多边形（包括凹多边形），因此直接将气分成可计算
部分很困难，所以可以把他沿逆时针方向填补成一个凸多边形或者剪切成凸多边形，每
次纪录填补或剪切的三角形顶点坐标，最后把凸多边形一次分解为多个三角形，由于三
角形的形心可直接求解，因此得出铁板的形心。

────────────────────────────────────────
 cybernaut (大力神)                   于 2001年08月05日10:48:22 星期天 说道:

为什么一点要补成凸多边形呢？有必要吗？

────────────────────────────────────────
 eage (一休)                          于 2001年08月05日10:57:36 星期天 说道:

   //平面图,只分成一个有限域和一个无限域,求有限域的重心                         

────────────────────────────────────────
 fobcaesar (企鹅)                     于 2001年08月05日11:05:29 星期天 说道:

算法太麻烦了!特别是当多边形是凹多边形的时候!

────────────────────────────────────────
 dengnch (dengnch)                    于 Sun Aug  5 11:14:31 2001) 说道:

建议找本材料力学的书好好看看吧，不会很难的！





────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月05日11:37:58 星期天 说道:

重心怎么积分？

────────────────────────────────────────
 sino (茶水博士)                      于 2001年08月05日12:38:56 星期天 说道:

求重心不是求积分么？
我的意思是化成一些质点，然后分别在x、y方向上求质量乘坐标的和，再
除以总质量。

────────────────────────────────────────
 yahoo (yahoo)                        于 2001年08月05日16:38:21 星期天 说道:

由于这块铁板是均匀的，这使得问题变得很简单，只要找到整个铁板的形心就可以了。
首先要知道形心公式：
    X=Sigma(Ai*xi)/Sigma(Ai);Y=Sigma(Ai*yi)/Sigma(Ai);
    其中Ai表示第i个区域图形的面积，（xi,yi）表示第i个区域的形心坐标。
对图形的区域分化可以进行扫描法，也可以进行填补或者剪裁法，其中扫描法会得到一
系列的三角形和梯形，编程复杂，判断困难；剪裁法的速度较快，其中只生成三角形，
而三角形的面积和形心有很容易求得，因此应采用此方法。
具体方法是：任意取出多边形的一对相邻顶点，然后以此两点为起始点，沿顺时针或逆
时针方向切去“凸出”的三角形，然后记录其顶点坐标，直到全部都为三角形，代入形
心公式即得到形心。即铁板的重心。

────────────────────────────────────────
 virgin (virgin)                      于 2001年08月05日16:42:51 星期天 说道:

这么热闹

────────────────────────────────────────
 boss (boss)                          于 2001年08月05日16:44:46 星期天 说道:

补成凸多边形是因为凸多边形可以不用判断直接用剪切法求出形心

────────────────────────────────────────
 sino (茶水博士)                      于 2001年08月05日17:59:13 星期天 说道:

此法是否需要判断剪下的三角形是否在多边形内？

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月05日18:32:31 星期天 说道:

如果补成凸多边形自然不须判断，否则必须

────────────────────────────────────────