Πρόβλημα γεωμετρίας...

[Alchemist`]

Δεν είναι κάτι περίπλοκο στην σύληψη, αλλά δεν έχω καταφέρει ακόμη να βρώ ένα τρόπο λύσης...

 

Έχουμε λοιπόν 2 σχήματα, ένα τρίγωνο και ένα ορθογώνιο...

 

 

Θέλω όταν συμβαίνει αυτό που βλέπετε στην παρακάτω εικόνα, το πράσινο τμήμα του τριγώνου να αποκόπτεται από το τρίγωνο και να έχουμε ένα νέο τρίγωνο, αυτό που απομένει από το προηγούμενο

 

 

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

 

Μπορείτε να βοηθήσετε? Αν όχι να δώσετε μια ολοκληρωμένη λύση, έστω και μερικές σκέψεις θα ήταν ευπρόσδεκτες...

 

Ευχαριστώ προκαταβολικά!

[StavrosD]

Είναι θεωρία αναλυτικής γεωμετρίας.

 

Χρειάζεσαι τις εξισώσεις των πλευρών του κάθε σχήματος. Η κάθε πλευρά θα είναι μια γραμμή της μορφής Y=Ax+b , Χmin<Χ<Χmax, Υmin<Υ<Υmax.

 

Βρες τα σημεία τομής, και σύνθεσε το νέο σχήμα.

[C6WGMN]

Η λύση αναλύετε σε κάτι απλούστερο: δεν σε ενδιαφέρει πλέον το ορθογώνιο, αλλά μία μόνο πλευρά του. (δες φοτο)

 

Αν έχεις τις συντεταγμένες των κορυφών του τριγώνου και την εξίσωση της ευθείας, το καινούριο τρίγωνο σχηματίζεται από τα σημεία Α, Β', Γ'.

[parsifal]

Η λύση αναλύετε σε κάτι απλούστερο: δεν σε ενδιαφέρει πλέον το ορθογώνιο, αλλά μία μόνο πλευρά του. (δες φοτο)

 

Αν έχεις τις συντεταγμένες των κορυφών του τριγώνου και την εξίσωση της ευθείας, το καινούριο τρίγωνο σχηματίζεται από τα σημεία Α, Β', Γ'.

 

Δε νομίζω πως είναι τόσο απλό: Έστω ότι υπάρχει collision, αλλά η «μύτη» του τριγώνου δεν έχει διαπεράσει το ορθογώνιο. Π.χ. πάρε το σχήμα που έχεις παραθέσει, φαντάσου ότι είμαστε σε τρεις διαστάσεις και κάνε περιστροφή του τριγώνου κατά 180 μοίρες γύρω από τον άξονα-ευθεία που διέρχεται από τα Β', Γ'.

 

Δηλαδή χρειάζεται μία επιπλέον συνθήκη που πρέπει να ελεγχθεί, πέραν του collision: Η «μύτη» του τριγώνου να είναι εκτός του γεωμετρικού τόπου που ορίζει το ορθογώνιο.

[StavrosD]

Έχεις αρχικά 7 ευθύγραμμα τμήματα, 3 του τριγώνου και 4 του παραλληλογράμμου.

 

Ελέγχεις το καθένα από τα 3 πρώτα αν τέμνει ένα η περισσότερα από τα 4 επόμενα. Στην συνέχεια ανάλογα με τον αριθμό των τομών κρίνεις ποια περίπτωση έχεις.

[C6WGMN]

Δε νομίζω πως είναι τόσο απλό: Έστω ότι υπάρχει collision, αλλά η «μύτη» του τριγώνου δεν έχει διαπεράσει το ορθογώνιο. Π.χ. πάρε το σχήμα που έχεις παραθέσει, φαντάσου ότι είμαστε σε τρεις διαστάσεις και κάνε περιστροφή του τριγώνου κατά 180 μοίρες γύρω από τον άξονα-ευθεία που διέρχεται από τα Β', Γ'.

 

Δηλαδή χρειάζεται μία επιπλέον συνθήκη που πρέπει να ελεγχθεί, πέραν του collision: Η «μύτη» του τριγώνου να είναι εκτός του γεωμετρικού τόπου που ορίζει το ορθογώνιο.

 

Νομίζω πως εσύ περιπλέκεις το πρόβλημα. Φυσικά και δεν θα ήταν τόσο απλό αν θελήσουμε να πάρουμε όλες τις περιπτώσεις (λχ οι δυό πλευρές του ορθογωνίου μπορεί να είναι κάθετες και να μην είναι της μορφής ψ = αχ + β, αλλά χ = α). Άλλο πρόβλημα είναι πως μπορεί πολύ απλά να μην υπάρχει το ζητούμενο τρίγωνο ή ακόμα να σχηματίζετε μέσα στο ορθογώνιο. Δεν έδωσα μια γενική λύση αλλά νομίζω πως κάλυψα τον φίλο μας, διότι όλα τα προαναφέροντα ελένχοντε πολύ εύκολα. Ουδείς αγεωμέτρητος εισείτω!

[kagelos]

Ψάχνεις για γενική λύση μεταξύ δύο δισδιάστατων σχημάτων;

Υπάρχουν αλγόριθμοι για boolean operations (Constructive solid geometry) που κάνουν αυτό που περιγράφεις και κάποιες πράξεις ακόμα (τομή, ένωση, αφαίρεση, XOR κλπ).

Έχω υλοποιήσει και για 2D και για 3D αλλά δεν το γράφεις και σε ένα απόγευμα.

[Alchemist`]

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

 

