Author Topic: Point Containment Test: Convex and Concave Polygons  (Read 20635 times)

0 Members and 1 Guest are viewing this topic.

zoltan

  • Newt
  • Posts: 188
Re: Point Containment Test: Convex and Concave Polygons
« Reply #15 on: November 24, 2005, 09:25:49 AM »
My original notion for this was to process a list of points and not have to get or create any real objects.  Kerry, your solution with the rays is interesting because it is essentially the same as my code where the ray is one half of my pntXs to pntXe test line.  I could have tested a line from PNT to pntXs  or pntXe and it would always be odd if the point was inside and even if the point was outside.  But you would still come upon my current problem if your ray crossed a vertex.

 Joe, I will give your code by Luis and John a good looking-at.  Since ultimately when I use this function I will be getting the points by exploding a temporary copy of a REGION into lines and then erasing the lines, if your code will opperate on the region directly (edit: nevermind, it won't), it would be a better solution.  The interesting thing about that function is that it almost behaves correctly when the curve is self-intersecting.  I finds all of the insides but thinks that some of the nested outside are inside also. It's definatelly a keeper, though.

Take a covex, closed polyline with alot of points and hatch it with an associative hatch by selecting the object instead of picking a point.  Then twist it up by moving the vertices around.  The hatch will update and should always be valid by alternating inside/outside for any nested shapes.  Joe's function finds most of these correctly.

I am still going to work on my quirky code above to have a nice library function that is universal. The method it uses is probably pretty standard, since it is in a book about computer graphics algorithms.  So let me explain my ugly code a little bit:

The function asks for PNT as a point defined by a List of two or three Reals and lstPOINTS as a list of lists of two or three reals, kinda like the GetPolylinePoints function returns.  It also asks for a FUZZ which is given to the Equal function as the fuzz factor.
The first for conditions determin if the point is outside the min-max bounding box in each direction and it also establishes dXmin and dxMax as the min and max X coordinates for my test line. d stands for Decimal and it lets me know that they are Reals. (I'm Hungarian so Hungarian Notation holds a special place in my heart, and it's very well suited for LiSP).
If none of those conditions are true then we go on to the step 2 as described in the book.  I set up pntXs and pntXe as the start and end points of my test line.  I will eventually re-write this to eliminate the Inters function and test the intsection of an infinite line with the segments, but that code is about half done.  here I also add the first element in the list of points to the end of the list to make it a loop, so when I step through the length of the original list with the (Nth cnt ...) and (Nth (1+ cnt) ...) the last point will be the same as the fist to close the polygon.
Now I loop through the length of the original list (1- (Length ...)) and test every segment to see if it intersects my X test line.  If it does I Cons it to lstTest. Then I strip out all of the x coordinates and arrange them in ascending order by MapCar-ing the Car function thru the list and giving it to VL-Sort.
The next portion where I strip the duplicates from the front and end of the list is a result of my BFI coding and should be ignored before it embarrasses me!
Next I make a list of pairs of points, lstPairs by Constructins a List of the Car and Cadr of the list and dropping the first two elements with Cddr and looping until the original list is nil.  I only do this to make MapCar-ing through the list to test the pairs easier then looping the elements of the first list two at a time.
The list is backwards, so I reverse it.  The list looks like this ((x1 x2) (x3 x4) ...).  The next Cond determines the result.
If the Car of PNT Equals either the Car of one of the elements of lstPairs or the Cadr of one of the elements, then the test point is on the boundary of the polygon.
If the Car of PNT false between on of the pair so that x1 < xt > x2, than the point is on the inside.
Otherwise, the last T condition returns nil and the point is on the outside.
« Last Edit: November 24, 2005, 10:20:00 AM by zoltan »

LE

  • Guest
Re: Point Containment Test: Convex and Concave Polygons
« Reply #16 on: November 24, 2005, 10:15:35 AM »
Thinking further on this, I'd be interested in seeing a pure math based solution not requiring interaction with the database < as such>
... so we wouldn't want to consider bulges .. yes ?

I do not think it could be possible to do it in plain auto/visual lisp, I might be wrong, but I have tried before.... and no luck.

In my new functions for gbpoly16.arx I am including "PtInsPol" that I am using to find if a point is inside of a polyline [any shape]... the idea is to use it as a better alternative to highlight polylines when passing the cursor on top of them, but to work with the ones that are in the center of other ones and not required to even touch the polylines.....

zoltan

  • Newt
  • Posts: 188
Re: Point Containment Test: Convex and Concave Polygons
« Reply #17 on: November 24, 2005, 10:24:54 AM »
It is possible for polygons with streight line edges.  Polylines with arcs and splines would take some nasty mathematics that probably should not be done in lisp.

zoltan

  • Newt
  • Posts: 188
Re: Point Containment Test: Convex and Concave Polygons
« Reply #18 on: November 24, 2005, 10:56:37 AM »
ok...Here is a Kludgy solution:
Code: [Select]
(If (SetQ pntTest (Inters (Nth cnt lstPOINTS) (Nth (1+ cnt) lstPOINTS) pntXs pntXe) ) ;segment intersects test line
     (Cond
      ((And (Equal pntTest (Nth cnt lstPOINTS) FUZZ)
            (Or (And (> (Cadr (Nth (1+ cnt) lstPOINTS)) (Cadr pntTest))
                     (< (Cadr (Nth (1- cnt) lstPOINTS)) (Cadr pntTest))
                )
                (And (> (Cadr (Nth (1+ cnt) lstPOINTS)) (Cadr pntTest))
                     (< (Cadr (Nth (1- cnt) lstPOINTS)) (Cadr pntTest))
                )
            )
            (Not bVertHit )
       )
       (SetQ bVertHit T )
      )
      ((And (Equal pntTest (Nth (1+ cnt) lstPOINTS) FUZZ)
            (Or (And (> (Cadr (Nth cnt lstPOINTS)) (Cadr pntTest))
                     (< (Cadr (Nth (+ cnt 2) lstPOINTS)) (Cadr pntTest))
                )
                (And (> (Cadr (Nth cnt lstPOINTS)) (Cadr pntTest))
                     (< (Cadr (Nth (+ cnt 2) lstPOINTS)) (Cadr pntTest))
                )
            )
            (Not bVertHit )
       )
       (SetQ bVertHit T )
      )
      (T
       (SetQ lstTest (Cons pntTest lstTest) )
       (SetQ bVertHit nil )
      )
     )
    )

This is going on the idea that if the two segments are on the same side of the test line then the vertex has to represent to points.  If the intersection point is one of the vertices, it sets a flag and drops the point if the two vertices are on oposite sides of the test line. If the flag is already set when it hits the vetex of the next segment, it does not drop the point and resets the flag.

BFI: dumb, but simple.  Now I need to see how bad it will puke if the segment is horizontal and colinear with the test line.

Joe Burke

  • Guest
Re: Point Containment Test: Convex and Concave Polygons
« Reply #19 on: November 26, 2005, 07:49:26 AM »
zoltan,

Surely I don't understand everything you said.   :-)

I'll just underline the fact John's comments mention, "It will not work well with self-intersecting (overlapping) bulged polyline segments."

MP

  • Seagull
  • Posts: 17750
  • Have thousands of dwgs to process? Contact me.
Re: Point Containment Test: Convex and Concave Polygons
« Reply #20 on: November 26, 2005, 01:37:29 PM »
I can't contribute anything useful to this thread, but as first posts go this is quite an entrance!

Welcome to the swamp Zoltan.

:)
Engineering Technologist CAD Automation Practitioner
Automation ▸ Design ▸ Drafting ▸ Document Control ▸ Client
cadanalyst@gmail.com http://cadanalyst.slack.com http://linkedin.com/in/cadanalyst

