Every part it’s worthwhile to find out about Voronoi Diagrams: Analyze Service Areas of Transit Stations in Tokyo

With the world turning into more and more urbanized [1], public transport has turn into an omnipresent a part of city life. The most likely most city place on the planet is Tokyo [2] — a bustling Megapolis of an unmatched dimension the place most individuals primarily depend on public transport [3] of their on a regular basis lives.

This text introduces you to the idea of the Voronoi diagram in an city planning context and makes use of it to divide the service space of practice stations in Tokyo. We are going to use the acquired service areas to acquire varied, possibly barely fascinating, statistics concerning the practice station’s environment.

Introduction

Voronoi diagrams and Delaunay triangulations discover extensive software in lots of branches of science. [4] Voronoi diagrams, also referred to as Voronoi grids, are used to divide a flat floor into distinct areas that correspond to particular factors.

This downside is arising ceaselessly in many types. [5]

Some examples embrace:

• Authorities of Melbourne (2024-), once they assign college students to their nearest college [6]
• John Snow (1813–1853) when he associated the outbreak of cholera in London to the placement of water pumps [4]
• René Descartes (1596–1650) when he investigated the distribution of matter relative to mounted stars [4]

In the present day, Voronoi diagrams are being utilized in many areas, together with pc science, geography, and particularly city planning. City planning is the sphere I wish to introduce to you in additional element — we’ll decide service areas of mass transit stations in world’s largest metropolis: Tokyo.

The Elements of Voronoi

The Voronoi diagram consists out of a number of totally different end result units with distinct names and utilization:

• 🔵 Voronoi Web site is the reference location the Voronoi Area is calculated for.
• 🟣 Voronoi Area incorporates all of the factors on the floor nearer to the associated Voronoi website than some other.
• 🟢 Voronoi Arc is the straight line phase that could be a boundary between two Voronoi Areas [4]
• 🟠 Voronoi Vertex is some extent the place Voronoi Arcs intersect.

The Distance Features for Voronoi

The Voronoi diagram in a metropolis planning context is normally based mostly on a distance/reference system relationship. The gap is calculated based mostly on sure measures, equivalent to literal distance or journey time. There are a number of strategies for calculating mentioned distance:

Euclidean Distance. Is the air-line distance between two factors in a coordinate system. It’s assuming an open house between two factors with nothing blocking them in between. It’s the most simple solution to calculate distance.

Manhattan distance. Ignores the air-line distance and introduces a distance perform to approximate journey occasions in a metropolis grid — identical to in Manhattan. It’s higher fitted to sure metropolis environments.

Time-based distance. Essentially the most correct measure, but additionally the one most complex to accumulate.

Moreover, time based mostly distances might trigger anomalies, as journey occasions between areas won’t be linear to their distance and due to this fact may trigger the Voronoi Areas to erratically break up up [10]— identical to within the instance under.

Now, we have now all of the fundamentals for beginning with our actual life use case — Tokyo’s public transport. Let’s get began!

Probably the most vital features of city planning are mass transit networks — particularly in a spot like Tokyo. Tokyo is a spot that many individuals are eager for — particularly public transport fans.

Therefore, Tokyo gives us with the proper instance to make use of Voronoi diagrams with an actual life use case.

Idea

Think about a metropolis map dotted with public transit stations. Every station serves its surrounding space, referred to as a service zone. However how can we decide these zones?

To raised perceive the best way to obtain our purpose of buying service areas of public transport stations, I put the Voronoi diagram into our mass transit perspective:

• 🔵 Voronoi website is now a practice station in Tokyo
• 🟢 Voronoi Arc is now the border dividing service areas of practice stations
• 🟣 Voronoi Area is now the realm serviced by one particular practice station based mostly on our distance perform

That’s what Voronoi Diagrams can provide us. By dividing the map into areas based mostly on the gap to the closest station, we have now a quite simple strategy defining service areas of practice stations.

Now, because the idea is obvious, let’s get began with the precise implementation.

Identitifying Tokyo

We have to outline the realm we wish to create our Voronoi Diagram for. That course of is normally known as defining the Bounding Field.

When somebody says “Tokyo”, it may possibly imply various things to totally different folks.

Some might consider it as a:

1) Bustling metropolis (Tokyo Metropolis) with towering skyscrapers and vibrant avenue tradition, whereas others might view it as a

2) Prefecture (Tokyo Prefecture) with scenic landscapes and pure magnificence, whereas another person would possibly seek advice from

3) Better Tokyo Space, which is essentially the most populous metropolitan space on the planet [8], that consists out of a number of standalone cities (e.g. Tokyo, Saitama, Yokohama, ..).

Nonetheless, it’s vital to outline what we imply by “Tokyo” so as to keep away from confusion.

Utilizing the prefecture definition permits us to distinguish Tokyo from its neighboring cities like Saitama, Chiba, and Yokohama whereas together with most areas which individuals typically seek advice from as “in Tokyo”.

