Fuccaro
You may find some use for these functions that were in my collection from the forums.
;|Here are a set of LISP functions that do the job for old-style polylines
(I did it a few years ago and it may not be perfect LISP). You will have
to modify the function PLINEVERTICES to be able to use new-style plines.
INPOLY does not calculate bulges, but gives correct results even for
self-intersecting plines. I used the fact that the sum of angles from
the checkpoint to all vertices is equal 0 (360) degrees if the
checkpoint is inside and any othre value if it is outside. The FUZZY
value is to avoid rounding errors.
Code is free to use by anybody
Tom
|;
(setq imr_fuzzy 0.0001)
(defun inpoly (pt en /)
(if (equal 0.0 (anglesum pt (plinevertices en)) imr_fuzzy)
nil
t
)
)
(defun c:inpoly (/ pt en)
(setvar "cmdecho" 0)
(if (= "POLYLINE" (cdr (assoc 0 (entget (setq en (car (entsel)))))))
(while (setq pt (getpoint "\npoint to check: "))
(if (inpoly pt en)
(princ "INSIDE polyline!")
(princ "OUTSIDE polyline!")
)
)
)
(prin1)
)
(defun angd (scheitel p1 p2) (r2d (angr scheitel p1 p2)))
(defun r2d (winkel) (* (/ (float winkel) pi) 180.0))
(defun angr (scheitel p1 p2 / alf bet)
(setq bet (angle scheitel p1)
alf (angle scheitel p2)
alf (- alf bet)
)
(if (< alf 0)
(setq alf (+ (* 2 pi) alf))
)
alf
)
(defun plistisplanar (plist / isplanar)
(setq isplanar t
pl (cddr plist)
)
(while (and isplanar (< 3 (length plist)))
(while (< 1 (length pl))
(if (inters (car plist) (cadr plist) (car pl) (cadr pl))
(setq isplanar nil
pl nil
plist nil
)
)
(setq pl (cdr pl))
)
(if isplanar
(setq plist (cdr plist)
pl (cddr plist)
)
(setq plist nil)
)
)
isplanar
)
(defun anglesum (pt plist / as p1 p2 an1 an2 an)
(setq as 0.0
stp (car plist)
count 1
)
(while (< 1 (length plist))
(setq p1 (car plist)
p2 (cadr plist)
plist (cdr plist)
an (angd pt p1 p2)
an (if (< 180.0 an)
(- an 360.0)
an
)
as (+ as an)
)
(setq count (1+ count))
)
(setq
an (angd pt p2 stp)
an (if (< 180.0 an)
(- an 360.0)
an
)
)
(+ as an)
)
(defun plinevertices (en / el vl)
(while (= "VERTEX"
(cdr (assoc 0
(setq el (entget (setq en (entnext
en
)
)
)
)
)
)
)
(setq vl (cons (cdr (assoc 10 el)) vl))
)
(if (= (car vl) (car (reverse vl)))
(reverse (cdr (reverse vl)))
vl
)
)
;|Re: Point inside the perimeter of a closed polyline ?
Subject: Re: Point inside the perimeter of a closed polyline ?
From: "Michael Doerr" <mdoerr@cebacus.de>
Date: Tue, 14 Dec 1999 06:47:25 +0000
Newsgroups: autodesk.autocad.customization
Hi Dominique,
the following code calculates the sum of the angles from a given point to
the points of the polyline and decides wether the point is inside or outside
in that way. 'PointInQuestion' means the point which has to be tested and
'Point_List' is the list of Points which represent the polyline. If the
function returns 'T' the given point is inside your polyline.
Greetings, Michael|;
(defun punktinpolylinie (pointinquestion
point_list
/
)
(if (equal 0.0 (pipwinkelsumme pointinquestion point_list) 0.0001)
nil
t
)
)
(defun pipwinkelsumme (pointinquestion point_list
/ count p1
p2 scheitel winkeleins
winkelzwei
)
(setq winkeleins 0.0
scheitel (car point_list)
count 1
)
(while (< 1 (length point_list))
(setq p1 (car point_list)
p2 (cadr point_list)
point_list (cdr point_list)
winkelzwei (pipwinkelhilfe pointinquestion p1 p2)
winkelzwei (if (< 180.0 winkelzwei)
(- winkelzwei 360.0)
winkelzwei
)
winkeleins (+ winkeleins winkelzwei)
)
(setq count (1+ count))
)
(setq winkelzwei (pipwinkelhilfe pointinquestion p2 scheitel)
winkelzwei (if (< 180.0 winkelzwei)
(- winkelzwei 360.0)
winkelzwei
)
)
(+ winkeleins winkelzwei)
)
(defun pipwinkelhilfe (pointinquestion p1 p2 / alpha beta)
(setq beta (angle pointinquestion p1)
alpha (angle pointinquestion p2)
alpha (- alpha beta)
)
(if (< alpha 0)
(setq alpha (+ (* 2 pi) alpha))
)
(* (/ (float alpha) pi) 180.0)
)
;; Updated (03-07-03)
;; Given:
;;-------------------------------------------------------
;; Function to find or create an invisible ray VLA-Object
;; on Layer "0" an to create a global symbol $cv_ray.
;; It will leave the Ray object in the drawing to save time.
(defun @cv_ray ( / e ss)
(if (setq ss (ssget "X" '((0 . "RAY")(8 . "0")(60 . 1))))
(setq $cv_ray (vlax-ename->vla-object (ssname ss 0)))
(setq $cv_ray
(entmakex
(list
'(0 . "RAY")'(100 . "AcDbEntity")'(100 . "AcDbRay")
'(8 . "0")'(60 . 1)'(10 0.0 0.0 0.0)'(11 1.0 0.0 0.0)
)
)
$cv_ray (vlax-ename->vla-object $cv_ray)
)
)
)
;; And:
;;-------------------------------------------------
;; Function originated by Ken Alexander (03-05-03)
;; that is 10X faster than my @cv_parse_list,
;; to group data into triplets.
;; Thanks, Ken!
;;
(defun @cv_triple_up (old / new)
(while
(setq new (cons (list (car old)(cadr old)(caddr old)) new)
old (cdddr old)
)
)
(reverse new)
)
;; And:
;;-------------------------------------------------------------------
;; Function to determine if a point <PIQ> is inside a closed polyline
;; based on the number of intersections found between a ray whose
;; basepoint is the PIQ, and that PIQ is not one of the intersection
;; points.
;; Arguments:
;; PIQ = 3D Point in WCS
;; Outer = Outer Polyline VLA-Object
;; Returns:
;; either T (inside) or nil (on or outside)
(defun @cv_inside (PIQ Outer / Points)
(vl-load-com)
(and
(> (vl-list-length PIQ) 1)
(vl-every 'numberp PIQ)
(= (type Outer) 'VLA-Object)
(vlax-property-available-p Outer 'Closed)
(= (vla-get-closed Outer) :vlax-true)
(or $cv_ray (@cv_ray))
(or (vlax-put $cv_ray "Basepoint" PIQ) T)
(setq Points (vlax-invoke Outer "IntersectWith" $cv_ray acExtendNone))
(setq Points (@cv_triple_up Points))
(= (rem (length Points) 2) 1)
(not (equal PIQ (vlax-curve-getclosestpointto Object PIQ) 1e-11))
)
)
;; Then:
;; ... define your point and Outer object ...
(setq Inside (@cv_inside PIQ Outer))
Re: Point inside the perimeter of a closed polyline ?
Subject: Re: Point inside the perimeter of a closed polyline ?
From: kboutora@francemel.com (Kamal Boutora)
Date: Thu, 16 Dec 1999 15:40:45 +0000
Newsgroups: autodesk.autocad.customization
In article <838ik5$kje17@adesknews2.autodesk.com>,
not.robertb@mwengineers.com says...
> Could you post code, or a link to some?
>
From the faq of comp.graphics.algorithms (a very interesting faq that
every programmer should have IMHO).
you can look at the latest HTML version at either of these two sites:
http://www.exaflop.org/docs/cgafaq
http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/algorithms-
faq/faq.html
The code below is from Wm. Randolph Franklin <wrf@ecse.rpi.edu>
int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++) {
if ((((yp[i]<=y) && (y<yp[j])) ||
((yp[j]<=y) && (y<yp[i]))) &&
(x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
c = !c;
}
return c;
}
Subject: Re: About Polyline
Author: Horst Kraemer <horst.kraemer@snafu.de>
Date Posted: Oct 2 1999 9:15:21:000AM
On Sat, 02 Oct 1999 09:34:42 GMT, philipma@ms5.hinet.net (Philip Ma)
wrote:
> Hi,
>
> Maybe the questions are stupid, but I need the answers. Thank you in
> advance!
>
> There are some questions about 2-D closed polyline as following:
> 1. How to know a polyline is crisscross (intersection itself) ?
> 2. If the polyline is not crisscross, how to know the polyline is
> clockwise or counterclockwise?
> 3. If the polyline is not crisscross, how to know a point is inside,
> outside or on the polyline?
> 4. If the polyline is not crisscross, how to know the area of the
> polyline?
In the order of ascending computational cost:
If
P0=(x0,y0),P1=(x1,y1),....,PN=(xN,yN)=P0
is your closed polygon consisting of a sequence of N distinct points
P1,..,PN then the _oriented_ area is 1/2 of the sum of
x_i*y_{i+1}-y_i*x_{i+1}
for i from 0 to N-1, i.e. for all adjacent pairs of vertices of the
closed polygon. This area may be positive or negative, according to
the orientation of the sequence relative to the coordinate system. In
any case its magnitude is the surface area.
If the coordinate system is oriented in a way that turning the
positive x-axis counterclockwise by 90deg will turn it into the
positive y-axis, then a positive area means that the polygon is
oriented counterclockwise. In fact "positive" doesn't mean
"counterclockwise". It just means "the same orientation as the
coordinate system". In fact in 2D geometry "clockwise" has no meaning.
If you look at a plane from the other side "clockwise" will turn into
"counterclockwise". You have to define additionally which side of the
plane is the "upside" and this definition can only be done by "looking
at it" from 3D. (Sorry for the side-step...)
There are many methods to test if a point of the plane is inside a
simple polygon. None of them is technical trivial.
The method I prefer is this one. It has been published by the german
mathematician Ahlemeyer, although he may not be the first who invented
it. Let's assume for simplicity that the point to be tested is the
origin.
Divide the plane into 3 regions.
S0 consists only of the origin (0,0)
S+ is the "upper sector", consisting of all points with y>0 + all
points (x,0) with x>0
S- is the "lower sector", consisting of all points with y<0 + all
points (x,0) with x<0.
Every point of the plane belongs to exactly one sector.
Initialize a counter with 0.
Now make a round trip as before through all pairs of vertex points. If
any vertex is in S0 then (0,0) is a a vertex of the polygon and you
make your decision depending on the detail if an edge/vertex is
"inside" or "outside" the polygon.
Otherwise
if two adjacent vertices (x_i,y_i),(x_{i+1},y_{i+1}) are in
the same sector, do nothing.
else if they are in two distinct sectors then calculate
d = x_i*y_{i+1) - y_i*x_{i+1)
if d=0 then the origin is situated on the edge and you
make your decision
else if d>0 then add 1 to the counter
else (d<0) subtract 1 from the counter
If no final decision could be taken in the middle then the point is
outside if the counter is ZERO, otherwise the point is outside. (Then
the counter is either 2 or -2).
Testing if a polygon is simple (not crossing itself) is probably the
most difficult task in terms of computation time. The crude and
straightforward approach is to test for each pair of edges if they
intersect or not. This will only be a problem for _very_ many
vertices.
Some time ago we hat a long thread about this problem in
sci.math.research, but nobody could come up with a _working_ algorithm
which was not O(n^2), i.e. which did need significantly less than
n^2/2 distinct tests. There were a lot of "convincing" proposals but
none of them was waterproof.
Regards
Horst