如何获取外围轮廓线？

feng582304

nxy_918 发表于 2011-3-29 09:45
我现在通过程序可得到已知每个方形的上下左右的是哪个方形，想先得到构成外围轮廓线的方形（即该方形的上 ...

其实你这种想法就像那“扫雷”游戏，做个递归函数：一个方块是一个单元，判断这个单元四个方向是否有连接其它单元，有的话就回调，没有的返回对应的单元以及没有连接其它单元的边。最终得到最外围的所有单元以及对应的边，再把对应的边的几个方向做个排序，应该就可以出来了。不知道我这样理解对不对。

nxy_918

feng582304 发表于 2011-11-10 23:52
其实你这种想法就像那“扫雷”游戏，做个递归函数：一个方块是一个单元，判断这个单元四个方向是否有连接 ...

有启发，谢谢

wowolwj

还可以考虑用线段扫描算法，sweepline
1.建立次序x，y
2.从左到右，从下到上扫描找出边界

shang_123

此贴 先顶起来！！！

chlh_jd

由于是讨论算法，暂时先不贴出源码；
思路（和qjchen老师所提相同，只列出逆时针详细思路）：
   1. 找出最左下角点的关联线段，至少是2条 。
   2. 取出中点最下面的一条p0p1，利用其他条p2做顺逆判断，决定该条线段两的顶点的先后；
       如果p2p0p1为逆时针，那么顺序为p0p1，反之则为p1p0。
   3. 然后由其实向量p0-->p1依次查找下一条线段p1-->p2，查找方法：
         3.1 取出以p1为顶点的所有其他线段；
         3.2 这些线段群的另一个顶点为P2，找出向量p1-->p0顺时针转到向量P1-->P2扫过的夹角最大的那条；
         3.3 该条线段的另一个顶点即为所求的下一个顶点。
  4.  重复循环步骤3，直到找到的顶点与起始线段的第1点相同或者重合。

尘缘一生

chlh_jd 发表于 2012-10-16 21:58
由于是讨论算法，暂时先不贴出源码；
思路（和qjchen老师所提相同，只列出逆时针详细思路）：
   1. 找出 ...

可以发出来看看？

hhh454

已经过去快10年了，估计是没有回复了，我也写到一个这样的，猫老师也讲过这个算法，目前还是不能很好的理解

tionsy

hhh454 发表于 2022-1-2 18:06
已经过去快10年了，估计是没有回复了，我也写到一个这样的，猫老师也讲过这个算法，目前还是不能很好 ...

我想到一个方法，就是先去除重合线，就可以得到外围

1227588

我的理解是先 把每个点坐标找到 然后reg 然后按面积排序 取面积最大的

landsat99

算法上是说，平面上有n个点坐标，求n点的外轮廓线(即点坐标的序列)。