Newsgroup: it.hobby.enigmi
Titolo: Due segmenti

Sul piano cartesiano sono dati due segmenti, ognuno, naturalmente,
identificato da due punti. Sulla base del valore delle coordinate dei
quattro punti, bisogna riuscire a determinare se i detti segmenti si
intersecano tra loro.
Ciao :-)
Giorgio

 ha scritto nel messaggio
news:ber3sf$8296j$1...@ID-56302.news.uni-berlin.de...

Trovo l'equazione delle due rette e le metto a sistema. Se non ho soluzione
non c'č intersezione (segmenti su rette parallele). Se ho una sola soluzione
controllo che appartenga a ciascuno dei due segmenti. Se infine il sistema č
indeterminato (rette coincidenti) basta controllare che almeno uno dei due
estremi del primo segmento appartenga all'altro segmento.
Forse non č la soluzione + rapida, d'altronde credo si possa descrivere un
segmento con un sistema di un'equazione e una disequazione, che forse
fornisce una soluzione + elegante e piů rigorosa.
Ciao, Spider

 wrote in message
news:BGwQa.173506$lK4.4...@twister1.libero.it...


 wrote

Ciao Marco,
pur essendo corretta anche la soluzione di Spider, la tua č proprio quella
che intendevo.
Perché i due segmenti si intersechino bisogna che, rispetto al segmento AB,
il punto C si trovi dalla "parte opposta" del punto D e contemporaneamente
rispetto al segmento CD il punto A e il punto B si trovino anch'essi da
parti opposte. Per verificare che le cose stiano cosě č sufficiente trovare
un modo per stabilire se, ad esempio, per andare da A e B e poi a C si
"volta" a sinistra oppure a destra e cosě per A-B-D, C-D-A e C-D-B.
Vi allego alcune righe di codice commentato scritto in C (non scritto da me,
l'ho trovato non ricordo piů dove) che fanno apprezzare quanto sia semplice
l'implementazione della soluzione (una volta trovata la soluzione! :-) )
/*************************************************************************
 * FUNCTION:   CCW (CounterClockWise)
 *
 * PURPOSE
 * Determines, given three points, if when travelling from the first to
 * the second to the third, we travel in a counterclockwise direction.
 *
 * RETURN VALUE
 * (int) 1 if the movement is in a counterclockwise direction, -1 if
 * not.
 *************************************************************************/
int CCW(POINT p0, POINT p1, POINT p2)
{
   LONG dx1, dx2 ;
   LONG dy1, dy2 ;
   dx1 = p1.x - p0.x ; dx2 = p2.x - p0.x ;
   dy1 = p1.y - p0.y ; dy2 = p2.y - p0.y ;
   /* This is basically a slope comparison: we don't do divisions because
    * of divide by zero possibilities with pure horizontal and pure
    * vertical lines.
    */
   return ((dx1 * dy2 > dy1 * dx2) ? 1 : -1) ;
}
BOOL Intersect(POINT p1, POINT p2, POINT p3, POINT p4)
{
   return ((( CCW(p1, p2, p3) * CCW(p1, p2, p4)) <= 0)
        && (( CCW(p3, p4, p1) * CCW(p3, p4, p2)  <= 0) )) ;
}
Ciao
Giorgio

 }
Però l'uguale a zero non si verifica mai. Dal fatto che sia
stato messo deduco che si vogliono considerare intersezioni
anche se l'estremo di A_B sta su C_D (o viceversa) (ti
assicuro che questi casi vanno seeempre consederati perchè
prima o poi saltano fuori e ti mandano in tilt il
programma).
Ma per fare ciò è necessario restituire 0 se tre punti sono
allineati. Altrimenti
CCW(p1, p2, p3) e CCW(p1, p2, p4)  poterbbero essere
entrambi -1 se p3 o p4 stanno su P1_P2.
Ciao
Marco

 entrambi -1 se p3 o p4 stanno su P1_P2.
Quello che dici è vero, in particolare l'appunto sull'uso del <= quando
sarebbe stato sufficiente un < (anche se non si può dire che sia un errore).
C'è però da considerare che nelle intenzioni dell'autore si vogliono
trattare punti definiti da numeri interi (oltre alle distanze dichiarate
come LONG, anche la struttura POINT è formata da due interi) adatti
probabilmente a gestire coordinate video. In questo caso il tentativo di
considerare allineamenti perfetti si perde nell'imperfezione intrinseca
della rappresentazione di segmenti a video.
Ciao
Giorgio


Temo di non capire cosa intendi; io ho avuto problemi con
cose di questo tipo.. lavorando proprio con coordinate
intere. Anzi, credo che non sarebbe successo con punti dati
in float.
Potresti spiegarmi meglio cosa intendi dire? E.. giusto per
curiosità, se è lecito, per cosa stai usando queste cose?
Grazie, ciao
marco

 che intendevo.
Decisamente meglio :) Cmq non avevo capito che si parlava di una soluzione
algoritmica.
Ciao,
Spider


Hai ragione Spider, non lo avevo, volutamente, specificato perché nel caso
di una risposta come la tua avrei poi suggerito di trovare una soluzione piů
facilmente implementabile sotto forma di codice. Ma Marco č arrivato
prima... :-)
Ciao
Giorgio

 wrote

Intendo dire, ad esempio, questo. Se prendi un segmento che va dal punto 0,0
al punto 2,1 potresti ottenere questo risultato (ogni pixel è un asterisco):
**
  *
oppure questo:
*
 **
Probabilmente Windows lo rende nel primo modo, ma non credo si possa
affermare con certezza che sarà sempre così e che sia così sotto un'altra
interfaccia grafica.
In ogni caso, se adesso individuiamo un punto in mezzo al segmento, questo,
in base ai nostri possibili arrotondamenti o troncamenti potrebbe avere
coordinate 1,0 o 1,1. Quindi, pur essendo un punto che idealmente doveva
essere sul segmento, potrebbe a questo punto esserlo o non esserlo (da una
parte o dall'altra) ancora prima che entri in azione il codice di cui stiamo
dibattendo.
Queste cose le ho utilizzate nel passato per varie applicazioni in cui era
necessario capire se l'utente cliccava dentro o fuori di una certa area,
area che poteva essere racchiusa da una qualsiasi poligonale. Non facevo
altro che contare le intersezioni tra il segmento identificato dal punto in
cui l'utente cliccava e un altro punto "lontano" e ogni segmento formante la
poligonale. Se il conteggio dava risultato dispari, il punto era interno.
(L'utilizzo di funzioni del tipo PtInRegion non danno prestazioni
accettabili.)
In questo contesto non è molto importante curarsi del fatto che l'utente
clicchi proprio sul bordo dell'area.
Ciao
Giorgio

 clicchi proprio sul bordo dell'area.
Già, è vero. Io dicevo perchè per me era importante decidere
cosa fare quando un segmento terminava proprio sopra
all'altro.
Ciao
marco