Vzdialenosť pohybu dvoch polygónov tak, aby sa dotkli okrajov - geometria, výpočtová geometria, polygóny

Najlepšie popísané na obrázku nižšie.

Potrebujem poznať minimálnu vzdialenosť na pohybreferenčný polygón (zobrazený červenou farbou) v jednej osi (práve y), ktorý sa bude dotýkať iného polygónu. Ak je vo vnútri mnohouholníka, bude sa musieť pohybovať smerom von.

Snažil som sa pozrieť na všetky čiary v jednom polygónea všetky body v inom, premietnite bod na čiaru a získajte rozdiel medzi bodom y a projekčným bodom y, potom nájdite minimálnu vzdialenosť. To však malo problém, že ak by sa polygóny prekrývali a najvzdialenejšia čiara v jednom mnohouholníku a najvzdialenejšom bode v druhom mala minimálnu vzdialenosť, znamenalo by to výsledok, ktorý by spôsobil prekrývanie polygónov.

Edit: premietnutím bodu na riadok, myslím, že nájdite hodnotu y pre bod na čiare, ktorá má rovnakú hodnotu x ako pôvodný bod. Tento krok preskočte, ak hodnota x leží mimo čiary.

odpovede:

"Nie som si istý, či som správne pochopil váš návrh (čo" s "premieta bod na čiaru"?).

Každopádne by som to skúsil (pseudo kód),:

for pA: points of polygon A:
for sB: segments of polygon B
compute distance along y-axis d(pA,sB) and store in table
Find minimum distance in table: d1
Proceed as above by reversing A and B: d2
final d = min(d1,d2)

Bohužiaľ, toto pravdepodobne nie je dobré, ak sú vaše polygóny konkávne, čo sa zdá byť pravda.

Je potrebné nakresliť zvislú čiaru cez každý vrchol oboch polygónov a určiť jej priesečník s polygónmi (priesečník čiara / mnohouholník je vytvorený z nespojitých intervalov).

Na danej zvislici vypočítajte rozdielmedzi najvyšším koncovým bodom mnohouholníka a najnižším iným. Odpoveď je najmenší rozdiel medzi všetkými vertikálmi (čo môže byť záporné číslo).

Ak chcete vykonať výpočet efektívne, môžetepoužite princíp skenovania: zoradte všetky vrcholy zľava doprava a udržujte "aktívny zoznam", čo je zoznam hrán, ktoré pretínajú aktuálnu vertikálu. Keď sa pohybujete z jedného vrcholu na druhý, budete aktualizovať tento zoznam.

Pre dva polygóny veľkosti N a M, triedenie bude stáť O(N+M)Log(N+M)); potom skenovanie bude stáť približne O((N+M)K), kde K je priemerný počet priesečníkov vertikály s mnohouholníkom, zvyčajne malé číslo medzi 2 a 4.