Tokyo Prefecture shall be our base border field for all subsequent Voronoi calculations.

For buying geospatial details about Tokyo prefecture, we resort to official authorities sources, as referenced under:

Dataset: Nationwide Land Numerical Data | Administrative Boundaries Information (mlit.go.jp), Licensed below the Open Information Coverage, permitting business use. 利用規約 (mlit.go.jp)

Finding Practice Stations

The Japanese Authorities gives a dependable supply for details about practice stations. Their web site provides an in depth dataset containing all practice stations throughout the nation, together with different associated metadata.

It’s price noting that the dataset focuses solely on practice stations as per Japan authorities’s definition and should exclude modes of mass transit like metro and monorail whereas together with modes of transit folks typically wouldn’t seek advice from as trains, equivalent to particular cable automobiles.

There could be alternatives to extend the correctness of knowledge retrieved via combining further information sources. [9] On this article, I’ll proceed with the governmental dataset with out additional enhancements.

Dataset: Nationwide Land Numerical Data | Railway Information (mlit.go.jp), Licensed below the Open Information Coverage, permitting business use. 利用規約 (mlit.go.jp)

Acquiring Service Zones

Now that we have now established the borders of Tokyo and an inventory of related practice stations, we are able to proceed with calculating our service zones. We shall be using KNIME, a strong device for scientific computations that minimizes the necessity for in-depth math data or coding, by abstracting a lot of the complexity away.

1. Extract information

We begin with connecting our information sources to the device. Luckily, KNIME gives a set of instruments for Geospatial operations, which we are able to use out of the field.

We proceed by creating two nodes for importing our information. GeoFile Reader node is able to dealing with each Shapefile and geojson information varieties.

To make use of the 2 datasets, some preparation is critical.

1. We take away some fields resulting from an extra quantity inside every dataset with the Column Filter node.
2. To boost readability, we rename sure columns throughout the datasets with the Column Renamer node.
3. To keep away from confusion in a while, equivalent columns inside every dataset are given distinctive names with the Column Renamer node.

Having accomplished the info extraction and preparation, we are able to now transfer ahead with our computations.

2. Work with information

Our subsequent goal is to acquire the Voronoi polygons for every station, thereby enabling us to derive their respective service zones.

1. We create a bounding field for our Voronoi diagram, utilizing our Tokyo Prefecture dataset, with the Bounding Field node.
2. To be able to carry out our calculations, we’d like factors as a substitute of polygon representations for the stations. The Geometry to Level node is used to transform them.
3. We carry out the Voronoi calculation utilizing the Voronoi (Thiessen) Polygon node, which produces polygons and related IDs. Nonetheless, since we additionally require station metadata, we should be part of the Voronoi polygons with this info once more utilizing the Spatial Be part of node.

That’s all the pieces we have to acquire station service zones in KNIME. Let’s have a look on the outcomes.

Service Zones (V1)

Now we are able to see that the Voronoi diagram has divided our map, assigning a singular space to every station.

We should always remember that sure stations like Takadanobaba appear to be one station in particular person, however really encompass a number of stations in actuality. Due to this, we have to do some additional work to verify our calculations replicate this precisely.

Cleansing Information and Service Zones (V2)

The station dataset incorporates an extra ID that teams stations by their public title and/or real-life look. By using this ID and the Group By node, we are able to be part of the person stations right into a single one.

After consolidating the person stations, we have been capable of create a extra correct dataset of service zones that higher displays how folks see stations in the actual world. Take a look at Takadanobaba — it’s positioned in a single Voronoi area now.

End result

We have now accomplished our calculations and obtained service zones that may present helpful insights and statistics.

To discover the outcomes your self, you could find all the pieces on this GitHub repository:

Subsequent, we’ll acquire some real-life statistics that we are able to derive from our service zones.

Statistics Instance — Restaurant Density

In terms of planning a trip, one of many greatest hassles is determining the place to remain. I imply, you wish to decide a location that’s near all of the eating places, outlets and different cool stuff, proper?

However with so many choices on the market, it may be complicated to search out the proper spot. That’s the place our newly acquired Transit Station Service Areas might help us:

Purpose: Figuring out the station with essentially the most POI in it’s environment. To make issues straightforward, we’ll deal with eating places.

Buying Information

Information worthwhile for enterprise functions appears to ceaselessly be protected and exhausting to retrieve. Within the case of eating places, there is no such thing as a official supply out there.

Essentially the most correct sources, equivalent to Enterprise Registrations or Google Maps, are both related to a steep price ticket or simply aren’t authorized for big scale processing utilization.

The Overpass API provided by the OpenStreetMap basis, is likely one of the solely sources that gives the info we’d like. With a easy question in Overpass Turbo, we are able to purchase all eating places in Tokyo.

nwr[amenity=restaurant](round:60000,{{middle}});
out middle;

The information is being displayed in Overpass Turbo immediately and is on the market for export to a file kind of our selection:

