Contour plot

[kagelos]

Καλησπέρα,

γνωρίζει κανείς κάποιον αλγόριθμο για την κατασκευή ισοϋψών καμπυλών;

 

Εννοώ κάτι τέτοιο και τέτοιο.

 

Έχω ήδη υλοποιήσει έναν αλγόριθμο αλλά έχω μερικά προβλήματα και θα ήθελα να δω και μια διαφορετική λύση.

 

Υ.Γ. Δεν με ενδιαφέρει raster λύση.

[V.I.Smirnov]

Εγώ το έχω κάνει - πριν περίπου δυό χρόνια.

 

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

ίδιες τιμές κάνοντας παρεμβολή (marching squares).

Εσένα εδώ το πεδίο σου είναι θερμοκρασίες.

 

Επίσης, το έχω κάνει και στον χώρο δηλ. για ισοϋψείς επιφάνειες (marching cubes) !

 

Δεν το έκανα με raster λύση.

Αλλά δεν επιχείρησα να βάψω τις κλειστές περιοχές. Απλώς σχεδίαζα τις καμπύλες (στον χώρο τις επιφάνειες) με διαφορετικά χρώματα.

 

Πες μου πώς το έκανες εσύ ;

[kagelos]

Δημιουργώ μια κλίμακα από min εώς max με n βήματα.

Για κάθε βήμα scanάρω το grid (έχω rectangular grid) και μαρκάρω τις οριζόντιες και κάθετες πλευρές που βρίσκονται ανάμεσα από δύο σημεία οι τιμές των οποίων είναι η μία μεγαλύτερη και η άλλη μικρότερη από το τρέχον βήμα.

Στη συνέχεια ενώνω τις πλευρές που έχω μαρκάρει (με κάποια λογική)

 

Π.χ.

έστω ότι min = 0, max = 10 και n = 5

Άρα η κλίμακα μου έχει τα εξής βήματα :

0, 2, 4, 6, 8, 10

 

Έστω το τρέχον βήμα = 4

ένα τμήμα του grid :

 

>
---------------------------------------
|      2     [b]*[/b]      7      |     10       |
---------------------------------------
|      3     [b]*[/b]       5     |     9       |
------------------[b]*[/b]--------------------
|      1     |     3,2    [b]*[/b]     7       |
------------------[b]*[/b]--------------------
|      2     [b]*[/b]      9      |      8      |
------[b]*[/b]--------------------------------
|      5     |      7      |     6       |
---------------------------------------

 

Όπου * σημαίνει μαρκαρισμένο edge

 

Είχα ένα πρόβλημα αρχικά με τις τρύπες (πολύγωνα μέσα σε άλλα πολύγωνα) αλλά κάνοντάς τα sort με βάση το εμβαδό, το πρόβλημα λύνεται 100%.

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

Επόμενο πρόβλημα (άλυτο) είναι πως γίνεται η ένωση σε σημεία όπου η καμπύλη μπορεί να πάει σε περισσότερες από μία πλευρές του ίδιου κελιού.

 

Για αυτό πλέον ψάχνω μια λύση με mesh.

Έχω κάνει απλές δοκιμές να τυπώνω rectangles αλλά το grid μου δεν έχει αρκετή ανάλυση. Κάνοντας Interpolation πιάνει πολύ μνήμη χωρίς να βελτιώνεται αισθητά το αποτέλεσμα.

 

Θα ανεβάσω μερικά screenshots να δείτε.

[kagelos]

Ανεβάζω μερικά screenshot

Το πρώτο είναι ένα πετυχημένο run.

Το δεύτερο αφήνει κενό γιατί έχει το εξής πρόβλημα :

Όταν μια καμπύλη για παράδειγμα ξεκινάει από την αριστερή πλευρά και τερματίζει στην πάνω, χωρίζει "χοντρά" το grid σε 2 κομμάτια :

το πάνω αριστερά τεταρτημόριο και τα 3 υπόλοιπα. Κανονικά θα έπρεπε όταν το κλείνω, ώστε να γίνει πολύγωνο, να βάζω και το αντίθετό του ώστε να γεμίζει και το δεύτερο κομμάτι (τα 3 τεταρτημόρια).

Το τρίτο screenshot είναι η προσέγγιση με τα rectangles. Κάνω upsample εκεί που χρειάζεται για εξοικονόμηση πόρων. Παρόλα αυτά το αποτέλεσμα δεν είναι ικανοποιητικό.

Το τέταρτο είναι απλά το ίδιο με το τρίτο και επιπλέον δείχνει τα borders.

