Anonymous user
Convex hull: Difference between revisions
Added solution for Action!
(Added solution for Action!) |
|||
Line 82:
(5, 19)
(-3, 15)
</pre>
=={{header|Action!}}==
<lang Action!>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</lang>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Convex_hull.png Screenshot from Atari 8-bit computer]
<pre>
Points:
(16,3) (12,17) (0,6) (-4,-6) (16,6) (16,-7) (17,-4) (5,19) (19,-8) (3,16) (12,13) (3,-4) (17,5) (-3,15) (-3,-9) (0,11) (-9,-3) (-4,-2) (12,10)
Convex hull:
(-9,-3) (-3,-9) (19,-8) (17,5) (12,17) (5,19) (-3,15)
</pre>
| |||