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

N

newstar

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-15

• #1

已知多边形的n个顶点的坐标，怎样判断任两个顶点的连线是否是该多形的边

 

D

darnis

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-15

• #2

如果你的多边形是有序的，那就简单了，只需要判断两个顶点是不是相邻的（比如是
用数组来表示的顶点，那如果这两个顶点的下标值的差的绝对值不等于1不是相邻的）。
如果不是有序的，而是乱的，可不可以想办法先排序再判断呢？

 

J

jsxjd

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-15

• #3

仅给出 n 个顶点，可以构造出不止一个多边形。
一般是按顺序给出的。这样应该就简单了。
如果只知道 n 个顶点，应该再加上约束。比如是“凸多边形”等信息。

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-15

• #4

同意楼上的同志们。
如果能够确定这些点是按顺序给出的，或者虽然不能确定顺序，但是可以确定是凸多边形
的话，也可以通过计算来判断。如果不能满足上述任何一个条件，完全可能得到多个结果。
例如：
D
A C
F
B E
可能结果：
A B F E C D
A F B E C D
A B E F C D
...

 

H

Haha...

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-15

• #5

逐点比较的话很慢,建议你先求出多边形的边长(像素个数)然后用图形矢量运算
你先看一下我以前回的这个帖子:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1310195
应该能明白我的意思

 

N

newstar

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-15

• #6

thank jsxjd!
只知道 n 个顶点,要先判断是否能构成凸多边形

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-15

• #7

判断是否是凸多边形的方法很简单：
1.遍历序列，找到位于最左边的顶点(A)
2.计算其它顶点与A的连线的斜率，并根据斜率进行顶点排序。（如果所给的点集可以构成
一个凸多边形，且没有三个顶点在一条直线上的情况，那么如此排序后的顶点就已经是“
顺序”的了）。
3.遍历排序后的顶点，过每对相邻顶点做直线，如果发现其它的点并不都在直线的同侧，那
么该点集就不能构成凸多边形，算法结束。
4.如果第3步的验证没有问题，那么在第2步计算出的排序后顶点序列就已经是我们需要的东
西了。
写完上面的算法，我想到了一个简便的方法：过待考察的两个顶点做一条直线，若其它的
点都在直线的同侧，则可以认为该连线是多边形的边（未考虑凹多边形的情况，但是算法非
常容易实现）。

 

J

jsxjd

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-15

• #8

给出足够的约束信息。

 

N

newstar

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-16

• #9

多人接受答案了。