当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 11 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : [问题]一矩形重叠/切割算法题,望高手给出解答,期待中......
帖子发表于 : 2008-05-19 11:22 
头像

注册: 2008-04-05 10:56
帖子: 129
地址: 学校
送出感谢: 0 次
接收感谢: 0 次
矩形用两个坐标点表示,左下角坐标和右上角坐标。现有两个矩形A和B,分别输入两个矩形的左下角和右上角坐标,求出矩形A被矩形B切割后的所形成的若干个矩形区域,也分别用左下角和右上角表示。

如下输入:
0,0 //A的左下角坐标
2,2 //A的右上角坐标
1,1 //B的左下角坐标
3,3 //B的右上角坐标

输出为:
(0,0)-(1,2)
(1,0)-(2,1)

或另一种表达方式也可,如下
(0,0)-(2,1)
(0,1)-(1,2)

请问这样的题目,应该怎么做??
我已经用google和baidu搜索了很多,但就是找不到相类似的题目和解答,请高手给出解答,给出用什么数据结构表示,算法的大概思路即可,不用源代码(有的话更好 :)。 不胜感激,谢谢。期待解答中.....


_________________
修己,安人


页首
 用户资料  
 
2 楼 
 文章标题 :
帖子发表于 : 2008-05-22 10:25 
头像

注册: 2008-04-05 10:56
帖子: 129
地址: 学校
送出感谢: 0 次
接收感谢: 0 次
期待中。。。。。。


_________________
修己,安人


页首
 用户资料  
 
3 楼 
 文章标题 :
帖子发表于 : 2008-05-22 12:46 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
只有两个矩形?

不过思路都是差不多

1. 按所有矩形的数据对平面离散化
2. 标记
3. 扫描平面, 找所有矩形


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
4 楼 
 文章标题 :
帖子发表于 : 2008-05-22 17:12 
头像

注册: 2007-07-12 16:30
帖子: 303
地址: 桂林
送出感谢: 0 次
接收感谢: 2
BigSnake.NET 写道:
1. 按所有矩形的数据对平面离散化
2. 标记
3. 扫描平面, 找所有矩形
:em66实在太精练了!差点没明白 :em08


页首
 用户资料  
 
5 楼 
 文章标题 :
帖子发表于 : 2008-05-22 17:19 
头像

注册: 2008-04-05 10:56
帖子: 129
地址: 学校
送出感谢: 0 次
接收感谢: 0 次
最困难的就是扫描算法了,请问可否有扫描算法的详细步骤


_________________
修己,安人


页首
 用户资料  
 
6 楼 
 文章标题 :
帖子发表于 : 2008-05-22 17:24 
头像

注册: 2007-07-12 16:30
帖子: 303
地址: 桂林
送出感谢: 0 次
接收感谢: 2
google "凸多边形 扫描算法"

http://www.geomodel.com.cn/html/College/Application/Geophysical/20070806/281.html


页首
 用户资料  
 
7 楼 
 文章标题 :
帖子发表于 : 2008-05-22 17:29 
头像

注册: 2007-07-12 16:30
帖子: 303
地址: 桂林
送出感谢: 0 次
接收感谢: 2
这个可能更适合你:

代码:
摘  要:
提出了一个面向快速成型扫描路径规划的凹多边形凸分解算法。首先应用所提出的基于正负法搜索凹点对应的可见点的新算法来找出凹点的可见点串,然后结合所提出的适用于快速制造中扫描分区的剖分准则,利用权函数选择最佳剖分点,并合理使用辅助点,保证了剖分所得凸多边形的形态质量。该算法作为快速成形选区环形扫描路径规划软件的底层算法,在对待扫描的层面轮廓进行分区时得到了应用。[著者文摘]

关 键 词:
凹多边形 凸分解 正负法 可见点 快速成型 分区扫描

文章出处: 《计算机应用》-2005年25卷9期 -2143-2145页
journal of Computer Applications

栏目信息: 图形图像处理
分 类 号: TP391.72
文献标识码: A
文章编号: 1001-9081(2005)09-2143-03


页首
 用户资料  
 
