Cartography and USGS — Fake Building Footprints in PostGIS now with distance operator (part 2)

In a previous couple of posts (this one, and this one), we dealt with point rotations, first with bounding box searches, and then with nominal use of operators.

First we create a function to do our angle calculations, then use select to loop through all the records and do the calculations.

Within our function, first we find our first (in this case) five nearest streets using our distance operator , based on bounding boxes, then we further order by ST_Distance, with a LIMIT 1 to get just the closest street. By the way, this is about twice as fast as the last approach.

And our new code:

CREATE OR REPLACE FUNCTION angle_to_street (geometry) RETURNS double precision AS $$

WITH index_query as
                (SELECT ST_Distance($1,road.geom) as dist,
                                degrees(ST_Azimuth($1, ST_ClosestPoint($1, road.geom))) as azimuth
                FROM street_centerlines As road
                ORDER BY $1 <#> road.geom limit 5)

SELECT azimuth
                FROM index_query
                ORDER BY dist
LIMIT 1;

$$ LANGUAGE SQL;

DROP TABLE IF EXISTS address_points_rot;
CREATE TABLE address_points_rot AS

                SELECT addr.*, angle_to_street(addr.geom)
                FROM
                                address_points addr;

I have to credit Alexandre Neto with much of the code for this solution.

Going deeper into web cartography: future=past? (and Swiss cartographic genius)

My favorite cartography book is Eduard Imhof’s Cartographic Relief Presentation.  A few years back I picked this book up (translated to English) from ESRI press for $75 if memory serves me.  Now it can be gotten for much cheaper.

Not created in GeoServer (nor TileMill– from Imhof’s book)

Imhof spends a lot of time on feature simplification and separation, a problem which keeps me up at night.  For example, if you have a lot of overlapping and/or touching contours, what are the local distortions and simplifications that can be done to enhance map readability?

Cartographic representation choices with overlapping and tightly packed contours, also from Cartographic Relief Presentation

This problem applies to other overlapping features, such as a road following a river, where at a given scale one might not distinguish between the two, so we exaggerate their differences, in this case, while maintaining their basic topology.

I’ve played with this problem before, but now I’m considering a new approach.  I pinged Martin Davis of JTS fame for some advice.  He suggested using force directed layout to solve this problem, much as he does in JTS Test Builder for magnifying/investigating topology.

I don’t know yet where or how (if) I’ll implement this, but it’s an interesting an potentially solvable problem.  Now where to work on this in the stack– in PostGIS, because I know it best, in the renderer (GeoServer) where I’ll be swimming in Java of a level I don’t have a chance, or in the browser/client, where there are already some examples written in Javascript… .

Cartography and USGS — Fake Building Footprints in PostGIS now with distance operator

In a previous post (I feel like I say that a lot), I wrote about rotating address points to match nearby roads in replicate the effect of USGS quads that represented small buildings with little squares that followed the nearby road alignment.

The function was effective:

ALTER TABLE jstein.address_points_all ADD COLUMN azimuth integer;
UPDATE jstein.address_points_all addr
SET azimuth = degrees(ST_Azimuth(addr.the_geom, ST_ClosestPoint(road.the_geom, addr.the_geom)))
FROM jstein.street_centerlines road;

but deadly slow when applied to all 500,000 address points. And so we iterate. First, I’ll show you our reasonably fast, but elegantly written solution. Later I’ll have a post on our very fast, but somewhat hackerish approach.

A reminder of our target aesthetic:

And our new code:

CREATE TABLE address_points_rot AS
WITH index_query AS
(
  SELECT
    addr.*, ST_Distance(addr.the_geom, road.the_geom) AS distance,
    degrees(ST_Azimuth(addr.the_geom, ST_ClosestPoint(road.the_geom, addr.the_geom))) as azimuth
  FROM address_pointssub as addr, street_centerlines as road
  WHERE ST_DWithin(addr.the_geom, road.the_geom, 2000) = true
  ORDER BY addr.the_geom <-> road.the_geom
)

SELECT DISTINCT ON(cartodb_id) * FROM index_query ORDER BY gid, distance

In the interest of full disclosure, I stole the structure of this from Paul Ramsey’s post on K Nearest Neighbor searches in PostGIS. AFAIK, you need Postgresql 9.1 and Postgis 2.0 or later to do this… . For 500,000 points this took 16 minutes. Narrowing that search distance would help a lot. I suspect there is a much better way to structure this using true KNN for each point, but my SQL-fu failed me here… . Suggestions welcome.

Cartography and USGS — Fake Building Footprints in PostGIS now with distance operator

Quick and fun post tonight.  Remember in USGS quads all the little building footprints that represented civilization?  We (me and my colleague John Stein) were contemplating how to pull off something similar with address points.  Here was our first attempt:

It looks ok, but may be a little crude to be considered cartography (click on it to see it bigger– you’ll see those buildings don’t look quite right… ).  So, what we wanted to do of course was to rotate these buildings relative to the road network.  With ST_ClosestPoint in PostGIS (1.5 and beyond) this is easier than advertised:

ALTER TABLE jstein.address_points_all ADD COLUMN azimuth integer;
UPDATE jstein.address_points_all addr
SET azimuth = degrees(ST_Azimuth(addr.the_geom, ST_ClosestPoint(road.the_geom, addr.the_geom)))
FROM jstein.street_centerlines road;

and Walla! (or voila, or something):

Ahh, now that, with some additional work, should result in some very nice cartography.  The buildings now follow the angle of the road (so long as we always use a square… ).  USGS quads are dead.  Long live USGS quads!

Fast Calculation of Voronoi Polygons in PovRay– Applied

In a further exploration of using PovRay to do fast calculation of Voronoi polygons, let’s look to a real stream system as an example.  Here’s where the magic comes out, and where medial axes are found.

First the simple but real example.

Here’s the povray code:

#include "transforms.inc"
#version 3.6;

#include "edge_coords1.inc"

#declare Camera_Location = <2258076, 10, 659923>;
#declare Camera_Lookat   = <2258076, 0, 659923>;
 #declare Camera_Size = 1800;

camera {
orthographic
location Camera_Location
look_at Camera_Lookat
right Camera_Size*x
up Camera_Size*y
}

background {color <0.5, 0.5, 0.5>}

//union {

#declare Rnd_1 = seed (1153);

#declare LastIndex = dimension_size(edge_coords, 1)-2;
#declare Index = 0;
#while(Index <= LastIndex)

cone {
<0.0, -5, 0.0>, 30,  <0.0, 5, 0.0>, 0.0
     hollow
material {
texture {
pigment {
rgb <rand(Rnd_1)*2 + 1, rand(Rnd_1)*5 + 2, rand(Rnd_1)*5 +5>
}
finish {
diffuse 0.6
                 brilliance 1.0
}
}
interior {
ior 1.3
}
}
translate edge_coords[Index]
}


#declare Index = Index + 1;

#end

#declare edge_coords = array[16842]
{<2256808.71000000000, 0.00000000000, 660094.46988100000> ,
<2256810.06170000000, 0.00000000000, 660092.99580200000> ,
<2256811.41308000000, 0.00000000000, 660091.52172400000> ,
  <2256811.68965000000, 0.00000000000, 660091.21988700000> ,
<2256813.46393000000, 0.00000000000, 660090.29698900000> ,
<2256815.23820000000, 0.00000000000, 660089.37376200000> ,
<2256817.01248000000, 0.00000000000, 660088.45086400000> ,
  <2256818.78675000000, 0.00000000000, 660087.52763700000> ,
<2256820.56103000000, 0.00000000000, 660086.60473900000> ,
<2256822.33530000000, 0.00000000000, 660085.68151200000> ,
<2256824.10958000000, 0.00000000000, 660084.75861400000> ,
  <2256825.88352000000, 0.00000000000, 660083.83538800000> ,
<2256827.65780000000, 0.00000000000, 660082.91248900000> ,
<2256829.43207000000, 0.00000000000, 660081.98926300000> ,
<2256831.20635000000, 0.00000000000, 660081.06636400000> ,

 

Fast Calculation of Voronoi Polygons in PovRay

Yet further abuse to follow in the application of PovRay for spatial analyses– be forwarned… .

Calculating Voronoi polygons is a useful tool for calculating the initial approximation of a medial axis. We densify the vertices on the polygon for which we want a medial axis, and then calculate Voronoi polygons on said vertices. I’ll confess– I’ve been using ArcGIS for this step. There. I said it. My name is smathermather, and I use ArcGIS. It’s a darn useful tool, and, and, I’m not ashamed to say that I use it all the time.

But, I do like the idea of doing this with non-proprietary, open source tools. I’ve contemplated using the approach that Regina Obe blogs about using PL/R + PostGIS to calculate them, but the installation of PL/R on my system failed my initial Yak Shaving Test.

So, with some google-fu, I stumbled upon articles on using 3D approaches to calculate 2D Voronoi diagrams, and my brain went into high gear. Right cones of equal size, viewed orthogonally generate lovely Voronoi diagrams, the only caveat being you need to know what your maximum distance you want to calculate in your diagram. For my use cases, this isn’t a limitation at all.

And so we abuse PovRay, yet again, to do our dirty work in analyses. I’ll undoubtedly have some follow up posts on this, but in the mean time, some diagrams and really dirty code:

global_settings {
	ambient_light rgb <0.723364, 0.723368, 0.723364>
}

camera {
	orthographic 
	location < 0.0, 5, 0>
	right x * 3
	up y * 3
	look_at < 0.0, 0.0, 0.0>
}

light_source {
	< 0.0, 100, 0>
	rgb <0.999996, 1.000000, 0.999996>
	parallel
	point_at < 0.0, 0.0, 0.0>
}


light_source {
	< 0.0, 100, 100>
	rgb <0.999996, 1.000000, 0.999996>
	parallel
	point_at < 0.0, 0.0, 0.0>
}

light_source {
	< 100, 100, 0>
	rgb <0.999996, 1.000000, 0.999996>
	parallel
	point_at < 0.0, 0.0, 0.0>
}

cone {
	<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
	hollow
	material {
		texture {
			pigment {
				rgb <0.089677, 0.000000, 1.000000>
			}
			finish {
				diffuse 0.6
				brilliance 1.0
			}
		}
		interior {
			ior 1.3
		}
	}
}

cone {
	<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
	hollow
	material {
		texture {
			pigment {
				rgb <1, 0.000000, 1.000000>
			}
			finish {
				diffuse 0.6
				brilliance 1.0
			}
		}
		interior {
			ior 1.3
		}
	}
	translate <-0.5,0,-0.5>
}

cone {
	<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
	hollow
	material {
		texture {
			pigment {
				rgb <1, 0.000000, 000000>
			}
			finish {
				diffuse 0.6
				brilliance 1.0
			}
		}
		interior {
			ior 1.3
		}
	}
	translate <-0.5,0,0.5>
}

cone {
	<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
	hollow
	material {
		texture {
			pigment {
				rgb <1, 1.000000, 000000>
			}
			finish {
				diffuse 0.6
				brilliance 1.0
			}
		}
		interior {
			ior 1.3
		}
	}
	translate <0.3,0,0.3>
}

cone {
	<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
	hollow
	material {
		texture {
			pigment {
				rgb <0, 1.000000, 000000>
			}
			finish {
				diffuse 0.6
				brilliance 1.0
			}
		}
		interior {
			ior 1.3
		}
	}
	translate <0.4,0,-0.2>
}

cone {
	<0.0, -0.5, 0.0>, 0.5,  <0.0, 0.5, 0.0>, 0.0
	hollow
	material {
		texture {
			pigment {
				rgb <1, 1.000000, 1.000000>
			}
			finish {
				diffuse 0.6
				brilliance 1.0
			}
		}
		interior {
			ior 1.3
		}
	}
	translate <0,0,-.7>
}

What is the center line of a complex polygon? New approach.

Today, I just show pictures of my process for filtering the medial axis of extraneous elements. I’ll let the pics tell the story for now:

Original Geometry, with ST_Segmentize run to densify the vertices

Medial Axis (Calculated outside PostGIS... at this time)

Density of vertex points in Medial Axis-- proportional to how closely it matches the direction of the local geometry

Medial Axis filtered based on density of vertices. Red segments are the removed ones, blue are the retained. It's not perfect, but it's very cheap computationally... .

scale axis transform 3

scale axis transform 2
scale axis transform 1

previous post

original

What is the center line of a complex polygon? (cont. again!)

I didn’t remember that I had 4 previous post on this topic, but I’ve gotten a little obsessed with this problem– how to (with relatively little computational cost) kind the centerline of complex polygons, so we can extract flow lines from streams, label long complex polygons, easily generate the centerline parcel boundary line for river bound parcels, etc..  FYI, here are my 4 previous posts on this topic:

scale axis transform 2
scale axis transform 1

previous post

original

I’ll confess, I became somewhat enamored of the scale axis transform as a method for tackling this problem.  In short, the scale axis transform identifies the medial axis of the polygon using Amenta and Kolluri’s finite union of balls to identify the initial centerline of the polygon, and then tries to fix the deficiencies in the robustness of the medial axis.

The problem, of course, is the degree to which bumps in the shape result in extra little lines hanging off our medial axis.  This does not represent an intuitive medial axis.  This is not what we would (in this case) call the centerline of the stream.

The scale axis transform suggests expanding these balls by a multiplicative factor, and deriving the new axis from that scaled version:

This step can easily be done in PostGIS once you have the medial axis:

CREATE TABLE rr_expand_r3_12 AS

SELECT
ST_Buffer(b.the_geom, ST_Distance(b.the_geom, ST_Union(a.the_geom)) * 1.2 )
FROM medial_axis b, polyline a
GROUP BY <a href="http://a.id/" target="_blank">a.id</a>, b.the_geom
 ;

I will play a bit more with this, but the initial results I got around areas with islands (torus like topology) were disappointing.  Also, at least as I have this implemented in PostGIS, this is a computationally intensive process.  I think though that I have a good (enough) alternative, which will be the topic of my next post.

PostGIS Cartographic Effects– Cartoonify Nearly Coincident Lines

In my previous post, a long 24-hours ago, I proposed some automatic modification of line for cartographic reasons. I had some flaws in my code. The points were over-rotated by 45 degrees. Can you spot why? Tip: it’s a basic trigonometric mistake. Here’s the corrected code (though there may be a better way):

CREATE TABLE movedRoad AS
SELECT
    ST_Translate(b.the_geom,
        0.5 * ST_Distance(b.the_geom, ST_Union(a.the_geom)) * (cos(ST_Azimuth(b.the_geom, ST_ClosestPoint(ST_Union(a.the_geom), b.the_geom))) - 3.14159/4),
        0.5 * ST_Distance(b.the_geom, ST_Union(a.the_geom)) * (sin(ST_Azimuth(b.the_geom, ST_ClosestPoint(ST_Union(a.the_geom), b.the_geom))) - 3.14159/4) )
            AS the_geom
    FROM road2_points b, road1 a
        GROUP BY a.id, b.the_geom
    ;

An alternate approach is to only move those points that are too close, ala:

CREATE TABLE movedRoadAgain AS
	SELECT
        ST_Translate(b.the_geom,
	        (100 - ST_Distance(b.the_geom, ST_Union(a.the_geom))) * (cos(ST_Azimuth(b.the_geom, ST_ClosestPoint(ST_Union(a.the_geom), b.the_geom))) - 3.14159/4) ,
	        (100 - ST_Distance(b.the_geom, ST_Union(a.the_geom)))* (sin(ST_Azimuth(b.the_geom, ST_ClosestPoint(ST_Union(a.the_geom), b.the_geom))) - 3.14159/4) ) AS the_geom
	    FROM road2_points b, road1 a
	        GROUP BY a.id, b.the_geom
		HAVING ST_Distance(b.the_geom, ST_Union(a.the_geom)) < 100

	UNION ALL

	SELECT
		b.the_geom AS the_geom
	    FROM bridle_points b, apt a
	        GROUP BY a.id, b.the_geom
		HAVING ST_Distance(b.the_geom, ST_Union(a.the_geom)) >= 100
	    ;

PostGIS Cartographic Effects– Cartoonify Nearly Coincident Lines

I’m still working on this query, but I thought I’d post what I’ve done so far. My intent is to produce scale-dependent exaggeration of the distances between quasi-parallel lines. The reason for this is so that lines such as street lines which are nearly coincident at a particular viewing scale can be spread from each other, much in the same way great cartography lies a little to display a relatively correct map. The nice thing about digital cartography is that as we zoom in, we can make the lie a smaller and smaller, until it is just barely a fib .

My thought was to start with the simplest case– move one line away from another (stationary) line. First step is to find the closest point on the stationary line, determine the distance and angle to that point, and then translate the point outward by some scale factor along that angle. Don’t take my code as gospel, though, I think there’s some deeper logical error, but see what you think:

ST_ShortestLine gives us the shortest line from a given point to the road from which we are trying to offset. This is just to help visualize the problem:

CREATE TABLE shortLine AS

SELECT
	ST_ShortestLine(b.the_geom, ST_Union(a.the_geom)) AS the_geom
    FROM road2_points b, road1 a
    GROUP BY a.id, b.the_geom
    ;

Now, we try to translate the point outward at the same angle, by half again the distance to the closest point:

CREATE TABLE movedRoad AS
SELECT
	ST_Translate(b.the_geom,
		0.5 * ST_Distance(b.the_geom, ST_Union(a.the_geom)) * cos(ST_Azimuth(b.the_geom, ST_ClosestPoint(ST_Union(a.the_geom), b.the_geom))),
		0.5 * ST_Distance(b.the_geom, ST_Union(a.the_geom)) * sin(ST_Azimuth(b.the_geom, ST_ClosestPoint(ST_Union(a.the_geom), b.the_geom))) )
			AS the_geom
    FROM road2_points b, road1 a
        GROUP BY a.id, b.the_geom
    ;

Resulting in something looking like this (red dashed line is the road we are moving away from, the dotted blue are the points making up the line we are moving, and the dotted brown are the newly transformed points, with ST_ShortestLine also visualized in thin brown):

/>