chlh_jd

  • Guest
Re: Point Containment Test: Convex and Concave Polygons
« Reply #21 on: March 27, 2011, 04:56:18 PM »
hi All , just see this site .
here's my method .
Code: [Select]
(defun pt-in-region (pt pts Acc / ss-member-pts pt1 ptn p at)
  ;;judge a point is in the 2D polygon , polygon given with vetexs .
  ;;by GSLS(SS) 2011.03.28
  ;;return 0 at polygon, 1 in it, -1 out it .
  (defun ss-member-pts (pt ptl acc / is_go i len a b)
    (setq is_go T i 0  len(length ptl))
    (while (and is_go (< i len))
      (setq a(car ptl)ptl(cdr ptl)i(1+ i))
      (if (and a (equal a pt acc))
(setq is_go nil  b (cons a ptl)))))
  (setq pt1(list (+ (car (apply (function mapcar) (cons (function max) pts)))(abs acc)(abs acc))(cadr pt))) 
  (mapcar(function(lambda (x y)
    (if(setq p (inters pt pt1 x y T))
      (progn (if(equal (+(distance pt x)(distance pt y))(distance x y)acc)(setq at T))
(if(not (ss-member-pts p pts acc)) (setq ptn (cons p ptn)))))))
(cons (last pts) pts) pts)
  (cond (at 0)
((and (not at) ptn)
(if (= (rem (length ptn) 2) 1)
   1  -1 ))
(t -1)
  )
)
;;
(defun c:test (/ ss-assoc pts pt is)
  (defun ss-assoc (a lst / b lst2)
    (while (setq b (assoc a lst))
      (setq lst (cdr (member b lst))
    lst2 (cons (cdr b) lst2)
      ))
    (reverse lst2)
  )
  (setq pts (ss-assoc 10 (entget (car (entsel "Select a polyline :")))))
  (while (setq pt (getpoint))
    (setq is (pt-in-region pt pts 1e-8))
    (cond ((= is -1) (alert "Out ."))
  ((= is 0) (alert "At ."))
  ((= is 1) (alert "In ."))
  )   
  )
  (princ)
)

