Γεωμετρικοί τύποι

Τα προβλήματα γεωμετρίας σε διαγωνισμούς πληροφορικής βασίζονται συνήθως σε αλγορίθμους όπως η εύρεση κυρτής θήκης, ή σε δομές δεδομένων όπως το kd-tree. Συχνά όμως χρειάζονται κάποιοι υπολογισμοί οι οποίοι, αν και δεν λύνουν ολόκληρο το πρόβλημα, χρειάζονται στην λύση, όπως για παράδειγμα η εύρεση τομής ευθειών. Σας συστήνουμε να μην μάθετε απ’έξω τις παρακάτω υλοποιήσεις, αλλά να ξέρετε σε γενικές γραμμές τους πιο εύκολους τρόπους για να λύσετε μικρά γεωμετρικά προβλήματα.

• Αναπαράσταση γεωμετρικών αντικειμένων
  • Σημεία
  • Ευθείες
  • Κύκλοι
• Βασικές συναρτήσεις
  • Απόσταση σημείων
  • Απόσταση παράλληλων ευθειών
  • Απόσταση σημείου και ευθείας
  • Ευθεία που διέρχεται από δύο σημεία
  • Προβολή σημείου σε ευθεία
  • Μεσοκάθετος
  • Κύκλος που διέρχεται από τρία σημεία
• Τομές
  • Τομή ευθειών
  • Τομή κύκλου και ευθείας
  • Τομή κύκλων
• Σχετικές θέσεις
  • Έλεγχος παραλληλίας/καθετότητας ευθειών
  • Σχετική θέση ευθείας και σημείου
  • Σχετική θέση τριών σημείων (CCW)
  • Έλεγχος τομής ευθυγράμμων τμημάτων
• Γωνίες
  • Γωνία σημείου με τον άξονα x
  • Γωνία δύο σημείων με την αρχή των αξόνων
  • Γωνία τριών σημείων
• Μέτρηση εμβαδού
• Προβλήματα
• Πηγές

Αναπαράσταση γεωμετρικών αντικειμένων

Σημεία

Τα σημεία στο δισδιάστατο καρτεσιανό σύστημα αναπαριστώνται από την τετμημένη και την τεταγμένη τους ως $\left (x, y\right )$. Στην c++ μπορούμε να χρησιμοποιήσουμε την δομή pair της STL για να αναπαραστήσουμε σημεία και να μετονομάσουμε το first σε X και το second σε Y χρησιμοποιώντας #define. Αυτή η υλοποίηση μας επιτρέπει εύκολα να ταξινομούμε και να συγκρίνουμε σημεία. Εναλλακτικά, στην c/c++ μπορούμε να κατασκευάζουμε εμείς την δομή ως ένα struct (που θεωρείται καλύτερη πρακτική, αλλά χρειάζεται λίγες παραπάνω γραμμές). Στο άρθρο αυτό θα χρησιμοποιούμε την δεύτερη κατασκευή.

Για ευθύγραμμα τμήματα μπορούμε απλά να κατασκευάσουμε ζεύγη σημείων ως ένα νέο struct.

struct pt {
    double x, y;
};

struct seg {
    pt a, b;
};

int main() {
    pt a;
    a.x = 10;
    a.y = 20;
    pt b = {4, 5}; // Αυτός ο τρόπος κατασκευής είναι αποκλειστικός στην c++11
    assert(a.x==10 && a.y==20);
    assert(b.x==4 && b.y==5);
    return 0;
}

Ευθείες

Η αναπαράσταση ευθειών είναι κάπως πιο ενδιαφέρουσα, καθώς στα μαθηματικά υπάρχουν δύο τρόποι ορισμού ευθειών. Ο πιο συνηθισμένος τρόπος ευθειών είναι η εξίσωση $y=ax+b$. Αυτή η εξίσωση αναπαριστά με μοναδικό τρόπο κάθε ευθεία, οπότε είναι εύκολο να ελέγξουμε αν δύο ευθείες ταυτίζονται, όμως δεν μπορεί να αναπαραστήσει κάθετες ευθείες (της μορφής $x=c$). Ο εναλλακτικός τρόπος αναπαράστασης ευθειών είναι η εξίσωση $Ax+By+C=0$. Αν και με αυτόν τον τρόπο δεν είναι τόσο απλό να ελέγξουμε για ισότητα ευθειών, ο τύπος αυτός περιγράφει όλες τις ευθείες του επιπέδου, και διευκολύνει υπολογισμούς με ευθείες.

