Prepare Maps for Processing

Posted On September 9, 2011

Filed under ArcGIS

Comments Dropped one response

First, two ArcGIS shapefiles, one for the terrain and one for buildings, need to be merged. Then we need to create polygonal surface mesh which will be used to create 3D volume mesh (much later).

Parts of this guide are taken from http://dmg.caup.washington.edu/Reports/GIS-to-3DS/index.html. Some minor details are changed.

  1. Download sample data provided . Unzip the files.
  2. Start ArcMap.
  3. Click the Add Layer button.
  4. In the Add Data menu, highlight and select both building_sample.shp and contour_sample.shp. Both of these shapefiles will be added to the Layers Manager (on the left of the screen) and appear in the main viewing window. You may want to drag the building_sample layer above the contour_sample layer so that the buildings appear above the contour lines.
  5.  Since the area is very large, we will want to work with a smaller portion of the map. So we need to crop the area of the map we want to work with:
    1. Click on the contour_sample layer. Use the selection tool to highlight the areas you want to save into a separate shapefile.
    2. Right-click the layer name in the layers browser. Under the ‘Data’ menu, select ‘Export Data’
    3. Give the shapefile a new name and save it. When prompted, add the new layer to the current map and remove the old contour_sample layer (right-click the layer name and then Remove)
    4. Now click on the building_sample layer. This time, you can select only the buildings that intersect the contour lines. Under the ‘Selection menu’, click ‘Select By Location. In the ‘Selection By Location’ menu, select features from the building_sample layer that ‘intersect’ the features in the cropped contour layer.
    5. Once the buildings are selected, simply repeat the ‘Export Data’ instructions in steps 1,2 and 3. (above).
    6. Repeat this process with each layer you wish to work with (if you are doing only buildings and terrain, then you only need to do this twice.)
      It is important that each layer be saved separately into a shapefile (for this example, terrain in one shapefile, building footprints in another).
  6. Convert terrain to 3D.  The general idea is to convert the contour lines to a TIN (Triangulated Irregular Network) . However, simply converting to a TIN  produces overly detailed geometries in which every point on every contour is connect to every other contour line. This is unnecessary, but there is a workaround which requires converting the contour to a TIN, then to a Raster format, then back to a TIN, in the process loosing some of the detail, but preserving the terrain characteristics.
    1. Click and highlight the terrain crop layer in the Layers manager on the left.
    2. In ‘Toolbox’, under the ‘3D Analyst’ , ‘Create/Modify TIN,’ select ‘Create TIN from Features’
    3. In the ‘Create TIN from Features’ menu, check the terrain crop layer, verify that the ‘Height source’ is set to ELEV, and give the tin a new name.
    4. The resulting TIN should appear on the screen. Remove the old terrain crop layer from the Layers manager (right-click on the layer name and select ‘Remove’).
    5. Click and highlight the new terrain crop tin layer in the Layers manager
    6. Under the ‘3D Analyst’ Toolbar, under ‘Convert,’ select ‘TIN to Raster’
    7. In the ‘Convert TIN to Raster’ menu, set the ‘Cell size’ to a setting that gives a reasonable number (5.37 is good) of Rows and Columns. There is no hard and fast rule for this, but something that is under 1000 Rows and 1000 Columns is safe. Generally speaking, the smaller the cell size, the more detailed the terrain. Next, give the new raster layer a name (such as contour_rast)
    8. The resulting Raster image should appear on the screen. Remove the old contour tin from the Layers manager (right-click on the layer name and select ‘Remove’).
    9. Click and highlight the contour_rast layer in the Scene Layers manager.
    10. Under the ‘3D Analyst’ Tools, under ‘Convert,’ select ‘Raster to TIN’
    11. In the ‘Convert Raster to TIN’ menu, set the ‘Z tolerance’ to a reasonable setting…again, there is no hard and fast rule for this, but something that is between 5 and 10 ought to work. The smaller the Z unit value, the more points in the TIN. Next, give the new TIN layer a name (such as contour_tin2)
    12. The resulting TIN should appear on the screen. Even though the TIN is less detailed version of the original contour, the features should be accurate enough for terrain modeling.
    13. Remove the old contour_rast layer from the Scene (right-click on the layer name and select Remove).

Create Terrain Triangles

Next, we need to convert tin layer to polygons (triangles). Do this by selecting (in the tool box) ‘3D Analyst Tools’ -> ‘Conversion’ -> ‘From TIN’ -> ‘TIN Triangle’. Save the new shapefile. From Layers manager, remove all files except for the terrain triangles and building footprints. Move building footprints above terrain triangles so that the buildings appear of top of the triangles.

