 |
Lisp »Tips 'n Tricks » Intersezione di 2 segmenti
Problemi geometrici risolvibili con un semplice sguardo da una persona vedente richiedono algoritmi non banali; ad esempio due segmenti si intersecano o meno?
INTSZ è la traduzione in Autolisp del seguente codice in C:
struct point { int x, y; }
struct line { struct point p1, p2; };
int ccw (struct point p0,
struct point p1,
struct point p2)
{
int dx1,dx2,dy1,dy2;
dx1 = p1.x-p0.x;
dy1 = p1.y-p0.y;
dx2 = p2.x-p0.x;
dy2 = p2.y-p0.y;
if (dx1*dy2 > dy1*dx2) return +1;
if (dx1*dy2 < dy1*dx2) return -1;
if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1;
if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) return +1;
return 0;
}
int intersect(struct line l1,
struct line l2)
{
return ((ccw(l1.p1,l1.p2,l2.p1)*ccw(l1.p1,l1.p2,l2.p2)) <=0) &&
((ccw(l2.p1,l2.p2,l1.p1)*ccw(l2.p1,l2.p2,l1.p2)) <=0);
}
|| = OR
&& = AND
(R. Sedgewick. Algoritmi in C++, ed. Addison-Wesley, 1993)
|
L'immagine mostra che due segmenti si intersecano se hanno (almeno) un punto in comune (e non devono necessariamente incrociarsi).
La funzione ccw dà una risposta alla fondamentale domanda se dati tre punti (p0 p1 p2) passando dal primo al secondo e dal secondo al terzo si gira in senso orario o antiorario.
La pendenza del tratto p0-p1 è dy1/dx1 mentre la pendenza del tratto p0-p2 è dy2/dx2; se dy2/dx2 > dy1/dx1 allora è necessario svoltare a sinistra per passare da p1 a p2, altrimenti a destra. Il resto si legge direttamente dal codice C.
I vari return della funzione ccw sono stati trasformati, in Lisp, in una serie di funzioni (if) una dentro l'altra, dove K è 0 (zero) se l'ultima condizione è falsa (nil).
INTSZ
;|
INTSZ.LSP
Copyright (C) 2006 Claudio Piccini. All rights reserved
www.cg-cad.com
Metodo per determinare se 2 segmenti si intersecano o meno
Basato su : Algoritmi in C++, Sedgewick (Addison-Wesley)
|;
(defun myerror (s)
(if (/= s "Function cancelled")
(princ (strcat "\nError: " s))
)
(ripVar)
(princ)
)
(defun salVar ()
(setq orto (getvar "orthomode"))
(setq snapp (getvar "osmode"))
(setq snm (getvar "snapmode"))
(setq piano (getvar "clayer"))
)
(defun ripVar ()
(command "_redraw")
(setvar "cmdecho" 1)
(setvar "osmode" snapp)
(setvar "snapmode" snm)
(setvar "orthomode" orto)
(setvar "clayer" piano)
(setvar "cecolor" "BYLAYER")
(setq *error* olderr)
(princ)
)
(defun ccw ( a b c / dx1 dx2 dy1 dy2 )
(setq dx1 (- (car b)(car a)))
(setq dy1 (- (cadr b)(cadr a)))
(setq dx2 (- (car c)(car a)))
(setq dy2 (- (cadr c)(cadr a)))
(if (> (* dx1 dy2)(* dy1 dx2))(setq K 1)
(if (< (* dx1 dy2)(* dy1 dx2))(setq K -1)
(if (or (< (* dx1 dx2) 0)(< (* dy1 dy2) 0))(setq K -1)
(if (< (+ (* dx1 dx1)(* dy1 dy1))(+ (* dx2 dx2)(* dy2 dy2)))(setq K 1)
(setq K 0)
)
)
)
)
)
(defun intersezione ( l1p1 l1p2 l2p1 l2p2 )
(if
(and
(<= (* (ccw l1p1 l1p2 l2p1)(ccw l1p1 l1p2 l2p2)) 0)
(<= (* (ccw l2p1 l2p2 l1p1)(ccw l2p1 l2p2 l1p2)) 0)
)
(setq K 1) ; si intersezione
(setq K 0) ; no intersezione
)
)
(defun C:INTSZ (/ olderr snapp snm orto piano
p1 p2 ; punti estremi finestra di selezione
s1 ; insieme di selezione non vuoto
nEnt ; numero di elementi di s1
e l ; contatori di entita'
lsp ; lista di punti
K ; test di intersezione
)
(setq olderr *error* *error* myerror)
(setvar "cmdecho" 0)
(salVar)
(setq K 0) ; no intersezione
(command "osnap" "_non")
(setq p1 (getpoint "\n Seleziona i 2 segmenti con una finestra: "))
(initget (+ 1 32))
(setq p2 (getcorner p1 "\n Secondo punto della finestra: "))
(setq s1 (ssget "_C" p1 p2)) ; intercetta le entita'
(if (/= s1 nil)
(progn
(setq nEnt (sslength s1))
(setq e 0) ; conta le entita'
(setq l 0) ; conta le linee
(repeat nEnt
(setq ent (entget (ssname s1 e)))
(if (= "LINE" (cdr (assoc 0 ent)))
(progn
(setq l (+ l 1))
(if (<= l 2)
(progn
;|
aggiunge alla lista LSP le coordinate
dei punti estremi delle prime 2 linee della selezione
|;
(setq lsp (append lsp (list (cdr (assoc 10 ent)))))
(setq lsp (append lsp (list (cdr (assoc 11 ent)))))
)
)
)
)
(setq e (+ e 1))
)
)
(alert "Non e' stata selezionata nessuna entita'")
)
(intersezione (nth 0 lsp)(nth 1 lsp)(nth 2 lsp)(nth 3 lsp))
(if (= K 1)(princ "\n OK")(princ "\n NO"))
(ripVar)
)
;;;eof
|
Lisp »Tips 'n Tricks
Ultimo Aggiornamento_Last Update: 28 Marzo 2006
|
|