Για να αποκτήσουμε μια διαίσθηση της σημασίας του τύπου αυτού, ας θεωρήσουμε ένα σημείο το οποίο κινείται με σταθερή ταχύτητα. Ως προς τον άξονα $x$ κινείται με $B$ εκατοστά το δευτερόλεπτο προς τα δεξιά, ενώ ως προς τον άξονα $y$ με $A$ εκατοστά το δευτερόλεπτο προς τα κάτω. Συνεπώς, εάν ξεκίνησε στο σημείο $\left (0, 0\right )$, μπορούμε να δούμε εύκολα ότι βρίσκεται πάνω στην ευθεία $Ax+By=0$. Ο συντελεστής $C$ ορίζει απλά τη μετατόπιση.

Για να διευκολύνουμε τις παρακάτω πράξεις, αλλά και να μπορούμε να ελέγχουμε εύκολα για ισότητα ευθειών θα θεωρούμε ότι το $A$ είναι πάντα μη αρνητικό και θα διαιρούμε όλους τους συντελεστές με το $\sqrt{A^2+B^2}$ (έτσι ώστε να ισχύει πάντα ότι $\sqrt{A^2+B^2}=1$). Παρατηρήστε ότι ποτέ δεν θα έχουμε $\sqrt{A^2+B^2}=0$, αφού αν $A=B=0$ δεν ορίζεται ευθεία.

ΠΡΟΣΟΧΗ: Από εδώ και πέρα θα θεωρούμε ότι όλες οι ευθείες είναι αυτής της μορφής.

Και πάλι, αν και μπορούμε να χρησιμοποιήσουμε pair, ειδικότερα σε αυτήν την περίπτωση συμφέρει η χρήση struct.

struct ln {
    double A, B, C;
    ln normalize() {
        double norm = (A<0?-1:1)*sqrt(A*A+B*B);
        A/=norm;
        B/=norm;
        C/=norm;
        return *this;
    }
};

Κύκλοι

Οι κύκλοι στο δισδιάστατο καρτεσιανό σύστημα ορίζονται με βάση το κέντρο τους και την ακτίνα τους. Συνεπώς, μπορούμε να χρησιμοποιήσουμε την εξής υλοποίηση:

struct circ {
    pt o;
    double r;
};

Βασικές συναρτήσεις

Απόσταση σημείων

Είναι γνωστό ότι η ευκλείδεια απόσταση σημείων $a=\left (x_a, y_a\right ), b=\left (x_b, y_b\right )$ στο καρτεσιανό επίπεδο ορίζεται ως $d\left (a,b \right) = \sqrt{\left (x_a-x_b\right )^2+\left (y_a-y_b\right )^2}$

#define sqr(x) ((x)*(x))

double P2Dist(pt a, pt b) {
    return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}

Απόσταση παράλληλων ευθειών

Δύο ευθείες $l_1: A_1x+B_1y+C_1=0, l_2: A_2x+B_2y+C_2=0$, με τις ιδιότητες που ορίσαμε παραπάνω, είναι παράλληλες εάν $A_1=A_2, B_1=B_2$. Δύο παράλληλες ευθείες έχουν απόσταση $\lvert C_1-C_2\rvert$.

double L2Dist(ln a, ln b) {
    return fabs(a.C-b.C);
}

Απόσταση σημείου και ευθείας

Η απόσταση μεταξύ σημείου $a=\left (x_a,y_a\right )$ και ευθείας $l: Ax+By+C=0$ είναι ίση με $d\left (a, l\right ) = \lvert Ax_a+By_a+C\rvert$

Διαισθητικά, ας θεωρήσουμε μια ευθεία $l^\prime: A^\prime x+ B^\prime y + C=0$ (για την οποία ισχύουν οι ιδιότητες $A^\prime\geq 0, \sqrt{A^{\prime2}+B^{\prime2}}$), παράλληλη στην ευθεία $l$, η οποία περνάει από το σημείο $a$. Όπως είδαμε παραπάνω, η παραλληλία σημαίνει ότι $A^\prime=A, B^\prime=B$. Μένει λοιπόν να βρούμε την σωστή τιμή του $C^\prime$ έτσι ώστε η ευθεία $l^\prime$ να περνάει από το $a$. Λύνοντας την εξίσωση έχουμε: $A^\prime x_a+B^\prime y_a+C^\prime =0 \Leftrightarrow C^\prime = -\left (Ax_a+By_a\right )$

Μένει λοιπόν να βρούμε την απόσταση των δύο ευθειών, η οποία όπως είδαμε παραπάνω είναι ίση με $\lvert C-C^\prime\rvert= \lvert Ax_a+By_A+C\rvert$. Είναι εύκολο να δει κανείς γιατί η απόσταση των δύο ευθειών είναι ίση με την απόσταση του σημείου $a$ και της ευθείας $l$.

