Debian Codegraph @

reals/fast/Plot.v

raw
1 (*
2 Copyright © 2008 Russell O’Connor
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this proof and associated documentation files (the "Proof"), to deal in
6 the Proof without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
8 the Proof, and to permit persons to whom the Proof is furnished to do so,
9 subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Proof.
13
14 THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
16 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
17 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF.
20 *)
21 From Coq Require Import ZArith Qround.
22 Require Import CoRN.metric2.Metric.
23 Require Import CoRN.metric2.ProductMetric.
24 Require Import CoRN.metric2.UniformContinuity.
25 Require Export CoRN.reals.fast.RasterizeQ.
26 Require Import CoRN.reals.fast.Interval.
27 Require Export CoRN.metric2.Graph.
28 Require Import CoRN.model.totalorder.QMinMax.
29 Require Export CoRN.model.totalorder.QposMinMax.
30
31 (**
32 * Plotting
33 Plotting a uniformly continuous function on a finite interval consists
34 of producing the graph of a function as a compact set, approximating that
35 graph, and finally rasterizing that approximation.
36
37 A range for the plot must be provided. We choose to clamp the plotted
38 function so that it lies inside the specified range. Thus we plot
39 [compose (clip b t) f] rather than [f].
40
41 Afterwards we will plot more general located subsets of the plane:
42 - Each blank pixels is correct, meaning there are no points of the subset
43 inside the rectangular regions it represents. In other words, filled
44 pixels cover the subset.
45 - Each filled pixel means there exists a point of the subset inside its
46 rectangular region, or inside one of the adjacent pixels. Thus when we
47 zoom in the filled pixels, we will see more structure.
48 - The pixels overlap, meaning each edge belongs to the 2 pixels that
49 touch it, and each corner belongs to the 4 pixels that touch it.
50
51 *)
52
53 Local Open Scope uc_scope.
54
55 Section PlotPath.
56 Variable (from to:Q).
57 Hypothesis Hfromto:from<=to.
58
59 Variable (l r:Q).
60 Hypothesis Hlr : l < r.
61
62 Variable (b t:Q).
63 Hypothesis Hbt : b < t.
64
65 Variable n : positive.
66
67 Let w := r - l.
68 Let h := t - b.
69
70 Lemma wpos : 0 < w.
71 Proof.
72 apply Qlt_minus_iff in Hlr. exact Hlr.
73 Qed.
74
75 Lemma hpos : 0 < h.
76 Proof.
77 apply Qlt_minus_iff in Hbt. exact Hbt.
78 Qed.
79
80 (* Compute the number of pixels on the Y-axis to make square pixels. *)
81 Let m : positive := Z.to_pos (Qceiling ((t-b) * inject_Z (Z.pos n) / (r-l))).
82
83 (**
84 Half the error in the Plot example, since we need to approximate twice.
85 *)
86 Let err := Qpos_max ((1 # 8 * n) * (exist _ _ wpos))
87 ((1 # 8 * m) * (exist _ _ hpos)).
88
89 Variable path:Q_as_MetricSpace --> Complete Q2.
90
91 (** The actual plot function.
92 The approximation of PathImage make a list (Complete Q2), ie a list
93 of points in the real plane. Those points still need to be approximated
94 by rational numbers, which map approximate does. *)
95 Definition PlotPath : positive * positive * Q * sparse_raster n m
96 := (n, m, 2#1,
97 sparse_raster_data n m
98 (map
99 (fun x : Z =>
100 rasterize2 n m t l b r
101 ((let (approximate, _) :=
102 path
103 (from +
104 (to - from) * (2 * x + 1 # 1) /
105 (2 *
106 Z.pos
107 (Z.to_pos
108 (Qceiling
109 ((to - from) /
110 (inject_Z 2 *
111 proj1_sig (FinEnum_map_modulus (1 # 1) (mu path) err)))))
112 # 1)) in
113 approximate) err))
114 (iterateN_succ 0
115 (Z.to_pos
116 (Qceiling
117 ((to - from) /
118 (inject_Z 2 * proj1_sig (FinEnum_map_modulus (1 # 1) (mu path) err)))))))).
119
120 Definition PlotPath_slow : positive * positive * Q * sparse_raster n m
121 := (n, m, 2#1,
122 RasterizeQ2
123 (map (fun x : Q_as_MetricSpace => approximate (path x) err)
124 (approximate (CompactIntervalQ Hfromto)
125 (FinEnum_map_modulus (1 # 1) (mu path) err)))
126 n m t l b r).
127
128 Lemma PlotPath_correct : eq PlotPath PlotPath_slow.
129 Proof.
130 unfold PlotPath, PlotPath_slow, RasterizeQ2.
131 rewrite map_map.
132 unfold CompactIntervalQ, approximate.
133 unfold CompactIntervalQ_raw, UniformPartition.
134 rewrite map_map.
135 reflexivity.
136 Qed.
137
138 End PlotPath.
139
140
141 Lemma plFEQ : PrelengthSpace (FinEnum Q_as_MetricSpace).
142 Proof.
143 apply FinEnum_prelength.
144 apply locatedQ.
145 apply QPrelengthSpace.
146 Qed.
147
148
149 Section Plot.
150
151 Variable (l b:Q).
152 Variable w h:Qpos.
153
154 Let r:=l+proj1_sig w.
155 Let t:=b+proj1_sig h.
156
157 Let clip := uc_compose (boundBelow b) (boundAbove t).
158
159 Variable f : Q_as_MetricSpace --> CR.
160
161 Lemma lrle : l <= r.
162 Proof.
163 rewrite <- (Qplus_0_r l).
164 unfold r. apply Qplus_le_r, Qpos_nonneg.
165 Qed.
166
167 Definition graphQ f : Compact Q2
168 := CompactGraph_b f plFEQ (CompactIntervalQ lrle).
169
170 Lemma graphQ_bonus : forall e x y,
171 In (x, y) (approximate (graphQ (uc_compose clip f)) e)
172 -> l <= x <= r /\ b <= y <= t.
173 Proof.
174 intros [e|] x y;[|intros; contradiction].
175 simpl.
176 unfold Cjoin_raw.
177 Opaque CompactIntervalQ.
178 simpl.
179 unfold FinCompact_raw.
180 rewrite map_map.
181 rewrite -> in_map_iff.
182 unfold graphPoint_b_raw; simpl.
183 unfold Couple_raw; simpl.
184 intros [z [Hz0 Hz1]].
185 inversion Hz0.
186 subst x. subst y.
187 clear Hz0.
188 split.
189 eapply CompactIntervalQ_bonus_correct.
190 apply Hz1.
191 split. apply Qmax_ub_l.
192 apply Qmax_lub.
193 rewrite <- (Qplus_0_r b).
194 unfold t. apply Qplus_le_r, Qpos_nonneg.
195 apply Qmin_lb_l.
196 Qed.
197
198 Variable n m : positive. (* Number of horizontal and vertical pixels *)
199
200 Let err := Qpos_max ((1 # 4 * n) * w)
201 ((1 # 4 * m) * h).
202
203 (** [PlotQ] is the function that computes the pixels. *)
204 Definition PlotQ : sparse_raster n m
205 := RasterizeQ2 (approximate (graphQ (uc_compose clip f)) err) n m t l b r.
206
207 Local Open Scope raster.
208
209 (** The resulting plot is close to the graph of [f] *)
210 Theorem Plot_correct :
211 @ball (Compact Q2)
212 (proj1_sig (err + Qpos_max ((1 # 2 * n) * w) ((1 # 2 * m) * h))%Qpos)
213 (graphQ (uc_compose clip f))
214 (Cunit (CentersOfPixels (PixelizeQ2 PlotQ) (l,t) (r,b))).
215 Proof.
216 apply ball_triangle with (Cunit (approximate (graphQ (uc_compose clip f)) err)).
217 apply ball_approx_r.
218 unfold Compact.
219 rewrite -> ball_Cunit.
220 apply ball_sym.
221 split. apply Qpos_nonneg.
222 apply RasterizeQ2_correct.
223 intros.
224 destruct (InStrengthen H) as [[zx xy] [Hz0 [Hz1 Hz2]]].
225 simpl in Hz1, Hz2.
226 apply Qball_0 in Hz1.
227 apply Qball_0 in Hz2.
228 rewrite -> Hz1, Hz2.
229 eapply graphQ_bonus.
230 apply Hz0.
231 Qed.
232
233 End Plot.
234
235 (** Some nice notation for the graph of f. *)
236 Notation "'graphCR' f [ l '..' r ]" :=
237 (graphQ l r (refl_equal _) f) (f at level 0) : raster.
238
239 (*
240 (* Some graph examples *)
241 Local Open Scope raster. (* enables pretty printing of rasters *)
242 Definition id_raster : raster _ _
243 := PlotQ 0 1 eq_refl 0 1 eq_refl (@Cunit Q_as_MetricSpace) 30 30.
244 Compute id_raster.
245
246 Require Import CoRN.reals.fast.CRexp.
247 Definition exp_raster
248 := PlotQ (-2) 1 eq_refl 0 3 eq_refl (exp_bound_uc 3) 30 30.
249 Compute exp_raster.
250 *)
251
252 (* Difficult to make tail-recursive, because the current vector
253 has no clear size to declare. Vector.map is not tail-recursive either. *)
254 Fixpoint PlotLine (A : CR*CR -> Prop) (i:nat)
255 (r step:Q) (y : CR) (d e:Q) (ltde : d < e)
256 (loc : LocatedSubset (ProductMS CR CR) A)
257 { struct i }
258 : list bool :=
259 match i with
260 | O => nil
261 | S p =>
262 cons (let xi := inject_Q_CR (r - inject_Z (Z.of_nat i) * step)%Q in
263 if loc d e (xi,y) ltde then false else true)
264 (PlotLine A p r step y d e ltde loc)
265 end.
266
267 Fixpoint PlotSubset_fix (A : CR*CR -> Prop) (n j:nat)
268 (b r stepX stepY:Q) (d e:Q) (ltde : d < e)
269 (loc : LocatedSubset (ProductMS CR CR) A)
270 { struct j }
271 : list (list bool) :=
272 match j with
273 | O => nil
274 | S p => let yj := inject_Q_CR (b + inject_Z (Z.of_nat j) * stepY)%Q in
275 cons (PlotLine A n r stepX yj d e ltde loc)
276 (PlotSubset_fix A n p b r stepX stepY d e ltde loc)
277 end.
278
279 Definition PlotRadius (n m : positive) (t l b r : Q) : Q
280 := Qmax ((r-l) * (1#n))%Q
281 ((t-b) * (1#m))%Q.
282
283 Lemma PlotRadiusInc
284 : forall n m t l b r,
285 l < r -> (1#2) * PlotRadius n m t l b r < PlotRadius n m t l b r.
286 Proof.
287 intros. rewrite <- (Qmult_1_l (PlotRadius n m t l b r)) at 2.
288 apply Qmult_lt_r.
289 2: reflexivity. apply (Qlt_le_trans _ ((r-l) * (1#n))%Q).
290 apply Qlt_minus_iff in H.
291 apply (Qpos_ispos (exist _ _ H * (1 # n))).
292 apply Qmax_ub_l.
293 Qed.
294
295 Definition PlotSubset {A : CR*CR -> Prop} (n m : positive) (t l b r : Q)
296 (ltlr : l < r) (loc : LocatedSubset (ProductMS CR CR) A)
297 : raster n m
298 := let stepX := ((r-l) * (1#n))%Q in
299 let stepY := ((t-b) * (1#m))%Q in
300 (* A pixel is a square ball and its radius it half its side. *)
301 raster_data
302 _ _
303 (PlotSubset_fix A (Pos.to_nat n) (Pos.to_nat m) (b-(1#2)*stepY) (r+(1#2)*stepX)
304 stepX stepY _ _
305 (PlotRadiusInc n m t l b r ltlr) loc).
306
307 (*
308 Definition PlotDiagLocated := (PlotSubset
309 10 10 (1#1) (0#1) (0#1) (1#1) eq_refl
310 (undistrib_Located (CompactIsLocated
311 _ (graphQ 0 1 eq_refl (@Cunit Q_as_MetricSpace))
312 (ProductMS_located locatedQ locatedQ)))).
313 Local Open Scope raster. (* enables pretty printing of rasters *)
314 Time Eval vm_compute in PlotDiagLocated.
315 *)
316
317
318 (* The blank pixels have no points of the subset, in other words
319 the filled pixels cover the subset. *)
320 Lemma PlotLine_blank
321 : forall (A : CR*CR -> Prop) (n i:nat) (ltni : (n < i)%nat)
322 (r step:Q) (x y z : CR) (d e:Q) (ltde : d < e)
323 (loc : LocatedSubset (ProductMS CR CR) A),
324 ball d x (inject_Q_CR (r - inject_Z (Z.of_nat (i-n)) * step)%Q)
325 -> ball d y z
326 -> nth n (PlotLine A i r step y d e ltde loc) false = false
327 -> ~A (x,z).
328 Proof.
329 induction n.
330 - intros. intro abs.
331 destruct i. exfalso; inversion ltni.
332 simpl in H1.
333 destruct (loc d e
334 (@pair (@RegularFunction Q Qball) (@RegularFunction Q Qball)
335 (inject_Q_CR
336 (Qminus r (Qmult (inject_Z (Zpos (Pos.of_succ_nat i))) step))) y)
337 ltde).
338 2: discriminate. clear H1.
339 specialize (n (x,z) abs).
340 contradict n. split.
341 + unfold fst.
342 apply ball_sym.
343 exact H.
344 + exact H0.
345 - intros. intro abs.
346 destruct i. inversion ltni. simpl in H1.
347 revert abs.
348 refine (IHn i (proj2 (Nat.succ_lt_mono n i) ltni) r step x y z d e
349 ltde loc _ H0 H1).
350 replace (i-n)%nat with (S i - S n)%nat by reflexivity.
351 exact H.
352 Qed.
353
354 Lemma PlotSubset_fix_blank
355 : forall (A : CR*CR -> Prop) (x y : CR) (i j n m:nat)
356 (ltin : (i < n)%nat) (ltjm : (j < m)%nat)
357 (b r stepX stepY:Q) (d e:Q) (ltde : d < e)
358 (loc : LocatedSubset (ProductMS CR CR) A),
359 ball d x (inject_Q_CR (r - inject_Z (Z.of_nat (n-i)) * stepX)%Q)
360 -> ball d y (inject_Q_CR (b + inject_Z (Z.of_nat (m-j)) * stepY)%Q)
361 -> nth i
362 (nth j (PlotSubset_fix A n m b r stepX stepY
363 d e ltde loc)
364 nil)
365 false = false
366 -> ~A (x,y).
367 Proof.
368 induction j.
369 - intros. intro abs.
370 destruct m. exfalso; inversion ltjm.
371 simpl in H1.
372 refine (PlotLine_blank
373 A i n ltin r stepX x
374 (' (b + inject_Z (Z.pos (Pos.of_succ_nat m)) * stepY)%Q)%CR
375 y d e ltde loc H _ H1 abs).
376 apply ball_sym.
377 exact H0.
378 - intros. intro abs.
379 destruct m. inversion ltjm.
380 simpl in H1.
381 apply (IHj n m ltin (proj2 (Nat.succ_lt_mono j m) ltjm) b r stepX stepY
382 d e ltde loc H H0 H1 abs).
383 Qed.
384
385 Lemma PlotSubset_blank
386 : forall {A : CR*CR -> Prop} (i j : nat) (n m : positive) (t l b r : Q) (x y : CR)
387 (ltin : (i < Pos.to_nat n)%nat) (ltjm : (j < Pos.to_nat m)%nat) (ltlr : l < r)
388 (loc : LocatedSubset (ProductMS CR CR) A),
389 RasterIndex (PlotSubset n m t l b r ltlr loc) j i = false
390 -> let stepX := ((r-l) * (1#n))%Q in
391 let stepY := ((t-b) * (1#m))%Q in
392 ball ((1#2)*(Qmax stepX stepY)) x
393 (inject_Q_CR (l + (inject_Z (Z.of_nat i) + (1#2)) * stepX)%Q)
394 -> ball ((1#2)*(Qmax stepX stepY)) y
395 (inject_Q_CR (t - (inject_Z (Z.of_nat j) + (1#2)) * stepY)%Q)
396 -> ~A (x,y).
397 Proof.
398 intros.
399 setoid_replace (l + (inject_Z (Z.of_nat i)+(1#2)) * stepX)%Q
400 with ((r + (1#2)*stepX) - inject_Z (Z.of_nat (Pos.to_nat n - i)) * stepX)%Q
401 in H0.
402 setoid_replace (t - (inject_Z (Z.of_nat j) + (1#2)) * stepY)%Q
403 with ((b-(1#2)*stepY) + inject_Z (Z.of_nat (Pos.to_nat m - j)) * stepY)%Q
404 in H1.
405 exact (PlotSubset_fix_blank
406 A x y i j (Pos.to_nat n) (Pos.to_nat m) ltin ltjm
407 _ _ stepX stepY
408 ((1#2)*(Qmax stepX stepY))
409 (Qmax stepX stepY)
410 (PlotRadiusInc n m t l b r ltlr) loc
411 H0 H1 H).
412 - unfold canonical_names.equiv, stdlib_rationals.Q_eq.
413 rewrite Nat2Z.inj_sub.
414 unfold Zminus. rewrite Q.Zplus_Qplus, inject_Z_opp.
415 rewrite <- (Qplus_inj_r _ _ ((inject_Z (Z.of_nat j)+(1#2)) * stepY)).
416 ring_simplify.
417 rewrite positive_nat_Z.
418 unfold stepY.
419 rewrite <- Qmult_assoc.
420 setoid_replace ((1 # m) * inject_Z (Z.pos m)) with 1%Q by reflexivity.
421 rewrite Qmult_1_r. ring.
422 apply (Nat.le_trans _ (S j)).
423 apply le_S, Nat.le_refl. exact ltjm.
424 - unfold canonical_names.equiv, stdlib_rationals.Q_eq.
425 rewrite Nat2Z.inj_sub.
426 unfold Zminus. rewrite Q.Zplus_Qplus, inject_Z_opp.
427 rewrite positive_nat_Z.
428 rewrite <- (Qplus_inj_r _ _ (stepX * inject_Z (Z.pos n)
429 -inject_Z (Z.of_nat i) * stepX
430 - (1#2)*stepX)).
431 ring_simplify.
432 unfold stepX.
433 rewrite <- Qmult_assoc.
434 setoid_replace ((1 # n) * inject_Z (Z.pos n)) with 1%Q by reflexivity.
435 rewrite Qmult_1_r. ring.
436 apply (Nat.le_trans _ (S i)).
437 apply le_S, Nat.le_refl. exact ltin.
438 Qed.