怎样判断,任意多边形的任意两个顶点的连线是否是该多边形的边界。(200分)

N

newstar

Unregistered / Unconfirmed
GUEST, unregistred user!
已知多边形的n个顶点的坐标,怎样判断任两个顶点的连线是否是该多形的边
 
如果你的多边形是有序的,那就简单了,只需要判断两个顶点是不是相邻的(比如是
用数组来表示的顶点,那如果这两个顶点的下标值的差的绝对值不等于1不是相邻的)。
如果不是有序的,而是乱的,可不可以想办法先排序再判断呢?
 
仅给出 n 个顶点,可以构造出不止一个多边形。
一般是按顺序给出的。这样应该就简单了。
如果只知道 n 个顶点,应该再加上约束。比如是“凸多边形”等信息。
 
同意楼上的同志们。
如果能够确定这些点是按顺序给出的,或者虽然不能确定顺序,但是可以确定是凸多边形
的话,也可以通过计算来判断。如果不能满足上述任何一个条件,完全可能得到多个结果。
例如:
D
A C
F
B E
可能结果:
A B F E C D
A F B E C D
A B E F C D
...
 
逐点比较的话很慢,建议你先求出多边形的边长(像素个数)然后用图形矢量运算
你先看一下我以前回的这个帖子:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1310195
应该能明白我的意思
 
thank jsxjd!
只知道 n 个顶点,要先判断是否能构成凸多边形
 
判断是否是凸多边形的方法很简单:
1.遍历序列,找到位于最左边的顶点(A)
2.计算其它顶点与A的连线的斜率,并根据斜率进行顶点排序。(如果所给的点集可以构成
一个凸多边形,且没有三个顶点在一条直线上的情况,那么如此排序后的顶点就已经是“
顺序”的了)。
3.遍历排序后的顶点,过每对相邻顶点做直线,如果发现其它的点并不都在直线的同侧,那
么该点集就不能构成凸多边形,算法结束。
4.如果第3步的验证没有问题,那么在第2步计算出的排序后顶点序列就已经是我们需要的东
西了。
写完上面的算法,我想到了一个简便的方法:过待考察的两个顶点做一条直线,若其它的
点都在直线的同侧,则可以认为该连线是多边形的边(未考虑凹多边形的情况,但是算法非
常容易实现)。
 
给出足够的约束信息。
 
多人接受答案了。
 
顶部