double PLDist(pt p, ln l) {
    return fabs(l.A*p.x+l.B*p.y+l.C);
}

Ευθεία που διέρχεται από δύο σημεία

Είναι γνωστό ότι από δύο διαφορετικά μεταξύ τους σημεία διέρχεται μία και μοναδική ευθεία. Για να υλοποιήσουμε τη συνάρτηση που βρίσκει αυτήν την ευθεία, πρώτα θα υλοποιήσουμε μια συνάρτηση η οποία δέχεται τιμές $A$ και $B$ και σημείο $p$ και επιστρέφει την ευθεία με εξίσωση $Ax+By+C=0$ που διέρχεται από το σημείο $p$ (δηλαδή βρίσκει το $C$).

Υπενθυμίζουμε τη διαίσθηση που δώσαμε για την εξίσωση της ευθείας, ότι το $Α$ δηλώνει την ταχύτητα προς τα κάτω ως προς τον άξονα $y$ ενώ το $B$ δηλώνει την ταχύτητα προς τα δεξιά ως προς τον άξονα $x$. Μένει απλά να βρούμε τη σωστή μετατόπιση.

ln PLine(double A, double B, pt p) {
    return ((ln){A, B, -A*p.x-B*p.y}).normalize();
}

ln P2Line(pt p1, pt p2) {
    return PLine(p1.y-p2.y, p2.x-p1.x, p1);
}

Να σημειωθεί ότι στην πράξη δεν είναι απαραίτητο να χρησιμοποιούμε δύο συναρτήσεις, αλλά κάτι τέτοιο βοηθάει στην κατανόηση της μεθόδου.

Προβολή σημείου σε ευθεία

Η προβολή ενός σημείου $a$ σε μια ευθεία $l$ είναι το κοντινότερο σημείο $b$ στο $a$ το οποίο βρίσκεται πάνω στην ευθεία $l$. Αφού ήδη γνωρίζουμε πώς βρίσκουμε την απόσταση $d\left (a, l\right )$ η οποία είναι ίση με την απόσταση των σημείων $d\left (a, b\right )$, και ισχύει η εξίσωση $Ax_b+By_b+C=0$, μένει απλά να λύσουμε τις εξισώσεις αυτές. Παρακάτω παραθέτουμε μόνο τον κώδικα.

pt PLProject(pt p, ln l) {
    double k=PLDist(p, l);
    return (pt){p.x-l.A*k, p.y-l.B*k};
}

Μεσοκάθετος

Η μεσοκάθετος ενός ευθύγραμμου τμήματος ορίζεται ως η ευθεία η οποία περνάει από το μέσο του τμήματος και είναι κάθετη σε αυτό. Γνωρίζουμε ότι δύο κάθετες μεταξύ τους ευθείες έχουν αντιθετοαντίστροφες κλίσεις, και ότι το μέσο δύο σημείων είναι ο μέσος όρος των συντεταγμένων τους, άρα μπορούμε να κατασκευάσουμε ως εξής:

ln P2MidLine(pt p1, pt p2) {
    pt m = {(p1.x+p2.x)/2, (p1.y+p2.y)/2};
    ln l = P2Line(p1, p2);
    return PLine(l.B, -l.A, m);
}

Κύκλος που διέρχεται από τρία σημεία

Γνωρίζουμε ότι τρία μη συνευθειακά σημεία ορίζουν πάντα κύκλο. Επίσης γνωρίζουμε ότι το περίκεντρο ενός τριγώνου είναι το σημείο τομής των μεσοκαθέτων των πλευρών του. Παρακάτω θα ορίσουμε τη συνάρτηση τομής ευθειών L2Point αλλά θα την χρησιμοποιήσουμε τώρα. Για να βρούμε τον κύκλο που ορίζουν τρία σημεία κάνουμε το εξής:

circ P3Circle(pt p1, pt p2, pt p3) {
    pt c = L2Point(P2MidLine(p1, p2), P2MidLine(p2, p3));
    return (circ){c, P2Dist(c, p1)};
}

Τομές

Τομή ευθειών

Για να βρούμε την τομή δύο ευθειών αρκεί να λύσουμε τις εξισώσεις, κάτι που δεν είναι ιδιαίτερα δύσκολο.

pt L2Point(ln l1, ln l2) {
    return (pt){-(l1.C*l2.B-l2.C*l1.B)/(l1.A*l2.B-l1.B*l2.A), -(l1.C*l2.A-l2.C*l1.A)/(l1.B*l2.A-l1.A*l2.B)};
}

