Όταν οι άνθρωποι σκέφτονται την υπολογιστική γεωμετρία, κατά την εμπειρία μου, συνήθως σκέφτονται ένα από δύο πράγματα:
- Ουάου, αυτό ακούγεται περίπλοκο.
- Ω! ναι, κυρτό κύτος .
Σε αυτήν την ανάρτηση, θα ήθελα να ρίξω λίγο φως στην υπολογιστική γεωμετρία, ξεκινώντας με μια σύντομη επισκόπηση του θέματος πριν προχωρήσω σε μερικές πρακτικές συμβουλές με βάση τις δικές μου εμπειρίες ( παραλείψτε μπροστά αν έχετε μια καλή λαβή για το θέμα).
s corp ή c corp για μικρές επιχειρήσεις
Για τι φασαρία;
Ενώ οι αλγόριθμοι υπολογιστικής γεωμετρίας κυρτού κύτους περιλαμβάνονται συνήθως σε ένα μάθημα εισαγωγικών αλγορίθμων , η υπολογιστική γεωμετρία είναι ένα πολύ πιο πλούσιο θέμα που σπάνια λαμβάνει επαρκή προσοχή από τον μέσο προγραμματιστή / επιστήμονα υπολογιστών (εκτός αν κάνετε παιχνίδια ή κάτι τέτοιο).
Θεωρητικά ενδιαφέρον…
Από θεωρητική άποψη, οι ερωτήσεις στην υπολογιστική γεωμετρία είναι συχνά εξαιρετικά ενδιαφέρουσες. οι απαντήσεις, συναρπαστική? και τα μονοπάτια στα οποία φτάνουν, ποικίλλουν. Αυτές οι ιδιότητες το καθιστούν μόνο ένα πεδίο που αξίζει να μελετηθεί, κατά τη γνώμη μου.
Για παράδειγμα, σκεφτείτε το Πρόβλημα γκαλερί τέχνης : Διαθέτουμε μια γκαλερί τέχνης και θέλουμε να εγκαταστήσουμε κάμερες ασφαλείας για να προστατεύσουμε τα έργα τέχνης μας. Ωστόσο, έχουμε περιορισμένο προϋπολογισμό, επομένως θέλουμε να χρησιμοποιήσουμε όσο το δυνατόν λιγότερες κάμερες. Πόσες κάμερες χρειαζόμαστε;
Όταν το μεταφράζουμε σε υπολογιστική γεωμετρική σημειογραφία, η «κάτοψη» της γκαλερί είναι ένα απλό πολύγωνο. Και με λίπος αγκώνα, μπορούμε να το αποδείξουμε αυτό n / 3 Οι κάμερες είναι πάντα επαρκείς για ένα πολύγωνο ν κορυφές, ανεξάρτητα από το πόσο βρώμικο είναι. ο απόδειξη χρησιμοποιεί διπλά γραφήματα, κάποια θεωρία γραφημάτων, τριγωνισμούς και άλλα.
Εδώ, βλέπουμε μια έξυπνη τεχνική απόδειξης και ένα αποτέλεσμα που είναι αρκετά περίεργο για να εκτιμηθεί από μόνη της. Αλλά αν η θεωρητική συνάφεια δεν είναι αρκετή για εσάς…
Και σημαντικό στην πράξη
Όπως ανέφερα νωρίτερα, η ανάπτυξη παιχνιδιών βασίζεται σε μεγάλο βαθμό στην εφαρμογή της υπολογιστικής γεωμετρίας (για παράδειγμα, ανίχνευση σύγκρουσης συχνά βασίζεται στον υπολογισμό του κυρτού κύτους ενός συνόλου αντικειμένων). όπως και γεωγραφικά συστήματα πληροφοριών (GIS) , που χρησιμοποιούνται για την αποθήκευση και εκτέλεση υπολογισμών σε γεωγραφικά δεδομένα · και ρομποτική (π.χ., για προβλήματα ορατότητας και σχεδιασμού).
Γιατί είναι τόσο δύσκολο;
Ας πάρουμε ένα αρκετά απλό πρόβλημα υπολογιστικής γεωμετρίας: δεδομένου ενός σημείου και ενός πολυγώνου, το σημείο βρίσκεται μέσα στο πολύγωνο; (Αυτό ονομάζεται σημείο-σε-πολύγωνο ή PIP πρόβλημα .)
Το PIP κάνει εξαιρετική δουλειά για να δείξει γιατί η υπολογιστική γεωμετρία μπορεί να είναι (παραπλανητικά) δύσκολη. Για το ανθρώπινο μάτι, αυτό δεν είναι δύσκολο ερώτημα. Βλέπουμε το παρακάτω διάγραμμα και είναι αμέσως είναι προφανές σε μας ότι το θέμα είναι στο πολύγωνο:
Ακόμα και για σχετικά πολύπλοκα πολύγωνα, η απάντηση δεν μας ξεφεύγει για περισσότερο από ένα δευτερόλεπτο ή δύο. Αλλά όταν τροφοδοτούμε αυτό το πρόβλημα σε έναν υπολογιστή, μπορεί να δει τα εξής:
poly = Polygon([Point(0, 5), Point(1, 1), Point(3, 0), Point(7, 2), Point(7, 6), Point(2, 7)]) point = Point(5.5, 2.5) poly.contains(point) Αυτό που είναι διαισθητικό για τον ανθρώπινο εγκέφαλο δεν μεταφράζεται τόσο εύκολα στη γλώσσα του υπολογιστή.
Πιο αφηρημένα (και αγνοώντας την ανάγκη να αντιπροσωπεύσουμε αυτά τα πράγματα στον κώδικα), τα προβλήματα που βλέπουμε σε αυτήν την πειθαρχία είναι πολύ δύσκολο να σκληρυνθούν («κάνουμε αυστηρά») σε έναν αλγόριθμο υπολογιστικής γεωμετρίας. Πώς θα περιγράφαμε το σενάριο point-in-polygon χωρίς τη χρήση ταυτολογικής γλώσσας όπως «Ένα σημείο βρίσκεται μέσα σε ένα πολύγωνο εάν βρίσκεται μέσα στο πολύγωνο»; Πολλές από αυτές τις ιδιότητες είναι τόσο θεμελιώδεις και τόσο βασικές που είναι δύσκολο να τις προσδιορίσουμε συγκεκριμένα.
Πώς θα περιγράφαμε το σενάριο point-in-polygon χωρίς τη χρήση ταυτολογικής γλώσσας όπως «είναι μέσα στο πολύγωνο εάν είναι μέσα στο πολύγωνο»;Δύσκολο, αλλά όχι αδύνατο. Για παράδειγμα, θα μπορούσατε να προσαρμόσετε το σημείο-σε-πολύγωνο με τους ακόλουθους ορισμούς:
- Ένα σημείο βρίσκεται μέσα σε ένα πολύγωνο εάν κάθε άπειρη ακτίνα που ξεκινά από το σημείο τέμνει με έναν περίεργο αριθμό ακμών πολυγώνου (γνωστό ως ομοιόμορφος κανόνας ).
- Ένα σημείο βρίσκεται μέσα σε ένα πολύγωνο εάν έχει μη μηδέν αριθμός περιέλιξης (ορίζεται ως ο αριθμός των φορών που η καμπύλη που ορίζει το πολύγωνο κινείται γύρω από το σημείο).
Αν δεν είχατε κάποια εμπειρία με την υπολογιστική γεωμετρία, αυτοί οι ορισμοί πιθανότατα δεν θα είναι μέρος του υπάρχοντος λεξιλογίου σας. Και ίσως αυτό είναι το σύμβολο του πώς η υπολογιστική γεωμετρία μπορεί να σας ωθήσει σκεφτείτε διαφορετικά .
Παρουσιάζουμε το CCW
Τώρα που έχουμε την αίσθηση για τη σημασία και τη δυσκολία των υπολογιστικών γεωμετρικών προβλημάτων, ήρθε η ώρα να βρέξουμε τα χέρια μας.
Στην ραχοκοκαλιά του θέματος βρίσκεται μια παραπλανητικά ισχυρή πρωτόγονη λειτουργία: αριστερόστροφα ή «CCW» για συντομία. (Θα σας προειδοποιήσω τώρα: Το CCW θα εμφανιστεί ξανά και ξανά.)
Το CCW παίρνει τρία σημεία A, B και C ως επιχειρήματα και ρωτά: αυτά τα τρία σημεία συνιστούν μια αριστερόστροφη στροφή (έναντι δεξιόστροφης στροφής); Με άλλα λόγια, είναι το A -> B -> C μια αριστερόστροφη γωνία;
Για παράδειγμα, το πράσινος σημεία είναι CCW, ενώ το καθαρά τα σημεία δεν είναι:
Γιατί έχει σημασία το CCW
Το CCW μας δίνει ένα πρωτόγονος λειτουργία στην οποία μπορούμε να οικοδομήσουμε. Μας δίνει ένα μέρος για να αρχίσουμε να επεξεργαζόμαστε και να επιλύουμε προβλήματα υπολογιστικής γεωμετρίας.
Για να σας δώσουμε μια αίσθηση για τη δύναμή του, ας εξετάσουμε δύο παραδείγματα.
Προσδιορισμός της κυρτότητας
Ο πρώτος: δεδομένου ενός πολυγώνου, μπορείτε να προσδιορίσετε εάν είναι κυρτό; Κυρτότητα είναι μια ανεκτίμητη ιδιότητα: γνωρίζοντας ότι τα πολύγωνα σας είναι κυρτά συχνά σας επιτρέπει να βελτιώσετε την απόδοση κατά παραγγελίες μεγέθους. Ως συγκεκριμένο παράδειγμα: υπάρχει ένα αρκετά απλός αλγόριθμος PIP που τρέχει σε Log (n) ώρα για κυρτά πολύγωνα, αλλά αποτυγχάνει για πολλά κοίλα πολύγωνα.
Διαισθητικά, αυτό το κενό έχει νόημα: τα κυρτά σχήματα είναι «ωραία», ενώ τα κοίλα σχήματα μπορούν να έχουν αιχμηρές άκρες που ανοίγουν προς τα έξω - απλά δεν ακολουθούν τους ίδιους κανόνες.
Ένας απλός (αλλά μη προφανής) υπολογιστικός αλγόριθμος γεωμετρίας για τον προσδιορισμό της κυρτότητας είναι να ελέγξετε ότι κάθε τρίδυμο διαδοχικών κορυφών είναι CCW. Αυτό απαιτεί λίγες γραμμές κώδικα γεωμετρίας Python (υποθέτοντας ότι τα points παρέχονται σε αριστερόστροφη σειρά - εάν points είναι δεξιόστροφα, θα θέλατε όλα τα τρίδυμα να είναι δεξιόστροφα):
class Polygon(object): ... def isConvex(self): for i in range(self.n): # Check every triplet of points A = self.points[i % self.n] B = self.points[(i + 1) % self.n] C = self.points[(i + 2) % self.n] if not ccw(A, B, C): return False return True Δοκιμάστε αυτό σε χαρτί με μερικά παραδείγματα. Μπορείτε ακόμη να χρησιμοποιήσετε αυτό το αποτέλεσμα καθορίζω κυρτότητα. (Για να κάνετε τα πράγματα πιο διαισθητικά, σημειώστε ότι μια καμπύλη CCW από A -> B -> C αντιστοιχεί σε γωνία μικρότερη από 180º, η οποία είναι ευρέως διδακτική τρόπος καθορισμού της κυρτότητας .)
Διασταύρωση γραμμής
Ως δεύτερο παράδειγμα, σκεφτείτε τη διασταύρωση τμήματος γραμμής, η οποία μπορεί επίσης να είναι λύθηκε μόνο με χρήση CCW :
def intersect(a1, b1, a2, b2): '''Returns True if line segments a1b1 and a2b2 intersect.''' return ccw(a1, b1, a2) != ccw(a1, b1, b2) and ccw(a2, b2, a1) != ccw(a2, b2, b1) Γιατί συμβαίνει αυτό; Η διασταύρωση τμήματος γραμμής μπορεί επίσης να διατυπωθεί ως: δεδομένου ενός τμήματος με τελικά σημεία Α και Β, βρίσκονται τα τελικά σημεία C και D ενός άλλου τμήματος στην ίδια πλευρά του AB; Με άλλα λόγια, εάν οι στροφές από A -> B -> C και A -> B -> D είναι στην ίδια κατεύθυνση, τα τμήματα δεν μπορούν να τέμνονται. Όταν χρησιμοποιούμε αυτόν τον τύπο γλώσσας, καθίσταται σαφές ότι ένα τέτοιο πρόβλημα είναι το ψωμί και το βούτυρο της CCW.
Ένας αυστηρός ορισμός
Τώρα που έχουμε μια γεύση για τη σημασία του CCW, ας δούμε πώς υπολογίζεται. Δεδομένων των σημείων Α, Β και Γ:
def ccw(A, B, C): '''Tests whether the turn formed by A, B, and C is ccw''' return (B.x - A.x) * (C.y - A.y) > (B.y - A.y) * (C.x - A.x) Για να καταλάβετε από πού προέρχεται αυτός ο ορισμός, σκεφτείτε τα διανύσματα AB και BC. Εάν πάρουμε το διασταυρούμενο προϊόν τους, AB x BC, αυτό θα είναι ένα διάνυσμα κατά μήκος του άξονα z. Αλλά σε ποια κατεύθυνση (δηλαδή, + z ή -z); Όπως αποδεικνύεται, εάν το εγκάρσιο προϊόν είναι θετικό, η στροφή είναι αριστερόστροφα. Διαφορετικά, είναι δεξιόστροφα.
Αυτός ο ορισμός θα φαίνεται ακούσιος, εκτός αν έχετε μια πολύ καλή κατανόηση της γραμμικής άλγεβρας, του δεξιού κανόνα κ.λπ. Αλλά γι 'αυτό έχουμε αφαίρεση - όταν σκέφτεστε το CCW, σκεφτείτε απλώς τον διαισθητικό ορισμό του παρά τον υπολογισμό του. Η τιμή θα είναι αμέσως σαφής.
Η κατάδυση μου σε υπολογιστική γεωμετρία και προγραμματισμός με χρήση του Python
Τον τελευταίο μήνα, εργάζομαι για την εφαρμογή διάφορων αλγορίθμων υπολογιστικής γεωμετρίας στο Python. Καθώς θα τις σχεδιάζω στις επόμενες ενότητες, θα αφιερώσω ένα δευτερόλεπτο για να περιγράψω τις υπολογιστικές μου εφαρμογές γεωμετρίας, τις οποίες μπορείτε να βρείτε στο GitHub .
Σημείωση: Η εμπειρία μου είναι βεβαίως περιορισμένη. Καθώς εργάζομαι σε αυτά τα πράγματα για μήνες και όχι χρόνια, πάρτε τη συμβουλή μου με έναν κόκκο αλατιού. Τούτου λεχθέντος, έμαθα πολλά αυτούς τους λίγους μήνες, οπότε ελπίζω αυτές οι συμβουλές να αποδειχθούν χρήσιμες.
Αλγόριθμος του Kirkpatrick
Στον πυρήνα της δουλειάς μου ήταν μια υλοποίηση του Αλγόριθμος του Kirkpatrick Για σημείο σημείο . Η δήλωση προβλήματος θα ήταν κάτι σαν: δοθεί μια επίπεδη υποδιαίρεση (μια δέσμη μη επικαλυπτόμενων πολυγώνων στο επίπεδο) και ένα σημείο P, ποιο πολύγωνο περιέχει P; Σκεφτείτε το πολύγωνο για τα στεροειδή - αντί για ένα πολύγωνο, έχετε ένα επίπεδο από αυτά.
Ως περίπτωση χρήσης, σκεφτείτε μια ιστοσελίδα. Όταν ένας χρήστης κάνει κλικ στο ποντίκι, η ιστοσελίδα πρέπει να το καταλάβει τι ο χρήστης έκανε κλικ στο συντομότερο δυνατό. Ήταν το κουμπί Α; Ήταν σύνδεσμος Β; Η ιστοσελίδα αποτελείται από μη επικαλυπτόμενα πολύγωνα, οπότε ο Αλγόριθμος του Kirkpatrick θα ήταν σε καλή θέση για να βοηθήσει.
Αν και δεν θα συζητήσω σε βάθος τον αλγόριθμο, μπορείτε να μάθετε περισσότερα εδώ .
Ελάχιστο οριακό τρίγωνο
Ως δευτερεύον έργο, έκανα επίσης εφαρμογή Ο αλγόριθμος του O'Rourke για τον υπολογισμό ενός ελάχιστου τριγώνου εγκλεισμού / οριοθέτησης (δηλαδή, εύρεση του μικρότερου τριγώνου που περικλείει κυρτό ένα σύνολο σημείων) σε γραμμικό χρόνο.
Σημείωση: Ο υπολογισμός του ελάχιστου τριγώνου οριοθέτησης δεν βοηθά ούτε βλάπτει την ασυμπτωτική απόδοση του Αλγόριθμου του Kirkpatrick, καθώς ο υπολογισμός είναι γραμμικός χρόνος - αλλά είναι χρήσιμος για αισθητικούς σκοπούς.
Πρακτικές συμβουλές, εφαρμογές και ανησυχίες
Οι προηγούμενες ενότητες επικεντρώθηκαν στο γιατί η υπολογιστική γεωμετρία μπορεί να είναι δύσκολο να σκεφτεί κανείς αυστηρά.
Στην πράξη, πρέπει να αντιμετωπίσουμε ένα εντελώς νέο πλήθος ανησυχιών.
Θυμάστε CCW; Ως ένα ωραίο τμήμα, ας δούμε ακόμη μία από τις υπέροχες ιδιότητές του: μας προστατεύει από τους κινδύνους των σφαλμάτων κυμαινόμενου σημείου.
Σφάλματα Floating-Point: Γιατί το CCW είναι King
Στο μάθημα υπολογιστικής γεωμετρίας μου, Bernard Chazelle , ένας αξιότιμος καθηγητής που είναι δημοσίευσε περισσότερα άρθρα από ό, τι μπορώ να μετρήσω, έκανε έναν κανόνα ότι δεν θα μπορούσαμε να αναφέρουμε γωνίες όταν προσπαθούμε να περιγράψουμε έναν αλγόριθμο ή μια λύση.
Έγινε κανόνας που δεν μπορούσαμε καν αναφέρω γωνίες. Γιατί; Οι γωνίες είναι ακατάστατες - οι γωνίες είναι «βρώμικες».Γιατί; Οι γωνίες είναι ακατάστατες. Οι γωνίες είναι «βρώμικες». Όταν πρέπει να υπολογίσετε μια γωνία, πρέπει να διαιρέσετε ή να χρησιμοποιήσετε κάποια προσέγγιση (οτιδήποτε περιλαμβάνει το Pi, για παράδειγμα) ή κάποια τριγωνομετρική συνάρτηση.
Όταν πρέπει να υπολογίσετε μια γωνία σε κωδικό , σχεδόν πάντα να πλησιάζει. Θα απομακρυνθείτε από έναν μικρό μικροσκοπικό βαθμό ακρίβειας - που έχει σημασία όταν δοκιμάζετε την ισότητα. Μπορείτε να επιλύσετε κάποιο σημείο στο αεροπλάνο με δύο διαφορετικές μεθόδους και, φυσικά, να περιμένετε ότι p1.x == p2.x and p1.y == p2.y. Όμως, στην πραγματικότητα, αυτός ο έλεγχος θα αποτύχει συχνά . Περαιτέρω (και προφανώς), αυτά τα σημεία θα έχουν διαφορετικά κατακερματισμούς.
Για να επιδεινωθούν τα πράγματα, ο βαθμός σφάλματος θα αυξηθεί καθώς οι μικροσκοπικές διαφορές σας εξαπλώνονται μέσω των υπολογισμών σας. (Για μερικά πιο επιστημονικά παραδείγματα, αυτό το χαρτί περνάει από το τι μπορεί να πάει στραβά κατά τον υπολογισμό του κυρτού κύτους ή του τριγωνισμού Delaunay.)
Λοιπόν, τι μπορούμε να κάνουμε γι 'αυτό;
σχεδόν ισοδύναμο
Μέρος του προβλήματος υπολογιστικής γεωμετρίας Python είναι αυτό που χρειαζόμαστε ακρίβεια σε έναν κόσμο όπου τα πράγματα είναι σπανίως ακριβής. Αυτό θα γίνει πρόβλημα συχνότερα από ό, τι όταν χειρίζεστε γωνίες. Σκέψου τα ακόλουθα:
# Define two random points p1 = RandomPoint() p2 = RandomPoint() # Take the line through them l1 = Line(p1, p2) # Shift both points up by sqrt(2) p1.y += sqrt(2) p2.y += sqrt(2) l2 = Line(p1, p2) # Slope 'should' be the same? if abs(l1.slope - l2.slope) > 0: print 'Error!' # Error! Στην πραγματικότητα, αυτός ο κωδικός θα εκτυπώσει 'Σφάλμα!' περίπου το 70% του χρόνου (εμπειρικά). Μπορούμε να αντιμετωπίσουμε αυτήν την ανησυχία κάνοντας ελαφρώς πιο επιεικής με τον ορισμό της ισότητας. δηλαδή, θυσιάζοντας έναν βαθμό ακρίβειας.
Μία προσέγγιση που έχω χρησιμοποιήσει (και έχω δει, π.χ. σε ορισμένες OpenCV modules) είναι να ορίσετε δύο αριθμούς ως ίσους, εάν διαφέρουν μόνο από κάποια μικρή τιμή epsilon. Στο Python, μπορεί να έχετε:
def almostEqual(x, y, EPSILON=1e-5): return abs(x - y) Στην πράξη, αυτό είναι πολύ χρήσιμο. Σπάνια, αν υπήρχε ποτέ, υπολογίζατε δύο σημεία που διαφέρουν κατά λιγότερο από 1e-5 που στην πραγματικότητα πρόκειται να είναι διαφορετικά σημεία. Συνιστώ ανεπιφύλακτα την εφαρμογή αυτού του τύπου παράκαμψης. Παρόμοιες μέθοδοι μπορούν να χρησιμοποιηθούν για γραμμές, για παράδειγμα:
class Line(object): ... def __eq__(self, that): return (almostEqual(self.slope, that.slope) and almostEqual(self.intercept, that.intercept)) Φυσικά έχουν προταθεί πιο προηγμένες λύσεις. Για παράδειγμα, η σχολή σκέψης «ακριβής γεωμετρικός υπολογισμός» (περιγράφεται στο αυτό το χαρτί ) στοχεύει στο να εξαρτώνται όλες οι διαδρομές αποφάσεων σε ένα πρόγραμμα αποκλειστικά από το σημάδι κάποιου υπολογισμού, αντί της ακριβούς αριθμητικής του αξίας, αφαιρώντας πολλές από τις ανησυχίες που σχετίζονται με υπολογισμούς κινητής υποδιαστολής. Μας κοντά στην ισότητα Η προσέγγιση απλώς γρατσουνίζει την επιφάνεια, αλλά συχνά θα είναι επαρκής στην πράξη.
Το CCW είναι King
Σε υψηλότερο επίπεδο, είναι (αναμφισβήτητα) προβληματικό ότι ακόμη κι εμείς καθορίζω οι λύσεις μας σε όρους ακριβών υπολογιστικών ποσοτήτων όπως γωνίες ή συντεταγμένες σημείων. Αντί να αντιμετωπίζουμε μόνο τα συμπτώματα (δηλαδή, να ξεπλένουμε τα σφάλματα κυμαινόμενου σημείου με almostEqual), γιατί να μην αντιμετωπίσουμε την αιτία; Η λύση: αντί να σκεφτόμαστε από άποψη γωνιών, σκεφτείτε με όρους CCW , το οποίο θα συμβάλει στην απομάκρυνση των ανησυχιών που σχετίζονται με τον υπολογισμό κυμαινόμενου σημείου.
διαφορά μεταξύ s corp και c corp and llc
Ακολουθεί ένα συγκεκριμένο παράδειγμα: ας υποθέσουμε ότι έχετε κάποιο κυρτό πολύγωνο Π , μια κορυφή β , και κάποιο σημείο εσύ έξω από το πολύγωνο Πώς μπορείτε να καταλάβετε εάν η γραμμή uv τέμνει Π πάνω ή κάτω β , ή καθόλου, σε σταθερό χρόνο;
Η λύση brute force (εκτός από το γραμμικό-χρόνο και όχι η σταθερή) θα ήταν προβληματική καθώς θα έπρεπε να υπολογίσετε ορισμένα ακριβή σημεία τομής γραμμής.
Μια προσέγγιση σταθερού χρόνου που έχω δει περιλαμβάνει:
- Υπολογισμός ορισμένων γωνιών χρησιμοποιώντας
arctan2. - Μετατροπή αυτών των γωνιών σε μοίρες πολλαπλασιάζοντας επί 180 / Pi.
- Εξέταση των σχέσεων μεταξύ αυτών των διαφόρων γωνιών.
Ευτυχώς, ο συγγραφέας χρησιμοποίησε το almostEqual τεχνική παραπάνω για την εξομάλυνση των σφαλμάτων κινητής υποδιαστολής.
Κατά τη γνώμη μου, θα ήταν καλύτερα να αποφύγουμε εντελώς το ζήτημα των σφαλμάτων κινητής υποδιαστολής. Εάν χρειάζεστε λίγα λεπτά για να εξετάσετε το πρόβλημα σε χαρτί, μπορείτε να βρείτε μια λύση βασισμένη εξ ολοκλήρου στο CCW. Η διαίσθηση: εάν οι κορυφές γειτνιάζουν με β βρίσκονται στην ίδια πλευρά του uv , τότε η γραμμή δεν τέμνει? αλλιώς, δείτε αν εσύ και β βρίσκονται στην ίδια πλευρά της γραμμής μεταξύ των γειτονικών κορυφών και, ανάλογα με το αποτέλεσμα, συγκρίνουν τα ύψη τους.
Ακολουθεί ο κώδικας Python για τη δοκιμή της διασταύρωσης παραπάνω β (η διασταύρωση παρακάτω αντιστρέφει ακριβώς την κατεύθυνση των συγκρίσεων):
def intersectsAbove(verts, v, u): ''' Returns True if uv intersects the polygon defined by 'verts' above v. Assumes v is the index of a vertex in 'verts', and u is outside of the polygon. ''' n = len(verts) # Test if two adjacent vertices are on same side of line (implies # tangency) if ccw(u, verts[v], verts[(v - 1) % n]) == ccw(u, verts[v], verts[(v + 1) % n]): return False # Test if u and v are on same side of line from adjacent # vertices if ccw(verts[(v - 1) % n], verts[(v + 1) % n], u) == ccw(verts[(v - 1) % n], verts[(v + 1) % n], verts[v]): return u.y > verts[v].y else: return u.y Η λύση δεν είναι άμεσα προφανής με γυμνό μάτι, αλλά είναι στο Γλώσσα ενός αλγορίθμου υπολογιστικής γεωμετρίας: «η ίδια πλευρά της γραμμής» είναι ένα κλασικό στοιχείο αυτού του αξιόπιστου αλγορίθμου.
Ολοκληρώθηκε είναι καλύτερο από το τέλειο
Στην υπολογιστική γεωμετρική βιβλιογραφία, υπάρχει συχνά αρκετός μάγος που εμπλέκεται σε φαινομενικά απλές λειτουργίες. Αυτό σας δίνει μια επιλογή: μπορείτε να κάνετε τα πράγματα με σκληρό τρόπο, ακολουθώντας κάποιο χαρτί που καθορίζει μια απίστευτα προηγμένη λύση σε ένα όχι τόσο προηγμένο πρόβλημα - ή μπορείτε να κάνετε τα πράγματα με τον εύκολο τρόπο με λίγο ωμή δύναμη.
Και πάλι, θα χρησιμοποιήσω ένα παράδειγμα: δειγματοληψία ενός τυχαίου εσωτερικού σημείου από ένα αυθαίρετο πολύγωνο. Με άλλα λόγια, σας δίνω ένα απλό πολύγωνο και μου δίνετε ένα τυχαίο σημείο μέσα του (ομοιόμορφα κατανεμημένο σε όλο το πολύγωνο).
Συχνά, απαιτούνται εσωτερικά σημεία για δοκιμές. Σε αυτήν την περίπτωση, δεν έχετε συγκεκριμένες απαιτήσεις χρόνου εκτέλεσης στον αλγόριθμο υπολογιστικής γεωμετρίας που τις παράγει (εντός του λόγου). Η γρήγορη και βρώμικη λύση, η οποία χρειάζεται ~ 2 λεπτά για την εφαρμογή, θα ήταν να επιλέξετε ένα τυχαίο σημείο μέσα σε ένα κουτί που περιέχει το πολύγωνο και να δείτε αν το ίδιο το σημείο βρίσκεται εντός του πολυγώνου.
Για παράδειγμα, ενδέχεται να χάσουμε δύο φορές και να βρούμε ένα έγκυρο δείγμα μόνο στο τρίτο σημείο:
Εδώ είναι ο κωδικός:
class Polygon(object): ... def interiorPoint(self): '''Returns a random point interior point''' min_x = min([p.x for p in self.points]) max_x = max([p.x for p in self.points]) min_y = min([p.y for p in self.points]) max_y = max([p.y for p in self.points]) def x(): return min_x + random() * (max_x - min_x) def y(): return min_y + random() * (max_y - min_y) p = Point(x(), y()) while not self.contains(p): p = Point(x(), y()) return p def contains(self, p): for i in range(self.n): p1 = self.points[i] p2 = self.points[(i + 1) % self.n] p3 = self.points[(i + 2) % self.n] if not ccw(p1, p2, p3): return False return True Αυτό είναι γνωστό ως δειγματοληψία απόρριψης : πάρτε τυχαία σημεία έως ότου κάποιος ικανοποιήσει τα κριτήριά σας. Παρόλο που ενδέχεται να απαιτηθούν αρκετά δείγματα για να βρεθεί ένα σημείο που πληροί τα κριτήριά σας, στην πράξη, η διαφορά θα είναι αμελητέα για τη σουίτα δοκιμών σας. Γιατί λοιπόν να δουλεύεις πιο σκληρά; Συνοπτικά: μην φοβάστε να ακολουθήσετε τη βρώμικη διαδρομή όταν το ζητά η περίσταση.
Παρεμπιπτόντως: εάν θέλετε ένα ακριβής αλγόριθμος για τυχαία δειγματοληψία, υπάρχει ένας έξυπνος εδώ που έχω εφαρμόσει παρακάτω. Η ουσία του:
- Τριγωνίζω το πολύγωνό σας (δηλαδή, σπάστε το σε τρίγωνα).
- Επιλέξτε ένα τρίγωνο με πιθανότητα ανάλογη με την περιοχή του.
- Πάρτε ένα τυχαίο σημείο από το επιλεγμένο τρίγωνο (μια λειτουργία σταθερού χρόνου).
Λάβετε υπόψη ότι αυτός ο αλγόριθμος απαιτεί από εσάς να τριγωνίσετε το πολύγωνό σας, το οποίο επιβάλλει αμέσως έναν διαφορετικό χρόνο εκτέλεσης στον αλγόριθμο, καθώς και την αναγκαιότητα έχω μια βιβλιοθήκη τριγωνικών αυθαίρετων πολυγώνων (χρησιμοποίησα poly2tri με συνδέσεις Python).
from p2t import CDT class Triangle(object): ... def area(self): return abs((B.x * A.y - A.x * B.y) + (C.x * B.y - B.x * C.y) + (A.x * C.y - C.x * A.y)) / 2 def interiorPoint(self): r1 = random() r2 = random() # From http://www.cs.princeton.edu/~funk/tog02.pdf return (1 - sqrt(r1)) * A + sqrt(r1) * (1 - r2) * B + r2 * sqrt(r1) * C class Polygon(object): ... def triangulate(self): # Triangulate poly with hole cdt = CDT(poly.points) triangles = cdt.triangulate() def convert(t): A = Point(t.a.x, t.a.y) B = Point(t.b.x, t.b.y) C = Point(t.c.x, t.c.y) return Triangle(A, B, C) return map(convert, triangles) def interiorPoint(self): # Triangulate polygon triangles = self.triangulate() areas = [t.area() for t in triangles] total = sum(areas) # Calculate normalized areas probabilities = [area / total for area in areas] weighted_triangles = zip(triangles, probabilities) # Sample triangles according to area r = random() count = 0 for (triangle, prob) in weighted_triangles: count += prob # Take random point from chosen triangle if count > r: return triangle.interiorPoint() Ας ελπίσουμε ότι η επιπλέον προσπάθεια είναι εμφανής από τον κώδικα. Θυμηθείτε: όπως λένε στο Facebook, 'Το τελειωμένο είναι καλύτερο από το τέλειο' . Το ίδιο ισχύει για υπολογιστικά προβλήματα γεωμετρίας.
Οπτική και αυτοματοποιημένη δοκιμή
Δεδομένου ότι πολλά από τα προβλήματα που αντιμετωπίζετε στην υπολογιστική γεωμετρία ορίζονται σε όρους εύκολα ορατών ποιοτήτων ή ποσοτήτων, η οπτική δοκιμή είναι ιδιαίτερα σημαντικό - αν και ανεπαρκές από μόνο του. Η ιδανική δοκιμαστική σουίτα θα έχει συνδυασμό οπτικών και τυχαιοποιημένων αυτοματοποιημένων δοκιμών.
Η ιδανική δοκιμαστική σουίτα θα έχει συνδυασμό οπτικών και τυχαιοποιημένων αυτοματοποιημένων δοκιμών.Και πάλι, προχωρούμε με το παράδειγμα. Εξετάστε το ενδεχόμενο να δοκιμάσετε την εφαρμογή του Αλγόριθμου του Kirkpatrick. Σε ένα βήμα, ο αλγόριθμος πρέπει να συνδέσει το δεδομένο πολύγωνο με ένα τρίγωνο και να τριγωνίσει την περιοχή μεταξύ του πολυγώνου και του εξωτερικού τριγώνου. Ακολουθεί ένα οπτικό παράδειγμα, όπου η συμπαγής πράσινη γραμμή καθορίζει το αρχικό πολύγωνο και οι διακεκομμένες γραμμές καθορίζουν την τριγωνική περιοχή:
Η επιβεβαίωση ότι αυτός ο τριγωνισμός έχει εκτελεστεί σωστά είναι πολύ δύσκολο να επαληθευτεί μέσω κώδικα, αλλά είναι άμεσα εμφανής στο ανθρώπινο μάτι. Σημείωση: Προτείνω ιδιαίτερα τη χρήση Matplotlib για να βοηθήσετε στην οπτική δοκιμή σας - υπάρχει ένας καλός οδηγός εδώ .
Αργότερα, θα θέλαμε να επαληθεύσουμε ότι ο αλγόριθμος εντοπίζει σωστά τα σημεία. Μια τυχαιοποιημένη, αυτοματοποιημένη προσέγγιση θα ήταν να δημιουργήσουμε μια δέσμη εσωτερικών σημείων για κάθε πολύγωνο και να βεβαιωθούμε ότι επιστρέφουμε το επιθυμητό πολύγωνο. Σε κωδικό:
class TestLocator(unittest.TestCase): ... def runLocator(self, polygons): # Pre-process regions l = Locator(polygons) # Ensure correctness for polygon in polygons: # Test 100 random interior points per region for k in range(100): target = polygon.interiorPoint() target_polygon = l.locate(target) self.assertEqual(polygon, target_polygon) self.assertTrue(target_polygon.contains(target)) Θα μπορούσαμε τότε να χρησιμοποιήσουμε το runLocator μέθοδος σε διαφορετικά σύνολα πολυγώνων, δίνοντάς μας μια καλά διαφοροποιημένη σουίτα δοκιμών.
Λύσεις ανοιχτού κώδικα
Η υπολογιστική γεωμετρία διαθέτει μια ωραία σουίτα ανοιχτών πηγών βιβλιοθηκών και λύσεων, ανεξάρτητα από τη γλώσσα προγραμματισμού της επιλογής σας (αν και οι βιβλιοθήκες C ++ φαίνεται να εμφανίζουν δυσανάλογο ποσό).
τι είδους llc χρειάζομαι
Τα οφέλη από τη χρήση υφιστάμενων λύσεων ανοιχτού κώδικα ( όπως με την επιστημονική πληροφορική στην Python ) είναι γνωστά και έχουν συζητηθεί εκτενώς, οπότε δεν θα το συζητήσω εδώ. Αλλά σκέφτηκα ότι θα αναφέρω μερικούς πόρους Python-centric που θεώρησα χρήσιμους:
- poly2tri : μια εξαιρετική βιβλιοθήκη για γρήγορους τριγωνισμούς πολυγώνων. Υποστηρίζει επίσης (και αυτό είναι συχνά κρίσιμο) πολύγωνα με τρύπες σε αυτούς. Γραμμένο σε C ++, το poly2tri έχει επίσης συνδέσεις Python και ήταν αρκετά εύκολο να σηκωθεί και να λειτουργήσει. Δείτε το
triangulate παραπάνω μέθοδος για μια γεύση για τις κλήσεις συνάρτησης. - scipy.spatial : περιλαμβάνει λειτουργίες για τον υπολογισμό κυρτών κύτους, Delaunay Triangulations και άλλα. Γρήγορη (όπως πάντα), αξιόπιστη κ.λπ. Σημείωση: Το βρήκα χρήσιμο να χρησιμοποιήσω το δικό μου
Point τύπος δεδομένων με toNumpy μέθοδος: def np(self): return [self.x, self.y]. Τότε, θα μπορούσα εύκολα να καλέσω scipy. χωρικές μεθόδους, π.χ.: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points)) . - OpenCV : η βιβλιοθήκη ανοιχτού κώδικα υπολογιστή έχει μερικές ωραίες αυτόνομες υπολογιστικές ενότητες γεωμετρίας. Συγκεκριμένα, το χρησιμοποίησα ελάχιστη συνάρτηση τριγώνου για λίγο πριν το εφαρμόσω ο ίδιος.
συμπέρασμα
Ελπίζω αυτή η ανάρτηση να σας δώσει μια γεύση για την ομορφιά της υπολογιστικής γεωμετρίας ως Προγραμματιστής Python , ένα θέμα πλούσιο σε συναρπαστικά προβλήματα και εξίσου συναρπαστικές εφαρμογές.
Στην πράξη, οι υπολογιστικές γεωμετρικές εφαρμογές παρουσιάζουν μοναδικές προκλήσεις που θα σας ωθήσουν να ασκήσετε νέες και συναρπαστικές δεξιότητες επίλυσης προβλημάτων.
Εάν ενδιαφέρεστε να μάθετε περισσότερα ή έχετε ερωτήσεις για εμένα, μπορείτε να επικοινωνήσετε μαζί μου [προστασία μέσω email] .