8 楼 
 文章标题 :
帖子发表于 : 2008-05-23 8:33 
头像

注册: 2005-10-25 11:15
帖子: 1016
送出感谢: 0 次
接收感谢: 1
两个正交矩形处理起来不需要那么复杂吧,手工把几个情况枚举一下就可以。下面的程序是python写的
代码:
x=[0,2,1,3]
y=[0,2,1,3]
print [(a,c,b,d) for (a,b,c,d) in [(x[0],min(x[1],x[2]),y[0],y[1]), (max(x[0],x[3]),x[1],y[0],y[1]), (max(x[0],x[2]),min(x[1],x[3]),y[0],min(y[1],y[2])), (max(x[0],x[2]),min(x[1],x[3]),max(y[0],y[3]),y[1])] if b>a and d>c]

输出
代码:
[(0, 0, 1, 2), (1, 0, 2, 1)]


_________________
hreiser@oakland:~$ killall -9 wife
police@oakland:~$ sudo find / -user hreiser
court@oakland:~$ sudo mv /home/hreiser /jail/
court@oakland:~$ sudo usermod -d /jail/hreiser -s "/usr/sbin/chroot /jail/" hreiser


页首
 用户资料  
 
9 楼 
 文章标题 :
帖子发表于 : 2008-05-31 15:21 
头像

注册: 2008-04-05 10:56
帖子: 129
地址: 学校
送出感谢: 0 次
接收感谢: 0 次
解决方案:
#include <iostream>
using namespace std;

int main()
{
int m1_l, m1_r, m1_b, m1_t;
int m2_l, m2_r, m2_b, m2_t;

cin >> m1_l >> m1_b >> m1_r >> m1_t;
cin >> m2_l >> m2_b >> m2_r >> m2_t;

if (m1_l < m2_l && m1_b < m1_t)
cout << m1_l << " " << m1_b << " - " << m2_l << " " << m1_t << endl;
if (m2_l < m1_r && m1_b < m2_b)
cout << m2_l << " " << m1_b << " - " << m1_r << " " << m2_b << endl;
if (m2_l < m2_r && m2_t < m1_t)
cout << m2_l << " " << m2_t << " - " << m2_r << " " << m1_t << endl;
if (m2_r < m1_r && m2_b < m1_t)
cout << m2_r << " " << m2_b << " - " << m1_r << " " << m1_t << endl;

return 0;
}


_________________
修己,安人


页首
 用户资料  
 
10 楼 
 文章标题 :
帖子发表于 : 2008-05-31 15:22 
头像

注册: 2008-04-05 10:56
帖子: 129
地址: 学校
送出感谢: 0 次
接收感谢: 0 次
代码:
#include <iostream>
using namespace std;

int main()
{
   int m1_l, m1_r, m1_b, m1_t;
   int m2_l, m2_r, m2_b, m2_t;

   cin >> m1_l >> m1_b >> m1_r >> m1_t;
   cin >> m2_l >> m2_b >> m2_r >> m2_t;

   if (m1_l < m2_l && m1_b < m1_t)
      cout << m1_l << " " << m1_b << " - " << m2_l << " " << m1_t << endl;
   if (m2_l < m1_r && m1_b < m2_b)
      cout << m2_l << " " << m1_b << " - " << m1_r << " " << m2_b << endl;
   if (m2_l < m2_r && m2_t < m1_t)
      cout << m2_l << " " << m2_t << " - " << m2_r << " " << m1_t << endl;
   if (m2_r < m1_r && m2_b < m1_t)
      cout << m2_r << " " << m2_b << " - " << m1_r << " " << m1_t << endl;

   return 0;
}
[/code]


_________________
修己,安人


页首
 用户资料  
 
11 楼 
 文章标题 :
帖子发表于 : 2008-05-31 15:25 
头像

注册: 2008-04-05 10:56
帖子: 129
地址: 学校
送出感谢: 0 次
接收感谢: 0 次
我还想出了一个解决方案,就是比较繁锁了点
代码:
#include <iostream>
#include <vector>

using namespace std;

struct Point
{
   int left;
   int right;
};


