source: subversion/applications/rendering/gosmore/density6.cpp @ 19882

Last change on this file since 19882 was 19882, checked in by nic, 10 years ago

Windows: Add Nullsoft Installer script
Windows: Add map update capability
Check in voice commands
Generate voice/visual commands at splits, e.g. exiting motorways
Add voice output support under Linux.
Update bboxes.
Add program for generating bboxes.
WinCE: Removing wince from David's ARCH tag. What is the right one ??

  • Property svn:executable set to *
File size: 8.1 KB
Line 
1// Finds rectangles that cover the planet. Requires density.csv, which is created by
2// make CFLAGS="-DMKDENSITY_CSV -O2" && bzcat planet.osm.bz2 | ./gosmore sortRelations
3// g++ -O2 density6.cpp && time nice -n 19 ./a.out >density.txt
4// Run time is approximately 5 minutes and will require 5 GB of RAM
5
6#include <string.h>
7#include <stdlib.h>
8#include <stdio.h>
9#include <vector>
10#include <queue>
11#include <assert.h>
12using namespace::std;
13
14int b[4000000][8], cnt = 0;
15
16int BCmp (int *a, int *b)
17{
18  return *a - *b;
19}
20
21struct state {
22  long long nCovered;
23  int **s, **best, c;
24  state () {}
25};
26
27bool operator < (const state &a, const state &b)
28{
29//  return a.c == 0 ? false : b.c == 0 ? true : a.nCovered / a.c < b.nCovered / b.c;
30  return (a.nCovered + 80000000) / (a.c + 15) < (b.nCovered + 80000000) / (b.c + 15);
31}
32
33int IPtrCmp (int **a, int **b)
34{
35  return **b - **a;
36}
37
38vector<state> states;
39priority_queue<state> que;
40vector<int*> active;
41
42int dp[1025][1025], target;
43
44#define I(a,b,e,d) (dp[a+1][b+1] - dp[e][b+1] - dp[a+1][d] + dp[e][d])
45#define M 12000000
46
47void Try (int col)
48{
49  while (states.size () < 40 && !que.empty ()) {
50    //printf ("%lld %d\n", que.top ().nCovered, states.size ());
51    int rh[1024], i, j, **s = que.top ().s, l, c = que.top ().c;
52    int **best = que.top ().best, nCovered = que.top ().nCovered;
53          for (l = 0; best[l]; l++) {}
54          assert (l ==c);
55    memset (rh, 0, sizeof (rh));
56    for (i = 0, l = 0; s[i]; i++) {
57      for (j = s[i][1]; j < s[i][3]; j++) {
58        if (rh[j] < s[i][2]) rh[j] = s[i][2];
59      }
60      if (s[i][2] > col) s[l++] = s[i]; // Remove rectangles we passed.
61    }
62    s[l] = NULL; // Remove rectangles we passed.
63    for (i = 0; i < 1024 && rh[i] > col; i++) {}
64    if (i == 1024) { // The state covers this column
65      states.push_back (state ()); //que.top ());
66      memcpy (&states.back (), &que.top (), sizeof (que.top ()));
67//          for (l = 0; states.back().best[l]; l++) {}
68//          assert (l ==states.back().c);
69     
70/*      for (j = states.size () - 1; j >= 0; j--) {
71            for (l = 0; states[j].best[l]; l++) {}
72            assert (l ==states[j].c);
73      }*/
74    }
75    //printf ("%d\n", i);
76//          assert (states.empty () || states[0].best[0]);
77    que.pop ();
78//          assert (states.empty () || states[0].best[0]);
79    for (j = 0; i < 1024 && j < active.size (); j++) { // 'i' is the first row not covered.
80      for (l = 0x3fffff; l >= active.size (); l/=2) {}
81      int *a = active[j < l ? j ^ (nCovered & l) : j];
82      if (a[1] <= i && i < a[3]) {
83        int newNcov = nCovered;
84        for (l = a[1]; l < a[3]; l++) {
85          if (rh[l] < a[2]) newNcov += I (l, a[2] - 1, l,
86            (rh[l] < col ? col : rh[l]));
87        }
88        assert (newNcov < nCovered + 14000000);
89        assert (newNcov >= I (1023, col - 1, 0, 0));
90        //assert (a[2] > 800 ||newNcov <= I (1023, a[2] + 168, 0, 0));
91        if (newNcov > nCovered + (col < 700 ? 2000000: col<780 ? 1000000: 500000)) { // (c + 1) * 1000000) { //target) {
92          state nxt;
93          for (l = 0; s[l]; l++) {}
94          nxt.s = new int *[l+2];//(int**) malloc ((l + 2) * sizeof (*s));
95          nxt.s[0] = a;
96          memcpy (nxt.s + 1, s, (l + 1) * sizeof (*s));
97
98          for (l = 0; best[l]; l++) {}
99          assert (l ==c);
100          nxt.best = new int *[l+2]; //(int**) malloc ((l + 2) * sizeof (*s));
101          nxt.best[0] = a;
102          memcpy (nxt.best + 1, best, (l + 1) * sizeof (*s));
103/*          nxt.best = new int*[1];
104          nxt.best[0] = NULL;*/
105          nxt.c = c + 1;
106          nxt.nCovered = newNcov;
107          //printf ("push %lld\n", nxt.nCovered);
108//          for (l = 0; nxt.best[l]; l++) {}
109//          assert (l ==nxt.c);
110//          assert (states.empty () || states[0].best[0]);
111          que.push (nxt);
112//          assert (states.empty () || states[0].best[0]);
113        }
114      }
115    } // Look for a bbox that can cover the gap.
116    if (i < 1024) delete s; //free (s);
117//          assert (states.empty () || (states[0].best[0] && best != states[0].best));
118    if (i < 1024) delete best; //free (best);
119/*          assert (states.empty () || states[0].best[0]);
120    for (j = states.size () - 1; j >= 0; j--) {
121          for (l = 0; states[j].best[l]; l++) {}
122          assert (l ==states[j].c);
123    }*/
124  } // While creating new states
125  for (; !que.empty (); que.pop ()) {
126    delete que.top().s; //free (que.top ().s);
127    delete que.top().best;//free (que.top ().best);
128  }
129}
130
131main ()
132{
133  FILE *in = fopen ("density.csv", "r");
134  FILE *bf = fopen ("b.bin", "r+");
135  if (!bf) bf = fopen ("b.bin", "w");
136//  memset (c, 0, sizeof (c));
137//  memset (dc, 0, sizeof (dc));
138  int d, i, j, k, l;
139  #if 1
140  for (i = 0; i < 1025; i++) dp[i][0] = dp[0][i] = 0;
141  for (i = 0; i < 1024; i++) {
142    for (j = 0; j < 1024; j++) {
143      fscanf (in, j == 1023 ? "%d\n" : "%d ", &d);
144      dp[i+1][j+1] = d + dp[i][j+1] + dp[i+1][j] - dp[i][j];
145    }
146  }
147  #endif
148  //printf ("%d\n", dp[1024][1024]);
149#if 1
150#define O 3
151  for (i = 0; i < 1024; i++) {
152    for (j = 0; j < 1024; j++) {
153      for (k = i, l = 1023; k < 1024; k++) {
154        for (; l >= j && I (l, k, j, i) > M; l--) {}
155        if (l >= j && // Area > 0
156            (i == 0 || I (l, k, j, i - 1) > M) && // Not expandable Westwards
157            (j == 0 || I (l, k, j - 1, i) > M) && // Not expandable Northwards
158            (k == 1023 || I (l, k + 1, j, i) > M)) { // Not expandable Eastwards
159          if ((l >= 1024-O*2 || j < O*2 || l >= j + O*2) && 
160              (k >= 1024-O*2 || i < O*2 || k >= i + O*2)) {
161            b[cnt][0] = i < (k - i + O*9)/11 ? i : i + (k - i + O*9)/110;
162            b[cnt][1] = j < (l - j + O*9)/11 ? j : j + (l - j + O*9)/110;
163            b[cnt][2] = k > 1023 - (k - i + O*9)/11 ? k+1 : k + 1 - (k - i + O*9)/110;
164            b[cnt][3] = l > 1023 - (l - j + O*9)/11 ? l+1 : l + 1 - (l - j + O*9)/110;
165/*            b[cnt][0] = i;
166            b[cnt][1] = j;
167            b[cnt][2] = k + 1;
168            b[cnt][3] = l + 1;*/
169            b[cnt][4] = i;
170            b[cnt][5] = j;
171            b[cnt][6] = k + 1;
172            b[cnt++][7] = l + 1;
173          }
174          //printf ("%4d %4d %4d %4d %d\n", i, j, k, l, I (l, k, j, i));
175        }
176      }
177    }
178  }
179  qsort (b, cnt, sizeof (b[0]), (int (*)(const void *, const void *)) BCmp);
180  fwrite (b, cnt, sizeof (b[0]), bf);
181#else 
182  cnt = fread (b, sizeof (b[0]), sizeof (b) / sizeof (b[0]), bf);
183#endif
184  fprintf (stderr, "%d bboxes\n", cnt);
185  states.push_back (state ());
186  states.back ().s = new int*[1];//(int**) calloc (sizeof (*states.back ().s), 1);
187  states.back ().s[0] = NULL;
188  states.back ().best = new int*[1]; //(int**) calloc (sizeof (*states.back ().best), 1);
189  states.back ().best[0] = NULL;
190  states.back ().nCovered = 0;
191  states.back ().c = 0;
192  for (i = 0, j = 0; i < 1024 && !states.empty (); i++) {
193    for (;j < cnt && b[j][0] <= i; j++) active.push_back (&b[j][0]);
194    target = 0; //10000000 / (state.size () + 3);
195    for (k = 0; k < states.size (); k++) {
196      target += (states[k].nCovered + 12000000 + states.size()*5000) / (states[k].c + 1) /
197        states.size ();
198      //printf ("%d %d\n", states[k].nCovered,
199    }
200    fprintf (stderr, "%4d %d active, %d states %d %d\n", i, active.size (), states.size (),
201      target, states[0].c);
202    for (k = states.size () - 1; k >= 0; k--) {
203      for (l = 0; states[k].s[l] && states[k].s[l][2] > i; l++) {}
204      if (states[k].s[l] || l == 0 /* bootstrap */) {
205        que.push (states[k]);
206        memcpy (&states[k], &states.back (), sizeof (states[k]));
207        states.pop_back ();
208      }
209    }
210    Try (i);
211/*    for (k = states.size () - 1; k >= 0; k--) {
212          for (l = 0; states[k].best[l]; l++) {}
213          assert (l ==states[k].c);
214    }*/
215    for (k = active.size () - 1; k >= 0; k--) {
216      if (active[k][2] <= i + 1) {
217        active[k] = active.back();
218        active.pop_back ();
219      }
220    }
221  }
222  for (i = 1, j = 0; i < states.size (); i++) {
223    if (states[i].c < states[j].c) j = i;
224  }
225  fprintf (stderr, "%d rectangles\n", states[j].c);
226  for (i = 0; states[j].best[i]; i++) {
227    printf ("%d %d %d %d\n", states[j].best[i][4], states[j].best[i][5],
228      states[j].best[i][6], states[j].best[i][7]);
229  }
230 
231}
Note: See TracBrowser for help on using the repository browser.