[kagelos]

Γραμμές βγάζω και εγώ χωρίς σφάλματα. Θέλω όμως filled πολύγωνα και είναι μάλλον πιο δύσκολο.

Τείνω προς λύση τύπου mesh.

 

---------- Προσθήκη στις 01:20 ---------- Προηγούμενο μήνυμα στις 01:02 ----------

 

Λοιπόν σκέφτομαι το εξής :

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

 

Οι τιμές του αρχικού grid δεν έχουν (οπωσδήποτε) τις τιμές των βημάτων τις κλίμακας.

Με την κλίμακα που θα φτιάχνω, θα μπορώ να πω για κάθε τιμή του grid, σε ποιο βήμα της κλίμακας ανήκει.

 

Δηλαδή με την παραπάνω κλίμακα (5 βήματα, τιμές: 0,2,4,6,8,10)

θα θεωρώ π.χ. ότι το κάθε βήμα περιέχει -1 < βήμα <= +1

Δηλαδή το 3 ανήκει στο δεύτερο βήμα.

 

Στην συνέχεια για κάθε τιμή του αρχικού grid, θα βάζω στο νέο grid το βήμα στο οποίο αντιστοιχεί, μετακινώντας το σημείο ανάλογα.

 

Δηλαδή με inverse linear interpolation αν ένα σημείο έχει τιμή π.χ. 2.8, στην θέση του θα μπει το 2, αφού πρώτα υπολογιστεί το χ,y του 2.

>
                     upLeft-------up-------upRight
                     |              |            |
                     |              |            |
                     left---------center--------right
                     |               |           |
                     |               |           |
                 downLeft-----down-----downRight

 

Έστω δηλαδή ότι το center έχει z = 2.8

Θα πρέπει κάνοντας interpolation με τα γύρω γύρω σημεία να βρω που είναι το 2.

 

Προτείνει κανείς τίποτα;

[bxenos]

Μια απλή σκέψη: ταξινόμησε τα πολύγωνα με το τετραγωνισμένο μέγεθος τους και βάψε από το μεγαλύτερο προς το μικρότερο. Οπότε κάθε επόμενο πολύγωνο, θα υπερκαλύπτει μέρος κάποιου άλλου ζωγραφισμένου.

Ιδανική λύση θα ήταν ταξινόμηση με το εμβαδό, αλλά θα φάει χρόνο με τριγωνισμούς/τύπο του Ήρωνα κλπ.

 

Μια δεύτερη: αν δεν είναι πολύ μεγάλος ο αριθμός, θα έκανα σάρωση σε ανάλυση viewport (οθόνης/εκτυπωτή/αρχείου ή ότι άλλη έξοδο έχεις) από αριστερά προς τα δεξιά και κάθε φορά (σε κάθε γραμμή που θα σάρωνα για draw) που θα έκανε intersect με πλευρά πολυγώνου, θα άλλαζα την κατάσταση του pen_down.

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

Αυτό πέρνει και βελτίωση, να μην αλλάζει την κατάσταση pen down σε pen up και αντίστροφα, αλλά να βάφει όλα τα τμήματα της οριζόντιας γραμμής με τα χρώματα του πολυγώνου που έχουμε intersect.

[Technology fan]

Αυτο που ψάχνεις είναι ο αλγόριθμος Marching squares

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

 

Αν έχεις καμια απορία σχετικά με τον αλγόριθμο ρώτα. Τα χω πολύ πρόσφατα...

 

Αυτό είναι ένα πολύ καλό pdf

[V.I.Smirnov]

@kagelos :

To πρόβλημα εύρεσης των ισοϋψών είναι στην πραγματικότητα το ίδιο με τη γραφική παράσταση μιας πλεγμένης συνάρτησης.

Μια σχέση y=f(x) μπορεί να σχεδιαστεί εύκολα.

Μια σχέση F(x,y)=c όμως όχι.

Η μέθοδος που χρησιμοποιείται είναι η marching squares (cubes για τον χώρο).

 

Εγώ είχα σε ένα πλέγμα τις τιμές ενός πεδίου και ήθελα να σχεδιάσω τις ισοσταθμικές.

Αυτό το έκανα με την εν λόγω μέθοδο αλλά δεν γέμιζα πολύγωνα ούτε τα αποθήκευα - ήταν real time.

 

Όταν σε κάποιο κελί, από την παρεμβολή προκύπτουν περισσότερες από μια πιθανές τιμές για να ενωθούν (ambiguous cases)