Τομή κύκλου και ευθείας

Για να λύσουμε αυτό το πρόβλημα, πρώτα θα κατασκευάσουμε μια άλλη συνάρτηση, η οποία δέχεται έναν κύκλο $c$ και ένα σημείο $p$ και επιστρέφει τα σημεία τομής (εάν υπάρχουν) του κύκλου με την ευθεία η οποία διέρχεται από το $p$ και είναι κάθετη στο τμήμα με άκρα το κέντρο του κύκλου και το $p$. Η συνάρτηση αυτή είναι αρκετά πιο απλή από το αρχικό πρόβλημα, και μπορούμε να την βρούμε χρησιμοποιώντας το γεγονός ότι σχηματίζονται αρκετά ορθογώνια τρίγωνα. Για να θυμάστε αυτόν τον τύπο, καλό θα ήταν να προσπαθήσετε να τον αποδείξετε.

seg CPPoints(circ c, pt p) {
    double d=P2Dist(c.o, p);
    if(d>c.r) {
        return (seg){c.o, c.o};
    }
    double t=sqrt(c.r*c.r-d*d)/d;
    double dy=(p.x-c.o.x)*t;
    double dx=(p.y-c.o.y)*t;
    return (seg){(pt){p.x-dx, p.y+dy}, (pt){p.x+dx, p.y-dy}};
}

Αφού έχουμε αυτήν τη συνάρτηση, μπορούμε εύκολα να τη χρησιμοποιήσουμε για να βρούμε την τομή κύκλου και ευθείας.

seg CLPoints(circ c, ln l) {
    return CPPoints(c, PLProject(c.o, l));
}

Τομή κύκλων

Όπως και πριν, θα χρησιμοποιήσουμε τη συνάρτηση CPPoints. Αρκεί λοιπόν να βρούμε το κατάλληλο σημείο που πρέπει να ορίσουμε. Πάλι με μερικές πράξεις, μπορούμε να καταλήξουμε στο θεμιτό αποτέλεσμα. Όπως και πριν, προσπαθήστε να το αποδείξετε.

seg C2Points(circ c1, circ c2) {
    double d=P2Dist(c1.o, c2.o);
    double r=(c1.r*c1.r-c2.r*c2.r+d*d)/(2*d*d); 
    return CPPoints(c2, (pt){c1.o.x+(c2.o.x-c1.o.x)*r, c1.o.y+(c2.o.y-c1.o.y)*r});  
}

Σχετικές θέσεις

Έλεγχος παραλληλίας/καθετότητας ευθειών

Με τον τρόπο που έχουμε ορίσει τις ευθείες, είναι εύκολο να ελέγξουμε για παραλληλία και καθετότητα.

Δύο ευθείες $l_1: A_1x+B_1y+C_1=0, l_2: A_2x+B_2y+C_2=0$

• είναι παράλληλες αν $Β_1=Β_2=0$ ή $A_1/Β_1=A_2/Β_2$

• είναι κάθετες αν $Α_1=Β_2=0$ ή $A_2=B_1=0$ ή $A_1/B_1=-B_2/A_1$

Σχετική θέση ευθείας και σημείου

Ας θυμηθούμε τον τύπο που έδινε την απόσταση ευθείας και σημείου: $d\left (p, l\right )= \lvert A_lx_p+B_ly_p+C_l\rvert$. Ήδη γνωρίζουμε ότι εάν η τιμή αυτής της παράστασης είναι $0$, τότε το σημείο βρίσκεται πάνω στην ευθεία. Αποδεικνύεται ότι το πρόσημο της παράστασης $A_lx_p+B_ly_p+C_l$ μας δίνει την σχετική θέση του σημείου $p$ με την ευθεία $l$. Αυτό χρησιμεύει περισσότερο για να βρούμε εάν δυο σημεία βρίσκονται σε διαφορετικές πλευρές της ευθείας, καθώς δεν ορίζεται ιδιαίτερα απλά το από ποια πλευρά θα είναι το σημείο ανάλογα με το πρόσημο.

#define EPS 1e-7

int LPRel(ln l, pt p) {
    if(fabs(l.A*p.x+l.B*p.y+l.C)<EPS) {
        return 0;
    }
    return l.A*p.x+l.B*p.y+l.C>0?1:-1;
}

Σχετική θέση τριών σημείων (CCW)

