| 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. |