Να πω πως το τρίγωνο είναι ένα σχεδιασμένο sprite. Δεν το ορίζω με 3 ευθείες, ψάχνω να βρώ τρόπο για να βρίσκω τις 3 κορυφές του, προς το παρόν ξέρω μόνο την μία, την μύτη.

 

Επίσης να αναφέρω πως:

 

α) Σε περίπτωση που το τρίγωνο είναι τραπέζιο, θα λειτουργήσουμε με παρόμοιο τρόπο, αν όμως είναι κύκλος?

 

β) Επειδή αυτός ο έλεγχος γίνεται τουλάχιστον 50 φορές σε ένα step (1500/δευτερόλεπτο), για διαφορετικά σχήματα, κατα πόσο θα είναι αποδοτική (σύμφωνα με τις εκτιμήσεις σας) μια μέθοδος που χρησιμοποιεί τόσα πολλά αριθμητικά δεδομένα? Θα μπορούσε να υπάρξει ένας τρόπος "μετατροπής"-"αλλαγής" του sprite με το νέο υπολογισμένο σχήμα ώστε να μην ξαναγίνονται συνέχεια οι υπολογισμοί? (για τα στατικά φώτα)

 

Ευχαριστώ και πάλι για το χρόνο σας.

[V.I.Smirnov]

Το πρόβλημά σου είναι πρόβλημα τομής/επικάλυψης πολυγώνων, κλασσικό θέμα στην Υπολογιστική Γεωμετρία και μελετάται στα περισσότερα αντίστοιχα βιβλία.

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

 

Μια αντιμετώπιση για κυρτά πολύγωνα στο ίδιο επίπεδο αναπτύσσεται στο "Computational Geometry in C, 2nd ed" O Rourke, παρ. 7.6 . Δίνει και τον βασικό κώδικα αλλά μην περιμένεις ότι θα τα καταφέρεις χωρίς προσπάθεια...

