Matt Duckham

@duckham.org

1245 Followers 589 Following

Academic: Professor at RMIT University, GIScience, spatial algorithms, AI, and databases, ontologies http://gkl.rmit.melbourne Author: GIS 3e http://gisacp.duckham.org Me: gender equity, wheelchair user, food, new music

Fontaines DC on stage bathed in peach coloured light silhouetting three audience members on others’ shoulders.

Screenshot of DeepSeek giving a confident and incorrect answer to a basic spatial query “who is Elizabeth Street in Melbourne named after?”

Finding the shortest path is the most important network operation of all in a GIS.

Dijkstra's shortest path algorithm begins by initializing every node in the network with the maximum possible path length. We also update the start node's path length to zero.

Processing a node involves three steps: select, update, and stash.

First, select the unprocessed node with the smallest path length. Here that's Beswick pottery.

Second, if we find a shorter route to any unprocessed neighbors of our node, like the City Museum, update their path lengths.

Third, stash our processed node (Minton pottery in this iteration) in a list of visited nodes.

Iterating through all the nodes in the network creates all the information needed to reconstruct the shortest path from the start node to any other node in the network.

Screenshot of the accessibility settings in the Bluesky app, with “Require alt text before positing” checked

Line simplification reduces the level of detail in an arc or polyline, while retaining its essential geometric character.

The most famous line-simplification algorithm in GIS is called the Douglas-Peuker algorithm.

The algorithm begins by constructing the straight-line segment formed by the two end points of the arc to be simplified.

Next, we search for that point on the arc with the greatest perpendicular distance to the line segment.

This point is then used to split the line segment into two parts.

The procedure is applied recursively to each of the new parts.

The algorithm iterates as long as the perpendicular distance from a straight-line segment to its furthest point on the arc is above some predefined threshold.

Line simplification algorithms like Douglas-Peuker, are fundamental to cartographic generalization, where maps need to be displayed at different scales.

This is the formula for the area of a triangle.

Note that this calculation always yields a positive or a negative area, depending on the order of triangle vertices.

We can use this property to test whether two line segments intersect.

Using the first line segment as the base, make two triangles each using a vertex of the other line segment at its apex.

Then compute the areas of the two triangles, and test if they have the same sign.

Finally, repeat the test using the other line segment as the triangle base.

If both pairs of areas have different signs, then the line segments must intersect.

Line segment intersection underlies a huge range of the operations found in any GIS.

A region quadtree is a recursive subdivision of a square array of cells into four equal-sized quadrants. The decomposition is applied to each subarray until all the squares bound homogeneous regions.

Each square can be uniquely addressed using the Z-order convention. 0, 1, 2, and 3 address the top left, top right, bottom left, and bottom right quadrants, respectively.

Concatenating addressed numbers at each level of the tree leads to a unique address for every cell.

For example, the top-left quadrant has the address 0; the top-right sub-quadrant is assigned the address 01; and the bottom-left sub-quadrant of that quadrant has address 012 and so on.

Quadtrees and quadtree addresses have many uses in GIS, including efficient storage; geohashing; and discrete global grids.

Two teams of small humanoid robots, playing soccer in a brightly lit green alcove with 4 human robocup team members in red and black sports uniform.

One of the most frequently used clustering algorithms is called k-means clustering.

k-means partitions an input dataset into a specified number of k clusters.

The clusters are constructed such that: each input data point in the cluster is closer to the centroid of that cluster, than of any other cluster.

k-means clustering begins by randomly generating a set of k points, called cluster heads, and shown here with square colored points.

The algorithm then computes the subset of points nearest to each cluster head, termed the "assignment" step.

Next, the algorithm calculates the centroid of each subset, termed the "update" step.

Alternating assignment and update steps, the algorithm iterates until the solution stabilizes and the cluster heads no longer move after each iteration.

Some maps deliberately distort distances or angles in the pursuit of clearer communication of mapped data. A schematic map suppresses geometric details in favor of highlighting connectivity between places.

Schematic maps are especially useful as transport maps.This map shows the Oslo metro network, highlighting the connections between stations. In common with most schematic transport maps, the lines are straight; the angles between lines are fixed to a small set of possibilities; and the distances between stations are fixed across the map, only lengthened for graphical clarity.

This is the same Oslo metro network, but in planimetric view, with geographic distances and shapes preserved. Although geometrically more faithful, the results would be much less useful if you needed to get around Oslo using public transport.

Two glasses of wine on a table in front of a spectacular 80th floor city view.

Video: Maps are often used to present information that has been aggregated across different areas, such as city districts or grids. The "modifiable areal unit problem" concerns the question: what would these aggregate maps look like if we had chosen different areas to aggregate over.

Imagine these points represent the locations of houses in a region. A grid can then be used to map the distribution of houses. The map on the left suggests an even distribution over the region. But, a 16 degree rotation of the grid on the right gives a completely different, uneven picture of the distribution of houses.

Any patterns in spatial data aggregated over arbitrary (or “modifiable”) areal units may depend as much on the chosen areas as on the underlying spatial distribution.

That's the modifiable areal unit problem.

Selection of Indian cuisine dishes on a table with a white table cloth.

Lisa presenting at a podium taking in front of a display screen

Video: What can we deduce about the spatial relationship between two regions from the intersection between region interiors and boundaries.

This question underpins the four intersection model: one of the most famous ideas in GIS.

The four intersections are: between the two region boundaries; the two region interiors; between the first boundary and the second interior; and between the second boundary and the first interior.

Each of these intersections may be empty or not. In general, there are four-times-four equals 16 different combinations. For simple regions in the plane only eight of the 16 combinations can occur.

These eight mutually exclusive possibilities are:

Disjoint, meets, and overlaps; covers, contains, and equals; inside and covered by.

Any pair of regions must match exactly one of these combinations.

Screen shot showing locations of setting in Teams software to disable status bar item

Dozens of circular shortbread cookies, each containing a red star, freshly baked on a cooling rack.

An abstract diagram of numbered points, connected by dotted lines, with a non-convex shape picked out from the dots in lilac.

Indian meal on a wooden table, steaming in the sunlight

Laptop at a shared desk, with 6 other laptops around it with team working on shared problem

Golden brown financiers stacked on a beige kitchen worktop.

Shirt front with dressmakers pin and hand preparing for alteration