Algoritmusok és adatszerkezetek II. Horváth Gyula Szegedi Tudományegyetem Természettudományi és Informatikai Kar
[email protected]
9.
Geometriai algoritmusok
Számos olyan gyakorlati számítási probléma van, amely megoldható olyan geometriai modellben, amelyben csak egyszeru˝ objektumok, pontok, egyenesek, szakaszok, szögek, szögtartományok, poligonok szerepelnek. Ilyen alapveto˝ feladatokat vizsgálunk.
9.1.
Alapfogalmak
Pont: (x, y) ∈ R × R Szakasz Legyen p1 , p2 pont. A p1 és p2 pont által meghatározott szakasz:
p1 p2 = {p = (x, y) : x = α p1 .x + (1 − α)p2 .x, y = α p1 .y + (1 − α) p2 .y), α ∈ R, 0 ≤ α ≤ 1} → Ha p1 és p2 sorrendje számít, akkor irányított szakaszról beszélünk, jele: − p− 1 p2 . Egyenes Egyenes megadása: 1. y = m x + b egyenlettel: azon (x, y) pontok halmaza, amelyekre teljesül az egyenlet. 2. a x + b y + c = 0 egyenlettel. 3. Egyenes megadása két pontjával: e(p1 , p2 )
9.2.
Feladat: Pontok összekötése zárt, nem-metszo˝ poligonná.
Adott a síkon n darab pont, amelyek nem esnek egy egyenesre. A pontok (x, y) koordinátáikkal adottak, amelyek egész számok. A pontokat a 1, . . . , n számokkal azonosítjuk. Kössünk össze pontpárokat egyenes szakaszokkal úgy, hogy olyan zárt poligont kapjunk, amelyben nincs metszo˝ szakaszpár. Egy ilyen zárt, nem-metszo˝ poligon megadható a pontok azonosítóinak egy felsorolásával: a felsorolásban egymást követo˝ pontokat kötjük össze egyenes szakaszokkal, ˝ továbbá, az utolsót az elsovel is összekötjük.
Bemeneti specifikáció A poligon.be szöveges állomány elso˝ sora a pontok n (3 < n < 100000) számát tartalmazza. A további n sor mindegyike két egész számot tartalmaz, egy pont x és y koordinátáit, (−20000 ≤ x, y ≤ 20000). A pontok nem esnek egy egyenesre.
Kimeneti specifikáció A poligon.ki szöveges állományba a bemenetre kiszámított zárt, nem-metszo˝ poligont leíró sorozatot kell kiírni.
Példa bemenet és kimenet poligon.be
poligon.ki
6 2 1 0 3 2 2
3 1 4 5 6 2 0 4 2 2 4 6
Megoldás Válasszuk ki a legkisebb x-koordinátájú pontot, ha több ilyen van, akkor ezek közül válasszuk a legkisebb y-koordinátájút. Ezt nevezzük (bal-alsó) sarokpontnak és jelöljük Q-val. Húzzunk (fél) egyenest a Q sarokpontból minden ponthoz. Rendezzük az egyeneseket a Q ponton áthaladó, x-tengellyel párhuzamos egyenessel bezárt ˝ (elojeles) szög alapján. pi
φ(Q, pi) Q
Q
φ(Q, pi)
pi
˝ 1. ábra. A pi ponthoz tartozó elojeles szög: φ(Q, pi ).
˝ és pi elobb ˝ Rendezzük a pontokat úgy, hogy a Q sarokpont legyen az elso, legyen mint p j akkor és csak akkor, ha A φ(Q, pi ) < φ(Q, p j ), vagy φ(Q, pi ) = φ(Q, p j ) és pi közelebb van Q-hoz, azaz pi .x < p j .x, vagy φ(Q, pi ) = φ(Q, p j ) és pi .x = p j .x és pi .y < p j .y. Ha ebben a sorrendben kötjük össze a pontokat, kivéve, hogy az utolsó egyenesen lévo˝ pontokat fordított sorrendben vesszük, akkor egy zárt, nem metszo˝ poligont kapunk.
Q
6
4 5 3
Q
2 1
6
4 5 3
Q
2 1
6
4 5 3
Q
2 1
6
4 5 3
Q
2 1
6
4 5 3
Q
2 1
6
4 5 3
Q
2 1
6
4 5 3
Q
2 1
6
4 5 3
Q
2 1
6
4 5 3
Q
2 1
6
4 5 3
Q
2 1
6
4 5 3
Q
2 1
6
4 5 3
Q
2 1
Hogyan döntheto˝ el, hogy φ(Q, pi ) < φ(Q, p j )? Minden i > 1-re − π2 < φ(Q, pi ) ≤ π2 és ebben a tartományban a tangens függvény szigorúan pj
pi
p j .y − Q.y pi.y − Q.y
pi.x − Q.x Q
p j .x − Q.x
2. ábra. A φ(Q, pi ) és φ(Q, p j ) szögek viszonya.
˝ tehát monoton növekvo, φ(Q, pi ) < φ(Q, p j ) akkor és csak akkor, ha
tan(φ(Q, pi )) =
p j .y − Q.y pi .y − Q.y < = tan(φ(Q, p j )) pi .x − Q.x p j .x − Q.x
Mivel Q sarokpont, így pi .x − Q.x ≥ 0 és p j .x − Q.x ≥ 0, tehát
φ(Q, pi ) < φ(Q, p j )
akkor és csak akkor, ha
(pi .y − q.y)(p j .x − Q.x) < (p j .y − Q.y)(pi .x − Q.x) ˝ p j -t akkor és csak akkor, ha Tehát a pontok rendezése: pi megelozi
(pi .y − Q.y)(p j .x − Q.x) < (p j .y − Q.y)(pi .x − Q.x) ∨
(1)
(pi .y − Q.y)(p j .x − Q.x) = (p j .y − Q.y)(pi .x − Q.x) ∧ pi .x < p j .x ∨ (pi .y − Q.y)(p j .x − Q.x) = (p j .y − Q.y)(pi .x − Q.x) ∧ pi .x = p j .x ∧ pi .y < p j .y
(2)
A sík pontjainak ábrázolására a P ONT osztályt használjuk.
public class Pont{ double x, y;//a pont x- és y-koordinátája int az; //a pont azonosítója Pont(double x, double y, int az){ this.x=x; this.y=y; this.az=az; } Pont(double x, double y){ this.x=x; this.y=y; } Pont(){} }
(3)
Tegyük fel, hogy van olyan S AROK R ENDEZ eljárásunk, amely a P ponthalmazt rendezi a bal˝ alsó sarokpontjára vonatkozó polárszög szerint. Ekkor a feladat megoldása a következoképpen adható meg.
public class Poligon{ public static int[] Osszekot(Pont[] P){ int n=P.length; int[] S=new int[n]; //bal-alsó sarokpont szerinti polár-szög rendezés Geom.SarokRendez(P); for (int i=0; i
A S AROK R ENDEZ eljárás a kupacrendezést használva rendezi a ponthalmazt. A R EN DEZ .K UPAC R END 1 eljárásnak paraméterként adjuk meg az r rendezési relációt, ami az (1-3) képletet valósítja meg.
public int int for
static void SarokRendez(Pont[] P){ mi=0; n=P.length; (int i=1; i
}
Tehát a teljes feladat megoldása:
public class Polifelad{ public static void main (String[] args)throws IOException{ Pont[] P=BeOlvas(); int[] S=Poligon.Osszekot(P); KiIr(S); } public static Pont[] BeOlvas()throws IOException{ Scanner bef = new Scanner(new File("poligon.be")); int n=bef.nextInt(); bef.nextLine(); Pont[] P=new Pont[n]; for (int i=0; i
static void KiIr(int[] S)throws IOException{ PrintWriter kif=new PrintWriter( new BufferedWriter( new FileWriter("poligon.ki") ) ); for (int x:S) kif.print(x+" "); kif.println(); kif.close(); } }
˝ Gyakran elofordul, hogy a síkon adott p1 és p2 pontra el kell dönteni, hogy a p1 ponthoz képest a p2 pont milyen forgásirányba esik. Tekintsük a 3. ábrán látható p1 és p2 vektorokat. A p1 × p2 keresztszorzat a (0, 0), p1 , p2 és a p1 + p2 = (p1 .x + p2 .x, p1 .y + p2 .y) pontok által ˝ ˝ alkotott paralelogramma elojeles területeként értelmezheto.
x2
x1
p1 + p2
y1 p2
y2
y2 p1 y1 x1
x2
(0, 0)
˝ 3. ábra. A paralelogramma elojeles területe:
T = (x1 + x2 )(y1 + y2 ) − x1 y1 − x2 y2 − x2 y1 − x2 y1 = x1 y1 + x1 y2 + x2 y1 + x2 y2 − x1 y1 − x2 y2 − x2 y1 − x2 y1 = x1 y2 − x2 y1
y
p1 + p2
y
p p2 (0, 0)
x
p1 (0, 0)
x (b)
(a)
˝ 4. ábra. (a) A p1 és p2 vektorok keresztszorzata a paralelogramma elojeles területe. (b) A ˝ órajárással egyezo˝ irányba világos tartomány azokat a pontokat tartalmazza, amelyek a p-tol ˝ esnek, a sötétebb pedig azokat, amelyek órajárással ellentétes irányba esnek p-tol.
p1 × p2
x1 x2 = det y1 y2 = x1 y2 − x2 y1 = −p2 × p1 .
p1 × p2 > 0 ⇔ p2 az órajárással ellentétes irányban van p1 -hez képest. p1 × p2 = 0 ⇔ a (0, 0), p1 és p2 pontok egy egyenesre esnek (kollineárisak). p1 × p2 < 0 ⇔ p2 az órajárás irányban van p1 -hez képest.
→ −−→ Még általánosabban, adott két csatlakozó irányított szakasz, − p− 0 p1 és p1 p2 , milyen irányba − − → − − → fordul p1 p2 a p0 p1 -hez viszonyítva? A válasz (p1 − p0 )×(p2 − p0 ) = (p1 .x− p0 .x)(p2 .y− p0 .y)−(p2 .x− p0 .x)(p1 .y− p0 .y) keresztp2
p2 p1
p1
p0
p0
5. ábra. Csatlakozó szakaszok forgásiránya.
˝ szorzat elojele alapján megadható. → (p1 − p0 ) × (p2 − p0 ) > 0 : − p− 1 p2 balra fordul, → −−→ (p1 − p0 ) × (p2 − p0 ) = 0 : − p− 0 p1 és p1 p2 kollineárisak, → (p1 − p0 ) × (p2 − p0 ) < 0 : − p− 1 p2 jobbra fordul.
public static int ForgasIrany(Pont p0, Pont p1, Pont p2){ /** Kimenet: +1 ha p0->p1->p2 balra fordul, * 0 ha p0,p1 és p2 kollineárisak, * -1 ha p0->p1->p2 jobbra fordul. */ double p1xp2=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); return (int)Math.signum(p1xp2); } Annak eldöntése, hogy a kollineáris p0 , p1 , p2 pontok esetén p1 közelebb van-e p0 -hoz, mint p2 :
public static boolean Kozel(Pont p0, Pont p1, Pont p2){ /** *Feltétel: (p0,p1,p2) kollineáris *Kimenet: p1 közelebb van p0-hoz, mint p2 */ return Math.abs(p1.x-p0.x)<Math.abs(p2.x-p0.x) || Math.abs(p1.y-p0.y)<Math.abs(p2.y-p0.y) ; }
p1 max(p1.y,p2.y) q
q.y
min(p1.y,p2.y)
p2
min(p1.x,p2.x)
q.x
max(p1.x,p2.x)
6. ábra. A q pont a p1 p2 szakaszra esik, ha p1 , p2 és q kollineárisak és min(p1 .x, p2 .x) ≤ q.x ≤ max(p1 .x, p2 .x) és min(p1 .y, p2 .y) ≤ q.y ≤ max(p1 .y, p2 .y).
public static boolean Kozte(Pont p1, Pont p2, Pont q){ return Math.abs(p1.x-q.x)<=Math.abs(p2.x-p1.x) && Math.abs(p2.x-q.x)<=Math.abs(p2.x-p1.x) && Math.abs(p1.y-q.y)<=Math.abs(p2.y-p1.y) && Math.abs(p2.y-q.y)<=Math.abs(p2.y-p1.y) ; }
A F ORGAS I RANY és a KOZEL felhasználásával megadhatjuk a bal-alsó sarokponthoz viszonyított polárszög szerinti rendezés rendezési relációját.
/** *A this.sarok bal-alsó sarokponthoz viszonyított pollárszög szerinti rendez *rendezési relációja */ public class SarokRend implements Comparator
{ Pont sarok; //a ponthalmaz bal-alsó sarokpontja public int compare(Pont p1, Pont p2){ if (p1.x==p2.x && p1.y==p2.y) return 0; int forg=Geom.ForgasIrany(sarok,p1,p2); return (forg>0 || forg==0 && Geom.Kozel(sarok,p1,p2)) ? -1:1; } SarokRend(Pont q){ sarok=new Pont(q.x,q.y); } SarokRend(){ sarok=new Pont(); } }
˝ Hasonlóképpen, tetszoleges q pontra vonatkozó polárszög szerinti rendezés rendezési relációja is megadható a F ORGAS I RANY és a KOZTE felhasználásával. 13 11 14
12 2
q
1
9
3
10
7
4
8
5 6
7. ábra. A q pontra vett polárszög szerinti rendezés. A pont mellé írt szám a pontnak a rendezésbeli sorszáma.
/** A this.polar ponthoz viszonyított pollárszög szerinti rendezés * rendezési relációja */ public class PolarRend implements Comparator{ private Pont polar; public int compare(Pont p1, Pont p2){ if (p1.x==p2.x && p1.y==p2.y) return 0; int forg=Geom.ForgasIrany(polar,p1,p2); switch (forg){ case -1: return (p1.y<=polar.y && p2.y>polar.y) ? -1:1; case 0 : return Geom.Kozte(polar,p2,p1) || Geom.Kozte(p1,p2,polar) && (p1.y<polar.y || p1.y==polar.y && p1.x<polar.x) ? -1:1; case 1 : return (p1.y<=polar.y || p2.y>polar.y) ? -1:1; default : return 0; } }
9.3.
Feladat: Pont helyzetének megállapítása.
Adott a síkon egy zárt, nem-metszo˝ poligon a csúcsainak p1 , . . . , pn órajárással ellentétes felsorolásával és adott egy q pont. Eldöntendo˝ a q pontnak a poligonhoz képesti helyzete, azaz, hogy a belsejéhez tartozik-e, az oldalán van-e, avagy külso˝ pont?
Megoldás Válasszunk egy olyan q0 pontot, amely biztosan nem tartozik a poligon belsejéhez és a poligon egyetlen csúcsa sem esik a q0 q szakaszra, legfeljebb ha q megegyezik valamelyik csúccsal. (Van ilyen pont.) ˝ Ha a q0 q szakasz a poligon páratlan számú oldalát metszi, akkor q belso˝ pont, egyébként külso.
q
q0
8. ábra. A q0 q szakasz a poligon páratlan sok oldalát metszi, tehát belso˝ pont.
q
q0
9. ábra. A poligonnak több csúcsa is a q0 q szakaszra esik.
A q0 külso˝ pont választása. Legyen q0 .y = max{pi .y|pi .y < q.y, i = 1, . . . n} és q0 .x = min{pi .x|i = 1, . . . n} − 1. Ha a poligonnak nincs olyan csúcspontja, amelynek y-koordinátája kisebb, mint q.y, akkor q biztosan külso˝ pont. A q0 pont ilyen választása esetén legfeljebb a q pont esik a poligon valamelyik
q
q0
10. ábra. A q0 pont választása:q0 .y = max{pi .y|pi .y < q.y, i = 1, . . . n} és q0 .x = min{pi .x|i = 1, . . . n} − 1.
˝ oldalára, amikor is q nem belso˝ pont lesz. Ezt az esetet külön ellenorizzük. Egyébként, a poligon bármely pi pi+1 oldalának akkor és csak akkor van közös pontja a q0 q szakasszal, ha pi és pi+1 az e(q0 , q) egyenes különbözo˝ oldalára esik és a q0 és q pont az e(pi , pi+1 ) egyenes különbözo˝ oldalára esik. Ez a feltétel a F ORGÁS I RANY eljárás felhasználásával egyszeruen ˝ kiszámítható.
p1 max(p1.y,p2.y) q
q.y
min(p1.y,p2.y)
p2
min(p1.x,p2.x)
q.x
max(p1.x,p2.x)
11. ábra. A q pont a p1 p2 szakaszra esik, ha p1 , p2 és q kollineárisak és |q.x − p1 .x| ≤ |p2.x − p1.x| és |q.x − p2 .x| ≤ |p2.x − p1.x|
/** a p1-p2 szakaszon van-e a q pont? */ public static boolean Szakaszon(Pont p1, Pont p2, Pont q){ double fir=(p1.x-q.x)*(p2.y-q.y)-(p2.x-q.x)*(p1.y-q.y); return fir==0.0 && Math.abs(q.x-p1.x)<=Math.abs(p2.x-p1.x) && Math.abs(q.x-p2.x)<=Math.abs(p2.x-p1.x) && Math.abs(q.y-p2.y)<=Math.abs(p2.y-p1.y) && Math.abs(q.y-p2.y)<=Math.abs(p2.y-p1.y) ; }
/** Kimenet: -1 ha a q pont a poligon belsejében van, * 0 az oldalán van, * +1 ha kivül van */ public static int PontHelyzete(Pont[] P, Pont q){ int n=P.length; double y0=q.y; double x0=P[0].x; for (int i=1; iy0 || y0==q.y) ) y0=P[i].y; if (P[i].x<x0) x0=P[i].x; } Pont q0=new Pont(x0-1,y0); int metsz=0; for (int i=0; i
A algoritmus futási ideje legrosszabb esetben is a poligon csúcsainak n számával arányos, tehát O(n).
9.4.
Metszo˝ szakaszpárok
˝ hogy metszi-e egymást adott p1 p2 és q1 q2 szakasz? Eldöntendo, p2
p2
p2
q2 q2 q1 p1
q1 q1
p1
p1
q2
p2
p1
q2 q2 p1
p2 q1 q1
12. ábra. Szakaszpárok metszésének öt lehetséges esete.
public class Szakasz{ Pont bal, jobb; //a szakasz bal- és jobb-végpontja int az; //a szakasz azonisítója Szakasz(Pont b, Pont j, int a){ bal=b; jobb=j; az=a; } Szakasz(Pont b, Pont j){ bal=b; jobb=j; } Szakasz(){} } public static boolean SzakaszParMetsz(Szakasz s1, Szakasz s2){ int fpq1=ForgasIrany(s1.bal,s1.jobb,s2.bal); int fpq2=ForgasIrany(s1.bal,s1.jobb,s2.jobb); int fqp1=ForgasIrany(s2.bal,s2.jobb,s1.bal); int fqp2=ForgasIrany(s2.bal,s2.jobb,s1.jobb); return (fpq1*fpq2<0) && (fqp1*fqp2<0) || fpq1==0 && Kozte(s1.bal,s1.jobb,s2.bal) || fpq2==0 && Kozte(s1.bal,s1.jobb,s2.jobb) || fqp1==0 && Kozte(s2.bal,s2.jobb,s1.bal) || fqp2==0 && Kozte(s2.bal,s2.jobb,s1.jobb); }
9.5.
Ponthalmaz konvex burka
˝ poligon konvex, ha bármely két belso˝ pontját összeköto˝ Definíció. Egy egyszeru˝ (nem metszo) szakasz minden pontja a poligon belsejében, vagy határán van. Definíció. Egy P = {p1 , . . . , pn } ponthalmaz konvex burka az a legszukebb ˝ Q konvex poligon, amely a ponthalmaz minden pontját tartalmazza . Megoldás Graham-féle pásztázással Elso˝ lépésként rendezzük a ponthalmazt polárszög szerint, majd minden egyenesen csak a sarokponttól legtávolabbi pontot hagyjuk meg, a többit töröljük. Az így törölt pontok biztosan nem lehetnek csúcspontjai a konvex buroknak. Legyen hq1 , . . . , qm i az így kapott pontsorozat polárszög szerinti rendezésben. Mindaddig, amíg van három olyan cirkulárisan egymást követo˝ −−−→ −−−→ qi , qi+1 qi+2 pont, hogy − q− i+1 qi+2 jobbra fordul qi qi+1 -hez képest, hagyjuk el a qi+1 pontot. Az algoritmus futási ideje O(n lg n), ha a polárszög szerinti rendezést olyan algoritmussal valósítjuk meg amelynek futási ideje O(n lg n).
13. ábra. Ponthalmaz konvex burka.
14. ábra. A pontok halmazának rendezése polárszög szerint.
15. ábra. Minden egyenesen csak a legtávolabbi pont marad meg.
/** *Konvex burok Graham-féle páztázó algoritmusa *Bemenet: Pont[] P ponthalmaz *Kimenet: m: a konvex burok pontjainak száma * P[0..m-1] tartalmazza a konvex burok pontjait */ public static int GrahamKB(Pont[]P){ int n=P.length; Pont x; SarokRendez(P); int m=1; for (int i=2; i0 && ForgasIrany(P[m-1],P[m], P[i])<=0) m--; m++; x=P[m]; P[m]=P[i]; P[i]=x; } return m; }
9.6.
˝ Érinto˝ egyenes keresése lineáris idoben
9.1. definíció. Legyen P ponthalmaz, a ∈ P és q egy pont. Azt mondjuk, hogy az e(q, a) a P ponthalmaz jobboldali érinto˝ (támasztó) egyenese, ha P minden − pontja → qa-tól nem jobbra van. Hasonlóan, az e(q, a) a P ponthalmaz baloldali − érinto˝ (támasztó) egyenese, ha P minden pontja → qa-tól nem balra van.
b
a
q
16. ábra. e(q, a) a P ponthalmaz jobboldali, e(q, b) pedig a baloldali érinto˝ egyenese.
Nyilvánvaló, hogy akkor és csak akkor létezik adott q ponton átmeno˝ érinto˝ egyenes, ha q a P ponthalmaz konvex burkán kivül, vagy az oldalán van. Feladat: érinto˝ egyenes meghatározása. Bemenet: P ponthalmaz, q pont Kimenet: 1. (a, 0, 0), ha P minden pontja az e(q, a) egyenesre esik 2. (a, b, 0), ha q a P konvex burkán kivül van, és ekkor e(q, a) jobboldali, e(q, b) pedig baloldali érinto˝ egyenes 3. (a, b, c), ha q a P konvex burkán belül van, és ekkor a, b és c olyan három pontja P-nek, hogy q az 4(a, b, c) háromszög belsejébe, vagy oldalára esik, de P egyetlen más pontja sem esik a háromszögbe sem oldalára.
4 b
a
3
q
1
2
4 b
a
3
q
1
P[i]
2
4 b
a
P[i]
3
q
1
2
4 b
a = P[i]
3
q
1
2
4 b
a = P[i]
3
q
1
2
4
b =P[i]
a
3
q
1
2
c
q a b 17. ábra.
c
q a b
c
q a b
c
q a b
public static int[] Erinto(Pont[] P, Pont q){ /* Bemenet: P pon Kimenet: (i,0,0) ha P minden pontja az e(q,P[i+1]) egyenesre esik (a,b,0) ha q a P konvex burkán kívül van, és ekkor az e(q,a) és e(q,b) a két érint˝ o egyenes (a,b,c) ha q a P konvex burkán belül van, és ekkor (a,b,c) olyan háromszög, hogy q a háromszögben van, és a,b és c kivételével P egyetlen pontja sem esik a háromszögbe, sem oldalára. */ int n=P.length; int[] abc={0,0,0}; Pont a=P[0]; Pont b=null; Pont c=null; int firqa,firqb, firqc; int i=0; for (i=1; i
b=P[i]; if (Geom.ForgasIrany(q,a,b)<0){//q-a-tól b balra essen a=b; b=P[0]; } for (int j=1; j=0 || firqa<=0 && firqb>0){//1.eset c=P[j]; break; }else if (firqa<0 && firqb<0){//2.eset a=P[j]; }else if (firqa>0 && firqb>0){//3.eset b=P[j]; }//else nincs mit tenni, sem a, sem b nem vátozik } //ha c==null, akkor q kivül van, és ekkor e(q,a) és e(q,b) érin if (c==null){ abc[0]=a.az; abc[1]=b.az; abc[2]=0; return abc; }
//Az (a,b,c) háromszög tartalmazza a q pontot, finomítás: for (int i=0; i=0 && Geom.ForgasIrany(b,c,P[i])>=0 && Geom.ForgasIrany(c,a,P[i])>=0){ firqa=Geom.ForgasIrany(q,a,P[i]); firqb=Geom.ForgasIrany(q,b,P[i]); firqc=Geom.ForgasIrany(q,c,P[i]); if (firqb<=0 && firqc>=0){ a=P[i]; }else if (firqa>=0 && firqc<=0){ b=P[i]; }else { c=P[i]; } } abc[0]=a.az; abc[1]=b.az; abc[2]=c.az; return abc; }//Erinto
9.7.
Feladat: Ponthalmaz legtávolabbi pontpárja.
Adott a síkon egy P = {p1 , . . . , pn } ponthalmaz. Határozzuk meg a ponthalmaz egy legtávolabbi pontpárját! Megoldás. A naiv algoritmus, amely minden pontpárra kiszámítja azok távolságát, futási n (n−1) n−1 ideje O(∑i=1 i) = 2 = O(n2 ). Konvex burok alkalmazásával O(n lg n) ideju˝ algoritmust adhatunk. 9.2. lemma. A legtávolabbi pontpár P konvex burkának két pontja lesz. Definíció A P ponthalmaz átellenes pontpárja olyan pi és p j pontpár, hogy ha van olyan pi -n és p j -n átmeno˝ egyenes, amelyek párhuzamosak és a P ponthalmaz minden pontja a két egyenes közé esik. Konvex poligon összes átellenes pontpárjának meghatározása görgetéssel. Legyen P = hp1 , . . . , pm i a konvex poligon csúcspontjainak órajárással ellentétes felsorolása. Legyen pi a konvex poligon legkisebb y-koordinátájú pontja, ha ketto˝ ilyen van, akkor ezek közöl válasszuk a legnagyobb x-koordinátájút. Legyen továbbá p j pedig a legnagyobb y-koordinátájú pontja, ha ketto˝ ilyen van, akkor ezek közül
válasszuk a legkisebb x-koordinátájút. pi és p j nyilvánvalóan átellenes pontjai a poligonnak. ˝ Az összes átellenes pontpár lineáris idoben meghatározható görgetéssel.
pj
p j+1
pi+1 pi
18. ábra. Görgetés
Ha az e(pi , pi+1 ) egyenes hajlásszöge kisebb, mint az e(p j , p j+1 ) egyenes hajlásszöge, akkor a pi+1 és p j is átellenes pontpár lesz, egyébként a pi p j+1 ˝ Forgassuk el balra a 14.ábrán lesz átellenes pontpár. (a +1 modulo m értendo). látható pi és p j pontokon átmeno˝ párhuzamos egyeneseket amíg valamelyik a − −→ −−−−→ −→ ˝ p− érjük el a − p− i pi+1 vagy a p j p j+1 oldalra nem ér. Ha elobb i pi+1 oldalt, akkor i := i + 1, egyébként j := j + 1. Folytassuk ezt mindaddig, amíg vissza nem érünk a kezdetben választott két átellenes ponthoz. A szögek viszonya eldöntheto˝ a következo˝ kifejezéssel:
F ORGAS I RANY(p j+1 , pi+1 − pi + p j+1 , p j ) > 0 Következmény n elemu˝ ponthalmaz egy legtávolabbi pontpárja O(n lg n) ideju˝ algoritmussal kiszámítható. Következmény n elemu˝ ponthalmaz vastagsága O(n lg n) ideju˝ algoritmussal kiszámítható.
public class LTavolPontpar{ private static Pont Eltol(Pont q1, Pont q2, Pont q3){ return new Pont(q3.x-q2.x+q1.x, q3.y-q2.y+q1.y,0); } /**@return A P ponthalmat legtavolabbi pontpárja */ public static PontPar ParKeres(Pont[] P){ int n=P.length; int m=Geom.GrahamKB(P); int i0=0; int j0=0; int i,j,ii,jj; double irany; /* A konvex burok két átellenes pontjának meghatározása */ for (int k=1; k<m; k++){ if (P[k].yP[i0].x))i0=k; if (P[k].y>P[j0].y||(P[k].y==P[j0].y&&P[k].x
double maxtav=(P[i0].x-P[j0].x)*(P[i0].x-P[j0].x)+ (P[i0].y-P[j0].y)*(P[i0].y-P[j0].y); PontPar Ptavol=new PontPar(P[i0], P[j0], maxtav); double ujtav; i=i0; j=j0; do{ //görgetés ii=(i+1)%m; jj=(j+1)%m; irany=Geom.ForgasIrany(P[jj],Eltol(P[jj],P[i],P[ii]),P[j]) if (irany>0){ i=ii; ii=(i+1)%m; }else { //irany>=0 j=jj; jj=(j+1)%m; } ujtav=(P[i].x-P[j].x)*(P[i].x-P[j].x)+ (P[i].y-P[j].y)*(P[i].y-P[j].y); if (ujtav>maxtav){ Ptavol.a=P[i]; Ptavol.b=P[j]; maxtav=ujtav; } }while(i!=i0 || j!=j0);
Ptavol.abtav=Math.sqrt(maxtav); return Ptavol; } }
9.8.
Metszo˝ szakaszpárok létezésének vizsgálata
Bemenet:
S = {s1 = p1 q1 , . . . sn = pn qn } Kimenet: ˝ i, j : 1 ≤ i < j ≤ n, a pi qi és p j q j szakasz metszo, 0, 0 ha nincs ilyen i, j pár. Sepro˝ egyenes Seprés során egy képzeletbeli sepro˝ egyenest mozgatunk a geometriai elemek ˝ halmazán. Azt a dimenziót, amelyben a sepro˝ egyenes halad, idodimenziónak hívjuk. Jelen esetben a sepro˝ egyenes az y-tengellyel párhuzamos egyenes, az ˝ idodimenzió az x-koordináta lesz. Egyszerusít ˝ o˝ feltételek: ˝ 1. Egyik bemeneti szakasz sem függoleges. 2. Nincs három olyan szakasz, amelyek egy pontban metszenék egymást. s = pq szakasz esetén : s.bal = p és s. jobb = q jelölést használjuk. A pontok koordinátáira pedig p.x és
p.y
9.9.
Szakaszok rendezése
Legyen s1 és s2 szakasz és x ∈ R Azt mondjuk, hogy s1 összehasonlítható s2 -vel x-nél, ha
s1 .bal.x ≤ x ≤ s1 . jobb.x ∧ s2 .bal.x ≤ x ≤ s2 . jobb.x 9.3. definíció. Az s1 szakasz felette van az s2 szakasznak, jelben s1 >x s2 , ha s1 összehasonlítható s2 -vel x-nél és az x sepero˝ egyenesnek s1 -el vett metszete magasabban van, mint s2 -el vett metszete. 9.4. Állítás. A >x reláció lineáris rendezési reláció 9.5. Állítás. Ha x1 < x2 -re s1 >x1 s2 és s2 >x2 s1 , akkor az s1 és s2 szakasz metszi egymást x1 és x2 között. Továbbá, ha x1 és x2 a sepro˝ egyenes két egymást követo˝ megállási helye, akkor x1 -ben a két szakasz egymást követo˝ lesz a rendezésben. Bizonyítás. Az ábráról látható.
˝ Tehát elegendo˝ ellenorizni minden szakasz berakásakor, hogy a rendezésben ˝ megeloz ˝ o, ˝ és követo˝ szakasz metszi-e a berakottat, és kivételkor ellenorizni, ˝ ot ˝ o˝ és követo˝ szakaszok metszik-e egymást. hogy a kivett szakaszt megeloz
x1
x2
x1
x2
19. ábra.
9.10.
A sepro˝ egyenes mozgatása
˝ ˝ 1. Esetpontok jegyzéke: azon idopontok (rendezett) sorozata, amely idopontokban a sepro˝ egyenes megáll. 2. A sepro˝ egyenes állapotleírása: az egyenes által metszett elemek rendezett halmaza. S Esetpontok jegyzéke: = {s.bal.x : s ∈ S} {s. jobb.x : s ∈ S} Pontosabban: tegyük fel, hogy a szakaszok az S[1], . . . , S[n] felsorolással adottak. Feltételezzük, hogy S[i].bal.x < S[i]. jobb.x
x 20. ábra. Az esetpontok jegyzéke azon x értékek halmaza, ahol a sepro˝ egyenes megáll.
VegP = {hS[i].bal.x,true, ii : i = 1, . . . , n}
[
{hS[i]. jobb.x, f alse, ii : i = 1, . . . , n}
˝ Rendezzük a VegP halmaz elemeit a sepro˝ egyenes haladásának megfeleloen, ˝ azaz a hx1, b1, i1i hármas akkor és csak akkor elozze meg az hx2, b2, i2i hármast, ha x1 < x2 vagy x1 = x2 és b1 = true és b2 = f alse vagy x1 = x2 és b1 = true és b2 = true és S[i1].bal.y < S[i2].bal.y vagy x1 = x2 és b1 = f alse és b2 = f alse és S[i1]. jobb.y < S[i2]. jobb.y Állapotleírás adott x-re legyen F az x-ben összehasonlítható szakaszok >x szerint rendezett halmaza. A sepro˝ egyenes mozgatásakor, azaz a VegP szakaszvégpontok fenti rendezése szerint haladva: Ha a hx, b, ii hármas az aktuális elem, akkor Ha b = true, azaz x az i. szakasz bal-végpontja, akkor szúrjuk be az si szakaszt F -be. Ha b = f alse, azaz x az i. szakasz jobb-végpontja, akkor töröljük az si szakaszt ˝ F -bol.
si.bal
si. jobb
s j. jobb sj si
si s j.bal
sj s j. jobb
si. jobb
s j.bal si.bal x
x 21. ábra.
s j .bal
si.bal
sj
si
si.bal
si. jobb
s j .bal s j . jobb x 22. ábra.
si si. jobb
sj
x
s j . jobb
˝ határozzuk meg a beszúrt si szakasz követojét ˝ Beszúrást közvetlenül követoen F -ben. Ha ez metszi si -t, akkor készen vagyunk. Hasonlóan, a beszúrást ˝ ˝ ojét ˝ F -ben. közvetlenül követoen határozzuk meg a beszúrt si szakasz megeloz Ha ez metszi si -t, akkor készen vagyunk. ˝ oen ˝ Törlés esetén a törlést megeloz határozzuk meg a törlendo˝ si szakaszt F ˝ o˝ s j1 és követo˝ s j2 szakaszokat. Ha mindketto˝ létezik és metszik ben megeloz egymást, akkor készen vagyunk. Tehát az alábbi muveletekre ˝ van szükség: B OVIT (F, I ) TOROL (F, I ) E LOZ (F, I ) KOVET (F, I ) Az RH ALMAZ adattípus mindezen muveleteket ˝ biztosítja.
Megvalósítás. ˝ Ezek a muveletek ˝ hatékonyan megvalósíthatók kiegyensúlyozott keresovával, pl. AVL-fával, vagy piros-fekete fával. Ekkor minden muvelet ˝ futási ideje legrosszabb esetben O(lg n). Ekkor az algoritmus futási ideje legrosszabb esetben O(n lg n) lesz, mivel a ˝ VegP halmaz rendezheto˝ O(n lg n) idoben, továbbá az, hogy két szakasz metszi˝ e egymást O(1) idoben megállapítható. ˝ A kiegyensúlyozott bináris keresofában nem kulcs szerinti a rendezés. Az adatmezo˝ tartalmazza a szakasz sorszámát, S a szakaszok tömbje legyen globális ˝ az eljárásokra nézve. A keresofában a < összehasonlítás legyen a <x reláció:
public class SzakaszMetszKereso{ private static class SeproE implements Comparable<SeproE>{ /** A sepr˝ o egyenes megállási pontjainak típusa */ double x,y; int az; boolean bal; SeproE(double xx, double yy, boolean b, int a){ x=xx; y=yy; bal=b; az=a; } public int compareTo(SeproE e){ if (this.x==e.x&&this.bal==e.bal&&this.az==e.az) return 0; if (this.x<e.x || this.x==e.x && this.bal && !e.bal|| this.x==e.x && this.bal==e.bal && this.y<e.y ){ return -1; }else return 1; } }
private static class FElem implements Comparable{ /** A Felett rendezési reláció megvalósítása */ public Szakasz[] S; int ind; public int compareTo(FElem e){ int fir; if (this.ind==e.ind) return 0; if (S[ind].bal.x<=e.S[e.ind].bal.x){ fir=Geom.ForgasIrany( S[ind].bal, S[ind].jobb, e.S[e.ind].bal); }else{ fir=-Geom.ForgasIrany( e.S[e.ind].bal,e.S[e.ind].jobb,S[ind].bal); } return (fir<0||fir==0&&ind<e.ind)?-1:1; } FElem(Szakasz[] q, int az){ S=q; ind=az;} FElem(){} }
public static Szakasz[] Keres(Szakasz[] S){ Szakasz[] MetszoPar=new Szakasz[2]; //az két metsz˝ o szakasz int n=S.length; SeproE[] VegP=new SeproE[2*n];//a sepr˝ o egyenes megállási po for (int i=0; i F=new RHalmazFa("PF"); FElem p, q; FElem t=new FElem();
for (int ii=0; ii<2*n; ii++){ int i=VegP[ii].az; if (VegP[ii].bal){ FElem e=new FElem(S,i); F.Bovit(e); p=F.Elozo(e); if (p!=null && Geom.SzakaszParMetsz(S[i],S[p.ind]) ){ MetszoPar[0]=S[i]; MetszoPar[1]=S[p.ind]; break; } p=F.Koveto(e); if (p!=null && Geom.SzakaszParMetsz(S[i],S[p.ind]) ){ MetszoPar[0]=S[i]; MetszoPar[1]=S[p.ind]; break; } }else{ t.S=S; t.ind=i; p=F.Elozo(t); q=F.Koveto(t); if (p!=null&&q!=null&& Geom.SzakaszParMetsz(S[p.ind],S[q.ind])){ MetszoPar[0]=S[p.ind]; MetszoPar[1]=S[q.ind]; break; }
F.Torol(t); } } return MetszoPar; } }
9.11.
Legközelebbi pontpár megkeresése
Legyen p és q a p síkon két pont. A két pont távolsága az Euklideszi távolság, azaz tav(p, q) = (p.x − q.x)2 + (p.y − q.y)2 . Bemenet: P = {p1 , . . . pn } ponthalmaz Kimenet: i, j : 1 ≤ i < j ≤ n, a tav(pi , p j ) minimális. Oszd-meg-és-uralkodj elvu˝ algoritmus. Legyen S a pontok (azonosítóinak) halmaza, X a pontok (azonosítóinak) xkoordináta szerint rendezett sorozata, Y pedig pontok (azonosítóinak) y-koordináta szerint rendezett sorozata.
Elvi algoritmus: Bemenet: S, X,Y Kimenet: d min. távolság, a, b két legközelebbi pont; tav(a, b) = d TAV K ERES (S,X,Y, D, A , B ) begin {TavKeres} if |S| ≤ 3 then Begin ˝ minden pontpárra ellenorizzük a távolságot és vegyük a legkisebbet; Exit; end; SL := S-nek d|S|/2e számú eleme x-koordináta szerint; SR := S-nek b|S|/2c számú eleme x-koordináta szerint; ˝ x-kootdináta érték; x0 := a felosztó (felezo) XL := SL elemeinek x-koordináta szerint rendezett sorozata; XR := SR elemeinek x-koordináta szerint rendezett sorozata; TAV K ERES(SL , XL ,YL , dL , aL , bL ); TAV K ERES(SR , XR ,YR , dR , aR , bR ); d := min(dL , dR ); Y d := azon S-beli pontok halmaza, amelyek x-koordinátájára |x0 − x| ≤ d ; Y d legyen y-koordináta szerint rendezett;
Ha van Y d -ben d -nél közelebbi pár, akkor azt adjuk vissza, egyébként d -t; end {TavKeres}
Állítás. Y d -ben elég minden p pontra csak p-t követo˝ 7 pontra nézni a távolságot, hogy találjuk d -nél közelebbi pontpárt, ha létezik ilyen. Futási ido˝ legrosszabb esetben.
T (n) = 2 T (n/2) + O(n) Tehát T (n) = (n lg n) Megvalósítás
pL
pR
δ SL
δ l
SR
23. ábra. A sik (tartomány) két részre osztása az l egyenessel.
Itt két pont is lehet,
δ
egy SL -ben, egySR -ben
δ SL
δ l
SR
˝ u˝ sávban adott p ponthoz legfeljebb 7 olyan pont lehet, amelynek p-tol ˝ vett 24. ábra. A δ átméroj ˝ távolsága legfeljebb δ. Ezek a pontok a y-koordináta szerinti rendezésben egymást követok.
public class LKozelPontpar{ private static class XKoord implements Comparator{ public int compare(Pont p1, Pont p2 ){ return (p1.x{ public int compare(Pont p1, Pont p2 ){ return (p1.y
public static PontPar ParKeres( Pont[] X, Pont[] Y, Pont[] Z, int bal, int jobb){ if (jobb-bal == 1) // csak két pont van return new PontPar(X[bal],X[jobb],Geom.Tav(X[bal],X[jobb if (jobb-bal == 2){ // 3 pont van, minden párra kiszámoljuk a táv-ot double t1 = Geom.Tav(X[bal], X[bal+1]); double t2 = Geom.Tav(X[bal+1], X[jobb]); double t3 = Geom.Tav(X[bal], X[jobb]); if (t1 <= t2 && t1 <= t3) return new PontPar(X[bal], X[bal+1], t1); if (t2 <= t3) return new PontPar(X[bal+1], X[jobb], t2); else return new PontPar(X[bal], X[jobb], t3); }
int kozep=(bal+jobb) >>1; int zbal = bal, // kurzor Z[bal:kozep]-hez zjobb = kozep+1; // kurzor Z[kozep+1:jobb]-hez for (int i = bal; i <= jobb; i++) if (Y[i].az <= kozep) Z[zbal++] = Y[i]; else Z[zjobb++] = Y[i]; // uralkodj PontPar balkozel = ParKeres(X, Z, Y, bal, kozep); PontPar jobbkozel = ParKeres(X, Z, Y, kozep+1, jobb); PontPar kozel; kozel= (balkozel.abtav<jobbkozel.abtav)? balkozel : jobbkoz
// Y rekonstruálása: Z[bal:kozep], Z[bal+1,jobb]->Y[bal:jobb] int k=bal; {int i=bal; int j=kozep+1; while (i<=kozep && j<=jobb) //összefésülés if (Z[i].y
for (int i = bal; i <= jobb; i++) if (Math.abs(X[kozep].x - Y[i].x) < kozel.abtav) Z[k++] = Y[i];
for (int i = bal; i < k-1; i++) for (int j=i+1; j
public static PontPar ParKeres(Pont[] P){ int n=P.length; int [] Az=new int[n]; //eredeti pont-azonosítok mentésére Pont[] X=new Pont[n]; //x-szerint rendezett ponthalmaz Pont[] Y=new Pont[n]; //y-szerint rendezett ponthalmaz Pont[] Z=new Pont[n]; //segéd for (int i=0; i
XKoord Xrend=new XKoord();//x-szerinti rendezés relációja Rendez.KupacRend2(X,Xrend);//el˝ orendezés x-koord szerint for (int i=0; i
