作者DRLai (苏打)
看板C_and_CPP
标题[问题] 线条组合是否有比较推荐的结构？
时间Fri Apr 17 13:50:47 2009
最近在解一个问题，关於线段的合并
我找不到一个比较好的结构or演算法来达成
假设我有下列资料
0,0 0,1
0,1 0,5
1,1 0,1
一行表示一条线段，例如第一行表示从座标(0,0)到(0,1)的线段
现在的问题是，我想进行线段合并
亦即范例中的第一行跟第二行可以合并为(0,0)到(0,5)的线段
目前我的作法是将所有线段存在list中
然後跑两层回圈一个一个比对
但是这样的作法感觉有点没效率@@而且要写得很复杂
请问有比较好的方式吗？
题目不会有线段压线段的问题
亦即当我有(0,0) - (0,1)这条线段时
就不可能会有另一条线段覆盖过他，如(0,0) - (0,2)
线段只有分为水平跟垂直两种，不会有其他类型的转弯
(如(0,0) - (1,1)这种线段不会出现)
最好的作法就是跑两层回圈吗@@"
烦请高手指导：）
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.138.145.212
1F：推 ledia:先把所有线段排序, 比大小的方式, 先斜率, 再 x, 再 y 04/17 13:52
2F：→ ledia:同斜率才会接起来, 因为不覆盖, 所以同斜率中只有 04/17 13:53
3F：→ ledia:以 x (或 y) 座标来看相邻的点才有可能接起来 04/17 13:53
4F：→ karcher:可以先取一点为参考中心，然後取得所有以该参考点为出发点 04/17 14:11
5F：→ karcher:的向量集合。然後用计算determinant的方式将集合分类 04/17 14:13
6F：推 snowlike:x=k(常数),排序y;y=k,排序x;阵列{0,1,1,5}重复出现就干掉 04/17 15:03
7F：推 Ebergies:那这样 {0,5} 是啥意思 XD 04/17 15:04
8F：→ snowlike:线段0-5，不排序也没关系输出再排就好了 04/17 15:05
9F：推 maplefog:给每个线段一个element number，建立connection matrix 04/17 15:49
10F：→ DRLai:感谢楼上几位@@我最後是使用s大说得阵列方式解决m(_ _)m 04/18 02:48