Debian Codegraph @

reals/fast/RasterizeQ.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.
22 Require Import CoRN.algebra.RSetoid.
23 Require Import CoRN.metric2.Metric.
24 Require Import CoRN.metric2.UniformContinuity.
25 Require Export CoRN.reals.fast.RasterQ.
26 Require Import CoRN.reals.fast.Interval.
27 Require Import CoRN.logic.Classic.
28 Require Import CoRN.model.totalorder.QposMinMax.
29 From Coq Require Import Qabs.
30 From Coq Require Import Qround.
31
32 Local Open Scope Q_scope.
33
34 Set Implicit Arguments.
35
36 (**
37 ** Rasterization
38 Rasterization takes finite enumeration of points in [Q2] and moves them
39 around a little so that they lie on a raster. Thus rasterization produces
40 a raster object that when interpreted as a finite enumeration of [Q2] is
41 close to the original enumeration of points. How close depends on how
42 fine a raster is chosen.
43
44 There is a choice as to how to treat points that lie outside of the bound
45 of a chosen rectangle for rasterization. In this implemenation I choose
46 to push all points inside the raster. In typical applications a rectangle
47 is chosen that contains all the points, so that this doesn't matter. *)
48
49 (* [Rasterize Point] adds a single point [p] into a raster.
50 The raster is inside the rectanle t l b r, meaning top, left, bottom and right.
51 It has n points horizontally and m points vertically. The indexes (0,0)
52 correspond to the point (l,t) ie the top left corner. That yields the correct
53 printing order of the raster, which is a vector of lines. *)
54 Definition rasterize2 (n m:positive) (t l b r:Q) (p:Q*Q) : Z*Z
55 := pair (Zpos m -1 - (Z.min (Zpos m -1) (Z.max 0 (rasterize1 b t m (snd p)))))%Z
56 (Z.min (Zpos n -1) (Z.max 0 (rasterize1 l r n (fst p)))).
57
58 Lemma rasterize2_bound :
59 forall n z, (0 <= Z.min (Zpos n -1) (Z.max 0 z) < Zpos n)%Z.
60 Proof.
61 split.
62 - apply Z.min_case.
63 apply Z.le_0_sub, Pos.le_1_l.
64 apply Z.le_max_l.
65 - apply (Z.le_lt_trans _ _ _ (Z.le_min_l _ _)).
66 rewrite <- (Z.add_0_r (Z.pos n)) at 2.
67 apply Z.add_lt_mono_l. reflexivity.
68 Qed.
69
70 Lemma rasterize1_origin : forall l r n, rasterize1 l r n l = 0%Z.
71 Proof.
72 intros.
73 unfold rasterize1.
74 unfold Qminus.
75 rewrite Qplus_opp_r, Qmult_0_r.
76 unfold Qdiv. rewrite Qmult_0_l.
77 reflexivity.
78 Qed.
79
80 Lemma rasterize2_origin
81 : forall n m (t l b r : Q),
82 b < t -> rasterize2 n m t l b r (pair l t) = pair 0%Z 0%Z.
83 Proof.
84 assert (forall n:positive, 0 <= Zpos n -1)%Z.
85 { intro n.
86 change 0%Z with (1-1)%Z.
87 apply Z.add_le_mono_r.
88 apply Pos.le_1_l. }
89 intros. unfold rasterize2, fst, snd.
90 rewrite rasterize1_origin.
91 replace (rasterize1 b t m t) with (Zpos m)%Z.
92 change (Z.max 0 0) with 0%Z.
93 rewrite Z.max_r. 2: discriminate.
94 rewrite Z.min_l.
95 rewrite Z.min_r.
96 rewrite Z.sub_diag. reflexivity.
97 apply H.
98 rewrite <- (Z.add_0_r (Zpos m)) at 2.
99 apply Z.add_le_mono_l. discriminate.
100 unfold rasterize1.
101 unfold Qdiv.
102 rewrite <- Qmult_assoc, Qmult_inv_r, Qmult_1_r.
103 rewrite Qfloor_Z. reflexivity.
104 intro abs. apply Qlt_minus_iff in H0.
105 unfold Qminus in abs. rewrite abs in H0.
106 exact (Qlt_irrefl 0 H0).
107 Qed.
108
109 (* Adding a point to a raster preserves all the points that were
110 already in it. *)
111 Lemma setRaster_carry : forall l r n m (bm:raster n m) i j,
112 raster_well_formed bm
113 -> Is_true (RasterIndex bm i j)
114 -> Is_true (RasterIndex (setRaster bm true l r) i j).
115 Proof.
116 intros l r m n bm i j rWf H.
117 destruct (le_lt_dec (Pos.to_nat n) l).
118 rewrite setRaster_overflow; auto.
119 destruct (le_lt_dec (Pos.to_nat m) r).
120 rewrite setRaster_overflow; auto.
121 destruct (eq_nat_dec i l).
122 destruct (eq_nat_dec j r).
123 rewrite e, e0.
124 rewrite setRaster_correct1; try constructor; congruence.
125 rewrite setRaster_correct2; auto.
126 rewrite setRaster_correct2; auto.
127 Qed.
128
129 Lemma setRaster_uncarry : forall n m (r:raster n m) i j ax ay,
130 raster_well_formed r
131 -> Is_true (RasterIndex (setRaster r true ax ay) i j)
132 -> (Is_true (RasterIndex r i j) \/ (ax, ay) = (i,j)).
133 Proof.
134 intros.
135 destruct (Nat.eq_dec ax i).
136 - destruct (Nat.eq_dec ay j).
137 right. f_equal; assumption.
138 left.
139 rewrite (setRaster_correct2 r) in H0.
140 exact H0. exact H.
141 right. intro abs. subst j. contradiction.
142 - left.
143 rewrite (setRaster_correct2 r) in H0.
144 exact H0. exact H.
145 left. intro abs. subst i. contradiction.
146 Qed.
147
148 (* Sparse rasters are faster than boolean matrices when the number of
149 points to plot is small with respect to the total number of pixels.
150 Each lit pixel of a sparse raster stores 2 positive numbers. For
151 a 1000x1000 image that's 20 allocations per pixel instead of 1
152 allocation for boolean matrices. *)
153 Variant sparse_raster (columns lines : positive) : Set :=
154 | sparse_raster_data : list (Z*Z) -> sparse_raster columns lines.
155
156 (** This function is slow to compute in Coq.
157 It is faster to plot a sparse raster with DumpGrayMap. *)
158 Definition PixelizeQ2 {columns lines:positive} (points:sparse_raster columns lines)
159 : raster columns lines :=
160 fold_left (fun (rast:raster columns lines) (p:Z*Z)
161 => setRaster rast true (Z.to_nat (fst p)) (Z.to_nat (snd p)))
162 (let (p) := points in p)
163 (emptyRaster columns lines).
164
165 Definition RasterizeQ2 (points:list Q2) (n m:positive) (t l b r:Q)
166 : sparse_raster n m :=
167 sparse_raster_data n m (map (fun p => rasterize2 n m t l b r p) points).
168
169 Lemma RasterizeQ2_wf : forall points n m t l b r,
170 raster_well_formed (PixelizeQ2 (RasterizeQ2 points n m t l b r)).
171 Proof.
172 intros. unfold PixelizeQ2, RasterizeQ2.
173 pose proof (emptyRaster_wf n m).
174 revert H. generalize (emptyRaster n m).
175 induction points.
176 - intros. exact H.
177 - intros. simpl. apply IHpoints.
178 apply setRaster_wf, H.
179 Qed.
180
181 Lemma RasterizeQ2_in : forall points (i j : Z) n m (r:raster n m),
182 In (i,j) points
183 -> raster_well_formed r
184 -> (Z.to_nat i < Pos.to_nat m)%nat
185 -> (Z.to_nat j < Pos.to_nat n)%nat
186 -> Is_true (RasterIndex
187 (fold_left (fun (rast:raster n m) (p:Z*Z)
188 => setRaster rast true (Z.to_nat (fst p)) (Z.to_nat (snd p)))
189 points r)
190 (Z.to_nat i) (Z.to_nat j)).
191 Proof.
192 assert (forall points i j n m (r:raster n m),
193 Is_true (RasterIndex r (Z.to_nat i) (Z.to_nat j))
194 -> raster_well_formed r
195 -> Is_true (RasterIndex
196 (fold_left (fun (rast:raster n m) (p:Z*Z)
197 => setRaster rast true (Z.to_nat (fst p)) (Z.to_nat (snd p)))
198 points r)
199 (Z.to_nat i) (Z.to_nat j))).
200 { induction points.
201 - intros. exact H.
202 - intros. simpl. apply IHpoints.
203 apply setRaster_carry. exact H0. exact H.
204 apply setRaster_wf, H0. }
205 induction points.
206 - intros. exfalso. inversion H0.
207 - intros. simpl. destruct H0.
208 + subst a. simpl.
209 apply H. apply Is_true_eq_left, setRaster_correct1.
210 exact H1. exact H2. exact H3.
211 apply setRaster_wf, H1.
212 + apply IHpoints. exact H0.
213 apply setRaster_wf, H1.
214 exact H2. exact H3.
215 Qed.
216
217 Lemma RasterizeQ2_in_recip : forall (points : list (Z*Z)) (i j : nat) n m (r:raster n m),
218 raster_well_formed r
219 -> Is_true (RasterIndex
220 (fold_left (fun (rast:raster n m) (p:Z*Z)
221 => setRaster rast true (Z.to_nat (fst p)) (Z.to_nat (snd p)))
222 points r) i j)
223 -> (In (i, j) (map (fun p => (Z.to_nat (fst p), Z.to_nat (snd p))) points)
224 \/ Is_true (RasterIndex r i j)).
225 Proof.
226 induction points as [|[ax ay] points].
227 - intros. right. exact H0.
228 - intros. simpl in H0.
229 destruct (RasterIndex r i j) eqn:des.
230 right. reflexivity. left.
231 destruct (IHpoints i j n m
232 (setRaster r true (Z.to_nat ax) (Z.to_nat ay)) ).
233 apply setRaster_wf, H.
234 exact H0.
235 right. exact H1.
236 destruct (Nat.eq_dec (Z.to_nat ax) i).
237 + destruct (Nat.eq_dec (Z.to_nat ay) j).
238 left. f_equal; assumption.
239 exfalso. apply setRaster_uncarry in H1.
240 destruct H1. unfold Is_true in H1.
241 rewrite des in H1. contradiction.
242 inversion H1. contradiction. exact H.
243 + exfalso. apply setRaster_uncarry in H1.
244 destruct H1. unfold Is_true in H1.
245 rewrite des in H1. contradiction.
246 inversion H1. contradiction. exact H.
247 Qed.
248
249 Lemma InFinEnumC_Qepsilon : forall (x y : Q) points,
250 @InFinEnumC (ProductMS _ _) (x,y) points
251 -> exists q, In q points /\ msp_eq q (x,y).
252 Proof.
253 intros. induction points as [|[i j] points].
254 - exfalso. unfold InFinEnumC, FinSubset_ball in H.
255 contradict H; intros [z [H _]]. inversion H.
256 - destruct (Qeq_dec x i).
257 + destruct (Qeq_dec y j).
258 exists (i,j). split. left. reflexivity.
259 split; apply Qball_0; symmetry; assumption.
260 destruct IHpoints.
261 intro abs.
262 unfold InFinEnumC, FinSubset_ball in H.
263 contradict H; intros [z [zin H0]].
264 destruct zin. subst z.
265 destruct H0. simpl in H0.
266 apply Qball_0 in H0. contradiction.
267 contradict abs. exists z. split.
268 exact H. exact H0.
269 exists x0. split. right. apply H0. apply H0.
270 + destruct IHpoints.
271 intro abs.
272 unfold InFinEnumC, FinSubset_ball in H.
273 contradict H; intros [z [zin H0]].
274 destruct zin. subst z.
275 destruct H0. simpl in H.
276 apply Qball_0 in H. contradiction.
277 contradict abs. exists z. split.
278 exact H. exact H0.
279 exists x0. split. right. apply H0. apply H0.
280 Qed.
281
282 (* end hide *)
283 Section RasterizeCorrect.
284
285 (* Middles of the horizontal subdivision of the segment [[l, r]].
286 Instead of l, l + (r-l)/n, ...
287 it is l + (r-l)/2n, l + (r-l)*3/2n, ... *)
288 Let C : Q -> Q -> positive -> Z -> Q
289 := fun l r (n:positive) (i:Z) => l + (r - l) * (2 * i + 1 # 1) / (2 * Z.pos n # 1).
290
291 (* rasterize1 is used in both horizontally and vertically,
292 so it will be called for left,width and also for bottom,height. *)
293 Lemma rasterize1_error : forall l (w:Qpos) n x,
294 (l <= x <= l + proj1_sig w) ->
295 Qball ((1 #2*n) * proj1_sig w)
296 (C l (l + proj1_sig w) n (Z.min (Z.pos n -1)
297 (Z.max 0 (rasterize1 l (l+proj1_sig w) n x))))
298 x.
299 Proof.
300 clear - C.
301 intros l w n x H0.
302 destruct (Qlt_le_dec x (l+proj1_sig w)).
303 - replace (Z.min (Z.pos n -1)
304 (Z.max 0 (rasterize1 l (l + proj1_sig w) n x)))
305 with (rasterize1 l (l + proj1_sig w) n x).
306 + apply ball_sym.
307 simpl.
308 rewrite -> Qball_Qabs.
309 assert (l < l + proj1_sig w).
310 { rewrite -> Qlt_minus_iff.
311 ring_simplify.
312 exact (Qpos_ispos w). }
313 eapply Qle_trans.
314 unfold C.
315 apply (rasterize1_close H).
316 setoid_replace (l + proj1_sig w - l) with (proj1_sig w)
317 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
318 unfold Qdiv. rewrite Qmult_comm.
319 apply Qmult_le_compat_r. apply Qle_refl.
320 apply Qpos_nonneg.
321 + rewrite Z.max_r.
322 apply Z.min_case_strong.
323 intros H.
324 apply Zle_antisym; auto.
325 apply Zlt_succ_le.
326 rewrite <- Z.add_1_r.
327 replace (Z.pos n - 1 + 1)%Z with (Z.pos n) by ring.
328 apply rasterize1_boundR; auto.
329 rewrite -> Qle_minus_iff.
330 ring_simplify.
331 exact (Qpos_nonneg w).
332 reflexivity.
333 destruct H0.
334 apply rasterize1_boundL; auto.
335 apply Qle_trans with x; auto.
336 - rewrite Z.min_l.
337 setoid_replace x with (l + proj1_sig w).
338 apply ball_sym.
339 rewrite -> Qball_Qabs.
340 unfold C.
341 rewrite <- (Qmult_comm (proj1_sig w)).
342 change (1 # 2*n) with (/((2#1)*inject_Z (Z.pos n))).
343 change (2*Z.pos n #1) with ((2#1)*inject_Z (Z.pos n)).
344 replace (2 * (Z.pos n - 1) + 1)%Z with (2*Z.pos n + - 1)%Z by ring.
345 change (2*Z.pos n + -1#1) with (inject_Z (2*Z.pos n + - 1)).
346 rewrite -> Q.Zplus_Qplus.
347 rewrite -> Q.Zmult_Qmult.
348 change (inject_Z 2) with (2#1).
349 change (inject_Z (-1)) with (-1#1)%Q.
350 setoid_replace (l + proj1_sig w - (l + (l + proj1_sig w - l) * ((2#1) * inject_Z (Z.pos n) + (-1#1)) / ((2#1) * (inject_Z (Z.pos n)))))
351 with ((proj1_sig w / ((2#1) * (inject_Z (Z.pos n)))))
352 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; field; unfold Qeq; simpl; auto with *).
353 rewrite -> Qabs_pos;[apply Qle_refl|].
354 apply Qle_shift_div_l.
355 rewrite <- (Qmult_0_r (2#1)). apply Qmult_lt_l. reflexivity.
356 simpl; auto with *; unfold Qlt; simpl; auto with *.
357 rewrite Qmult_0_l.
358 exact (Qpos_nonneg w).
359 destruct H0.
360 apply Qle_antisym; auto.
361 eapply Z.le_trans;[|apply Z.le_max_r].
362 unfold rasterize1.
363 rewrite <- (Qfloor_Z (Z.pos n -1)).
364 apply Qfloor_resp_le.
365 setoid_replace x with (l+proj1_sig w).
366 setoid_replace (l + proj1_sig w - l) with (proj1_sig w)
367 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
368 unfold Qdiv.
369 rewrite <- Qmult_assoc, Qmult_inv_r, Qmult_1_r.
370 2: apply Qpos_nonzero.
371 rewrite <- Zle_Qle.
372 rewrite <- (Z.add_0_r (Z.pos n)) at 2.
373 apply Z.add_le_mono_l. discriminate.
374 apply Qle_antisym.
375 apply H0. exact q.
376 Qed.
377
378 (* Strange, we should always have b <= t in rasterize1. *)
379 Lemma switch_line_interp : forall (t b : Q) (m : positive) (j : Z),
380 (j < Z.pos m)%Z
381 -> C t b m (Z.pos m - 1- j) == C b t m j.
382 Proof.
383 intros t b m j H.
384 unfold C.
385 replace (2 * (Z.pos m -1 - j) + 1)%Z with (2 * (Z.pos m - j) - 1)%Z by ring.
386 change (2 * (Z.pos m - j) - 1 # 1)
387 with (inject_Z (2 * (Z.pos m - j) + - 1)%Z).
388 change (2*Z.pos m#1) with ((2#1)*inject_Z (Z.pos m)).
389 change ((2*j +1)#1) with (inject_Z (2*j+1)%Z).
390 do 2 rewrite -> Q.Zplus_Qplus.
391 rewrite -> Q.Zmult_Qmult.
392 change (inject_Z (-1)) with (-1#1).
393 rewrite -> Q.Zmult_Qmult.
394 change (inject_Z 2) with (2#1).
395 unfold Zminus.
396 rewrite -> Q.Zplus_Qplus.
397 change (inject_Z (-j)) with (-inject_Z j).
398 field.
399 apply Q.positive_nonzero_in_Q.
400 Qed.
401
402 Variable b l:Q.
403 Variable w h:Qpos.
404
405 Let r:=l+proj1_sig w.
406 Let t:=b+proj1_sig h.
407
408 Variable points:FinEnum Q2.
409
410 Variable n m : positive.
411
412 Let errX : Qpos := ((1#2*n)*w)%Qpos.
413 Let errY : Qpos := ((1#2*m)*h)%Qpos.
414 Let err : Qpos := Qpos_max errX errY.
415
416 Hypothesis Hf : forall (x y : Q), InFinEnumC ((x,y):ProductMS _ _) points ->
417 (l<= x <= r) /\ (b <= y <= t).
418
419
420 (** The Rasterization is close to the original enumeration,
421 ie each one is approximately included in the other,
422 within error err (Hausdorff distance).
423 To measure closeness, we use the product metric on Q2, which has
424 square balls aligned with the 2 axes. *)
425 Lemma RasterizeQ2_correct1 : forall (x y:Q),
426 @InFinEnumC (ProductMS _ _) (x,y) points ->
427 exists p, In p (CentersOfPixels (PixelizeQ2 (RasterizeQ2 points n m t l b r))
428 (l,t) (r,b))
429 /\ ball (proj1_sig err) p (x,y).
430 Proof.
431 intros x y H.
432 pose proof (Hf H) as xybound.
433 apply InFinEnumC_Qepsilon in H.
434 destruct H as [q [H H0]].
435 assert (let (i,j) := rasterize2 n m t l b r q in
436 Is_true (RasterIndex (PixelizeQ2 (RasterizeQ2 points n m t l b r))
437 (Z.to_nat i) (Z.to_nat j))).
438 { apply RasterizeQ2_in.
439 apply (in_map (fun p : Q * Q => rasterize2 n m t l b r p) points).
440 exact H. apply emptyRaster_wf.
441 apply Nat2Z.inj_lt.
442 rewrite positive_nat_Z, Z2Nat.id.
443 apply Z.lt_0_sub. ring_simplify.
444 apply (Z.lt_le_trans _ (0+1)).
445 reflexivity.
446 apply Z.add_le_mono_r.
447 apply rasterize2_bound.
448 apply Z.le_0_sub. apply Z.le_min_l.
449 apply Nat2Z.inj_lt.
450 rewrite positive_nat_Z, Z2Nat.id.
451 apply rasterize2_bound.
452 apply rasterize2_bound. }
453 pose (Z.pos m - 1 - Z.min (Z.pos m - 1) (Z.max 0 (rasterize1 b t m (snd q))))%Z
454 as i.
455 pose (Z.min (Z.pos n - 1) (Z.max 0 (rasterize1 l r n (fst q)))) as j.
456 exists ((fun (l r : Q) (n : positive) (i : Z) =>
457 l + (r - l) * (2 * i + 1 # 1) / (2 * Z.pos n # 1)) l r n
458 (Z.of_nat (Z.to_nat j)),
459 (fun (l r : Q) (n : positive) (i : Z) =>
460 l + (r - l) * (2 * i + 1 # 1) / (2 * Z.pos n # 1)) t b m
461 (Z.of_nat (Z.to_nat i))).
462 split. apply InterpRaster_correct1.
463 apply RasterizeQ2_wf. exact H1.
464 rewrite Z2Nat.id.
465 rewrite Z2Nat.id.
466 destruct H0, q.
467 split.
468 - unfold fst.
469 destruct xybound.
470 apply Qball_0 in H0.
471 unfold fst in H0. clear H2.
472 rewrite <- H0 in H3.
473 unfold j, r. rewrite <- H0. unfold fst.
474 apply ball_weak_le with (e:=((1 # 2 * n) * proj1_sig w)).
475 apply (Qpos_max_ub_l errX errY).
476 apply (@rasterize1_error l w n _ H3).
477 - unfold snd.
478 destruct xybound.
479 apply Qball_0 in H2.
480 unfold snd in H2. clear H0.
481 rewrite <- H2 in H4.
482 unfold i, t. rewrite <- H2. unfold snd.
483 apply ball_weak_le with (e:=((1 # 2 * m) * proj1_sig h)).
484 apply (Qpos_max_ub_r errX errY).
485 pose proof (@rasterize1_error b h m _ H4).
486 rewrite <- switch_line_interp in H0.
487 apply H0.
488 apply rasterize2_bound.
489 - unfold i. apply Z.le_0_sub.
490 apply Z.le_min_l.
491 - apply rasterize2_bound.
492 Qed.
493
494 Lemma RasterizeQ2_correct2 : forall (x y : Q),
495 @InFinEnumC (ProductMS _ _) (x,y)
496 (CentersOfPixels (PixelizeQ2 (RasterizeQ2 points n m t l b r))
497 (l,t) (r,b))
498 -> exists p, In p points /\ ball (proj1_sig err) p (x,y).
499 Proof.
500 intros x y H.
501 apply InFinEnumC_Qepsilon in H.
502 destruct H as [q [qin qeq]].
503 destruct q as [qx qy].
504 destruct (InterpRaster_correct2
505 _ _ _ _ _ _ _ (RasterizeQ2_wf points n m t l b r) qin)
506 as [[j i] [Hij [Hx' Hy']]].
507 unfold fst, snd in Hij.
508 apply RasterizeQ2_in_recip in Hij.
509 2: apply emptyRaster_wf.
510 destruct Hij.
511 2: unfold Is_true in H; rewrite (emptyRasterEmpty n m j i) in H; contradiction.
512 unfold RasterizeQ2 in H.
513 rewrite map_map in H.
514 apply In_nth with (d:=(fun x : Q * Q =>
515 (Z.to_nat (fst (rasterize2 n m t l b r x)),
516 Z.to_nat (snd (rasterize2 n m t l b r x))))(0,0)) in H.
517 destruct H as [k [kin H]].
518 rewrite map_length in kin.
519 rewrite (map_nth (fun x : Q * Q =>
520 (Z.to_nat (fst (rasterize2 n m t l b r x)),
521 Z.to_nat (snd (rasterize2 n m t l b r x))))) in H.
522 exists (nth k points (0,0)). split.
523 apply nth_In. exact kin.
524 unfold snd in Hx'.
525 unfold fst in Hy'.
526 assert (Z.to_nat (fst (rasterize2 n m t l b r (nth k points (0, 0)))) = j
527 /\ Z.to_nat (snd (rasterize2 n m t l b r (nth k points (0, 0)))) = i).
528 { inversion H. split; reflexivity. }
529 clear H. destruct H0.
530 rewrite <- qeq. clear qeq x y.
531 specialize (@Hf (fst (nth k points (0,0))) (snd (nth k points (0,0)))).
532 rewrite <- surjective_pairing in Hf.
533 specialize (@Hf (InFinEnumC_weaken _ _ points (nth_In _ _ kin))).
534 split.
535 - unfold rasterize2, snd in H0. clear H.
536 simpl (fst (qx,qy)).
537 rewrite Hx', <- H0.
538 rewrite Z2Nat.id.
539 apply ball_weak_le with (e:=((1 # 2 * n) * proj1_sig w)).
540 apply (Qpos_max_ub_l errX errY).
541 apply ball_sym.
542 apply rasterize1_error.
543 apply Hf. apply rasterize2_bound.
544 - unfold rasterize2, fst in H. clear H0 Hx'.
545 simpl (snd (qx,qy)).
546 rewrite Hy', <- H.
547 apply ball_weak_le with (e:=((1 # 2 * m) * proj1_sig h)).
548 apply (Qpos_max_ub_r errX errY).
549 pose proof (@rasterize1_error b h m _ (proj2 Hf)).
550 rewrite <- switch_line_interp in H0.
551 apply ball_sym.
552 rewrite Z2Nat.id.
553 apply H0.
554 apply Z.le_0_sub, Z.le_min_l.
555 apply (Z.le_lt_trans _ _ _ (Z.le_min_l _ _)).
556 rewrite <- (Z.add_0_r (Z.pos m)) at 2.
557 apply Z.add_lt_mono_l. reflexivity.
558 Qed.
559
560 Lemma RasterizeQ2_correct :
561 ball (proj1_sig err)
562 (CentersOfPixels (PixelizeQ2 (RasterizeQ2 points n m t l b r)) (l,t) (r,b))
563 points.
564 Proof.
565 split. apply Qpos_nonneg.
566 split; intros [x y] Hx.
567 - pose proof (RasterizeQ2_correct2 Hx).
568 intro abs.
569 contradict H; intros [z [Hz0 Hz1]].
570 specialize (abs z). contradict abs.
571 split.
572 apply InFinEnumC_weaken, Hz0.
573 apply ball_sym, Hz1.
574 - intro abs.
575 pose proof (RasterizeQ2_correct1 Hx).
576 contradict H; intros [z [Hz0 Hz1]].
577 specialize (abs z). contradict abs.
578 split.
579 apply InFinEnumC_weaken, Hz0.
580 apply ball_sym, Hz1.
581 Qed.
582
583 End RasterizeCorrect.