Segmentace mapy - Map segmentation - Wikipedia

v matematika, segmentace mapy problém je druh optimalizační problém. Zahrnuje určitou geografickou oblast, která musí být rozdělena do menších podoblastí, aby bylo dosaženo určitého cíle. Mezi typické cíle optimalizace patří:^[1]

• Minimalizace pracovní zátěže vozového parku přiřazeného k podoblastím;
• Vyrovnávání spotřeby zdroje, jako v spravedlivé krájení dortu.
• Určení optimálních umístění zásobovacích skladů;
• Maximalizace pokrytí sledováním.

Spravedlivé rozdělení půdy je důležitou otázkou od starověku, např. v Starověké Řecko.^[2]

Zápis

Existuje zeměpisná oblast označená C („dort“).

Oddíl C, označený X, je seznam nesouvislých podoblastí, jejichž sjednocení je C:

${ displaystyle C = X_ {1} sqcup cdots sqcup X_ {n}}$

Existuje určitá sada dalších parametrů (například: překážky, pevné body nebo funkce hustoty pravděpodobnosti), označené P.

Na množině všech oddílů je funkce se skutečnou hodnotou označená G („cíl“).

Problémem segmentace mapy je najít:

${ displaystyle arg min _ {X} G (X_ {1}, tečky, X_ {n} střední P)}$

kde je minimalizace na množině všech oddílů C.

Často na oddílech existují omezení geometrických tvarů, např. Může být požadováno, aby každá část byla a konvexní sada nebo a připojená sada nebo alespoň a měřitelná množina.

Příklady

1. Červeno-modré rozdělení: existuje sada ${ displaystyle P_ {b}}$ modrých bodů a sady ${ displaystyle P_ {r}}$ červených bodů. Rozdělte letadlo na ${ displaystyle n}$ regiony, takže každá oblast obsahuje přibližně zlomek ${ displaystyle 1 / n}$ modrých bodů a ${ displaystyle 1 / n}$ červených bodů. Tady:

• Dort C je celé letadlo ${ displaystyle mathbb {R} ^ {2}}$;
• Parametry P jsou dvě sady bodů;
• Funkce cíle G je

${ displaystyle G (X_ {1}, dots, X_ {n}): = max _ {i in {1, dots, n }} left ( left | { frac {| P_ {b} cap X_ {i} | - | P_ {b} |} {n}} right | + left | { frac {| P_ {r} cap X_ {i} | - | P_ {r } |} {n}} vpravo | vpravo).}$

Rovná se 0, pokud má každá oblast přesně zlomek ${ displaystyle 1 / n}$ bodů každé barvy.

Související problémy

• A Voronoiho diagram je specifický typ problému segmentace mapy.
• Spravedlivé krájení dortu, když je koláč dvourozměrný, představuje další specifický problém segmentace mapy, když je koláč dvourozměrný, jako v Hill-Beckův problém rozdělení půdy.
• The Stone – Tukeyova věta souvisí s konkrétním problémem segmentace mapy.

Reference