Better Maps/Polygon Maps

Conceptual Overview

The purpose of this is to generate a bottom-up system of regions, duchies, realms, etc. So we start from the lowest reasonable element and build up.

Walkthrough

Our "unit" will be the place. A place is a single meaningful spot on the map and its related areas. The "spot" could be a village, a town, a castle or a city. Basically, a settlement. The area around it is the area this settlement claims as its own, belongs to it geographically. We could go looking for geographic features and derive the area from that, but it is easier to do it the other way around: Draw Voronoi cells around the settlements and define the geographic features based on their edges. This gives us a basic segmentation of our map, for example like shown on the right. The dots in this image are the settlements, and the lines are the borders between areas. The "tiles" are the places.
Let us select three places at random and use them for the following examples:
Estates An estate is a knights place of residence. It is always located in a place, but it can control several places. So a single knight could control a village, or he could control a castle and three surrounding villages, etc. In our example, this could look like shown on the right. The middle estate only controls one place, but it's a pretty large place. The two other estates control several places. So in the example bottom-left, you have the place X which also rules the other three nearby places. A knight can only control places that border his residence, so an estate is always a continuous area. This also puts a size limit on estates.
Regions Estates can band together to form regions. A region is an area that will be visible on the world map. Every estate always belongs to a region, though it can "belong" to itself, just like places always belong to an estate. So place, estate and region can all be the identical one unit, though that is unlikely. In our example, the two left-most estates belong to the same region, so they are now part of the same hierarchy, and their knights share a common lord. If in our example the leftmost estate is the region "capital", then the other estate would be its vassal.
Baronies, Duchies, etc Regions can band together into higher-level entities. There is no theoretical limit to the depth of this hierarchy, so several regions could form a barony, several baronies a duchy, several duchies a... - on a practical level, one or two layers is probably the maximum that will work. This layer is optional. In our example on the right, the other regions belonging to the same duchy as our examples are marked in yellow. The top-right region does not belong to a barony/duchy/etc while the lower-left region (containing our two example estates there) does. These intermediate layers mainly serve as vehicles for player creativity. They make it possible to create different kinds of realms, with flat or deep hierarchies, with intricate systems or simple ones. This layer serves as the foundation of pretty much any imaginable feudal system that players want to come up with.
Realms At the top of the hierarchy stands the realm. This is a generic term for empires, kingdoms and the like, but also for independent baronies, regions or even estates. The definition is simple: Anything that does not have anything else above it in the hierarchy is a realm. Realms are marked in red to the right. To make the example clearer, the two realms in our example do not touch, though in the real game they usually would.

(to be continued, please do not edit)