十万火急(200分)

L

LanFairy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-03-19

• #1

我在开发项目中遇到关于多边形计算问题，请各位大虾多多指教，可以帮我指出算法的思路
，或告诉我一些好的网站。

1、关于计算多边形面积，当多边形中即有直边，又有弧边的凹多边形时，如何计算。
2、两个不规则多边形相交时，相交面积如何计算。

 

V

VGA

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-03-19

• #2

从最低点向最高点扫描，用右端减左端。再逐行累加起来。
对于相交的多边形也可用此法。

不知你的多边形是什么存储结构？

 

G

g622

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-03-19

• #3

你的多边形存储的是位图吗？假如是：
笨办法如下：
1)逐行从左边边界逐点扫描，遇到第1个边界开始记数，第2个边界停止记数，以后在这一
行上奇数个边界处开始记数，偶数边界停止，最后的记数值就是你的面积，而实际面积和
这个面积的换算就不用说了
2）道理同上，只是在每一行自己判断一下边界的重叠区域就可以了

 

吕

吕雪松

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-03-19

• #4

如果是栅格数据，就进行逻辑求交操作（不用我多解释吧？）
如果是矢量数据。
1，分解多边形为多个三角形（弧边分解为扇形）。在DirectX中渲染表面时，也要用到多
边形分解为多个三角形的算法。
2，每个三角形用海伦公式求面积。

多边形求交
每条边遍历，开一个缓冲区，分别存放求得的交点和第一交点和最后交点之间的顶点。然后
生成多边形，再分解为三角形。

 

L

LanFairy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-03-22

• #5

我采用的是氏量图，多边形存储形式的说明如下如那位能写出优秀的详细算法分数不成
问题！！！，谢谢大家
多边形是按逆时针方向以顶点链表的形式存储的，顶点的表示方式为：
PpolygonTop=^TpolygonTop
TpolygonTop=record .
Ts,Te : Double;
Outflag : Boolean;
Case Integer of
0: (Xs,Ys,Xc,Yc : Double);
1 : (Ps,Pe : TCoordinate);
End;
{Tcoordinate=record
X,Youble;
End;}
顶点记录表示的是以该点为起点的多边形的一条边（弧）的特征，各字段代表的特征为：
Ts=-1表示下一条边为直线，此时Te无意义。
outFlag=False Ts<>-1则Ts表示下一条边为弧(圆的一部分)。
Ts代表弧的起始角，Te代表终止角。
所画的弧的方向为逆时针时OutFlag为真。所画弧的方向为顺时针时OutFlag为假。
当TS= -1时 Xs Ys为该点坐标，Xc Yc 无意义。
当Ts<> -1时 Xs Ys 为该点坐标，Xc Yc 为圆弧所在圆的圆心坐标。

 

L

LanFairy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-03-23

• #6

数学天才都到哪儿却了，这里有没有数学天才？有没在自己开发过做图平台的？？？

 

L

LanFairy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-03-24

• #7

我的数据结构已经列出来了，如果谁给写出好的算法，我愿再给200分，因为一般的问题我
已经解决有些特殊图形不好解决，图形在这里没法给出，如果哪位大侠想和我共同研究，
请Email me :lanfairy@sina.com

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-03-24

• #8

www.google.com
Keywords:
多边形 面积 -3D -游戏
1310个结果.

 

H

htw

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-04-13

• #9

?

 

T

threego

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-04-15

• #10

用积分就好了，不就是个简单的积分问题嘛。看看高数吧。

 

R

redcony

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-04-21

• #11

用多边形削减法，把当前边的起点和下一边的终点相连成一条直线，可以得到一个三角形
或扇形，判断当前边的终点在新直线的做侧还是右侧，可以规定一侧全部增加面积。一个for
循环即可作到。

 

R

redcony

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-04-21

• #12

两个多边形相交就复杂了，首先有一个求不规则多边形面积的函数f（）；
然后求出相交的多边形即可。
求相交多边形的算法可以用willer Arthon算法。
有不明白的地方发E-Mail给我。

 

L

LanFairy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-05-20

• #13

提前

 

L

LanFairy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-09-10

• #14

这个问题已经没什么意义了，版主看着把分分了算了

 

卷

卷起千堆雪tyn

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-10-11

• #15

不要灰心啊！

积分方法求多边形的面积：

首先定义数据结构：

const MaxPointNum = 65535;
type
PXY = ^TXY;
TXY = record // 点的数据结构
x, y: single;
end;
XYArray = array[0..MaxPointNum] of TXY;
PXYArray = ^XYArray; // 线的数据结构

// 多边形坐标在 xys 中，点数在 nn 中
function AreaOfPolygon(xys: PXYArray; nn: integer):single;
var ii:integer;
ss: single;
begin
ss := 0;
for ii := 0 to nn-2 do
ss := ss + (xys^[ii].y+xys^[ii+1].y) * (xys^[ii].x-xys^[ii+1].x) / 2;
result := abs(ss);
end;

对于问题2，只要你求解出两个多边形的交点坐标，组合成一个新的多边形，用上面的方法就可以
求解出来的。

 

H

Huzzz

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-10-11

• #16

1 简单积分和或差（岛或洞），楼上的厉害；
2 多个交节点组合（我不会）。

 

C

chennan16

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-10-12

• #17

http://www.geovista.psu.edu/sites/geocomp99/Gc99/076/gc_076.htm

 

L

LanFairy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-04-10

• #18

多人接受答案了。