应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 基础数学 » 撒一把绿豆在桌面上， 将其划分为合理的行和列， 求算法
131/2返回列表12下一页
查看: 1025  |  回复: 12
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

deho

捐助贵宾 (初入文坛)

[求助] 撒一把绿豆在桌面上， 将其划分为合理的行和列， 求算法

已知信息只有（x，y）坐标对：
(56052.5,        79061.7)
(56030.9,        78113.6)
(56428.6,        78425.4)
(56436.5,        78745.9)
。。。
合理的意思是划好的格子里面空洞最少。


例如下面附件里的形态：
撒一把绿豆在桌面上， 将其划分为合理的行和列， 求算法
回复此楼

» 猜你喜欢
1楼 2013-12-30 18:16:09
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
回帖支持 ( 显示支持度最高的前 50 名 )

feixiaolin

荣誉版主 (文坛精英)

优秀版主
问题：
1）曲线划分，还是直线划分？
2）划分格数目有没有限制？
------------------------------------
可以这么做：
以一定大小的方块遍历整个区域一次，大致得到密度分布图，根据密度分布图调整网格大小，确保每个网格有豆子。
赞一下(2人) 回复此楼
2楼2013-12-30 18:47:24
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
普通回帖

deho

捐助贵宾 (初入文坛)
xiaolin,
1 不限直线曲线划分
2 没有行列数的限制

确保每个网格都有豆子不太好办， 因为初始数据集事实上可能确实就有非联通的空洞。

[ 发自手机版 http://muchong.com/3g ]
赞一下 回复此楼
3楼2013-12-30 20:23:04
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

feixiaolin

荣誉版主 (文坛精英)

优秀版主
引用回帖:
3楼: Originally posted by deho at 2013-12-30 20:23:04
xiaolin,
1 不限直线曲线划分
2 没有行列数的限制

确保每个网格都有豆子不太好办， 因为初始数据集事实上可能确实就有非联通的空洞。

确保每个网格都有豆子也好办。
1）从左下角开始扫描，扫到第一个豆子；从第一个豆子在边界线投影处做第二次扫描，扫出第二个豆子；重复如前，扫出右下角的豆子。形成最下面一行豆子【曲线】。
2）将1）中的曲线做下边界线，重复1）中步骤，得到又一条曲线。
3）分界线就在1）、2）两条曲线之间。
……
以上为行扫描
-------------------------
与上面类似，
做左上角到右下角的列扫描，……；
画出一条条分界线就可以了。
赞一下 回复此楼
4楼2013-12-30 20:43:41
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

deho

捐助贵宾 (初入文坛)
引用回帖:
4楼: Originally posted by feixiaolin at 2013-12-30 20:43:41
确保每个网格都有豆子也好办。
1）从左下角开始扫描，扫到第一个豆子；从第一个豆子在边界线投影处做第二次扫描，扫出第二个豆子；重复如前，扫出右下角的豆子。形成最下面一行豆子【曲线】。
2）将1）中的曲线做 ...

xiaolin，
能否提供具体的实现， 先谢了
附件是数据
赞一下 回复此楼

» 本帖附件资源列表

  • 欢迎监督和反馈：小木虫仅提供交流平台，不对该内容负责。
    本内容由用户自主发布，如果其内容涉及到知识产权问题，其责任在于用户本人，如对版权有异议，请联系邮箱：xiaomuchong@tal.com
  • 附件 1 : temporary_24891512.xls
    • 2013-12-30 21:21:28, 748 K
5楼2013-12-30 21:24:13
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

feixiaolin

荣誉版主 (文坛精英)

优秀版主
数据太大了。如果数据少，可以转换成图片形式。
建议你这个利用有限元网格剖分算法，网格内的点可作为一个生成网格的判断条件。
找拥有有限元工具的人处理为好。
撒一把绿豆在桌面上， 将其划分为合理的行和列， 求算法-1
C1C2.JPG
赞一下 回复此楼
6楼2013-12-30 22:05:41
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

deho

捐助贵宾 (初入文坛)
引用回帖:
6楼: Originally posted by feixiaolin at 2013-12-30 22:05:41
数据太大了。如果数据少，可以转换成图片形式。
建议你这个利用有限元网格剖分算法，网格内的点可作为一个生成网格的判断条件。
找拥有有限元工具的人处理为好。

C1C2.JPG
...

是的，非常接近，结果就是图片形式， 叫map图。我说一下应用的背景

这个盘上有几万颗芯片， 可以通过伺服控制和机器视觉，提取出坐标对：
（其实间距也基本是确定的，不过存在测量上的微小噪声）
撒一把绿豆在桌面上， 将其划分为合理的行和列， 求算法-2

然后希望得到的是这个图片：
撒一把绿豆在桌面上， 将其划分为合理的行和列， 求算法-3
赞一下 回复此楼
7楼2013-12-31 11:04:26
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

feixiaolin

荣誉版主 (文坛精英)

优秀版主
引用回帖:
7楼: Originally posted by deho at 2013-12-31 11:04:26
是的，非常接近，结果就是图片形式， 叫map图。我说一下应用的背景

这个盘上有几万颗芯片， 可以通过伺服控制和机器视觉，提取出坐标对：
（其实间距也基本是确定的，不过存在测量上的微小噪声）


然后希望 ...

这个可以用Matlab作。
1）先遍历一次全部数据的x, y坐标，排序得到最小值、最大值；
2）根据1）中最小值、最大值等四个数，建立一个空白图版。
3）再遍历一次全部数据的x, y坐标，为图版上色，某处有点【绿豆】，刷绿；没有的话，涂黑。
   并记录、打印涂黑 位置的 x, y坐标，以备检查。
赞一下 回复此楼
8楼2013-12-31 11:16:28
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

deho

捐助贵宾 (初入文坛)
不错的主意
不过可能还需要细的调整，

因为首次生成的二维数组Map【rows，columns】， 可能他的行列数都会虚高
例如有的行上只有几个点， 其余都是空白，这肯定是分错了
还要把这样的点都归集到相邻的位置上去
赞一下 回复此楼
9楼2013-12-31 11:30:56
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

deho

捐助贵宾 (初入文坛)
上面这个有点类似金字塔这个算法。

还有个问题，由于机械方面实际的实现， 没有办法精确的旋转盘片，从而使盘上的芯片行为水平 列为竖直，；
这样， 际的物理排布 不是横平竖直 而是有个倾斜角
这个倾角导致行延伸到两端位置的颗粒时，已经落入上一行或下一行的位置上了。
这个怎么需要怎么处理 难道要根据某个预设的theta角度向两周进行投影吗
赞一下 回复此楼
10楼2013-12-31 13:01:20
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 deho 的主题更新
131/2返回列表12下一页
普通表情 龙 兔 虎 猫
信息提示
关闭
请填处理意见
关闭