είναι πρόβλημα που θέλει σκέψη αλλά δεν είναι άλυτο.

Η συνήθης αντιμετώπιση είναι ότι είναι αποδεκτές όλες οι τιμές οπότε διαλέγεις στην τύχη. Αυτό είχα κάνει κι εγώ.

Ένας άλλος κακός τρόπος, είναι να υποδιαιρεθεί περαιτέρω το κελί όπου εμφανίζεται η αμφιβολία.

Όλα αυτά είναι ημίμετρα.

Η σωστή λύση είναι να εξεταστεί η μορφή της καμπύλης γύρω από τις πλευρές του κελιού.

Από τις ασύμπτωτες της καμπύλης φαίνεται πιο σημείο είναι το πραγματικό από τα πιθανά.

Η λύση αυτή είναι του Ebelry και παραδόξως δεν διδάσκεται και δεν αναφέρεται παρόλο που είναι η πιο σωστή.

Και επιπλέον, γίνεται πολύ πιο εύκολα από την υποδιαίρεση του κελιού !

 

@Tecnolology fan: το pdf που προτείνεις είναι η απλοϊκή παρουσίαση της μεθόδου marching squares

όπου, όπως πολλά βιβλία, για τις εκφυλλισμένες περιπτώσεις (ambiguous cases) λέει ότι υποδιαιρείς το κελί περαιτέρω - κάτι που είναι

δύσκολο και άκομψο αφού υπάρχει ακριβής λύση.

 

 

Στo παρακάτω κείμενο περιγράφεται από τον Ebelry η marching squares με τη σαφήνεια και ακριβολογία που πρέπει

και παρουσιάζεται η ανάλυση για τις εκφυλλισμένες περιπτώσεις όπως είναι το σωστό :

[ATTACH]31019[/ATTACH]

Όσοι έχουν την μηχανή γραφικών του, Wild magic, μπορούν να δουν και τον κώδικα για την marching cubes - τον δίνει τσάμπα.

 

Aν θέλεις μπορώ να σου στείλω έτοιμο δικό μου demo τόσο για την marching squares όσο και για την

marching cubes που είναι πολύ πιο πολύπολοκη. Στείλε μου pm.

 

To παρακάτω exe είναι το demo που είχα φτιάξει κάποτε.

Είναι η γραφική παράσταση κάποιων γνωστών καμπύλων που δεν είναι συναρτήσεις (δηλ. είναι σε πλεγμένη μορφή).

Συγκεκριμένα, πατώντας F1-F8 σχεδιάζονται οι καμπύλες :

Κύκλος, Παραβολή, Έλλειψη, Υπερβολή, Οβάλ του Cassini, Φύλλο του Καρτέσιου,

Μάγισσα του Agnesi και Κισσοειδής του Διοκλή.

Οι καμπύλες έχουν δοθεί στον κώδικα στη μορφή F(x,y). Υπολογίζονται οι τιμές τους στα σημεία ενός πλέγματος και

σχεδιάζoνται οι ισοσταθμικές F(x,y)=c για διάφορα c με την μέθοδο marching squares.

Mε page up/down αυξομειώνεται το πλήθος των ισοσταθμικών (προσοχή, η πυκνότητα του πλέγματος, δηλ. των τιμών που έχουμε δεν αλλάζει).

Aν πρόκειται για έτοιμες τιμές όπως αυτές που έχει ο kagelos είναι το ίδιο πράγμα : αντί να τις υπολογίζουμε στα σημεία του πλέγματος με την

F(x,y), τις έχουμε έτοιμες...

Δεν είχα βάλει χρώματα για να μη βαρύνει πολύ ο κώδικας. Για δείτε...

[ATTACH]31020[/ATTACH]

[kagelos]

Ευχαριστώ πολύ παιδιά για τις απαντήσεις.

 

V.I.Smirnov οι περιπτώσεις που λες (περισσότερες από μια επιλογές σε ένα κελί) μου βγήκαν και μένα στον αλγόριθμό μου. Αυτό που έκανα ήταν να σταματάω όταν υπάρχει αμφιβολία και να ξεκινάω καινούρια γραμμή. Στο τέλος παίρνω όλες τις γραμμές και τις ενώνω και βγαίνουν τα πολύγωνα.

Κοιτάω τώρα τον marching squares ... αλλά αν είναι να πέσω πάλι στα ίδια προβλήματα, προτιμώ να προσπαθήσω να βελτιώσω τον δικό μου.

 

