Geometry.xtl

1⍝# Geometry: plane geometry -- points as 2-row matrices, distances,
2⍝# polygon area and centroid, rotation, scaling and moves, convex
3⍝# hulls, pictures.
4⍝# Import it with an alias of your choice: "ge:" u_se< "Geometry".
5⍝# Put libs/Geometry/src on XETAL_PATH ("just path"); the reference is libs/Geometry/docs.
6⍝# Names with l: are exported; those under h: are private to this file.
7⍝#
8⍝# Points are a matrix of 2 rows, x over y, one point per column, as
9⍝# X_eTaL's []P_ATH takes them; a polygon is its corners in order.
10⍝# Results are Floats.
11
12⍝## Distance and area
13
14ʰx̲s ← { p → f̲loat f̲irst p }                     ⍝ the x of every point
15ʰy̲s ← { p → f̲loat f̲irst 1 d̲rop p }              ⍝ the y of every point
16
17⍝# d_istances p: the distance between every pair of points (a matrix).
18ˡd̲istances ← { p →
19  dx ← (ʰx̲s p) '− t̲able ʰx̲s p
20  dy ← (ʰy̲s p) '− t̲able ʰy̲s p
21  ((dx × dx) + dy × dy) ^ 0.5
22}
23
24⍝# The polygon's area, signed: positive when the corners go round
25⍝# anticlockwise (the shoelace formula).
26ʰs̲igned ← { p → x ← ʰx̲s p◆ y ← ʰy̲s p◆ 0.5 × '+ r̲/ (x × 1 o̲- y) − y × 1 o̲- x }
27
28⍝# a_rea p: the area of the polygon.
29ˡa̲rea ← { p → a̲bs ʰs̲igned p }
30
31⍝## Moves
32
33⍝# c_entroid p: the polygon's center of mass, x and y.
34ˡc̲entroid ← { p →
35  0.000000000001 > a̲bs ʰs̲igned p ? @ p̲anic< "the polygon has no area (its corners are in a line): its centroid is undefined"
p̲anic< expands to(⎕P̲ANIC ("the polygon has no area (its corners are in a line): its centroid is undefined"))
36  x ← ʰx̲s p
37  y ← ʰy̲s p
38  c ← (x × 1 o̲- y) − y × 1 o̲- x
39  k ← 1.0 ÷ 6.0 × ʰs̲igned p
40  (k × '+ r̲/ c × x + 1 o̲- x) c̲at k × '+ r̲/ c × y + 1 o̲- y
41}
42
43⍝# angle r_otate p: the points turned anticlockwise about the origin
44⍝# by angle (radians).
45ˡr̲otate ← { a p →
46  c ← c̲os a
47  s ← s̲in a
48  x ← ʰx̲s p
49  y ← ʰy̲s p
50  (2 c̲at t̲ally x) r̲eshape ((c × x) − s × y) c̲at (s × x) + c × y
51}
52
53⍝# Two numbers (or one, used twice) as a column for every point.
54ʰc̲olumn ← { d p → o̲\ ((t̲ally ʰx̲s p) c̲at 2) r̲eshape f̲loat d }
55
56⍝# f s_cale p: the points scaled by f about the origin (one factor, or
57⍝# two: x and y).
58ˡs̲cale ← { f p → (f̲loat p) × f ʰc̲olumn p }
59
60⍝# d m_ove p: the points moved by d, two numbers dx dy.
61ˡm̲ove ← { d p → (f̲loat p) + d ʰc̲olumn p }
62
63⍝## Polygons
64
65⍝# The cross product of (q - c) and (r - c) for every candidate q and
66⍝# every point r: positive where r is left of the line from c to q.
67ʰc̲ross ← { p i →
68  x ← ʰx̲s p
69  y ← ʰy̲s p
70  dx ← x − f̲irst i s̲elect x
71  dy ← y − f̲irst i s̲elect y
72  (dx '× t̲able dy) − dy '× t̲able dx
73}
74
75⍝# The hull's next corner after corner i: the point with no point to
76⍝# the left of the line to it (the farthest, when several are in line).
77ʰn̲ext ← { p i →
78  ok ← ('∧ r̲/₂ 0.000000001 ≥ p ʰc̲ross i) ∧ (r̲ange t̲ally ʰx̲s p) ≠ i
79  d ← i s̲elect ˡd̲istances p
80  f̲irst g̲rade n̲eg d × f̲loat ok
81}
82
83⍝# The corners from i round to the start s, in order.
84ʰw̲alk ← { p s i acc →
85  j ← p ʰn̲ext i
86  j = s ? acc
87  ((((p ʰw̲alk s)_ j)_ acc c̲at j))
88}
89
90⍝# h_ull p: the convex hull, its corners in order (clockwise from the
91⍝# lowest of the leftmost points), as a polygon.
92ˡh̲ull ← { p →
93  x ← ʰx̲s p
94  y ← ʰy̲s p
95  left ← w̲here x = 'm̲in r̲/ x
96  s ← f̲irst (g̲rade (left s̲elect y)) s̲elect left
97  (((p ʰw̲alk s)_ s)_ 1 r̲eshape s) s̲elect₂ p
98}
99
100⍝## Pictures
101
102⍝# s_how! p: the polygon (closed) as a picture, shown with []S_HOW.
103ˡs̲how! ← { p → ⎕S̲HOW ⎕P̲ATH (f̲loat p) c̲at₂ 1 t̲ake₂ f̲loat p }