社区 › 几何算法 › 如何获取外围轮廓线？

feng582304 发表于 2011-11-10 23:52:48

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

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

nxy_918 发表于 2012-1-17 16:07:07

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

有启发，谢谢

wowolwj 发表于 2012-2-8 10:16:55

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

shang_123 发表于 2012-3-18 11:25:15

此贴 先顶起来！！！

chlh_jd 发表于 2012-10-16 21:58:52

本帖最后由 chlh_jd 于 2012-10-16 22:01 编辑

由于是讨论算法，暂时先不贴出源码；
思路（和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点相同或者重合。

尘缘一生 发表于 2021-12-22 11:43:53

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

可以发出来看看？

hhh454 发表于 2022-1-2 18:06:34

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

tionsy 发表于 2022-2-8 21:19:29

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

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

1227588 发表于 2022-8-18 10:12:37

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

landsat99 发表于 2023-2-4 09:44:00

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

查看完整版本: 如何获取外围轮廓线？