Αυτό που με ενδιαφέρει δεν είναι τόσο να βγάλω το outline όσο το να είναι σωστά χρωματισμένα τα μέρη του grid και να μην είναι έτσι edgy.

Όπως βλέπετε, τα 2 πρώτα screenshot είναι με linear interpolation και φαίνονται πιο ομαλά. Το 3ο είναι απλά το κάθε κελί βαμμένο με το χρώμα του, το οποίο είναι σίγουρα σωστό, αλλά δεν έχει ικονοποιητική ανάλυση.

 

@bxenos : ωραίες είναι οι ιδέες σου αλλά είναι τεχνικές που αφορούν rasterizer, εγώ δεν φτιάνω (αρχικά) εικόνα.

Επίσης δεν ξέρω αν κατάλαβες καλά το dataset μου. Έχω ήδη τετράγωνα που δεν κάνουν overlap και έχουν όλα το ίδιο εμβαδό.

Απλά αυτό που βλέπεις στο 4ο screenshot, το κάνω εγώ upsample με interpolation στα σημεία όπου αλλάζει χρώμα.

[V.I.Smirnov]

Η μέθοδος marching squares σχεδιάζει τις ισοσταθμικές αλλά δεν τις ως καμπύλες.

Το μόνο που μπορείς να πάρεις άμεσα από αυτήν είναι τα (ευθύγραμμα) τμήματα που συνδέουν τα σημεία παρεμβολής στα κελιά του πλέγματος.

Δηλ. αν μια ισοσταθμική αποτελείται ας πούμε από 4 τμήματα, αυτά τα βρίσκει ο αλγόριθμος και τα σχεδιάζει με τυχαία σειρά, πχ. το 3ο, 1ο, 2ο και 4ο.

Προφανώς η σειρά αυτή εξαρτάται από την σειρά με την οποία σαρώνονται τα κελιά.

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

Από ένα σύνολο σημείων δεν μπορούμε να λάβουμε την καμπύλη που αποτελούν, παρά μόνον την convex hull τους.

Eπειδή εδώ έχουμε ευθύγραμμα τμήματα, αναδημιουργία της καμπύλης (δηλ. του πολυγώνου) είναι δυνατή χρησιμοποιώντας το δεδομένο ότι είναι

συνδεδεμένα και έχουν κοινό σημείο ανά ζεύγη.

Έχοντας τις καμπύλες-πολύγωνα μπορείς να εντοπίσεις το εσωτερικό τους (ή αν είναι ανοιχτές μια συγκεκριμένη πλευρά τους) και να το χρωματίσεις.

Το ερώτημα είναι τι γίνεται όταν μια ισοσταθμική αποτελείται από περισσότερες από μια καμπύλες (πολύγωνα).

Πχ. η οβαλ του Cassini στο παραπάνω demo μου έχει κάποιες ισοσταθμικές με δύο κλειστές καμπύλες.

Αν (και πώς) μπορούν να εντοπιστούν από τα ευθύγραμμα τμήματα δεν ξέρω διότι δεν είναι πλέον όλα τα τμήματα συνδεδεμένα.

 

Τέλος, η κλασσική marching squares όπως στα παραπάνω pdf εφαρμόζει διγραμμική παρεμβολή και δουλεύει σε κάθε βήμα με τέσσερα σημεία (δηλ. σε κελί).

Yπάρχει παραλλαγή της που δουλεύει με τρία σημεία (δηλ. σε τρίγωνο) και κάνει γραμμική παρεμβολή.

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

χωρίς να χρειάζεται να φτιάχνεις τα τελικά πολύγωνα.

Και θυμάμαι ότι αυτό το είχα δει κάποτε σε ένα προγραμμα FEM αλλά δυστυχώς τότε δεν καταλάβαινα τι έκανε και δεν το κράτησα....

 

@Tecnology fan :

H marching squares και marching cubes μπορεί να σχεδιάσει μια επίπεδη καμπύλη F(x,y)=c για δεδομένα στο επίπεδο χy

ή μια επιφάνεια F(x,y,z)=c για δεδομένα στον χώρο.

Αν όμως η ισοσταθμική είναι μια καμπύλη στον χώρο τι γίνεται ; Δηλ. αν π.χ. τα δεδομένα ανήκουν σε μια ισοσταθμική που είναι έλικα

η οποία αναρριχάται κατά z (σαν ελατήριο) πώς προσδιορίζεται ;

Eίναι ειδική περίπτωση της marching cubes ;

[kagelos]

Λοιπόν για να χρωματίσω τα κελιά έχω τις εξής περιπτώσεις :