void overlap(Point a, Point b, vector<Point> & over_vector, vector<Point> & n_over_vector)
{
   Point temp_point;
   if (b.right <= a.left)
   {
      n_over_vector.push_back(a);   
   }for (int i = 0; i < h_n_over_vector.size(); i++)
   {
      cout << h_n_over_vector[i].left << " ";
      cout << v_1.left;
      cout << " , ";
      cout << h_n_over_vector[i].right << " ";
      cout << v_1.right;
   }
   else if (b.right > a.left && b.right < a.right)
   {
      if (b.left <= a.left)
      {
         temp_point.left = a.left, temp_point.right = b.right;   
         over_vector.push_back(temp_point);
         temp_point.left = b.right, temp_point.right = a.right;
         n_over_vector.push_back(temp_point);
      }
      else //b.left > a.left
      {
         temp_point.left = a.left, temp_point.right = b.left;
         n_over_vector.push_back(temp_point);
         temp_point.left = b.left, temp_point.right = b.right;
         over_vector.push_back(temp_point);
         temp_point.left = b.right, temp_point.right = a.right;
         n_over_vector.push_back(temp_point);
      }
   }
   else if (b.right == a.right)
   {
      if (b.left <= a.left)
      {
         over_vector.push_back(a);
      for (int i = 0; i < h_n_over_vector.size(); i++)
   {
      cout << h_n_over_vector[i].left << " ";
      cout << v_1.left;
      cout << " , ";
      cout << h_n_over_vector[i].right << " ";
      cout << v_1.right;
   }}
      else //b.left > a.left
      {
         temp_point.left = a.left, temp_point.right = b.left;
         n_over_vector.push_back(temp_point);
         temp_point.left = b.left, temp_point.right = a.right;
         over_vector.push_back(temp_point);
      }
   }
   else //b.right > a.right
   {
      if (b.left <= a.left)
      {
         over_vector.push_back(temp_point);
      }
      else if (b.left > a.left && b.left < a.right)
      {
         temp_point.left = a.left, temp_point.right = b.left;
         n_over_vector.push_back(temp_point);
      for (int i = 0; i < h_n_over_vector.size(); i++)
   {
      cout << h_n_over_vector[i].left << " ";
      cout << v_1.left;
      cout << " , ";
      cout << h_n_over_vector[i].right << " ";
      cout << v_1.right;
   }   temp_point.left = b.left, temp_point.right = a.right;
         over_vector.push_back(temp_point);
      }
      else //b.left >= a.right
      {
         n_over_vector.push_back(a);
      }
   }
}

int main()
{
   vector<Point> h_over_vector, v_over_vector;
   vector<Point> h_n_over_vector, v_n_over_vector;
   int left, bottom, right, top;
   Point h_1, h_2;
   Point v_1, v_2;
   
   cout << "第一个矩形的左下角坐标:"; cin >> h_1.left >> v_1.left;
   cout << "第一个矩形的右上角坐标:"; cin >> h_1.right >> v_1.right;
          cout << "第二个矩形的左下角坐标:"; cin >> h_2.left >> v_2.left;
   cout << "第二个矩形的右上角坐标:"; cin >> h_2.right >> v_2.right;

   overlap(h_1, h_2, h_over_vector, h_n_over_vector);
   overlap(v_1, v_2, v_over_vector, v_n_over_vector);

   for (int i = 0; i < h_n_over_vector.size(); i++)
   {
      cout << h_n_over_vector[i].left << " ";
      cout << v_1.left;
      cout << " , ";
      cout << h_n_over_vector[i].right << " ";
      cout << v_1.right << endl;
   }

   for (int i = 0; i < h_over_vector.size(); i++)
   {
      for (int j = 0; j < v_n_over_vector.size(); j++)
      {
         cout << h_over_vector[i].left << " ";
         cout << v_n_over_vector[j].left;
         cout << " , ";
         cout << h_over_vector[i].right << " ";
         cout << v_n_over_vector[i].right << endl;
      }
   }

   

   return 0;
}


_________________
修己,安人


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 11 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:Google [Bot] 和 3 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译