We now have a full dataset on all eating places in Tokyo. It’s coming with it’s limitations, as the info is crowd sourced, not validated and may also be centered round the preferred spots within the metropolis, as that’s the place folks normally contribute to on their platform. As it’s the finest information out there in our case, we proceed utilizing it.

Dataset: overpass turbo (overpass-turbo.eu), Information licensed below Open Database License (ODbL)

Matching Factors of Curiosity (POI) to their service zone

To calculate the person quantity of eating places in a station’s service zone, we have to match the POI to their respective service zones.

I’ve imported the station service zones as a layer in QGIS. That software provides us to calculate node counts inside areas out of the field.

The variety of eating places in every service zone doesn’t meet our necessities, as some giant zones have many eating places — however with lengthy distances to cowl in between them. Subsequently, we have to develop a brand new metric to deal with this state of affairs. The simplest strategy could be to find out the density of eating places.

Components for POI density

For a easy rating, eating places/km² per service zone could be a superb illustration. That method, we are able to discover the service zone with the best density of eating places.

In some circumstances, service zones could also be small but have numerous eating places, which may inflate their rating. Nonetheless, in our state of affairs, this isn’t a priority. Small service zones would possibly point out the presence of one other station and extra eating places in shut proximity.

There’s a method:

the place:

R = POI density think about n/km²
A = space of polygon in km²
n = variety of POI

We import the dataset with POI Depend/service space into KNIME and run our method for every service zone.

Lastly, we acquired the zones with the best density of eating places. Let’s check out the outcomes.

Outcomes

The highest 20 station service areas with the best density of eating places are:

We will additionally view our outcomes on a map to get extra insights:

We will see, that the areas with the best density are showing in clusters. I did some extra analysis and discovered that Tokyo is made out of particular person cities (e.g. Taito Metropolis, Shibuya Metropolis, Chiyoda). These clusters do signify the person cities Tokyo is made out of ultimately — fascinating!

It’s vital to notice that our dataset is crowd-sourced and is probably not totally consultant or full, because it may very well be biased in the direction of areas which were notably well-surveyed.

Nonetheless, based mostly on the info we have now, Ueno-Okachimachi Station is the clear winner.

If you happen to’re concerned about exploring the info additional, you possibly can try the Tableau Public web page, the place you possibly can work together with the visualization and delve deeper into the outcomes:

https://public.tableau.com/app/profile/martin.jurran/viz/Tokyo-RestaurantDensity/Map#1

Voronoi diagrams are extra versatile and helpful than we frequently notice. They allow us to uncover insights, equivalent to figuring out Ueno-okachimachi station as having the best restaurant density in Tokyo Prefecture.

Even main corporations like Uber possible use Voronoi diagrams to effectively assign drivers to pick-up areas. Their wide selection of functions makes them worthwhile throughout varied industries, particularly since they are often computed with minimal assets.

I encourage you to discover the capabilities of Voronoi diagrams and see how they will profit you. By together with them into your toolset, you possibly can improve your information evaluation abilities and acquire entry to extra insightful statistics.

[1] United Nations (2018, September 13), Urbanization, https://www.un.org/improvement/desa/pd/content material/urbanization-0

[2] Demographia (2023, January 24), World City Areas nineteenth Annual, http://www.demographia.com/db-worldua.pdf

[3] Demographia (2003, January 1), The place Rail Transit Works, and Why, http://demographia.com/db-htld-rail.htm

[4] Vera Galishnikova, Peter Jan Pahl (2018, Mar 15), Constained Building of Planar Delaunay Triangulations with out flipping, https://www.researchgate.web/publication/325582898_Constrained_Construction_of_Planar_Delaunay_Triangulations_without_Flipping

[5] Liebling T.M., Pournin L. (2010), Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twins. Documenta Mathematica. Arithmetic Topic Classification: 01A65, 49- 03, 52C99, 68R99, 70–08, 92–08

[6] Authorities of Melbourne (2024), Faculty Catchment Map, https://www.findmyschool.vic.gov.au/

[7] Wikipedia (2024), Taxicab geometry, https://en.wikipedia.org/wiki/Taxicab_geometry

[8] Wikipedia (2024), Better Tokyo Space, https://en.wikipedia.org/wiki/Greater_Tokyo_Area

[9] Public Transportation Open Information Middle (2024), Dataset — 公共交通オープンデータセンター データカタログサイト,ttps://www.odpt.org/

[10] D.T. Lee, Chung-Shou Liao, Wei-Bung Wang (N/A), TIme-based Voronoi Diagram, http://alumni.cs.ucr.edu/~weiw/paper/VD_highways.pdf

[11] Options for Planning Sensible Hybrid Public Transportation System — Poznan Agglomeration as a Case Research of Satellite tv for pc Cities’ Connections — Scientific Determine on ResearchGate. https://www.researchgate.web/determine/Voronoi-diagrams-of-selected-areas-for-geographical-a-road-b-and-travel-time_fig5_336071639

Pictograms by かわいいフリー素材集 いらすとや (irasutoya.com), © Takashi Mifune