Μία από τις πιο χρήσιμες συναρτήσεις στην υπολογιστική γεωμετρία είναι το CCW. Για μια πιο πληρέστερη περιγραφή του, μπορείτε να δείτε εδώ. Ουσιαστικά η συνάρτηση αυτή μας υποδεικνύει εάν τρία σημεία στρέφουν αριστερόστροφα (Counter Clock Wise) ή δεξιόστροφα. Στην πρώτη περίπτωση η τιμή της συνάρτησης είναι θετική, αλλιώς αρνητική. Εάν τα τρία σημεία είναι συνευθειακά, η τιμή της συνάρτησης είναι $0$.

long double CCW(pt A, pt B, pt C) {
    return A.x*B.y-A.y*B.x+B.x*C.y-B.y*C.x+C.x*A.y-C.y*A.x;
}

Έλεγχος τομής ευθυγράμμων τμημάτων

Δύο ευθύγραμμα τμήματα $\left (p_1, p_2\right ), \left (p_3, p_4\right )$ τέμνονται αν τα $p_1, p_2$ βρίσκονται σε αντίθετες σχετικές θέσεις με το $\left (p_3, p_4\right )$, δηλαδή εάν το ένα βρίσκεται αριστερά του τμήματος, τότε το άλλο βρίσκεται δεξιά του, και τα $p_3, p_4$ επίσης βρίσκονται σε αντίθετες σχετικές θέσεις με το $\left (p_1, p_2\right )$. Αυτό μπορούμε πολύ εύκολα να το ελέγξουμε με το CCW.

bool S2Intersect(seg s1, seg s2) {
    return ((CCW(s1.a, s1.b, s2.a)>0) ^ (CCW(s1.a, s1.b, s2.b)<0)) && ((CCW(s2.a, s2.b, s1.a)>0) ^ (CCW(s2.a, s2.b, s1.b)<0));
}

Να σημειωθεί ότι αυτός ο έλεγχος μπορεί να υλοποιηθεί και με γινόμενο, αλλά σε αυτήν την περίπτωση πρέπει να προσέξουμε καθώς οι αριθμοί γίνονται αρκετά μεγάλοι.

Γωνίες

Να σημειωθεί ότι η μέτρηση γωνιών συχνά δεν είναι ακριβής και στις περισσότερες περιπτώσεις τα προβλήματα λύνονται και χωρίς την χρήση γωνιών. Εάν μπορείτε, αποφύγετε να χρησιμοποιείτε γωνίες.

Γωνία σημείου με τον άξονα x

Η c παρέχει τη συνάρτηση atan2 με την οποία μπορούμε ιδιαίτερα εύκολα να μετρήσουμε τη γωνία σε rad με κέντρο την αρχή των αξόνων και άκρα κάποιο δεδομένο σημείο και τον άξονα $x$ (στην θετική κατεύθυνση).

double PXAngle(pt p) {
    double a=atan2(p.y, p.x);
    if(a<0) {
        a+=2*M_PI;
    }
    return a;
}

Γωνία δύο σημείων με την αρχή των αξόνων

Και πάλι, χρησιμοποιώντας τη συνάρτηση atan2, έχουμε:

double P2Angle(pt p1, pt p2) {
    double a=PXAngle(p1) - PXAngle(p2);
    if(a<0) {
        a+=2*M_PI;
    }
    return a;
}

Γωνία τριών σημείων

Αυτήν τη φορά χρειάζεται να μετακινήσουμε τα άλλα δύο σημεία έτσι ώστε το μεσαίο σημείο να ταυτιστεί με την αρχή των αξόνων και να χρησιμοποιήσουμε την προηγούμενη συνάρτηση.

double P3Angle(pt p1, pt p2, pt p3) {
    return P2Angle((pt){p1.x-p2.x, p1.y-p2.y}, (pt){p3.x-p2.x, p3.y-p2.y});
}

Μέτρηση εμβαδού

Δεν υπάρχει λόγος να καλύψουμε τους γνωστούς τύπους εμβαδών γνωστών σχημάτων. Στις περισσότερες περιπτώσεις, αν όχι όλες, υπολογισμού εμβαδού στην υπολογιστική γεωμετρία, ένας συγκεκριμένος τύπος είναι αρκετός, το Shoelace formula. Αποτελεί γενίκευση του CCW, και βρίσκει το εμβαδό πολυγώνων. Για να μάθετε περισσότερα, πατήστε εδώ.

Προβλήματα

GOALFR (Spoj)

CHASE (Spoj)

VISION (Spoj)

CLOPPAIR (Spoj)

Ruminations on Ruminants (Codeforces)

Πηγές

Υλοποίηση γεωμετρίας σε Pascal (ρώσικα σχόλια)

Σχόλια