aboutsummaryrefslogtreecommitdiff
path: root/ptinline.c
diff options
context:
space:
mode:
authorrodri <rgl@antares-labs.eu>2020-06-07 09:52:15 +0000
committerrodri <rgl@antares-labs.eu>2020-06-07 09:52:15 +0000
commitd6beda15798a3d1d604a033febca3756456345d1 (patch)
tree5b414c388e35e10f2aa49ecf4a2203fba6affa11 /ptinline.c
parent217d72a006e3b57526d889dc5b9ac591a3254e2f (diff)
downloadetoys-d6beda15798a3d1d604a033febca3756456345d1.tar.gz
etoys-d6beda15798a3d1d604a033febca3756456345d1.tar.bz2
etoys-d6beda15798a3d1d604a033febca3756456345d1.zip
new toy: ptinline prototype.
Diffstat (limited to 'ptinline.c')
-rw-r--r--ptinline.c101
1 files changed, 101 insertions, 0 deletions
diff --git a/ptinline.c b/ptinline.c
new file mode 100644
index 0000000..97be46e
--- /dev/null
+++ b/ptinline.c
@@ -0,0 +1,101 @@
+#include <u.h>
+#include <libc.h>
+#include <draw.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\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 > 0)
+ usage();
+
+ pts[0] = Pt(0,0);
+ pts[1] = Pt(2,2);
+
+ while((n = read(0, buf, sizeof(buf)-1)) > 0){
+ buf[n-1] = buf[n] = 0;
+
+ pts[2].x = strtol(buf, &p, 10);
+ if(p == nil || *p == 0){
+ fprint(2, "wrong x coordinate\n");
+ continue;
+ }
+ pts[2].y = strtol(p, &p, 10);
+ if(p == nil || *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);
+}