Matematické Fórum

↑ jterrry:

Ahoj, je to jednoduchý. Vždycky doporučuju si to nakreslit... Nejdřív si nastuduj jak se určuje poloha bodu vůči přímce.
Uvažuj třeba tuhle situaci:


Ten mnohoúhelník máš zadanej pravděpodobně pomocí dvojic bodů.
Teď každou tu úsečku si převedeš na rovnici přímky. Bod pak může ležet buď na přímce nebo na jedný z polorovin. Všimni si, žekdyž do tý rovnice úsečky dosazuješ body z jedný poloroviny tak má výsledek nějaký znamínko a když do tý rovnice dosazuješ body z druhý poloroviny, tak má opačný znamínko. Ty si pro každou tu přímku zjistíš znamínko výsledku když ten bod dosadíš do tý rovnice přímky a to znamínko se musí shodovat se znamínkem když do tý stejný rovnice přímky dosadíš libovolnej jinej bod toho n-úhelníku. Takže pro ten obrázek nahoře si zjistíš rovnici přímky AB, zjistíš si polohu toho vyšetřovanýho bodu vůči týhle přímce a polohu libovolnýho jinýho bodu n-úhelníku vůči týhle přímce, což je tady jenom bod C. Když oba body ležej ve stejný polorovině tak pokračuješ dál, když ne tak končíš s tím, že bod letí mimo.
Nakonec ještě musíš ošetřit, když ten bod leží na některý z těch přímek. Když leží na přímce AB a leží i na úsečce AB tak to dejme tomu bereme, že leží uvnitř.

↑ PeterSheldon:

Mutíte znát některý základní věci z matematiky... Co to je konvexní n-úhelník a co z toho plyne, že to řešíte pro konvexní n-úhelník? Jak se počítá poloha bodu vůči přímce? Bez tohodle se dál nepohnete...

K tomu obrázku co sem hodil nahoru. Vem si, že to je trojúhelník ABC, kde A je ten bod vlevo dole...
1) Zjistit si rovnici přímky AB
2) Zjistit si polohu toho vyšetřovanýho bodu vůči týhle přímce
3) Zjistit si polohu bodu C vůči týhle přímce
4) Leží tyhle dva body na stejný polorovině vůči přímce AB?
NE -> neni uvnitř
ANO -> pokračuješ dál pro přímku BC

↑ PeterSheldon: Pokud vím, že jsou vrcholy ve správném pořadí, pak by mělo stačit napočítat vektorové součiny po sobě jdoucích stran, měly by být všechny stejně orientované. Pokud jsou vrcholy zadané na přeskáčku, nezbude než napočítat konvexní obal (http://en.wikipedia.org/wiki/Convex_hull_algorithms), a ověřit, že jsou všechny body součástí obalu.

↑ PeterSheldon: no ten vektorový součin bude mít dvě složky nulové a jednu nenulovou (stačí počítat tu nenulovou). A my musíme zkontrolovat, že mají všechny součiny stejná znaménka (pak je konvexní).

↑ Kondr:
a nešlo by jen zjišťovat, jestli dalšího bodu x-ová souřadnice není nižší než předešlého? pokud jsem pochopil co je to konvexní mnohoúhelník tak by to tak mohlo být ne? (podle mě je konvexní mnohoúhelník právě takový, u kterého přímky vedené jeho bodama se neprotnou nikde jinde, než v místě, kde jsou krajní body(vrcholy) tohoto mnohoúhelníka--- snad to z tohoto pochopíš jak to myslím)

↑ Kondr:
no tak já ti to nakreslím


toto je alespoň dle mého názoru nekonvexní mnohoúhelník.... no a jednotlivé vrcholy pokud by jejich y-ová a x-ová souřadnice nebyla menší než toho předešlého bodu, pak by přece byl konvexní tedy pokud by to nebyl poslední bod ne?
takže přes ty souřadnice by se to mohlo taky dělat...

tedy trošku jinak.... ten průběh bodů musí být buď klesající a nebo stoupající a může se změnit pouze jednou... no nic to tvoje je asi lepší

↑ Kondr:
však ani jeden není snad konvesní nebo je?:-o

a tne druhý bod je od druhé přímky...ono to není úplně přesně nakreslené že se protne s tou nejvíce vlevo úsečkou...

můžeš prosím nakreslit oba ty mnohoúhelníky i s tou 0,0? protože já moc nevidím jak by mohl být nekonvexní, ale ani se mi tak nepovedl nakreslit...

otázkou je jestli se oba bavíme o tom samém nekonvexní mnohoúhelní ne konvexní....

↑ VojtechSejkora: Kreslit se mi nechce, tak dám lepší příklad: čtyřúhelníky
(0,3),(2,2),(3,0),(0,0)
a
(0,3),(1,1),(3,0),(0,0)
Zkus mi nějak popsat, jak tvůj algoritmus rozhodne o jejich (ne)konvexnosti.

↑ VojtechSejkora: První konvexní je, druhý ne. Algoritmus, tak jak ho popisuješ, prohlásí oba za konvexní. Algoritmus, který posuzuje zvlášť x a zvlášť y nemůže fungovat. Nekonvexní čtyřúhelník s nekonvexním úhlem menším než 270° mohu vždy otočit tak, aby tvůj algoritmus selhal.

↑ jterrry:
Protože jsme v sekci algoritmy a programování, tak předpokládám, že to potřebuješ nějak naprogramovat.
Pak věz, že existují 2 API funkce
CreatePolygonRgn - viz.
http://msdn.microsoft.com/en-us/library/dd183511(VS.85).aspx
a PtInRegion - viz.
http://msdn.microsoft.com/en-us/library/dd162883(VS.85).aspx
pomocí kterých je možné udělat region a pak zjišťovat zda se v něm nachází zadaný bod.

Pseudokód pro zjištění zda je bod [X,Y] v regionu

Když PtInRegion(region,X,Y) pak
nějaká akce (např. výpis, že ano)

Jenom upozorňuji, že region je deklarován jako pole bodů a index pole musí začínat
číslem 1. (0 to nebere)

Měl bych ještě jednu otázku..Pro to, abych mohl vypracovat výše zmíněný matematický postup, potřebuji načíst ze vstupu minimálně tři body, se kterými budu dále pracovat. Můj problém tkví v tom, že nevím jak body uložit. Napadl mě způsob body postupně ukládat do tří proměnných a postupně je šoupat tak, že by vždy jeden bod přibil a jeden ubyl. Ale realizace mi nešla provést. Nevíte někdo jak na to?

while (!feof(stdin)) {
   scanf("%d%d",&Xn,&Yn);
}