[Alchemist`]

Το πρόβλημά σου είναι πρόβλημα τομής/επικάλυψης πολυγώνων, κλασσικό θέμα στην Υπολογιστική Γεωμετρία και μελετάται στα περισσότερα αντίστοιχα βιβλία.

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

 

Μια αντιμετώπιση για κυρτά πολύγωνα στο ίδιο επίπεδο αναπτύσσεται στο "Computational Geometry in C, 2nd ed" O Rourke, παρ. 7.6 . Δίνει και τον βασικό κώδικα αλλά μην περιμένεις ότι θα τα καταφέρεις χωρίς προσπάθεια...

 

I know και το ότι πρόκειται για φως το κάνει ακόμη πιο δύσκολο... Στο παιχνίδι (2Δ) έχω ορίσει τα φώτα ως εξής. Για κάθε φως, φτιάχνω ένα sprite, ενώ σε όλο το δωμάτιο υπάρχει σκοτάδι. Το φως ορίζεται ως προσθήκη φωτεινότητας εκεί όπου βρίσκεται το sprite...

 

Ψάχνεις για γενική λύση μεταξύ δύο δισδιάστατων σχημάτων;

Υπάρχουν αλγόριθμοι για boolean operations (Constructive solid geometry) που κάνουν αυτό που περιγράφεις και κάποιες πράξεις ακόμα (τομή, ένωση, αφαίρεση, XOR κλπ).

Έχω υλοποιήσει και για 2D και για 3D αλλά δεν το γράφεις και σε ένα απόγευμα.

 

 

Δεν ήξερα πως να ψάξω σχετικά μέχρι τώρα, ευχαιρστώ, βρήκα αρκετά θεματάκια για Constructive Solid Geometry στο Γούγλη... Αν και τα περισσότερα αφορούν 3Δ.

[Crizzt]

Alchemist, αλλη μια λυση θα ηταν:

 

1. συγκρινεις δυο ευθυγραμα τμηματα: τη μεσοκαθετο του τριγωνου (Α) με την αποσταση κορυφης τριγωνου και "τοιχου" (Β). Εαν (Α) > (Β) εχεις collision και βρησκεις και κρατας τη γωνια προσκρουσης.

2. Κοψε καταλληλα το sprite του φωτος εχοντας γνωστα τη μεσοκαθετο και τη γωνια.

 

Θελει λιγη δουλιτσα αλλα νομιζω οτι γινεται

[V.I.Smirnov]

Ξέρω πως να λύσω το παρόμοιο πρόβλημα :

Δίνονται δυο συνεπίπεδα κυρτά πολύγωνα P, Q.

Aν τέμνονται να βρεθεί το πολύγωνο που είναι η τομή τους.

Αν όχι να βρεθεί να βρεθεί αν αν κάποιο περιέχεται εντός του άλλου ή όχι.

 

Mοιάζει με το δικό σου αλλά εσύ δεν θέλεις την τομή των P, Q αλλά ένα τμήμα της διαφοράς τους P\Q ...

[kagelos]

Το βιβλίο "Morgan Kaufmann - Geometric Tools for Computer Graphics" εκτός του ότι γενικώς είναι θησαυρός για 2Δ/3Δ γραφικά, περιγράφει σε ψευδοκώδικα boolean operations για 2Δ και 3Δ.

Ο ψευδοκώδικας περιέχει μερικά τυπογραφικά λάθη και γενικότερα τον εκφράζει με αναδρομή, πράγμα αδιανόητο για πραγματικές εφαρμογές. Με ελάχιστο όμως κόπο μπορείς να τον τροποποιήσεις και να έχεις boolean operations για ομο-επίπεδα σχήματα (δηλ. 2Δ).

Όλα τα σχήματα τελικά μπορείς να τα προσεγγίζεις με polygons/polylines. Έτσι και τον κύκλο μπορείς να τον εκφράζεις σαν ένα πολύγωνο με πολλές ακμές. Οπότε ο αλγόριθμός θα παίζει πάλι.

[V.I.Smirnov]

To βιβλίο "Geometric Tools for Computer Graphics" που αναφέρει ο Κagelos είναι η παλιότερη έκδοση του "3D Game Engine Design" και του συνοδευτικού του "3D Game Engine Αrchitecture".

Ουσιωδώς περιγράφει την μηχανή γραφικών Wild Magic που κάνει πάρα πολλά πράγματα τέτοιου είδους και λύνει και το προαναφερθέν πρόβλημα. Ο κώδικάς της (πάνω από 200.000 γραμμές) είναι ανοικτός και τσάμπα και είναι υπόδειγμα σαφήνειας, οργάνωσης και ακριβολογίας. Δεν έχω δει πιο καλογραμμένο πρόγραμμα, ακόμα και η στοίχιση του source code είναι άψογη και έχει συνέπεια.

Συνοδεύεται και από πολλά demo που δείχνει πως χρησιμοποιούνται οι κλάσσεις της σε κάθε περίπτωση. Υπάρχει και στο internet.

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

ΑΛΛΑ αν δεν ξέρεις μαθηματικά και προγραμματισμό (στα σοβαρά, όχι για τα πανηγύρια), ξέχνα το.

Ο D. Eberly που έγραψε τα βιβλία και και την Wild Magic έχει δυο μεταπτυχιακά και δυο διδακτορικά και κάνει βαριά χρήση μαθηματικών παντού.

 

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

[Alchemist`]

Προς το παρόν σκέφτομαι γύρω απ'όλες τις ιδέες που ειπώθηκαν, ήδη έχω αρχίσει να δουλεύω κάνα 2 πράγματα... Θα σας ενημερώσω αν υπάρξει κάποια εξέλιξη, ευχαριστώ ακόμη μια φορά για την βοήθειά σας!

 

@Smirnov: Τα μαθηματικά που έχω διδαχτεί είναι επιπέδου 3ης λυκείου, και θυμάμαι λίγα απο αυτά... Με το προγραμματισμό ασχολούμε τελείως ερασιτεχνικά και δεν έχω γνώσεις πανεπηστιμιακού επιπέδου... To παλέυω πάντως, έπιασα αρκετές φορές τον εαυτό μου να προσπαθεί να ξαναεφεύρει τον τροχό (ψάχνοντας π.χ. αλγόριθμο pathfinding έφτιαξα μια μορφή του αλγορίθμου BestFS), αλλά αυτό είναι που δίνει φάση στο όλο θέμα