home *** CD-ROM | disk | FTP | other *** search
open in:
MacOS 8.1
|
Win98
|
DOS
browse contents |
view JSON data
|
view as text
This file was processed as: Mailbox/MIME Entity
(archive/mbox).
Confidence | Program | Detection | Match Type | Support
|
---|
100%
| dexvert
| Mailbox/MIME Entity (archive/mbox)
| magic
| Supported |
100%
| dexvert
| Internet Message Format (text/imf)
| magic
| Supported |
1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
100%
| file
| Mailbox text, 1st line "From sbw@naucse.UUCP Mon Mar 23 13:30:21 1987"
| default
| |
99%
| file
| C source, ASCII text
| default
| |
100%
| TrID
| E-Mail message (Var. 2)
| default
| |
100%
| checkBytes
| Printable ASCII
| default
| |
100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
100%
| siegfried
| x-fmt/111 Plain Text File
| default
| |
100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
| |
100%
| xdgMime
| application/mbox
| default
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 20 73 62 77 | 40 6e 61 75 63 73 65 2e |From sbw|@naucse.|
|00000010| 55 55 43 50 20 4d 6f 6e | 20 4d 61 72 20 32 33 20 |UUCP Mon| Mar 23 |
|00000020| 31 33 3a 33 30 3a 32 31 | 20 31 39 38 37 0a 50 61 |13:30:21| 1987.Pa|
|00000030| 74 68 3a 20 73 65 69 73 | 6d 6f 21 72 75 74 67 65 |th: seis|mo!rutge|
|00000040| 72 73 21 73 72 69 2d 75 | 6e 69 78 21 68 70 6c 61 |rs!sri-u|nix!hpla|
|00000050| 62 73 21 68 61 6f 21 6e | 6f 61 6f 21 61 72 69 7a |bs!hao!n|oao!ariz|
|00000060| 6f 6e 61 21 6e 61 75 63 | 73 65 21 73 62 77 0a 46 |ona!nauc|se!sbw.F|
|00000070| 72 6f 6d 3a 20 73 62 77 | 40 6e 61 75 63 73 65 2e |rom: sbw|@naucse.|
|00000080| 55 55 43 50 20 28 53 74 | 65 76 65 20 57 61 6d 70 |UUCP (St|eve Wamp|
|00000090| 6c 65 72 29 0a 4e 65 77 | 73 67 72 6f 75 70 73 3a |ler).New|sgroups:|
|000000a0| 20 6e 65 74 2e 73 6f 75 | 72 63 65 73 0a 53 75 62 | net.sou|rces.Sub|
|000000b0| 6a 65 63 74 3a 20 4c 69 | 61 6e 67 2d 42 61 72 73 |ject: Li|ang-Bars|
|000000c0| 6b 79 20 50 6f 6c 79 67 | 6f 6e 20 43 6c 69 70 70 |ky Polyg|on Clipp|
|000000d0| 69 6e 67 20 28 32 20 43 | 20 76 65 72 73 69 6f 6e |ing (2 C| version|
|000000e0| 73 29 0a 4d 65 73 73 61 | 67 65 2d 49 44 3a 20 3c |s).Messa|ge-ID: <|
|000000f0| 32 37 30 40 6e 61 75 63 | 73 65 2e 55 55 43 50 3e |270@nauc|se.UUCP>|
|00000100| 0a 44 61 74 65 3a 20 32 | 33 20 4d 61 72 20 38 37 |.Date: 2|3 Mar 87|
|00000110| 20 31 38 3a 33 30 3a 32 | 31 20 47 4d 54 0a 4f 72 | 18:30:2|1 GMT.Or|
|00000120| 67 61 6e 69 7a 61 74 69 | 6f 6e 3a 20 4e 6f 72 74 |ganizati|on: Nort|
|00000130| 68 65 72 6e 20 41 72 69 | 7a 6f 6e 61 20 55 6e 69 |hern Ari|zona Uni|
|00000140| 76 65 72 73 69 74 79 2c | 20 46 6c 61 67 73 74 61 |versity,| Flagsta|
|00000150| 66 66 2c 20 41 72 69 7a | 6f 6e 61 0a 4c 69 6e 65 |ff, Ariz|ona.Line|
|00000160| 73 3a 20 32 39 34 0a 0a | 54 68 65 20 66 6f 6c 6c |s: 294..|The foll|
|00000170| 6f 77 69 6e 67 20 43 20 | 66 75 6e 63 74 69 6f 6e |owing C |function|
|00000180| 73 20 61 72 65 20 74 77 | 6f 20 76 65 72 73 69 6f |s are tw|o versio|
|00000190| 6e 73 20 6f 66 20 74 68 | 65 20 4c 69 61 6e 67 2d |ns of th|e Liang-|
|000001a0| 42 61 72 73 6b 79 0a 70 | 6f 6c 79 67 6f 6e 20 63 |Barsky.p|olygon c|
|000001b0| 6c 69 70 70 69 6e 67 20 | 61 6c 67 6f 72 69 74 68 |lipping |algorith|
|000001c0| 6d 2e 20 20 54 68 65 20 | 66 69 72 73 74 20 69 73 |m. The |first is|
|000001d0| 20 64 69 72 65 63 74 6c | 79 20 66 72 6f 6d 20 74 | directl|y from t|
|000001e0| 68 65 69 72 0a 70 61 70 | 65 72 20 69 6e 20 43 41 |heir.pap|er in CA|
|000001f0| 43 4d 20 28 61 6e 64 20 | 74 68 65 20 63 6f 72 72 |CM (and |the corr|
|00000200| 69 67 65 6e 64 61 20 74 | 68 61 74 20 66 6f 6c 6c |igenda t|hat foll|
|00000210| 6f 77 65 64 29 2e 20 20 | 54 68 65 20 73 65 63 6f |owed). |The seco|
|00000220| 6e 64 0a 69 73 20 73 6c | 69 67 68 74 6c 79 20 6d |nd.is sl|ightly m|
|00000230| 6f 64 69 66 69 65 64 20 | 61 6e 64 20 73 65 65 6d |odified |and seem|
|00000240| 73 20 74 6f 20 72 75 6e | 20 61 62 6f 75 74 20 36 |s to run| about 6|
|00000250| 25 20 71 75 69 63 6b 65 | 72 20 28 61 73 73 75 6d |% quicke|r (assum|
|00000260| 69 6e 67 0a 66 6c 6f 61 | 74 69 6e 67 20 70 6f 69 |ing.floa|ting poi|
|00000270| 6e 74 20 68 61 72 64 77 | 61 72 65 29 2e 0a 0a 23 |nt hardw|are)...#|
|00000280| 5f 5f 5f 5f 5f 5f 5f 5f | 5f 5f 5f 63 75 74 20 6d |________|___cut m|
|00000290| 61 72 6b 0a 0a 2f 2a 20 | 4c 69 61 6e 67 2d 42 61 |ark../* |Liang-Ba|
|000002a0| 72 73 6b 79 20 50 6f 6c | 79 67 6f 6e 20 43 6c 69 |rsky Pol|ygon Cli|
|000002b0| 70 70 69 6e 67 20 5b 43 | 41 43 4d 2c 20 56 6f 6c |pping [C|ACM, Vol|
|000002c0| 20 32 36 20 28 4e 6f 76 | 2c 20 31 39 38 33 29 5d | 26 (Nov|, 1983)]|
|000002d0| 0a 20 2a 20 20 20 20 28 | 77 69 74 68 20 63 6f 72 |. * (|with cor|
|000002e0| 72 65 63 74 69 6f 6e 73 | 20 66 72 6f 6d 20 5b 43 |rections| from [C|
|000002f0| 41 43 4d 20 28 41 70 72 | 69 6c 2c 20 31 39 38 34 |ACM (Apr|il, 1984|
|00000300| 29 5d 29 0a 20 2a 2f 0a | 0a 2f 2a 20 20 20 4e 6f |)]). */.|./* No|
|00000310| 74 65 20 74 68 61 74 20 | 74 68 69 73 20 61 73 73 |te that |this ass|
|00000320| 75 6d 65 73 20 74 68 65 | 20 6c 61 73 74 20 70 6f |umes the| last po|
|00000330| 69 6e 74 20 3d 3d 20 74 | 68 65 20 66 69 72 73 74 |int == t|he first|
|00000340| 20 69 6e 20 74 68 65 0a | 20 2a 20 20 20 20 70 6f | in the.| * po|
|00000350| 6c 79 67 6f 6e 20 72 65 | 70 72 65 73 65 6e 74 61 |lygon re|presenta|
|00000360| 74 69 6f 6e 20 74 68 65 | 20 63 6f 64 65 20 69 6e |tion the| code in|
|00000370| 20 74 68 65 20 61 72 74 | 69 63 6c 65 20 61 64 64 | the art|icle add|
|00000380| 73 20 74 68 65 0a 20 2a | 20 20 20 20 6c 61 73 74 |s the. *| last|
|00000390| 20 70 6f 69 6e 74 20 69 | 6e 20 61 74 20 74 68 65 | point i|n at the|
|000003a0| 20 73 74 61 72 74 20 6f | 66 20 74 68 65 20 61 6c | start o|f the al|
|000003b0| 67 6f 72 69 74 68 6d 20 | 28 70 72 6f 62 61 62 6c |gorithm |(probabl|
|000003c0| 79 0a 20 2a 20 20 20 20 | 61 20 62 65 74 74 65 72 |y. * |a better|
|000003d0| 20 61 70 70 72 6f 61 63 | 68 29 2e 0a 20 2a 2f 0a | approac|h).. */.|
|000003e0| 0a 09 2f 2a 20 54 68 65 | 20 66 6f 6c 6c 6f 77 69 |../* The| followi|
|000003f0| 6e 67 20 69 6e 63 6c 75 | 64 65 20 62 72 69 6e 67 |ng inclu|de bring|
|00000400| 73 20 69 6e 20 73 6f 6d | 65 20 6d 61 63 72 6f 20 |s in som|e macro |
|00000410| 64 65 66 69 6e 69 74 69 | 6f 6e 73 0a 09 20 2a 20 |definiti|ons.. * |
|00000420| 66 6f 72 20 61 63 63 65 | 73 73 69 6e 67 20 69 6e |for acce|ssing in|
|00000430| 66 6f 72 6d 61 74 69 6f | 6e 20 61 62 6f 75 74 20 |formatio|n about |
|00000440| 61 20 70 6f 6c 79 67 6f | 6e 3a 0a 09 20 2a 0a 09 |a polygo|n:.. *..|
|00000450| 20 2a 20 20 20 4e 50 4e | 54 53 28 29 20 20 69 73 | * NPN|TS() is|
|00000460| 20 74 68 65 20 6e 75 6d | 62 65 72 20 6f 66 20 76 | the num|ber of v|
|00000470| 65 72 74 69 63 65 73 20 | 69 6e 20 74 68 65 20 70 |ertices |in the p|
|00000480| 6f 6c 79 67 6f 6e 0a 09 | 20 2a 20 20 20 20 20 20 |olygon..| * |
|00000490| 20 20 20 20 20 20 28 63 | 6f 75 6e 74 69 6e 67 20 | (c|ounting |
|000004a0| 66 69 72 73 74 20 70 6f | 69 6e 74 20 74 77 69 63 |first po|int twic|
|000004b0| 65 29 0a 20 20 20 20 20 | 20 20 20 20 2a 0a 20 20 |e). | *. |
|000004c0| 20 20 20 20 20 20 20 2a | 20 20 20 47 45 54 50 4e | *| GETPN|
|000004d0| 54 28 29 20 61 63 63 65 | 73 73 65 73 20 74 68 65 |T() acce|sses the|
|000004e0| 20 73 70 65 63 69 66 69 | 65 64 20 70 6f 69 6e 74 | specifi|ed point|
|000004f0| 20 6f 75 74 20 6f 66 20 | 74 68 65 0a 09 20 2a 20 | out of |the.. * |
|00000500| 20 20 20 09 20 20 20 20 | 20 20 70 6f 6c 79 67 6f | . | polygo|
|00000510| 6e 2e 0a 09 20 2a 0a 09 | 20 2a 20 20 20 58 43 4f |n... *..| * XCO|
|00000520| 4f 52 44 2f 59 43 4f 4f | 52 44 28 29 20 61 63 63 |ORD/YCOO|RD() acc|
|00000530| 65 73 73 20 74 68 65 20 | 78 28 79 29 2d 63 6f 6f |ess the |x(y)-coo|
|00000540| 72 64 69 6e 61 74 65 20 | 69 6e 20 61 20 70 6f 69 |rdinate |in a poi|
|00000550| 6e 74 0a 09 20 2a 0a 09 | 20 2a 20 4d 61 63 72 6f |nt.. *..| * Macro|
|00000560| 73 20 77 65 72 65 20 75 | 73 65 64 20 62 65 63 61 |s were u|sed beca|
|00000570| 75 73 65 20 74 68 69 73 | 20 63 6f 64 65 20 6d 75 |use this| code mu|
|00000580| 73 74 20 75 6c 74 69 6d | 61 74 65 6c 79 20 74 69 |st ultim|ately ti|
|00000590| 65 0a 09 20 2a 20 20 69 | 6e 74 6f 20 6d 79 20 77 |e.. * i|nto my w|
|000005a0| 69 66 65 27 73 20 61 6e | 69 6d 61 74 69 6f 6e 20 |ife's an|imation |
|000005b0| 70 61 63 6b 61 67 65 2c | 20 61 6e 64 20 49 20 64 |package,| and I d|
|000005c0| 6f 6e 27 74 20 6b 6e 6f | 77 0a 09 20 2a 20 20 68 |on't kno|w.. * h|
|000005d0| 6f 77 20 73 68 65 20 69 | 73 20 67 6f 69 6e 67 20 |ow she i|s going |
|000005e0| 74 6f 20 72 65 70 72 65 | 73 65 6e 74 20 70 6f 6c |to repre|sent pol|
|000005f0| 79 67 6f 6e 73 20 79 65 | 74 2e 0a 09 20 2a 2f 0a |ygons ye|t... */.|
|00000600| 0a 23 20 69 6e 63 6c 75 | 64 65 20 22 70 6c 6e 2e |.# inclu|de "pln.|
|00000610| 68 22 0a 0a 23 20 64 65 | 66 69 6e 65 20 49 4e 46 |h"..# de|fine INF|
|00000620| 49 4e 49 54 59 09 28 31 | 2e 30 65 2b 33 30 29 0a |INITY.(1|.0e+30).|
|00000630| 0a 09 2f 2a 20 61 64 64 | 20 61 20 6e 65 77 20 76 |../* add| a new v|
|00000640| 65 72 74 65 78 20 69 6e | 74 6f 20 74 68 65 20 6f |ertex in|to the o|
|00000650| 75 74 70 75 74 20 70 6f | 6c 79 67 6f 6e 20 2a 2f |utput po|lygon */|
|00000660| 0a 0a 23 20 64 65 66 69 | 6e 65 20 61 64 64 28 78 |..# defi|ne add(x|
|00000670| 2c 79 29 20 7b 5c 0a 20 | 20 20 20 20 20 20 20 20 |,y) {\. | |
|00000680| 20 20 20 20 20 20 20 20 | 20 20 58 43 4f 4f 52 44 | | XCOORD|
|00000690| 28 47 45 54 50 4e 54 28 | 6e 70 6f 6c 79 2c 6e 70 |(GETPNT(|npoly,np|
|000006a0| 6e 74 29 29 20 3d 20 78 | 3b 5c 0a 20 20 20 20 20 |nt)) = x|;\. |
|000006b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 59 43 | | YC|
|000006c0| 4f 4f 52 44 28 47 45 54 | 50 4e 54 28 6e 70 6f 6c |OORD(GET|PNT(npol|
|000006d0| 79 2c 6e 70 6e 74 29 29 | 20 3d 20 79 3b 5c 0a 20 |y,npnt))| = y;\. |
|000006e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000006f0| 20 20 2b 2b 6e 70 6e 74 | 3b 5c 0a 20 20 20 20 20 | ++npnt|;\. |
|00000700| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 7d 0a 0a | | }..|
|00000710| 09 2f 2a 20 77 69 6e 64 | 6f 77 20 62 6f 75 6e 64 |./* wind|ow bound|
|00000720| 73 20 28 78 6c 65 66 74 | 2c 79 62 6f 74 74 6f 6d |s (xleft|,ybottom|
|00000730| 29 2c 20 28 78 72 69 67 | 68 74 2c 79 74 6f 70 29 |), (xrig|ht,ytop)|
|00000740| 20 2a 2f 0a 65 78 74 65 | 72 6e 20 66 6c 6f 61 74 | */.exte|rn float|
|00000750| 20 77 78 31 2c 77 79 31 | 2c 20 20 77 78 32 2c 77 | wx1,wy1|, wx2,w|
|00000760| 79 32 3b 0a 0a 09 2f 2a | 20 54 68 65 20 4c 69 61 |y2;.../*| The Lia|
|00000770| 6e 67 2d 42 61 72 73 6b | 79 20 50 6f 6c 79 67 6f |ng-Barsk|y Polygo|
|00000780| 6e 20 43 6c 69 70 70 69 | 6e 67 20 41 6c 67 6f 72 |n Clippi|ng Algor|
|00000790| 69 74 68 6d 20 2a 2f 0a | 66 63 6c 69 70 28 6f 70 |ithm */.|fclip(op|
|000007a0| 6f 6c 79 2c 6e 70 6f 6c | 79 29 0a 20 20 20 50 4c |oly,npol|y). PL|
|000007b0| 4e 20 2a 6f 70 6f 6c 79 | 2c 20 2a 6e 70 6f 6c 79 |N *opoly|, *npoly|
|000007c0| 3b 0a 0a 20 20 20 7b 0a | 20 20 20 72 65 67 69 73 |;.. {.| regis|
|000007d0| 74 65 72 20 69 6e 74 20 | 69 2c 20 6e 70 6e 74 3b |ter int |i, npnt;|
|000007e0| 0a 20 20 20 66 6c 6f 61 | 74 20 64 65 6c 74 61 78 |. floa|t deltax|
|000007f0| 2c 20 64 65 6c 74 61 79 | 2c 20 78 69 6e 2c 78 6f |, deltay|, xin,xo|
|00000800| 75 74 2c 20 20 79 69 6e | 2c 79 6f 75 74 3b 0a 20 |ut, yin|,yout;. |
|00000810| 20 20 66 6c 6f 61 74 20 | 74 69 6e 78 2c 74 69 6e | float |tinx,tin|
|00000820| 79 2c 20 20 74 6f 75 74 | 78 2c 74 6f 75 74 79 2c |y, tout|x,touty,|
|00000830| 20 20 74 69 6e 31 2c 20 | 74 69 6e 32 2c 20 20 74 | tin1, |tin2, t|
|00000840| 6f 75 74 31 2c 74 6f 75 | 74 32 3b 0a 20 20 20 66 |out1,tou|t2;. f|
|00000850| 6c 6f 61 74 20 78 31 2c | 79 31 2c 20 78 32 2c 79 |loat x1,|y1, x2,y|
|00000860| 32 3b 0a 20 20 20 0a 20 | 20 20 6e 70 6e 74 20 3d |2;. . | npnt =|
|00000870| 20 30 3b 0a 0a 20 20 20 | 66 6f 72 20 28 69 20 3d | 0;.. |for (i =|
|00000880| 20 30 3b 20 69 20 3c 20 | 4e 50 4e 54 53 28 6f 70 | 0; i < |NPNTS(op|
|00000890| 6f 6c 79 29 2d 31 3b 20 | 2b 2b 69 29 20 7b 0a 0a |oly)-1; |++i) {..|
|000008a0| 20 20 20 20 20 20 78 31 | 20 3d 20 58 43 4f 4f 52 | x1| = XCOOR|
|000008b0| 44 28 47 45 54 50 4e 54 | 28 6f 70 6f 6c 79 2c 69 |D(GETPNT|(opoly,i|
|000008c0| 29 29 3b 0a 20 20 20 20 | 20 20 79 31 20 3d 20 59 |));. | y1 = Y|
|000008d0| 43 4f 4f 52 44 28 47 45 | 54 50 4e 54 28 6f 70 6f |COORD(GE|TPNT(opo|
|000008e0| 6c 79 2c 69 29 29 3b 0a | 20 20 20 20 20 20 78 32 |ly,i));.| x2|
|000008f0| 20 3d 20 58 43 4f 4f 52 | 44 28 47 45 54 50 4e 54 | = XCOOR|D(GETPNT|
|00000900| 28 6f 70 6f 6c 79 2c 69 | 2b 31 29 29 3b 0a 20 20 |(opoly,i|+1));. |
|00000910| 20 20 20 20 79 32 20 3d | 20 59 43 4f 4f 52 44 28 | y2 =| YCOORD(|
|00000920| 47 45 54 50 4e 54 28 6f | 70 6f 6c 79 2c 69 2b 31 |GETPNT(o|poly,i+1|
|00000930| 29 29 3b 0a 0a 20 20 20 | 20 20 20 64 65 6c 74 61 |));.. | delta|
|00000940| 78 20 3d 20 78 32 2d 78 | 31 3b 0a 20 20 20 20 20 |x = x2-x|1;. |
|00000950| 20 64 65 6c 74 61 79 20 | 3d 20 79 32 2d 79 31 3b | deltay |= y2-y1;|
|00000960| 0a 0a 20 20 20 20 20 20 | 69 66 20 28 64 65 6c 74 |.. |if (delt|
|00000970| 61 78 20 3e 20 30 20 7c | 7c 20 28 64 65 6c 74 61 |ax > 0 ||| (delta|
|00000980| 78 20 3d 3d 20 30 20 26 | 26 20 78 31 3e 77 78 32 |x == 0 &|& x1>wx2|
|00000990| 29 29 20 7b 20 2f 2a 20 | 20 70 6f 69 6e 74 73 20 |)) { /* | points |
|000009a0| 74 6f 20 72 69 67 68 74 | 20 2a 2f 0a 20 20 20 20 |to right| */. |
|000009b0| 20 20 20 20 20 78 69 6e | 20 3d 20 77 78 31 3b 0a | xin| = wx1;.|
|000009c0| 20 20 20 20 20 20 20 20 | 20 78 6f 75 74 20 3d 20 | | xout = |
|000009d0| 77 78 32 3b 0a 20 20 20 | 20 20 20 20 20 20 7d 0a |wx2;. | }.|
|000009e0| 20 20 20 20 20 20 65 6c | 73 65 20 7b 0a 20 20 20 | el|se {. |
|000009f0| 20 20 20 20 20 20 78 69 | 6e 20 3d 20 77 78 32 3b | xi|n = wx2;|
|00000a00| 0a 20 20 20 20 20 20 20 | 20 20 78 6f 75 74 20 3d |. | xout =|
|00000a10| 20 77 78 31 3b 0a 20 20 | 20 20 20 20 20 20 20 7d | wx1;. | }|
|00000a20| 0a 20 20 20 20 20 20 69 | 66 20 28 64 65 6c 74 61 |. i|f (delta|
|00000a30| 79 20 3e 20 30 20 7c 7c | 20 28 64 65 6c 74 61 79 |y > 0 ||| (deltay|
|00000a40| 20 3d 3d 20 30 20 26 26 | 20 79 31 3e 77 79 32 29 | == 0 &&| y1>wy2)|
|00000a50| 29 20 7b 20 2f 2a 20 20 | 70 6f 69 6e 74 73 20 75 |) { /* |points u|
|00000a60| 70 20 2a 2f 0a 20 20 20 | 20 20 20 20 20 20 79 69 |p */. | yi|
|00000a70| 6e 20 3d 20 77 79 31 3b | 0a 20 20 20 20 20 20 20 |n = wy1;|. |
|00000a80| 20 20 79 6f 75 74 20 3d | 20 77 79 32 3b 0a 20 20 | yout =| wy2;. |
|00000a90| 20 20 20 20 20 20 20 7d | 0a 20 20 20 20 20 20 65 | }|. e|
|00000aa0| 6c 73 65 20 7b 0a 20 20 | 20 20 20 20 20 20 20 79 |lse {. | y|
|00000ab0| 69 6e 20 3d 20 77 79 32 | 3b 0a 20 20 20 20 20 20 |in = wy2|;. |
|00000ac0| 20 20 20 79 6f 75 74 20 | 3d 20 77 79 31 3b 0a 20 | yout |= wy1;. |
|00000ad0| 20 20 20 20 20 20 20 20 | 7d 0a 0a 20 20 20 20 20 | |}.. |
|00000ae0| 20 74 69 6e 78 20 3d 20 | 28 64 65 6c 74 61 78 20 | tinx = |(deltax |
|00000af0| 21 3d 20 30 29 20 3f 20 | 28 28 78 69 6e 20 2d 20 |!= 0) ? |((xin - |
|00000b00| 78 31 29 2f 64 65 6c 74 | 61 78 29 20 3a 20 2d 49 |x1)/delt|ax) : -I|
|00000b10| 4e 46 49 4e 49 54 59 20 | 3b 0a 20 20 20 20 20 20 |NFINITY |;. |
|00000b20| 74 69 6e 79 20 3d 20 28 | 64 65 6c 74 61 79 20 21 |tiny = (|deltay !|
|00000b30| 3d 20 30 29 20 3f 20 28 | 28 79 69 6e 20 2d 20 79 |= 0) ? (|(yin - y|
|00000b40| 31 29 2f 64 65 6c 74 61 | 79 29 20 3a 20 2d 49 4e |1)/delta|y) : -IN|
|00000b50| 46 49 4e 49 54 59 20 3b | 0a 20 20 20 0a 20 20 20 |FINITY ;|. . |
|00000b60| 20 20 20 69 66 20 28 74 | 69 6e 78 20 3c 20 74 69 | if (t|inx < ti|
|00000b70| 6e 79 29 20 7b 09 2f 2a | 20 68 69 74 73 20 78 20 |ny) {./*| hits x |
|00000b80| 66 69 72 73 74 20 2a 2f | 0a 20 20 20 20 20 20 20 |first */|. |
|00000b90| 20 20 74 69 6e 31 20 3d | 20 74 69 6e 78 3b 0a 20 | tin1 =| tinx;. |
|00000ba0| 20 20 20 20 20 20 20 20 | 74 69 6e 32 20 3d 20 74 | |tin2 = t|
|00000bb0| 69 6e 79 3b 0a 20 20 20 | 20 20 20 20 20 20 7d 0a |iny;. | }.|
|00000bc0| 20 20 20 20 20 20 65 6c | 73 65 09 09 09 2f 2a 20 | el|se.../* |
|00000bd0| 68 69 74 73 20 79 20 66 | 69 72 73 74 20 2a 2f 0a |hits y f|irst */.|
|00000be0| 20 20 20 20 20 20 20 20 | 20 7b 0a 20 20 20 20 20 | | {. |
|00000bf0| 20 20 20 20 74 69 6e 31 | 20 3d 20 74 69 6e 79 3b | tin1| = tiny;|
|00000c00| 0a 20 20 20 20 20 20 20 | 20 20 74 69 6e 32 20 3d |. | tin2 =|
|00000c10| 20 74 69 6e 78 3b 0a 20 | 20 20 20 20 20 20 20 20 | tinx;. | |
|00000c20| 7d 0a 0a 20 20 20 20 20 | 20 69 66 20 28 31 20 3e |}.. | if (1 >|
|00000c30| 3d 20 74 69 6e 31 29 20 | 7b 0a 20 20 20 20 20 20 |= tin1) |{. |
|00000c40| 20 20 20 69 66 20 28 30 | 20 3c 20 74 69 6e 31 29 | if (0| < tin1)|
|00000c50| 20 7b 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 61 | {. | a|
|00000c60| 64 64 28 78 69 6e 2c 79 | 69 6e 29 3b 0a 20 20 20 |dd(xin,y|in);. |
|00000c70| 20 20 20 20 20 20 20 20 | 20 7d 0a 20 20 20 20 20 | | }. |
|00000c80| 20 20 20 20 69 66 20 28 | 31 20 3e 3d 20 74 69 6e | if (|1 >= tin|
|00000c90| 32 29 20 7b 0a 09 20 20 | 20 20 69 66 20 28 64 65 |2) {.. | if (de|
|00000ca0| 6c 74 61 78 20 21 3d 20 | 30 29 20 74 6f 75 74 78 |ltax != |0) toutx|
|00000cb0| 20 3d 20 28 78 6f 75 74 | 2d 78 31 29 2f 64 65 6c | = (xout|-x1)/del|
|00000cc0| 74 61 78 3b 0a 09 20 20 | 20 20 65 6c 73 65 20 7b |tax;.. | else {|
|00000cd0| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00000ce0| 69 66 20 28 77 78 31 20 | 3c 3d 20 78 31 20 26 26 |if (wx1 |<= x1 &&|
|00000cf0| 20 78 31 20 3c 3d 20 77 | 78 32 29 20 74 6f 75 74 | x1 <= w|x2) tout|
|00000d00| 78 20 3d 20 49 4e 46 49 | 4e 49 54 59 3b 0a 20 20 |x = INFI|NITY;. |
|00000d10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 65 6c 73 | | els|
|00000d20| 65 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |e | |
|00000d30| 20 20 20 20 20 20 20 20 | 20 74 6f 75 74 78 20 3d | | toutx =|
|00000d40| 20 2d 49 4e 46 49 4e 49 | 54 59 3b 0a 09 20 20 20 | -INFINI|TY;.. |
|00000d50| 20 20 20 20 7d 0a 09 20 | 20 20 20 69 66 20 28 64 | }.. | if (d|
|00000d60| 65 6c 74 61 79 20 21 3d | 20 30 29 20 74 6f 75 74 |eltay !=| 0) tout|
|00000d70| 79 20 3d 20 28 79 6f 75 | 74 2d 79 31 29 2f 64 65 |y = (you|t-y1)/de|
|00000d80| 6c 74 61 79 3b 0a 09 20 | 20 20 20 65 6c 73 65 20 |ltay;.. | else |
|00000d90| 7b 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |{. | |
|00000da0| 20 69 66 20 28 77 79 31 | 20 3c 3d 20 79 31 20 26 | if (wy1| <= y1 &|
|00000db0| 26 20 79 31 20 3c 3d 20 | 77 79 32 29 20 74 6f 75 |& y1 <= |wy2) tou|
|00000dc0| 74 79 20 3d 20 49 4e 46 | 49 4e 49 54 59 3b 0a 20 |ty = INF|INITY;. |
|00000dd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 65 6c | | el|
|00000de0| 73 65 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |se | |
|00000df0| 20 20 20 20 20 20 20 20 | 20 20 74 6f 75 74 79 20 | | touty |
|00000e00| 3d 20 2d 49 4e 46 49 4e | 49 54 59 3b 0a 09 20 20 |= -INFIN|ITY;.. |
|00000e10| 20 20 20 20 20 7d 0a 0a | 09 20 20 20 20 74 6f 75 | }..|. tou|
|00000e20| 74 31 20 3d 20 28 74 6f | 75 74 78 20 3c 20 74 6f |t1 = (to|utx < to|
|00000e30| 75 74 79 29 20 3f 20 74 | 6f 75 74 78 20 3a 20 74 |uty) ? t|outx : t|
|00000e40| 6f 75 74 79 20 3b 0a 20 | 20 20 0a 20 20 20 20 20 |outy ;. | . |
|00000e50| 20 20 20 20 20 20 20 69 | 66 20 28 30 20 3c 20 74 | i|f (0 < t|
|00000e60| 69 6e 32 20 7c 7c 20 30 | 20 3c 20 74 6f 75 74 31 |in2 || 0| < tout1|
|00000e70| 29 20 7b 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 |) {. | |
|00000e80| 20 20 20 69 66 20 28 74 | 69 6e 32 20 3c 3d 20 74 | if (t|in2 <= t|
|00000e90| 6f 75 74 31 29 20 7b 0a | 20 20 20 20 20 20 20 20 |out1) {.| |
|00000ea0| 20 20 20 20 20 20 20 20 | 20 20 69 66 20 28 30 20 | | if (0 |
|00000eb0| 3c 20 74 69 6e 32 29 20 | 7b 0a 20 20 20 20 20 20 |< tin2) |{. |
|00000ec0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 69 | | i|
|00000ed0| 66 20 28 74 69 6e 78 20 | 3e 20 74 69 6e 79 29 20 |f (tinx |> tiny) |
|00000ee0| 7b 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |{. | |
|00000ef0| 20 20 20 20 20 20 20 20 | 20 20 61 64 64 20 28 78 | | add (x|
|00000f00| 69 6e 2c 20 79 31 2b 74 | 69 6e 78 2a 64 65 6c 74 |in, y1+t|inx*delt|
|00000f10| 61 79 29 3b 0a 20 20 20 | 20 20 20 20 20 20 20 20 |ay);. | |
|00000f20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 7d 0a 20 | | }. |
|00000f30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000f40| 20 20 20 20 65 6c 73 65 | 20 7b 0a 20 20 20 20 20 | else| {. |
|00000f50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000f60| 20 20 20 61 64 64 20 28 | 78 31 20 2b 20 74 69 6e | add (|x1 + tin|
|00000f70| 79 2a 64 65 6c 74 61 78 | 2c 20 79 69 6e 29 3b 0a |y*deltax|, yin);.|
|00000f80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000f90| 20 20 20 20 20 20 20 20 | 7d 0a 20 20 20 20 20 20 | |}. |
|00000fa0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 7d | | }|
|00000fb0| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00000fc0| 20 20 20 69 66 20 28 31 | 20 3e 20 74 6f 75 74 31 | if (1| > tout1|
|00000fd0| 29 20 7b 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 |) {. | |
|00000fe0| 20 20 20 20 20 20 20 20 | 20 69 66 20 28 74 6f 75 | | if (tou|
|00000ff0| 74 78 20 3c 20 74 6f 75 | 74 79 29 20 7b 0a 20 20 |tx < tou|ty) {. |
|00001000| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001010| 20 20 20 20 20 20 61 64 | 64 20 28 78 6f 75 74 2c | ad|d (xout,|
|00001020| 20 79 31 2b 74 6f 75 74 | 78 2a 64 65 6c 74 61 79 | y1+tout|x*deltay|
|00001030| 29 3b 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |);. | |
|00001040| 20 20 20 20 20 20 20 20 | 20 20 20 7d 0a 20 20 20 | | }. |
|00001050| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001060| 20 20 65 6c 73 65 20 7b | 0a 20 20 20 20 20 20 20 | else {|. |
|00001070| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001080| 20 61 64 64 20 28 78 31 | 20 2b 20 74 6f 75 74 79 | add (x1| + touty|
|00001090| 2a 64 65 6c 74 61 78 2c | 20 79 6f 75 74 29 3b 0a |*deltax,| yout);.|
|000010a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000010b0| 20 20 20 20 20 20 20 20 | 7d 0a 20 20 20 20 20 20 | |}. |
|000010c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 7d | | }|
|000010d0| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|000010e0| 20 20 20 65 6c 73 65 20 | 7b 0a 20 20 20 20 20 20 | else |{. |
|000010f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 61 | | a|
|00001100| 64 64 20 28 78 32 2c 79 | 32 29 3b 0a 20 20 20 20 |dd (x2,y|2);. |
|00001110| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001120| 20 7d 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001130| 20 20 20 20 20 7d 0a 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001140| 20 20 20 20 20 20 65 6c | 73 65 20 7b 0a 20 20 20 | el|se {. |
|00001150| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 69 | | i|
|00001160| 66 20 28 74 69 6e 78 20 | 3e 20 74 69 6e 79 29 20 |f (tinx |> tiny) |
|00001170| 7b 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |{. | |
|00001180| 20 20 20 20 20 20 20 61 | 64 64 20 28 78 69 6e 2c | a|dd (xin,|
|00001190| 20 79 6f 75 74 29 3b 0a | 20 20 20 20 20 20 20 20 | yout);.| |
|000011a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 7d 0a 20 | | }. |
|000011b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000011c0| 20 65 6c 73 65 20 7b 0a | 20 20 20 20 20 20 20 20 | else {.| |
|000011d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 61 64 64 | | add|
|000011e0| 20 28 78 6f 75 74 2c 20 | 79 69 6e 29 3b 0a 20 20 | (xout, |yin);. |
|000011f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001200| 20 20 20 7d 0a 20 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001210| 20 20 20 20 20 20 20 7d | 0a 20 20 20 20 20 20 20 | }|. |
|00001220| 20 20 20 20 20 20 20 20 | 7d 0a 20 20 20 20 20 20 | |}. |
|00001230| 20 20 20 20 20 20 7d 0a | 20 20 20 20 20 20 20 20 | }.| |
|00001240| 20 7d 0a 20 20 20 20 20 | 20 7d 0a 0a 20 20 20 69 | }. | }.. i|
|00001250| 66 20 28 6e 70 6e 74 29 | 20 7b 0a 20 20 20 20 20 |f (npnt)| {. |
|00001260| 20 61 64 64 28 58 43 4f | 4f 52 44 28 47 45 54 50 | add(XCO|ORD(GETP|
|00001270| 4e 54 28 6e 70 6f 6c 79 | 2c 30 29 29 2c 59 43 4f |NT(npoly|,0)),YCO|
|00001280| 4f 52 44 28 47 45 54 50 | 4e 54 28 6e 70 6f 6c 79 |ORD(GETP|NT(npoly|
|00001290| 2c 30 29 29 29 3b 0a 20 | 20 20 20 20 20 7d 0a 20 |,0)));. | }. |
|000012a0| 20 20 4e 50 4e 54 53 28 | 6e 70 6f 6c 79 29 20 3d | NPNTS(|npoly) =|
|000012b0| 20 6e 70 6e 74 3b 0a 20 | 20 20 7d 0a 0a 23 5f 5f | npnt;. | }..#__|
|000012c0| 5f 5f 5f 5f 5f 5f 5f 5f | 5f 20 63 75 74 20 6d 61 |________|_ cut ma|
|000012d0| 72 6b 0a 0a 2f 2a 20 4d | 6f 64 69 66 69 65 64 20 |rk../* M|odified |
|000012e0| 4c 69 61 6e 67 2d 42 61 | 72 73 6b 79 20 50 6f 6c |Liang-Ba|rsky Pol|
|000012f0| 79 67 6f 6e 20 43 6c 69 | 70 70 69 6e 67 20 5b 43 |ygon Cli|pping [C|
|00001300| 41 43 4d 2c 20 56 6f 6c | 20 32 36 20 28 4e 6f 76 |ACM, Vol| 26 (Nov|
|00001310| 2c 20 31 39 38 33 29 5d | 20 2a 2f 0a 0a 2f 2a 20 |, 1983)]| */../* |
|00001320| 73 65 65 20 74 68 65 20 | 63 6f 6d 6d 65 6e 74 73 |see the |comments|
|00001330| 20 61 74 20 74 68 65 20 | 73 74 61 72 74 20 6f 66 | at the |start of|
|00001340| 20 74 68 65 20 75 6e 6d | 6f 64 69 66 69 65 64 20 | the unm|odified |
|00001350| 76 65 72 73 69 6f 6e 20 | 66 6f 72 20 6d 6f 72 65 |version |for more|
|00001360| 0a 20 2a 20 64 65 74 61 | 69 6c 73 2e 0a 20 2a 2f |. * deta|ils.. */|
|00001370| 0a 0a 23 20 69 6e 63 6c | 75 64 65 20 22 70 6c 6e |..# incl|ude "pln|
|00001380| 2e 68 22 0a 0a 23 20 64 | 65 66 69 6e 65 20 49 4e |.h"..# d|efine IN|
|00001390| 46 49 4e 49 54 59 09 28 | 31 2e 30 65 2b 33 30 29 |FINITY.(|1.0e+30)|
|000013a0| 0a 23 20 64 65 66 69 6e | 65 20 4e 45 41 52 5a 45 |.# defin|e NEARZE|
|000013b0| 52 4f 09 28 31 2e 30 65 | 2d 33 30 29 09 2f 2a 20 |RO.(1.0e|-30)./* |
|000013c0| 31 2f 49 4e 46 49 4e 49 | 54 59 20 2a 2f 0a 0a 23 |1/INFINI|TY */..#|
|000013d0| 20 64 65 66 69 6e 65 20 | 61 64 64 28 78 2c 79 29 | define |add(x,y)|
|000013e0| 20 7b 5c 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 | {\. | |
|000013f0| 20 20 20 20 20 20 20 58 | 43 4f 4f 52 44 28 47 45 | X|COORD(GE|
|00001400| 54 50 4e 54 28 6e 70 6f | 6c 79 2c 6e 70 6e 74 29 |TPNT(npo|ly,npnt)|
|00001410| 29 20 3d 20 78 3b 5c 0a | 20 20 20 20 20 20 20 20 |) = x;\.| |
|00001420| 20 20 20 20 20 20 20 20 | 20 20 20 59 43 4f 4f 52 | | YCOOR|
|00001430| 44 28 47 45 54 50 4e 54 | 28 6e 70 6f 6c 79 2c 6e |D(GETPNT|(npoly,n|
|00001440| 70 6e 74 29 29 20 3d 20 | 79 3b 5c 0a 20 20 20 20 |pnt)) = |y;\. |
|00001450| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2b | | +|
|00001460| 2b 6e 70 6e 74 3b 5c 0a | 20 20 20 20 20 20 20 20 |+npnt;\.| |
|00001470| 20 20 20 20 20 20 20 20 | 20 20 7d 0a 0a 65 78 74 | | }..ext|
|00001480| 65 72 6e 20 66 6c 6f 61 | 74 20 77 78 31 2c 77 79 |ern floa|t wx1,wy|
|00001490| 31 2c 20 20 77 78 32 2c | 77 79 32 3b 09 2f 2a 20 |1, wx2,|wy2;./* |
|000014a0| 77 69 6e 64 6f 77 20 62 | 6f 75 6e 64 61 72 69 65 |window b|oundarie|
|000014b0| 73 20 2a 2f 0a 0a 66 63 | 6c 69 70 28 6f 70 6f 6c |s */..fc|lip(opol|
|000014c0| 79 2c 6e 70 6f 6c 79 29 | 0a 20 20 20 50 4c 4e 20 |y,npoly)|. PLN |
|000014d0| 2a 6f 70 6f 6c 79 2c 20 | 2a 6e 70 6f 6c 79 3b 0a |*opoly, |*npoly;.|
|000014e0| 0a 20 20 20 7b 0a 20 20 | 20 72 65 67 69 73 74 65 |. {. | registe|
|000014f0| 72 20 69 6e 74 20 69 2c | 20 6e 70 6e 74 3b 0a 20 |r int i,| npnt;. |
|00001500| 20 20 66 6c 6f 61 74 20 | 64 65 6c 74 61 78 2c 20 | float |deltax, |
|00001510| 64 65 6c 74 61 79 2c 20 | 78 69 6e 2c 78 6f 75 74 |deltay, |xin,xout|
|00001520| 2c 20 20 79 69 6e 2c 79 | 6f 75 74 3b 0a 20 20 20 |, yin,y|out;. |
|00001530| 66 6c 6f 61 74 20 74 69 | 6e 78 2c 74 69 6e 79 2c |float ti|nx,tiny,|
|00001540| 20 20 74 6f 75 74 78 2c | 74 6f 75 74 79 2c 20 20 | toutx,|touty, |
|00001550| 74 69 6e 31 2c 20 74 69 | 6e 32 2c 20 20 74 6f 75 |tin1, ti|n2, tou|
|00001560| 74 31 2c 74 6f 75 74 32 | 3b 0a 20 20 20 66 6c 6f |t1,tout2|;. flo|
|00001570| 61 74 20 78 31 2c 79 31 | 2c 20 78 32 2c 79 32 3b |at x1,y1|, x2,y2;|
|00001580| 0a 20 20 20 0a 20 20 20 | 6e 70 6e 74 20 3d 20 30 |. . |npnt = 0|
|00001590| 3b 0a 0a 20 20 20 66 6f | 72 20 28 69 20 3d 20 30 |;.. fo|r (i = 0|
|000015a0| 3b 20 69 20 3c 20 4e 50 | 4e 54 53 28 6f 70 6f 6c |; i < NP|NTS(opol|
|000015b0| 79 29 2d 31 3b 20 2b 2b | 69 29 20 7b 0a 0a 20 20 |y)-1; ++|i) {.. |
|000015c0| 20 20 20 20 78 31 20 3d | 20 58 43 4f 4f 52 44 28 | x1 =| XCOORD(|
|000015d0| 47 45 54 50 4e 54 28 6f | 70 6f 6c 79 2c 69 29 29 |GETPNT(o|poly,i))|
|000015e0| 3b 0a 20 20 20 20 20 20 | 79 31 20 3d 20 59 43 4f |;. |y1 = YCO|
|000015f0| 4f 52 44 28 47 45 54 50 | 4e 54 28 6f 70 6f 6c 79 |ORD(GETP|NT(opoly|
|00001600| 2c 69 29 29 3b 0a 20 20 | 20 20 20 20 78 32 20 3d |,i));. | x2 =|
|00001610| 20 58 43 4f 4f 52 44 28 | 47 45 54 50 4e 54 28 6f | XCOORD(|GETPNT(o|
|00001620| 70 6f 6c 79 2c 69 2b 31 | 29 29 3b 0a 20 20 20 20 |poly,i+1|));. |
|00001630| 20 20 79 32 20 3d 20 59 | 43 4f 4f 52 44 28 47 45 | y2 = Y|COORD(GE|
|00001640| 54 50 4e 54 28 6f 70 6f | 6c 79 2c 69 2b 31 29 29 |TPNT(opo|ly,i+1))|
|00001650| 3b 0a 0a 20 20 20 20 20 | 20 64 65 6c 74 61 78 20 |;.. | deltax |
|00001660| 3d 20 78 32 2d 78 31 3b | 0a 20 20 20 20 20 20 69 |= x2-x1;|. i|
|00001670| 66 20 28 64 65 6c 74 61 | 78 20 3d 3d 20 30 29 20 |f (delta|x == 0) |
|00001680| 7b 20 2f 2a 20 62 75 6d | 70 20 6f 66 66 20 6f 66 |{ /* bum|p off of|
|00001690| 20 74 68 65 20 76 65 72 | 74 69 63 61 6c 20 2a 2f | the ver|tical */|
|000016a0| 0a 20 20 20 20 20 20 20 | 20 20 64 65 6c 74 61 78 |. | deltax|
|000016b0| 20 3d 20 28 78 31 20 3e | 20 77 78 31 29 20 3f 20 | = (x1 >| wx1) ? |
|000016c0| 2d 4e 45 41 52 5a 45 52 | 4f 20 3a 20 4e 45 41 52 |-NEARZER|O : NEAR|
|000016d0| 5a 45 52 4f 20 3b 0a 20 | 20 20 20 20 20 20 20 20 |ZERO ;. | |
|000016e0| 7d 0a 20 20 20 20 20 20 | 64 65 6c 74 61 79 20 3d |}. |deltay =|
|000016f0| 20 79 32 2d 79 31 3b 0a | 20 20 20 20 20 20 69 66 | y2-y1;.| if|
|00001700| 20 28 64 65 6c 74 61 79 | 20 3d 3d 20 30 29 20 7b | (deltay| == 0) {|
|00001710| 20 2f 2a 20 62 75 6d 70 | 20 6f 66 66 20 6f 66 20 | /* bump| off of |
|00001720| 74 68 65 20 68 6f 72 69 | 7a 6f 6e 74 61 6c 20 2a |the hori|zontal *|
|00001730| 2f 0a 20 20 20 20 20 20 | 20 20 20 64 65 6c 74 61 |/. | delta|
|00001740| 79 20 3d 20 28 79 31 20 | 3e 20 77 79 31 29 20 3f |y = (y1 |> wy1) ?|
|00001750| 20 2d 4e 45 41 52 5a 45 | 52 4f 20 3a 20 4e 45 41 | -NEARZE|RO : NEA|
|00001760| 52 5a 45 52 4f 20 3b 0a | 20 20 20 20 20 20 20 20 |RZERO ;.| |
|00001770| 20 7d 0a 0a 20 20 20 20 | 20 20 69 66 20 28 64 65 | }.. | if (de|
|00001780| 6c 74 61 78 20 3e 20 30 | 29 20 7b 09 09 2f 2a 20 |ltax > 0|) {../* |
|00001790| 20 70 6f 69 6e 74 73 20 | 74 6f 20 72 69 67 68 74 | points |to right|
|000017a0| 20 2a 2f 0a 20 20 20 20 | 20 20 20 20 20 78 69 6e | */. | xin|
|000017b0| 20 3d 20 77 78 31 3b 0a | 20 20 20 20 20 20 20 20 | = wx1;.| |
|000017c0| 20 78 6f 75 74 20 3d 20 | 77 78 32 3b 0a 20 20 20 | xout = |wx2;. |
|000017d0| 20 20 20 20 20 20 7d 0a | 20 20 20 20 20 20 65 6c | }.| el|
|000017e0| 73 65 20 7b 0a 20 20 20 | 20 20 20 20 20 20 78 69 |se {. | xi|
|000017f0| 6e 20 3d 20 77 78 32 3b | 0a 20 20 20 20 20 20 20 |n = wx2;|. |
|00001800| 20 20 78 6f 75 74 20 3d | 20 77 78 31 3b 0a 20 20 | xout =| wx1;. |
|00001810| 20 20 20 20 20 20 20 7d | 0a 20 20 20 20 20 20 69 | }|. i|
|00001820| 66 20 28 64 65 6c 74 61 | 79 20 3e 20 30 29 20 7b |f (delta|y > 0) {|
|00001830| 09 09 2f 2a 20 20 70 6f | 69 6e 74 73 20 75 70 20 |../* po|ints up |
|00001840| 2a 2f 0a 20 20 20 20 20 | 20 20 20 20 79 69 6e 20 |*/. | yin |
|00001850| 3d 20 77 79 31 3b 0a 20 | 20 20 20 20 20 20 20 20 |= wy1;. | |
|00001860| 79 6f 75 74 20 3d 20 77 | 79 32 3b 0a 20 20 20 20 |yout = w|y2;. |
|00001870| 20 20 20 20 20 7d 0a 20 | 20 20 20 20 20 65 6c 73 | }. | els|
|00001880| 65 20 7b 0a 20 20 20 20 | 20 20 20 20 20 79 69 6e |e {. | yin|
|00001890| 20 3d 20 77 79 32 3b 0a | 20 20 20 20 20 20 20 20 | = wy2;.| |
|000018a0| 20 79 6f 75 74 20 3d 20 | 77 79 31 3b 0a 20 20 20 | yout = |wy1;. |
|000018b0| 20 20 20 20 20 20 7d 0a | 0a 20 20 20 20 20 20 74 | }.|. t|
|000018c0| 69 6e 78 20 3d 20 28 78 | 69 6e 20 2d 20 78 31 29 |inx = (x|in - x1)|
|000018d0| 2f 64 65 6c 74 61 78 3b | 0a 20 20 20 20 20 20 74 |/deltax;|. t|
|000018e0| 69 6e 79 20 3d 20 28 79 | 69 6e 20 2d 20 79 31 29 |iny = (y|in - y1)|
|000018f0| 2f 64 65 6c 74 61 79 3b | 0a 20 20 20 0a 20 20 20 |/deltay;|. . |
|00001900| 20 20 20 69 66 20 28 74 | 69 6e 78 20 3c 20 74 69 | if (t|inx < ti|
|00001910| 6e 79 29 20 7b 09 2f 2a | 20 68 69 74 73 20 78 20 |ny) {./*| hits x |
|00001920| 66 69 72 73 74 20 2a 2f | 0a 20 20 20 20 20 20 20 |first */|. |
|00001930| 20 20 74 69 6e 31 20 3d | 20 74 69 6e 78 3b 0a 20 | tin1 =| tinx;. |
|00001940| 20 20 20 20 20 20 20 20 | 74 69 6e 32 20 3d 20 74 | |tin2 = t|
|00001950| 69 6e 79 3b 0a 20 20 20 | 20 20 20 20 20 20 7d 0a |iny;. | }.|
|00001960| 20 20 20 20 20 20 65 6c | 73 65 09 09 09 2f 2a 20 | el|se.../* |
|00001970| 68 69 74 73 20 79 20 66 | 69 72 73 74 20 2a 2f 0a |hits y f|irst */.|
|00001980| 20 20 20 20 20 20 20 20 | 20 7b 0a 20 20 20 20 20 | | {. |
|00001990| 20 20 20 20 74 69 6e 31 | 20 3d 20 74 69 6e 79 3b | tin1| = tiny;|
|000019a0| 0a 20 20 20 20 20 20 20 | 20 20 74 69 6e 32 20 3d |. | tin2 =|
|000019b0| 20 74 69 6e 78 3b 0a 20 | 20 20 20 20 20 20 20 20 | tinx;. | |
|000019c0| 7d 0a 0a 20 20 20 20 20 | 20 69 66 20 28 31 20 3e |}.. | if (1 >|
|000019d0| 3d 20 74 69 6e 31 29 20 | 7b 0a 20 20 20 20 20 20 |= tin1) |{. |
|000019e0| 20 20 20 69 66 20 28 30 | 20 3c 20 74 69 6e 31 29 | if (0| < tin1)|
|000019f0| 20 7b 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 61 | {. | a|
|00001a00| 64 64 28 78 69 6e 2c 79 | 69 6e 29 3b 0a 20 20 20 |dd(xin,y|in);. |
|00001a10| 20 20 20 20 20 20 20 20 | 20 7d 0a 20 20 20 20 20 | | }. |
|00001a20| 20 20 20 20 69 66 20 28 | 31 20 3e 3d 20 74 69 6e | if (|1 >= tin|
|00001a30| 32 29 20 7b 0a 20 20 20 | 20 20 20 20 20 20 20 20 |2) {. | |
|00001a40| 20 74 6f 75 74 78 20 3d | 20 28 78 6f 75 74 20 2d | toutx =| (xout -|
|00001a50| 20 78 31 29 2f 64 65 6c | 74 61 78 3b 0a 20 20 20 | x1)/del|tax;. |
|00001a60| 20 20 20 20 20 20 20 20 | 20 74 6f 75 74 79 20 3d | | touty =|
|00001a70| 20 28 79 6f 75 74 20 2d | 20 79 31 29 2f 64 65 6c | (yout -| y1)/del|
|00001a80| 74 61 79 3b 0a 0a 20 20 | 20 20 20 20 20 20 20 20 |tay;.. | |
|00001a90| 20 20 74 6f 75 74 31 20 | 3d 20 28 74 6f 75 74 78 | tout1 |= (toutx|
|00001aa0| 20 3c 20 74 6f 75 74 79 | 29 20 3f 20 74 6f 75 74 | < touty|) ? tout|
|00001ab0| 78 20 3a 20 74 6f 75 74 | 79 20 3b 0a 20 20 20 0a |x : tout|y ;. .|
|00001ac0| 20 20 20 20 20 20 20 20 | 20 20 20 20 69 66 20 28 | | if (|
|00001ad0| 30 20 3c 20 74 69 6e 32 | 20 7c 7c 20 30 20 3c 20 |0 < tin2| || 0 < |
|00001ae0| 74 6f 75 74 31 29 20 7b | 0a 20 20 20 20 20 20 20 |tout1) {|. |
|00001af0| 20 20 20 20 20 20 20 20 | 69 66 20 28 74 69 6e 32 | |if (tin2|
|00001b00| 20 3c 3d 20 74 6f 75 74 | 31 29 20 7b 0a 20 20 20 | <= tout|1) {. |
|00001b10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 69 | | i|
|00001b20| 66 20 28 30 20 3c 20 74 | 69 6e 32 29 20 7b 0a 20 |f (0 < t|in2) {. |
|00001b30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001b40| 20 20 20 20 69 66 20 28 | 74 69 6e 78 20 3e 20 74 | if (|tinx > t|
|00001b50| 69 6e 79 29 20 7b 0a 20 | 20 20 20 20 20 20 20 20 |iny) {. | |
|00001b60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 61 | | a|
|00001b70| 64 64 20 28 78 69 6e 2c | 20 79 31 2b 74 69 6e 78 |dd (xin,| y1+tinx|
|00001b80| 2a 64 65 6c 74 61 79 29 | 3b 0a 20 20 20 20 20 20 |*deltay)|;. |
|00001b90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001ba0| 20 20 7d 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001bb0| 20 20 20 20 20 20 20 20 | 20 65 6c 73 65 20 7b 0a | | else {.|
|00001bc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001bd0| 20 20 20 20 20 20 20 20 | 61 64 64 20 28 78 31 20 | |add (x1 |
|00001be0| 2b 20 74 69 6e 79 2a 64 | 65 6c 74 61 78 2c 20 79 |+ tiny*d|eltax, y|
|00001bf0| 69 6e 29 3b 0a 20 20 20 | 20 20 20 20 20 20 20 20 |in);. | |
|00001c00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 7d 0a 20 | | }. |
|00001c10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001c20| 20 20 20 20 7d 0a 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001c30| 20 20 20 20 20 20 20 20 | 69 66 20 28 31 20 3e 20 | |if (1 > |
|00001c40| 74 6f 75 74 31 29 20 7b | 0a 20 20 20 20 20 20 20 |tout1) {|. |
|00001c50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 69 66 | | if|
|00001c60| 20 28 74 6f 75 74 78 20 | 3c 20 74 6f 75 74 79 29 | (toutx |< touty)|
|00001c70| 20 7b 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | {. | |
|00001c80| 20 20 20 20 20 20 20 20 | 20 20 20 61 64 64 20 28 | | add (|
|00001c90| 78 6f 75 74 2c 20 79 31 | 2b 74 6f 75 74 78 2a 64 |xout, y1|+toutx*d|
|00001ca0| 65 6c 74 61 79 29 3b 0a | 20 20 20 20 20 20 20 20 |eltay);.| |
|00001cb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001cc0| 7d 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |}. | |
|00001cd0| 20 20 20 20 20 20 20 65 | 6c 73 65 20 7b 0a 20 20 | e|lse {. |
|00001ce0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001cf0| 20 20 20 20 20 20 61 64 | 64 20 28 78 31 20 2b 20 | ad|d (x1 + |
|00001d00| 74 6f 75 74 79 2a 64 65 | 6c 74 61 78 2c 20 79 6f |touty*de|ltax, yo|
|00001d10| 75 74 29 3b 0a 20 20 20 | 20 20 20 20 20 20 20 20 |ut);. | |
|00001d20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 7d 0a 20 | | }. |
|00001d30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001d40| 20 20 20 20 7d 0a 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001d50| 20 20 20 20 20 20 20 20 | 65 6c 73 65 20 7b 0a 20 | |else {. |
|00001d60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001d70| 20 20 20 20 61 64 64 20 | 28 78 32 2c 79 32 29 3b | add |(x2,y2);|
|00001d80| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00001d90| 20 20 20 20 20 20 7d 0a | 20 20 20 20 20 20 20 20 | }.| |
|00001da0| 20 20 20 20 20 20 20 20 | 20 20 7d 0a 20 20 20 20 | | }. |
|00001db0| 20 20 20 20 20 20 20 20 | 20 20 20 65 6c 73 65 20 | | else |
|00001dc0| 7b 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |{. | |
|00001dd0| 20 20 20 20 69 66 20 28 | 74 69 6e 78 20 3e 20 74 | if (|tinx > t|
|00001de0| 69 6e 79 29 20 7b 0a 20 | 20 20 20 20 20 20 20 20 |iny) {. | |
|00001df0| 20 20 20 20 20 20 20 20 | 20 20 20 20 61 64 64 20 | | add |
|00001e00| 28 78 69 6e 2c 20 79 6f | 75 74 29 3b 0a 20 20 20 |(xin, yo|ut);. |
|00001e10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001e20| 20 20 7d 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00001e30| 20 20 20 20 20 20 65 6c | 73 65 20 7b 0a 20 20 20 | el|se {. |
|00001e40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001e50| 20 20 61 64 64 20 28 78 | 6f 75 74 2c 20 79 69 6e | add (x|out, yin|
|00001e60| 29 3b 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |);. | |
|00001e70| 20 20 20 20 20 20 20 20 | 7d 0a 20 20 20 20 20 20 | |}. |
|00001e80| 20 20 20 20 20 20 20 20 | 20 20 20 20 7d 0a 20 20 | | }. |
|00001e90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 7d 0a 20 | | }. |
|00001ea0| 20 20 20 20 20 20 20 20 | 20 20 20 7d 0a 20 20 20 | | }. |
|00001eb0| 20 20 20 20 20 20 7d 0a | 20 20 20 20 20 20 7d 0a | }.| }.|
|00001ec0| 0a 20 20 20 69 66 20 28 | 6e 70 6e 74 29 20 7b 0a |. if (|npnt) {.|
|00001ed0| 20 20 20 20 20 20 61 64 | 64 28 58 43 4f 4f 52 44 | ad|d(XCOORD|
|00001ee0| 28 47 45 54 50 4e 54 28 | 6e 70 6f 6c 79 2c 30 29 |(GETPNT(|npoly,0)|
|00001ef0| 29 2c 59 43 4f 4f 52 44 | 28 47 45 54 50 4e 54 28 |),YCOORD|(GETPNT(|
|00001f00| 6e 70 6f 6c 79 2c 30 29 | 29 29 3b 0a 20 20 20 20 |npoly,0)|));. |
|00001f10| 20 20 7d 0a 20 20 20 4e | 50 4e 54 53 28 6e 70 6f | }. N|PNTS(npo|
|00001f20| 6c 79 29 20 3d 20 6e 70 | 6e 74 3b 0a 20 20 20 7d |ly) = np|nt;. }|
|00001f30| 0a 0a 23 5f 5f 5f 5f 5f | 5f 5f 5f 5f 20 63 75 74 |..#_____|____ cut|
|00001f40| 20 6d 61 72 6b 0a 0a 0a | 2d 53 74 65 76 65 20 57 | mark...|-Steve W|
|00001f50| 61 6d 70 6c 65 72 0a 7b | 2e 2e 2e 7d 21 61 72 69 |ampler.{|...}!ari|
|00001f60| 7a 6f 6e 61 21 6e 61 75 | 63 73 65 21 73 62 77 0a |zona!nau|cse!sbw.|
|00001f70| 0a 0a | |.. | |
+--------+-------------------------+-------------------------+--------+--------+