Ένα κελί δεν τέμνεται από κάποια καμπύλη, άρα ανήκει εξ' ολοκλήρου σε ένα βήμα, άρα παίρνει ένα χρώμα.

Ένα κελί τέμνεται από μια ή περισσότερες καμπύλες, άρα το χωρίζω και χρωματίζω τα επί μέρους τμήματα με το κατάλληλο χρώμα.

 

Όπως είπα ο αλγόριθμος που έχω ήδη φτιάξει, βγάζει γραμμές (όχι απλά ευθύγραμμα τμήματα) οι οποίες βγαίνουν με bilinear interpolation.

 

Συμπεραίνω ότι δεν υπάρχει νόημα να δοκιμάσω το marching squares ... αφού το πολύ πολύ να μου δώσει το ίδιο αποτέλεσμα.

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

[V.I.Smirnov]

Όσο το σκέφτομαι τόσο το θυμάμαι καλύτερα.

Η λύση είναι με απλή γραμμική παρεμβολή στα τρίγωνα κι όχι με διγραμμική στα κελιά.

Έτσι κάθε τρίγωνο χωρίζεται δυο μέρη που βάφεις ανάλογα με την τιμή τους.

Το είχα δει πριν χρόνια σε πρόγραμμα πεπερασμένων στοιχείων σε μια ρουτίνα που σχεδίαζε τις ισοτασικές.

Και δεν ήταν πολύ δύσκολο. Δυστυχώς δεν είχα καταλάβει πώς δούλευε και δεν κράτησα τον κώδικα...

[kagelos]

Παίδες έχω ρίξει μια ματιά σε αυτό που λέει το wikipedia για τον marching squares. Διορθώστε με αν κάνω λάθος :

Αυτό που περιγράφει είναι ότι ο αλγόριθμος "ζωγραφίζει" το outline από κάθε σχήμα (για κάθε level) και

1) είτε κλείνει και άρα έχω πολύγωνο που το βάφω

2) είτε χτυπάω boundary και μένω ξεκρέμαστος (δεν ξέρω πως να το κλείσω - άρα δεν βάφω)

 

@V.I.Smirnov διαβάζω τώρα αυτά που μου έστειλες

[V.I.Smirnov]

Κοίτα, το αρθρο του Eberly θέλει κάποια προσπάθεια.

Ο τρόπος του διαφέρει κάπως από των άλλων αλλά χειρίζεται ενοποιημένα όλες τις περιπτώσεις (αμφίβολες και μη).

 

Εγώ όταν διάβασα την μέθοδο δεν είχα αυτά τα κείμενα και υλοποίησα την marching squares σύμφωνα με τον

αλγόριθμο της σελ. 192 που σου έστειλα και χωρίς τις αμφίβολες περιπτώσεις.

Αρίθμησα τις περιπτώσεις για τα τμήματα όπως δείχνεται στη σελ. 193.

Eιδικότερα, στο demo μου οι αμφίβολες περιπτώσεις είναι

 

>
    case  3:
    case  6:
    case  9:
    case 12:
       draw_adjacent(typeSegm,i,j,a,b,c,d);

και στην draw_adjacent για λόγους απλότητας δεν κάνω διερεύνηση των ασύμπτωτων όπως είναι το σωστό.

Αν χρειατείς κάποια άλλη διευκρίνιση στον κώδικά μου στείλε pm.

 

Παρατήρησε επίσης ότι ο υπολογισμός σε κάθε κελί είναι ανεξάρτητος οπότε ο αλγόριθμος μπορεί να παραλληλιστεί με το openMP.

 

Κάνω μια σκέψη για το πώς θα μπορούσαν να βαφούν τα πολύγωνα :

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

το τμήμα τελικά δεν θα προκύψει όλη η επιφάνεια βαμμένη όπως πρέπει ;

To "κάτω" είναι εύκολο να βρεθεί δεδομένου ότι σημαίνει ότι Υ<αΧ+β οπότε θα πάρεις τους ή τον κόμβο του κελιού που

πληρεί αυτή τη συνθήκη και τα σημεία παρεμβολής του τμήματος. Αυτά αποτελούν το τμήμα του κελιού που θα βάψεις.

Δηλ., το τμήμα που τέμνει το κελί ορίζει σε αυτό ένα μικρό πολύγωνο (πάνω ή κάτω). Έστω ότι βάφεις αυτό το πολύγωνο και

ότι αυτό το κάνεις για κάθε κελί. Δεν θα προκύψει όλη η επιφάνεια βαμμένη σωστά ;