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
R R
Pont: (x, y) ∈ × 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 szakaszok˝ kal, 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.
1
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. ˝ és pi elobb ˝ legyen mint p j akkor és csak akkor, ha Rendezzük a pontokat úgy, hogy a Q sarokpont legyen az elso, pi
φ(Q, pi) Q
Q
φ(Q, pi)
pi
˝ 1. ábra. A pi ponthoz tartozó elojeles szög: φ(Q, pi ). 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. Hogyan döntheto˝ el, hogy φ(Q, pi ) < φ(Q, p j )? ˝ tehát Minden i > 1-re − π2 < φ(Q, pi ) ≤ π2 és ebben a tartományban a tangens függvény szigorúan 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) 2
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.
˝ 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) ∨ (pi .y − Q.y)(p j .x − Q.x) = (p j .y − Q.y)(pi .x − Q.x) ∧ pi .x < p j .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 < p j .y
(3)
(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(){} } Tegyük fel, hogy van olyan S AROK R ENDEZ eljárásunk, amely a P ponthalmazt rendezi a bal-alsó sarokpontjára vonat˝ kozó 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
//egy helyes sorrend: S[0..i],S[n-1]..S[i+1] int j=n-1; i++; while (i<j){ int x=S[i]; S[i++]=S[j]; S[j--]=x; } return S; } } A S AROK R ENDEZ eljárás a kupacrendezést használva rendezi a ponthalmazt. A R ENDEZ .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 x2
x1 (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
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 sza→ −−→ −−→ −−→ kasz, − 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) keresztszorzat elojele alapján megadható. 5
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 világos tartomány azokat a ˝ órajárással egyezo˝ irányba esnek, a sötétebb pedig azokat, amelyek órajárással pontokat tartalmazza, amelyek a p-tol ˝ ellentétes irányba esnek p-tol.
p2
p2 p1
p1
p0
p0
5. ábra. Csatlakozó szakaszok forgásiránya.
6
(p1 − p0 ) × (p2 − p0 ) > 0 : (p1 − p0 ) × (p2 − p0 ) = 0 : (p1 − p0 ) × (p2 − p0 ) < 0 :
− → p− 1 p2 balra fordul, − → −−→ p− 0 p1 és p1 p2 kollineárisak, − p−→ p jobbra fordul. 1 2
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 :
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 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) ; } 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. 7
/** *A this.sarok bal-alsó sarokponthoz viszonyított pollárszög szerinti rendezés *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 OR GAS 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); 8
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.) ˝ A q0 külso˝ 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.
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 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ó.
/** a p1-p2 szakaszon van-e a q pont? */ 9
q
q0
9. ábra. A poligonnak több csúcsa is a q0 q szakaszra esik.
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.
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|
10
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,
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){ 11
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.
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˝ szakasz minden pontja Definíció. Egy egyszeru˝ (nem metszo) 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
12
13. ábra. Ponthalmaz konvex burka.
futási ideje O(n lg n).
/** *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; }
13
14. ábra. A pontok halmazának rendezése polárszög szerint.
14
15. ábra. Minden egyenesen csak a legtávolabbi pont marad meg.
15
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.
16
c
q a b 17. ábra.
17
public static int[] Erinto(Pont[] P, Pont q){ /* Bemenet: P ponthalmaz, q pont 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=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) érint˝ o egyenes 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]); 18
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. n (n−1) A naiv algoritmus, amely minden pontpárra kiszámítja azok távolságát, futási ideje O(∑n−1 = O(n2 ). i=1 i) = 2 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. Ha az e(pi , pi+1 ) egyenes hajlásszöge p j
p j+1
pi+1 pi
18. ábra. Görgetés
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 látható pi és p j pontokon átmeno˝ lesz átellenes pontpár. (a +1 modulo m értendo). − − − → vagy a − → −→ ˝ párhuzamos egyeneseket amíg valamelyik a pi pi+1 p−j − p− érjük el a − p− i pi+1 oldalt, j+1 oldalra nem ér. Ha elobb 19
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].x0){ 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); 20
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
R
Legyen s1 és s2 szakasz és x ∈ 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ó.
˝ ˝ megeloz ˝ o, ˝ és követo˝ szakasz metsziTehát elegendo˝ ellenorizni minden szakasz berakásakor, hogy a rendezésben ot ˝ ˝ o˝ és követo˝ szakaszok metszik-e egymást. e a berakottat, és kivételkor ellenorizni, hogy a kivett szakaszt megeloz
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. 21
x1
x2
x1
x2
19. ábra.
x 20. ábra. Az esetpontok jegyzéke azon x értékek halmaza, ahol a sepro˝ egyenes megáll.
22
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 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. ˝ ˝ Beszúrást közvetlenül követoen határozzuk meg a beszúrt si szakasz követojét F -ben. Ha ez metszi si -t, akkor
si. jobb
si.bal s j. jobb sj
si
si sj
s j.bal s j. jobb
s j.bal
si. jobb
si.bal x
x 21. ábra.
s j .bal
si.bal
sj
si
si.bal
si. jobb
s j . jobb si si. jobb
sj s j .bal s j . jobb
x
x 22. ábra.
˝ ˝ ojét ˝ készen vagyunk. Hasonlóan, a beszúrást közvetlenül követoen határozzuk meg a beszúrt si szakasz megeloz F -ben. Ha ez metszi si -t, akkor készen vagyunk. 23
˝ oen ˝ ˝ o˝ s j1 és követo˝ s j2 szakaTörlés esetén a törlést megeloz határozzuk meg a törlendo˝ si szakaszt F -ben megeloz szokat. Ha mindketto˝ létezik és metszik 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( 24
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 pontjai 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; } } 25
9.11.
Legközelebbi pontpár megkeresése p
Legyen p és q a 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) x-koordiná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
public class LKozelPontpar{ private static class XKoord implements Comparator{ public int compare(Pont p1, Pont p2 ){ return (p1.x
pL
pR
δ
δ
SL
SR
l
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 távolsága legfeljebb 24. ábra. A δ átméroj ˝ δ. Ezek a pontok a y-koordináta szerinti rendezésben egymást követok.
27
private static class YKoord implements Comparator{ public int compare(Pont p1, Pont p2 ){ return (p1.y>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 : jobbkozel; // 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
28
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
29
