1 2 !---------------------------------------------------------------------- 3 ! Courtesy: Jay Sandhu 4 ! email: jsandhu@esri.com 5 ! 6 ! 7 ! Please cite David H. Douglas, COLLECTED ALGORITHMS, Cambridge MA: 8 ! Harvard Laboratory for Computer Graphics, 1974 9 ! 10 ! This is my reinvention buster. 11 ! 1974 1974 1974 1974 1974 1974 1974 1974 1974 1974 1974 1974 12 ! 13 !>>>PNPY 14 ! ................................................................. 15 ! 16 ! SUBROUTINE PNPOLY 17 ! 18 ! PURPOSE 19 ! TO DETERMINE WHETHER A POINT IS INSIDE A POLYGON 20 ! 21 ! USAGE 22 ! CALL PNPOLY (PX, PY, X, Y, N, INOUT ) 23 ! 24 ! DESCRIPTION OF THE PARAMETERS 25 ! PX - X-COORDINATE OF POINT IN QUESTION. 26 ! PY - Y-COORDINATE OF POINT IN QUESTION. 27 ! X - N LONG VECTOR CONTAINING X-COORDINATES OF 28 ! VERTICES OF POLYGON. 29 ! Y - N LONG VECTOR CONTAINING Y-COORDINATES OF 30 ! VERTICES OF POLYGON. 31 ! N - NUMBER OF VERTICES IN THE POLYGON. 32 ! INOUT - THE SIGNAL RETURNED: 33 ! -1 IF THE POINT IS OUTSIDE OF THE POLYGON, 34 ! 0 IF THE POINT IS ON AN EDGE OR AT A VERTEX, 35 ! 1 IF THE POINT IS INSIDE OF THE POLYGON. 36 ! 37 ! REMARKS 38 ! THE VERTICES MAY BE LISTED IN CLOCKWISE OR ANTICLOCKWISE 39 ! ORDER. FOR THIS SUBROUTINE A POINT IS CONSIDERED INSIDE 40 ! THE POLYGON IF IT IS LOCATED IN THE ENCLOSED AREA DEFINED 41 ! BY THE LINE FORMING THE POLYGON. 42 ! THE INPUT POLYGON MAY BE A COMPOUND POLYGON CONSISTING 43 ! OF SEVERAL SEPARATE SUBPOLYGONS. IF SO, THE FIRST VERTEX 44 ! OF EACH SUBPOLYGON MUST BE REPEATED, AND WHEN CALCULATING 45 ! N, THESE FIRST VERTICES MUST BE COUNTED TWICE. 46 ! INOUT IS THE ONLY PARAMETER WHOSE VALUE IS CHANGED. 47 ! PNPOLY CAN HANDLE ANY NUMBER OF VERTICES IN THE POLYGON. 48 ! WRITTEN BY RANDOLPH FRANKLIN, UNIVERSITY OF OTTAWA, 6/72. 49 ! 50 ! SUBROUTINES AND FUNCTION SUBPROGRAMS REQUIRED 51 ! NONE 52 ! 53 ! METHOD 54 ! A VERTICAL SEMI-INFINITE LINE IS DRAWN UP FROM THE POINT 55 ! IN QUESTION. IF IT CROSSES THE POLYGON AN ODD NUMBER OF 56 ! TIMES, THE POINT IS INSIDE THE POLYGON. 57 ! 58 ! ................................................................. 59 ! 60 SUBROUTINE PNPOLY(PX,PY,X,Y,N,INOUT) 61 62 IMPLICIT NONE 63 64 INTEGER I , J , N , INOUT 65 REAL X(N) , Y(N) , XI , YI , XJ , YJ , PX , PY 66 LOGICAL IX , IY , JX , JY , EOR 67 68 ! EXCLUSIVE OR STATEMENT FUNCTION. 69 EOR(IX,IY) = (IX .OR. IY) .AND. .NOT.(IX .AND. IY) 70 71 INOUT = -1 ! 0 72 73 DO I = 1 , N 74 XI = X(I) - PX ! 0 75 YI = Y(I) - PY 76 ! CHECK WHETHER THE POINT IN QUESTION IS AT THIS VERTEX. 77 IF ( XI.EQ.0.0 .AND. YI.EQ.0.0 ) THEN 78 INOUT = 0 ! 0 79 RETURN 80 ENDIF 81 ! J IS NEXT VERTEX NUMBER OF POLYGON. 82 J = 1 + MOD(I,N) ! 0 83 XJ = X(J) - PX 84 YJ = Y(J) - PY 85 ! IS THIS LINE OF 0 LENGTH ? 86 IF ( XI.EQ.XJ .AND. YI.EQ.YJ ) GOTO 100 87 IX = XI.GE.0.0 ! 0 88 IY = YI.GE.0.0 89 JX = XJ.GE.0.0 90 JY = YJ.GE.0.0 91 ! CHECK WHETHER (PX,PY) IS ON VERTICAL SIDE OF POLYGON. 92 IF ( XI.EQ.0.0 .AND. XJ.EQ.0.0 .AND. EOR(IY,JY) ) THEN 93 INOUT = 0 ! 0 94 RETURN 95 ENDIF 96 ! CHECK WHETHER (PX,PY) IS ON HORIZONTAL SIDE OF POLYGON. 97 IF ( YI.EQ.0.0 .AND. YJ.EQ.0.0 .AND. EOR(IX,JX) ) THEN ! 0 98 INOUT = 0 ! 0 99 RETURN 100 ENDIF 101 ! CHECK WHETHER BOTH ENDS OF THIS SIDE ARE COMPLETELY 1) TO RIGHT 102 ! OF, 2) TO LEFT OF, OR 3) BELOW (PX,PY). 103 IF ( .NOT.((IY .OR. JY) .AND. EOR(IX,JX)) ) GOTO 100 ! 0 104 ! DOES THIS SIDE OBVIOUSLY CROSS LINE RISING VERTICALLY FROM (PX,PY) 105 IF ( .NOT.(IY .AND. JY .AND. EOR(IX,JX)) ) THEN ! 0 106 IF ( (YI*XJ-XI*YJ)/(XJ-XI).LT.0.0 ) THEN ! 0 107 GOTO 100 ! 0 108 ELSEIF ( (YI*XJ-XI*YJ)/(XJ-XI).EQ.0.0 ) THEN 109 INOUT = 0 ! 0 110 RETURN 111 ELSE 112 INOUT = -INOUT ! 0 113 ENDIF 114 ELSE 115 INOUT = -INOUT ! 0 116 ENDIF 117 118 100 ENDDO 119 120 CONTINUE ! 0 121 END
HyperKWIC - Version 1.00DD executed at 20:00 on 1 Mar 2018 | Personal or Academic or Evaluation User | Free for Non-Commercial, Non-Government Use