efernal

  • Bull Frog
  • Posts: 203
e.fernal

chlh_jd

  • Guest
Re: Point Containment Test: Convex and Concave Polygons
« Reply #23 on: March 28, 2011, 02:24:20 AM »
Thanks efernal ,
it's new
Code: [Select]
(defun pt-in-polygon (pt pts Eps / minpt maxpt pt1 ptn p at)
  ;;judge a point is in the 2D polygon , polygon given with vetexs .
  ;;by GSLS(SS) 2011.03.28
  ;;return 0 at polygon, 1 in it, -1 out it .
  (setq minpt (apply (function mapcar)(cons(function min)pts))
maxpt (apply (function mapcar)(cons(function max)pts))
Eps (abs Eps))
  (if (or(<(cadr pt)(- (cadr minpt)Eps))(<(+(cadr maxpt)Eps)(cadr pt))
(< (car pt)(-(car minpt)Eps))(<(+(car maxpt)Eps)(car pt)))
    -1
    (progn
      (setq pt1(list(+(car maxpt)Eps Eps)(cadr pt)))
      (mapcar(function(lambda (x y)
    (if(setq p (inters pt pt1 x y T))
      (progn (if(equal (+(distance pt x)(distance pt y))(distance x y)Eps)(setq at T))
(if(not (ss-member-pts p pts Eps)) (setq ptn (cons p ptn)))))))
(cons (last pts) pts) pts)
      (cond(at 0)((and (not at) ptn)(if (= (rem (length ptn) 2) 1)1 -1))(t -1))))
)

KWL

  • Guest
Re: Point Containment Test: Convex and Concave Polygons
« Reply #24 on: March 28, 2011, 03:22:06 AM »

chlh_jd

  • Guest
Re: Point Containment Test: Convex and Concave Polygons
« Reply #25 on: March 28, 2011, 03:38:23 AM »
Thanks KWL .
Another method
Code: [Select]
;;;it has a problem : if a point at the given polygon , it perhap return T or NIL .
(defun isPtinPM (pt pts)
  ;; by 狂刀  Handed Knife
  (equal  PI (abs (apply'+(mapcar'(lambda (x y) (rem (- (angle pt x) (angle pt y)) PI))
(cons (last pts) pts)
pts)))1e-3)
)
(defun c:test (/ ss-assoc pts pt is)
  (defun ss-assoc (a lst / b lst2)
    (while (setq b (assoc a lst))
      (setq lst (cdr (member b lst))
    lst2 (cons (cdr b) lst2)
      ))
    (reverse lst2)
  )
  (setq pts (ss-assoc 10 (entget (car (entsel "Select a polyline :")))))
  (while (setq pt (getpoint))
    (if (isptinpm pt pts)
      (alert "In .")
      (alert "Out .")
      ))   
  (princ)
)


chlh_jd

  • Guest
Re: Point Containment Test: Convex and Concave Polygons
« Reply #26 on: March 28, 2011, 03:54:12 AM »
hi All , a new version .
Code: [Select]
(defun isPtinPM (pt pts eps / is at)
  ;; by 狂刀  Handed Knife
  ;; Edit by GSLS(SS) 2011.03.28
  ;; Solved the problem : if a point at the given polygon , it perhap return T or NIL .
  (setq is(equal PI(abs(apply(function +)(mapcar(function(lambda (x y / a)    
       (setq a (rem (- (angle pt x) (angle pt y)) PI))
       (if (equal a 0.0 eps)(setq at T))a))
   (cons (last pts) pts) pts))) eps))
  (cond (at 0)(is 1)(T -1))
)
(defun c:test (/ pts pt is)
  (setq pts (ss-assoc 10 (entget (car (entsel "Select a polyline :")))))
  (while (setq pt (getpoint "Select point:>"))
    (setq is (isPtinPM pt pts 1e-8))
    (cond ((= is -1) (alert "Out ."))
  ((= is 0) (alert "At ."))
  ((= is 1) (alert "In ."))
    )
  )
  (princ)
)

Q1241274614

  • Guest
Re: Point Containment Test: Convex and Concave Polygons
« Reply #27 on: March 24, 2014, 08:25:34 AM »
ok
« Last Edit: March 24, 2014, 08:31:53 AM by Q1241274614 »