1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
#include <u.h>
#include <libc.h>
#include <draw.h>
#include <ctype.h>
int
max(int a, int b)
{
return a > b? a: b;
}
/*
* A Fast 2D Point-On-Line Test
* by Alan Paeth
* from "Graphics Gems", Academic Press, 1990
*/
int
ptinline(Point p, Point q, Point t)
{
/*
* given a line through q and t
* return 0 if p is not on the line through <--q--t-->
* 1 if p is on the open ray ending at q: <--q
* 2 if p is on the closed interior along: q--t
* 3 if p is on the open ray beginning at t: t-->
*/
if(q.x == t.x && q.y == t.y){
if(p.x == q.x && p.y == q.y)
return 2;
return 0;
}
if(abs((t.y - q.y)*(p.x - q.x) - (p.y - q.y)*(t.x - q.x)) >=
max(abs(t.x - q.x), abs(t.y - q.y)))
return 0;
if((t.x < q.x && q.x < p.x) || (t.y < q.y && q.y < p.y))
return 1;
if((p.x < q.x && q.x < t.x) || (p.y < q.y && q.y < t.y))
return 1;
if((q.x < t.x && t.x < p.x) || (q.y < t.y && t.y < p.y))
return 3;
if((p.x<t.x && t.x<q.x) || (p.y<t.y && t.y<q.y))
return 3;
return 2;
}
void
usage(void)
{
fprint(2, "usage: %s x0 y0 x1 y1\n", argv0);
exits("usage");
}
void
main(int argc, char *argv[])
{
Point pts[3];
char buf[256], *p;
int n;
fmtinstall('P', Pfmt);
ARGBEGIN{
default: usage();
}ARGEND;
if(argc != 4)
usage();
pts[0].x = strtol(argv[0], &p, 10);
if(*p != 0)
usage();
pts[0].y = strtol(argv[1], &p, 10);
if(*p != 0)
usage();
pts[1].x = strtol(argv[2], &p, 10);
if(*p != 0)
usage();
pts[1].y = strtol(argv[3], &p, 10);
if(*p != 0)
usage();
while((n = read(0, buf, sizeof(buf)-1)) > 0){
buf[n-1] = buf[n] = 0;
pts[2].x = strtol(buf, &p, 10);
if(!isspace(*p)){
fprint(2, "wrong x coordinate\n");
continue;
}
pts[2].y = strtol(p, &p, 10);
if(*p != 0){
fprint(2, "wrong y coordinate\n");
continue;
}
switch(ptinline(pts[2], pts[0], pts[1])){
case 0:
print("%P is not on %P%P\n", pts[2], pts[0], pts[1]);
break;
case 1:
print("%P in (∞,%P)\n", pts[2], pts[0]);
break;
case 2:
print("%P in [%P,%P]\n", pts[2], pts[0], pts[1]);
break;
case 3:
print("%P in (%P,∞)\n", pts[2], pts[1]);
break;
}
}
exits(nil);
}
|
