第一问答网»论坛 › 中问网 › 问答 › 如何判断多边形是否自相交

如何判断多边形是否自相交

[复制链接]

11 |

1 | 2013-8-23 10:48:42 | 显示全部楼层 |阅读模式

自相交是指一个多边形不相邻的边相交。
如何快速判断是否自相交？
时间复杂度应在O(n^2)以下
求出来再给附加d

使用道具举报

千问 | 2013-8-23 10:48:42 | 显示全部楼层

首先需要一个“快速”判断线段相交的算法（网上一大把，自己搜索一下）；逐边两两判断，如果存在2个线段相交，则多边形自相交；否则（最坏情况），多边形“不自相交”，比较次数n*(n-1)/2

使用道具举报

返回列表发新帖

千问

主题	0 回帖	4882万积分

论坛元老

Rank: 8 Rank: 8

积分: 48824836

加好友
发消息

回复楼主返回列表

问答

热门排行

1 帮我查下湛江是否有这家公司！十分感谢！
2 魔兽世界宠物问题
3 关于做NJ的一些关于cooledit的问题
4 UC空间？
5 买5173充值卡充的值能提现吗
6 哪里有QQ三国免费刷钱挂
7 找一本书,求书名,只知道主角叫开天语,是本异能的
8 求帝国时代3：亚洲王朝的作弊码
9 急!谁能准确的告诉我献血到底有没有不良后果啊?
10 奉贤西渡宽带
11 摩尔庄园免费获得超级拉姆的方法
12 摩托罗拉v3x驱动为什么安装不了啊？
13 sony热键
14 鲁东大学和烟大体院哪个好啊？
15 E2160要不要打双核补丁
16 “千里水天一色，看孤鸿明灭”是谁的诗？
17 淘宝绿卡（支付宝卡通）申请的问题。
18 鸡＼牵牛花＼小兔＼小猴＼绿草＼鸭＼喜鹊＼菊花＼羊＼鹅哪种属于禽类；哪种属于兽类；哪种属于植物
19 谁能找到罗伊绝杀火箭的那段解说员的声音？
20 金箔漆的价格和使用。
21 JSP的一个小问题
22 我想成为情侣空间
23 各位大虾！宽屏切换普屏怎麽调啊！？
24 中国平安保险公司
25 高一物理
26 剧本中的矛盾冲突和分析剧本这两点有什么关联
27 英语作文《八年级下册第三单元B部分4a作文》拜托了
28 我182,体重80KG,打篮球什么位置好??17岁!!
29 想做成功吗？想做成功人士吗？
30 帮忙翻译一下韩语
31 腰椎右侧一直疼，未生育，不想吃，偶尔回有恶心感觉，弯腰回疼才20岁不会是肾什么炎症吧？？？
32 对...产生影响的英文
33 我的mp4为什么关不了公放
34 亚洲国家的独立和振兴
35 打胎后5后天出血
36 汉语“露”翻译蒙语是什么？
37 三年级下学期数学补充习题的答案是什么
38 手机主题
39 怎样加载XP启动项
40 2008年奥运会人们普遍关注的是什么
41 计算机光驱坏了能否正常启动工作？
42 古灵《一家都是宝》
43 加拿大哪天休息？例如咱们是周六周日。
44 右耳正中央长了一颗小痣，看起来就像是耳洞，能不能打耳洞啊？
45 美术成绩查询
46 需东方神起王道小说TXT格式压缩包
47 第二个写成语
48 用下面偏旁组成一个双字词语，再用该词语写一句话：
49 高一物理天文学题怎么做
50 蛇在睡觉时
51 怎么注销QQ宠物？？？请详细些
52 怎么改变百度的头像阿？
53 液晶显示器黑屏
54 下面各题中的两种量是否成正比例？说明理由。
55 专转本，专接本，专升本，夜大的区别
56 大庆信息港房产频道这几天怎么总上不去啊??总是无法打开网页或网址不存在!
57 你们说她会生气吗？我不懂。
58 长期低热怎么办
59 剑侠世界武器问题
60 萧山盈笑幼儿园
61 清清楚楚一幅画，有树有草也有花，别处花草梢朝上，此处花草梢朝上
62 征途为什么我的手套/扇子没绑定让别人爆了，我有的手套就绑定了爆不了
63 南京中华门外新建到雨花台的距离
64 Windows Vista SP1(旗舰版)64位和32位问题！
65 郭采洁和张栋梁是男女朋友吗？
66 关于校园网
67 关于执业中医师注册问题,急!!!
68 DNF狂战要是都是穿的蓝色的装备和武器那觉醒好吗
69 ngl season6 哪里有直播
70 追加20 有关最游记的问题
71 无法读取光盘文件？
72 关于Nokia 5320XM的内存卡问题，急！
73 戴伊敬是谁？
74 荣威750i大师版广告曲
75 工行运动卡的问题
76 地球地轴与旋转轴的夹角在哪
77 摩尔庄园里小摩尔脖子上的珠子是什么？怎么得到？
78 要不要说出来???
79 诺基亚E50的问题！
80 偶尔网页图片不能显示
81 使命召唤4有几个版本
82 2009 暨大研究生复试
83 用所给词填空
84 是哪里啊
85 草桥到北京市丰台区方庄桥东四方景园二区怎么坐公交
86 两个人头中间形成一只杯子
87 管理员会不会删掉要英语答案的提问
88 古诗词中还是哪些也写到了农具
89 什么叫桃花眼？
90 请设计高手,帮我看看这个英文是什么字体名?
91 邮箱自己可以取注销掉吗？
92 从长宁区延安西路1882号东华大学到浦建路929号怎么走啊？？
93 高手帮忙看看配置是否有问题？
94 几斤大豆能炸出一斤豆油
95 为什么不能用鼠标把文字圈起来
96 我在当当网上买的书为什么25天了还没有给我邮过来。
97 qq华夏引魂在哪引比较好
98 有艾诺v6000hda初始固件，初始机子里的所有文件包括文件夹
99 写安庆春节习俗的作文
100 有关家的英语短文