102 lines
1.8 KiB
Text
102 lines
1.8 KiB
Text
DEFINE POINTSIZE="4"
|
|
TYPE PointI=[INT x,y]
|
|
|
|
CARD FUNC GetAddr(INT ARRAY points BYTE index)
|
|
RETURN (points+POINTSIZE*index)
|
|
|
|
BYTE FUNC GetMinXIndex(INT ARRAY points BYTE pLen)
|
|
PointI POINTER p
|
|
BYTE i,index
|
|
INT minX
|
|
|
|
p=GetAddr(points,0)
|
|
minX=p.x
|
|
index=0
|
|
FOR i=1 TO pLen-1
|
|
DO
|
|
p=GetAddr(points,i)
|
|
IF p.x<minX THEN
|
|
minX=p.x
|
|
index=i
|
|
FI
|
|
OD
|
|
RETURN (index)
|
|
|
|
BYTE FUNC Orientation(PointI POINTER p,q,r)
|
|
INT v
|
|
v=(q.y-p.y)*(r.x-q.x)
|
|
v==-(q.x-p.x)*(r.y-q.y)
|
|
|
|
IF v=0 THEN
|
|
RETURN (0)
|
|
ELSEIF v>0 THEN
|
|
RETURN (1)
|
|
FI
|
|
RETURN (2)
|
|
|
|
PROC ConvexHull(INT ARRAY points BYTE pLen
|
|
INT ARRAY res BYTE POINTER resLen)
|
|
PointI POINTER pSrc,pDst,p1,p2,p3
|
|
BYTE minIndex,i,p,q
|
|
|
|
IF pLen<3 THEN
|
|
resLen^=pLen
|
|
MoveBlock(res,points,pLen*POINTSIZE)
|
|
RETURN
|
|
FI
|
|
|
|
resLen^=0
|
|
minIndex=GetMinXIndex(points,pLen)
|
|
p=minIndex q=0
|
|
DO
|
|
pSrc=GetAddr(points,p)
|
|
pDst=GetAddr(res,resLen^)
|
|
pDst.x=pSrc.x
|
|
pDst.y=pSrc.y
|
|
resLen^==+1
|
|
|
|
q=(p+1) MOD pLen
|
|
FOR i=0 TO pLen-1
|
|
DO
|
|
p1=GetAddr(points,p)
|
|
p2=GetAddr(points,i)
|
|
p3=GetAddr(points,q)
|
|
IF Orientation(p1,p2,p3)=2 THEN
|
|
q=i
|
|
FI
|
|
OD
|
|
p=q
|
|
UNTIL p=minIndex
|
|
OD
|
|
RETURN
|
|
|
|
PROC PrintPoints(INT ARRAY points BYTE len)
|
|
PointI POINTER p
|
|
BYTE i
|
|
|
|
FOR i=0 TO len-1
|
|
DO
|
|
p=GetAddr(points,i)
|
|
PrintF("(%I,%I) ",p.x,p.y)
|
|
OD
|
|
RETURN
|
|
|
|
PROC Main()
|
|
INT ARRAY points=[
|
|
16 3 12 17 0 6 65532 65530
|
|
16 6 16 65529 17 65532 5 19
|
|
19 65528 3 16 12 13 3 65532
|
|
17 5 65533 15 65533 65527
|
|
0 11 65527 65533 65532 65534
|
|
12 10]
|
|
INT ARRAY result(38)
|
|
BYTE pLen=[19],rlen
|
|
|
|
ConvexHull(points,pLen,result,@rlen)
|
|
|
|
PrintE("Points:")
|
|
PrintPoints(points,pLen)
|
|
PutE() PutE()
|
|
PrintE("Convex hull:")
|
|
PrintPoints(result,rLen)
|
|
RETURN
|