Van egy sík sokszögem. Csak 90 vagy 270 fokos szögei vannak. Csúcsainak koordinátái adottak.
Le kellene fednem minél kevesebb téglalappal, amelyek lehetőleg ne fedjék egymást.
Minimalizáls oka. Több ilyen szabálytalan sokszög lesz. Weblaphoz jön a kérdés, adott pont benne van-e az adott alakzatban vagy sem.
Az egész adatbázisban lesz tárolva, a lefedésre szolgáló téglalapok bal felső és jobb alsó koordinátáival. Minél kevesebb téglalap, annál kevesebb adatbázis sor -> gyorsabb lekérdezés.
Tud valaki erre algoritmust ajánlani?
- 6378 megtekintés
Hozzászólások
Ha jol ertem szavaidat, akkor ilyenekre van szukseged:
Találatok
- A hozzászóláshoz be kell jelentkezni
1 nagy téglalap lefedi :)
Ilyen sokszöget le lehet fedni téglalappal bármikor (úgy hogy ne legyen kicsúszás), miért hozod be a "fedjék egymást" vagy a téglalapok mérete/darabszáma adott?
- A hozzászóláshoz be kell jelentkezni
Azért, mert a darabszámukat kell minimalizálni (akár azon az áron is, hogy néhány esetleg fedni fogja egymást).
- A hozzászóláshoz be kell jelentkezni
Ez így kevés... Ha le tudom fedni N darabbal úgy, hogy 2 téglalap X%-ban fedi egymást, és N+1 darabbal átfedés nélkül, akkor melyik a jobb?
Ha csak a minimális darabszám a fontos, akkor kb. annyi, hogy minden 90°-os sarokból indulva a lehető legnagyobb téglalapot állítod elő, ami még nem lóg kintre, az átfedésekkel meg egyáltalán nem foglalkozol.
Ha az a fontos, hogy ne fedjék egymást, akkor már linkeltek rá fentebb algoritmust.
A kettő között meg... hát sok sikert :)
- A hozzászóláshoz be kell jelentkezni
Valami gond van a böngészőmmel, nem nyitja meg a találatokat. Google search oldal bejön, onnan tovább semmi. Lényeg, meg fogom nézni azokat.
Minimalizálást beleírtam a kérdésbe, lásd fent.
- A hozzászóláshoz be kell jelentkezni
Amit utólag kiírtál, ahhoz biztos kell a téglalapra bontás? Van olyan algoritmus pl, hogy elindulsz a pontodból pl. balra, és megszámolod, hányszor metszel határoló vonalat, páratlan szám esetén belül voltál, páros esetén kívül, persze van 1-2 corner case. Mivel csak derékszögek vannak, ezt nagyon gyorsan és optimálisan lehet tárolni. Aztán az is ott van, hogy a jobbfajta adatbázis-kezelőkben van GIS támogatás, amik kezelése még egyszerűbb, mint saját algoritmust írni.
- A hozzászóláshoz be kell jelentkezni
Ha csak pontok vannak megadva, akkor nem tudod biztosra, azok hogyan vannak összekötve. Ha grafikus felvitel van, ott az ember meg tudja adni hogy mely pontok vannak összekötve. Az alakzatot úgy tárolnám le, hogy téglalapokra bontom. Ekkor egyszerű adatbázis lekérdezéssel el lehet dönteni hogy a pont része-e az alakzatnak.
Amikor meg kérésenként próbálgatnám hogy a pont bent van-e, az adatbázis lekérdezés az összes pontra, meg valahogy meg kell adni hogy melyek vannak összekötve. Mikor lépek át egy ilyen vonalat. Lassabbnak tűnik, mint az előre feltérképezés.
GIS-t megnézem majd.
- A hozzászóláshoz be kell jelentkezni
A point in polygon probléma megoldásához felesleges téglalapokra bontani a sokszögedet, az odd/even rule egyszerűbb, amennyiben a sokszöget nem tartalmaz lyukat.
Egy jó lib erre: Java Topology Suite.
De: ha okos adatbázist használsz, mondjuk PostGIS, vagy MySQL vagy MSSSQL vagy DB2 vagy bármi hasonló, akkor hozzáférsz GIS függvényekhez, így tudsz Contains(g1,g2) hívást is csinálni, ahol g1 és g2 két Simple Feature.
Lásd bővebben itt: http://dev.mysql.com/doc/refman/5.0/en/functions-for-testing-spatial-re…
- A hozzászóláshoz be kell jelentkezni
Javaslatom, a kesobb hozzairtak alapjan (gis kiterjesztesek nelkul):
- polygon tarolas
- polygonok geometria indexelese (befoglalo teglalapjuk alapjan)
- lekerdezes az indexelt bounding boxokbol, ez nem bonyolult lekerdezes, egyszerubb, mint point-in-poly sql alapon
- beolvasni az erintett polygonokat
- programozottan kiszamitani ezek kozul, melyik az erintett (point-in-polygon algoritmus)
Amire figyelni erdemes:
- polygon valtozas (ha van ilyen lehetoseg) -> indexelesre hat
- uj polygon -> indexeles
A legegyszerubb geo index ha felepitesz egy quadtree-t.
- A hozzászóláshoz be kell jelentkezni