Merge Shapefiles

We will now create one shapefile that contains both buildings and terrain triangles. The buildings will appear as holes in the terrain triangles (which will create some non-triangle polygons).

From the tool box select ‘Analysis Tools’->’Overlay’->’Erase’.  In ‘Input Features’ field pick the terrain triangles. In ‘Erase Features’ pick building footprints file. Name the resulting file and commit.

To associate this new file (containing cut-out buildings) with the buildings file, perform a union: from the tool box select ‘Analysis Tools’->’Overlay’->’Union’. Name the file and save.

All polygons created in this manner are oriented counter-clockwise.

Using LAPACK: QR factorization with Wilkinson shift

Posted On August 23, 2011

Filed under Code+Math

Comments Dropped leave a response

#define _USE_MATH_DEFINES
#define eps 1.0e-12
#define mz 1.0e-15
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <time.h>
#include <ctime>
using namespace std;
void qralgShift(vector<double>* matrix, int dim, vector<double>* resids);
//qr factorization
extern “C” void dgeqrf_(const int *M, const int *N, double *A, const int *lda,
double *tau, double *work, int *lwork, int *info);

//return new matrix in matrix
//return residuals in resids
//to get number of qr factorizations, look at how many resids there are
//shift is Wilkinson shift
void qralgShift(vector* matrix, int dim, vector* resids)
{
int i,j,k,l;

//stuff for lapack qr function
int M = dim; //number of rows
int N = dim; //number of cols
double *A;
int lda = M; //the leading dimension of the array A
double *tau; //min(M,N)
double *work;
int lwork = N;
int info;

A = (double*)malloc(M*N*sizeof(double));
tau = (double*)malloc(M*sizeof(double));
work = (double*)malloc(lwork*sizeof(double));

vectorR(dim*dim);
vectorQ(dim*dim);
vectornewQ(dim*dim);
vectorHQ(dim*dim);
vectorv(dim);
vector vvt(dim*dim);
vectorH(dim*dim);
double mu, sigma, SIG;
double resid;

double a, b, c,d,e;

do
{
//determine shift
// lower corner is:
// a(m-1) b(m-1)
// b(m-1) a(m)

//(a(m-1)-a(m))/2
sigma = 0.5*((*matrix)[(dim-2)*dim + (dim-2)] – (*matrix)[(dim-1)*dim + (dim-1)]);
SIG = -1.0;
if(sigma > mz)
SIG = 1.0;

// a(m) – (( sign(sigma) * b(m-1)^2) / (|sigma| + sqrt( sigma^2 + b(m-1)^2) )
mu = (*matrix)[(dim-1)*dim + (dim-1)] – ((SIG * (*matrix)[(dim-1)*dim + (dim-2)] * (*matrix)[(dim-1)*dim + (dim-2)]) / (fabs(sigma) + sqrt((sigma*sigma) + ((*matrix)[(dim-1)*dim + (dim-2)] * (*matrix)[(dim-1)*dim + (dim-2)]))));

//subtract shift from diagonals (A-muI)
for(j=0; j<dim; j++)//rows
{
for(k=0; k<dim; k++)//cols
{
if(j==k)
{
(*matrix)[j*dim+k] -= mu;
}
}
}

//printMatrix(dim, dim, &(*matrix));

//copy matrix into A, col-major; this is so I can give the matrix to the qr alg
for(i=0; i<dim; i++) //row matrix, col A
{
for(j=0; j= n);
//**************************************************************
R.assign(dim*dim,0.0); //initialize R to zeros
//copy A diagonal and above in R (this is R)
for(i=0; i<dim; i++) //row matrix, col A
{
for(j=0; j=i)
R[i*dim+j] = A[j*dim+i];
}
}
//I have R!

//**************************************************************
//Q: the elements below the diagonal,
//with the array TAU, represent the orthogonal matrix Q as a
//product of min(m,n) elementary reflectors
//The matrix Q is represented as a product of elementary reflectors
//Q = H(1) H(2) . . . H(k), where k = min(m,n).
//Each H(i) has the form
//H(i) = I – tau * v * vT
//where tau is a real scalar, and v is a real vector with
//v(1:i-1) = 0 and v(i) = 1; v(i+1:m) is stored on exit in A(i+1:m,i),
//and tau in TAU(i).
//**************************************************************
Q.assign(dim*dim, 0.0);
//copy A below diagonal in Q
for(i=0; i<dim; i++) //row matrix, col A
{
for(j=0; j<dim; j++) //col matrix, row A
{
if(j==i)
Q[i*dim+j] = 1.0;
if(j<i)
Q[i*dim+j] = A[j*dim+i];
}
}

//now cols of Q are my vectors v
for(i=0; i<dim; i++)
{
//get ith v
for(j=0; j<dim; j++)
v[j] = Q[j*dim+i];

//find vvT
for(j=0; j<dim; j++)
{
for(k=0; k<dim; k++)
{
vvt[j*dim+k] = v[j]*v[k];
}
}

//find I – tau[i]* vvT
H.assign(dim*dim, 0.0);
for(j=0; j<dim; j++)//rows
{
for(k=0; k<dim; k++)//cols
{
if(j==k)
{
H[j*dim+k] = 1.0 – tau[i]*vvt[j*dim+k];
}
else
{
H[j*dim+k] = -tau[i]*vvt[j*dim+k];
}

}
}

if(i==0)
{
//copy H into newQ
for(j=0; j<dim*dim; j++)
newQ[j] = H[j];
}
else
{
//multiply newQ and H
for(j=0; j<dim; j++)
{
for(k=0; k<dim; k++)
{
HQ[j*dim+k] = 0.0;
for(l=0; l<dim; l++)
{
HQ[j*dim+k] += newQ[j*dim+l] * H[l*dim+k];
}
}
}
//copy HQ into newQ
for(j=0; j<dim*dim; j++)
newQ[j] = HQ[j];
}

}
//now I have Q!

//newQ*R should give A – it does
//R*newQ is the next qr matrix
for(j=0; j<dim; j++)
{
for(k=0; k<dim; k++)
{
(*matrix)[j*dim+k] = 0.0;
for(l=0; l<dim; l++)
{
(*matrix)[j*dim+k] += R[j*dim+l] * newQ[l*dim+k];
}
}
}

//add shift to diagonals (A+muI)
for(j=0; j<dim; j++)//rows
{
for(k=0; k eps);

free (A);
}

Shooting Method

Posted On March 19, 2011

Filed under Code+Math

Comments Dropped leave a response

A nice concise explanation of BVPs and the shooting method + the algorithm for the same.

Shooting Method PDF

LAPACK on Windows with Visual Studio 2010

Posted On February 11, 2011

Filed under Code+Math, CS

Comments Dropped 2 responses

Scenario: you are pulling your hair out and are about to start punching your monitor (don’t! you’ll regret it) because you found this website:
http://icl.cs.utk.edu/lapack-for-windows/lapack/,
you followed all the steps, and you are still getting love letters from your compiler / linker saying “error LNK2001 unresolved external symbol” (or something equally frustrating).

Solution: If you are not going to be solving huge matrix systems, you do not care about performance, and pre-compiled Windows versions BLAS and Lapack are sufficient for you, read on.

If you happened to follow the instructions in that Lapack link above, and managed to trick Win7 into letting you paste BLAS.lib in the Windows/System32 directory, go ahead and delete it (you don’t want junk floating around, do you?). Also, delete all the stuff you downloaded from the website. Delete the project you were trying to compile too! Start over!

  1. Download the most recent stable version of Armadillo
  2. Create an empty C++ solution in VS 2010.
  3. Create a source code file, paste the tutorial code
  4. Add extern “C” in front of the function prototypes: void dgesv_( ) —– >    extern “C” void dgesv_( )
  5. In project properties, go to Configuration Properties -> Linker -> Input
    In Additional Dependencies add lapack_win32_MT.lib;blas_win32_MT.lib;
  6. Untar your Armadillo download. Go to armadillo-1.0.2\examples\lib_win32
  7. From lib_win32 copy lapack_win32_MT.lib and .dll and blas_win32_MT.lib and .dll and paste them in the same project directory where your source (.cpp) file is.
  8. Compile, Run… (the solution is -0.661082, 9.456125, -16.014625).

Taa-dah!

Several notes:

  1. If you want to put your libraries in a separate directory and set the linker directories, go ahead. This is obviously the most basic setup.
  2. This should work with VS 2008 and Windows XP and later (32-bit). You might have problems with the pre-compiled libraries. If you happen to encounter problems and still do not want to make your own compiles of Lapack and BLAS, Armadillo website provides additional sources for the pre-compiled versions of Lapack and BLAS at the bottom of this page.

Reading Esri Shapefile in VB.NET

Posted On December 7, 2010

Filed under ArcGIS

Comments Dropped leave a response

I am going to use VB.NET for most of my ArcGIS experiments because almost all of the nice, finished, detailed examples of ArcGIS code are in VB.NET. At this point, I really do not want to deal with syntax issues.

Incidentally, while aimlessly roaming esri.com’s dominion, I came across ShapeFile Read/Write OCX & DLL for VB6 and .NET. Neat, I thought, let me see what you have inside.

The help file explains how you are to use the contents of this package (it is actually well documented ^.^). The top of the Help tree, where it says Contents, is a good point to start reading.

Pay attention! There are 3 things inside that zip file that you can use. One ocx and 2 dll files. You should use the ocx only if you intend to have forms in your .NET project (which I don’t). The dll file that does not have the word NET in it is the one for VB6.

Setup

  1. Make a new Visual Studio VB.NET console project.
  2. Copy ArcViewShapeFileDLLNET.dll somewhere inside your project folder (this is just the way I do it, it could really be anywhere).  Right click on the project in the VS Solution Tree and add a reference to this dll
  3. Obtain a shapefile (you can hunt down your own or steal from somebody). I am assuming that you will be running in the debug mode, so copy all 3 parts of the shapefile (.shp, .shx, .dbf)  to “ProjectName/bin/Debug”. For all the details on the structure of shape files, check out Esri’s technical description.

Now you are ready to follow an example or two from the Help file to do something with the shapefile. Since the title of this post is “Reading Esri Shapefile”, I recommend you start with the example that deals with reading.

In order to access the library functions, you will need to create an object of its type. So yeah, don’t forget to do that:

Dim MyShape As New ArcViewShapeFileDLL.ShapeFiles

WTF is a raster image?

Posted On November 4, 2010

Filed under CS

Comments Dropped leave a response

Scenario: you do not know what “rasterize” means.
Solution: read the text below.

A raster or a bitmap is a representation of a digital image. The image is represented as bits which translate into pixels on the screen. The pixels form points of color which create a complete image.

When you rasterize an image, the image is converter into pixels. Each pixel is assigned a specific RGB color value which determines its color. The values available to express each color in RGB spectrum go from 0 to 256.

When you view a raster image, the pixels usually smooth out, and you see a photograph or a drawing. When you zoom in on the image, the pixels become apparent. Depending on resolution of the image, some raster images can be zoomed in to very large sizes, while others quickly become pixelized and difficult to see. Images with large resolution will result in large image files.

Resolution refers to the number of pixels per inch (PPI) or dots per inch (DPI) in the image. The higher the resolution, the greater the number of pixels, and the larger the size of the file. Larger number of pixels allows for a greater gradation of color and quality of image, which will translate better as the image is enlarged. For small images which do not need to be enlarged, a low DPI is sufficient.

The alternative to a rasterized image is a vector image. A vector image uses a mathematical formula to draw a picture. A vector image defines points and the paths that connect them to form a digital representation of an image. Because the mathematical formulas do not care about the size, a vector image can be enlarged and still preserve smooth edges.

However, vector images have their limitations and are most suitable for topography, line art, illustrations, and such. Raster images are the best choice for photography and shaded drawings.

Checking Partial Derivatives with Finite Differences

Posted On October 21, 2010

Filed under Code+Math

Comments Dropped leave a response

Scenario: your code is computing partial derivatives (gradients) of some function F with respect to one or more variables. You are getting numbers out, but you are not sure if they are correct.
Solution: use finite-difference approximations to check partial derivatives

  1. Take the variable with respect to which you are computing partial derivative (if you have several, then pick one) – call it q.
  2. Pick a constant (call it ε). It should be a value from e-4 to e-8.
  3. Change the value of q to q+ε (perturb up). Compute value of your function F using this new q_up. Call it F_up.
  4. Change the value of q to q-ε (perturb down). Compute value of your function F using q_down. Call it F_down.
  5. Now the central finite difference approximation of the partial derivative for the variable q is (F_up-F_down) / (2.0*epsilon).
    Compare this with the number your code is producing  (partial derivative of q w.r.t. F). The approximation should be within 10% of your code’s value, unless the derivatives are close to zero (machine zero).
    If your numbers are very different,  try changing the value of ε (if you used e-5, try using e-4 or e-6).
    If you cannot get your numbers to agree, then make yourself some coffee and start looking for bugs.

References: Gill, P.E., Murray, W. and Wright, M.H. (1981) Practical Optimization