Author Topic: Fasted way to find a closed polyline by point inside  (Read 7278 times)

0 Members and 1 Guest are viewing this topic.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1025
  • Marco
Re: Fasted way to find a closed polyline by point inside
« Reply #15 on: October 06, 2014, 10:00:00 AM »
I have edited many functions to work also with "non closed" LWPOLYLINE see "(70 . 1)",
these are the results, all comments are well accepted, attach files and test DWG:

test_Stefan     > 1 error
selcllwbypt+lay > 4 errors
Code: [Select]
    (GILE_TEST INTERNALPOINT LAYERNAME)...........1186 / 12.27 <fastest>
    (TEST_STEFAN INTERNALPOINT LAYERNAME).........1373 / 10.6
    (POLYFROMINSIDEPOINT_KGA INTERNALPOINT).......5273 / 2.76
    (POLYFROMINSIDEPOINT INTERNALPOINT)...........5632 / 2.58
    (SELCLLWBYPT+LAY INTERNALPOINT LAYER...).....14555 / 1 <slowest>

    (TEST_STEFAN INTERNALPOINT LAYERNAME)........1810 / 5.83 <fastest>
    (GILE_TEST INTERNALPOINT LAYERNAME)..........2137 / 4.93
    (POLYFROMINSIDEPOINT_KGA INTERNALPOINT)......6568 / 1.61
    (POLYFROMINSIDEPOINT INTERNALPOINT).........10545 / 1 <slowest>

    (GILE_TEST INTERNALPOINT LAYERNAME).........1185 / 5.45 <fastest>
    (TEST_STEFAN INTERNALPOINT LAYERNAME).......1373 / 4.7
    (POLYFROMINSIDEPOINT_KGA INTERNALPOINT).....6240 / 1.03
    (POLYFROMINSIDEPOINT INTERNALPOINT).........6458 / 1 <slowest>

roy_043

  • Water Moccasin
  • Posts: 1747
  • BricsCAD 18
Re: Fasted way to find a closed polyline by point inside
« Reply #16 on: October 06, 2014, 10:51:32 AM »
I don't know the context you want to use the code in, but I would not focus on speed just yet. All code examples have one or more issues:
- Bulges are not taken into account.
- Polylines may not be bisected by other polylines.
- The polyline must have an edge between the point and extmin.
- The polyline must be rectangular.
...

ribarm

  • Water Moccasin
  • Posts: 2226
  • Marko Ribar, architect
Re: Fasted way to find a closed polyline by point inside
« Reply #17 on: October 06, 2014, 11:28:29 AM »
I don't know the context you want to use the code in, but I would not focus on speed just yet. All code examples have one or more issues:
- Bulges are not taken into account.
- Polylines may not be bisected by other polylines.
- The polyline must have an edge between the point and extmin.
- The polyline must be rectangular.
...

All these issues are taken into consideration with my code... Maybe that's why it's the slowest... Or I missed something in OP's request?
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1025
  • Marco
Re: Fasted way to find a closed polyline by point inside
« Reply #18 on: October 06, 2014, 11:39:29 AM »
I don't know the context you want to use the code in, but I would not focus on speed just yet. All code examples have one or more issues:
- Bulges are not taken into account.
- Polylines may not be bisected by other polylines.
- The polyline must have an edge between the point and extmin.
- The polyline must be rectangular.
...
All these issues are taken into consideration with my code... Maybe that's why it's the slowest... Or I missed something in OP's request?
Marko did you seen my dwg?  There are 4 errors (selcllwbypt+lay > 4 errors)...

ribarm

  • Water Moccasin
  • Posts: 2226
  • Marko Ribar, architect
Re: Fasted way to find a closed polyline by point inside
« Reply #19 on: October 06, 2014, 12:22:50 PM »
Marko did you seen my dwg?  There are 4 errors (selcllwbypt+lay > 4 errors)...

Yes, the problem is fuzz factor... Change 1e-10 to 1e-4 and it'll work...

[EDIT] : I've updated code in my post... Test it now... [/EDIT]
« Last Edit: October 06, 2014, 12:38:39 PM by ribarm »
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

roy_043

  • Water Moccasin
  • Posts: 1747
  • BricsCAD 18
Re: Fasted way to find a closed polyline by point inside
« Reply #20 on: October 06, 2014, 02:52:47 PM »
All these issues are taken into consideration with my code... Maybe that's why it's the slowest... Or I missed something in OP's request?
I find that your code does not work if a polyline is bisected by another and if I click a point that is internal to the first and external to the second. Note: I use BricsCAD.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1025
  • Marco
Re: Fasted way to find a closed polyline by point inside
« Reply #21 on: October 06, 2014, 04:08:36 PM »
Marko did you seen my dwg?  There are 4 errors (selcllwbypt+lay > 4 errors)...

Yes, the problem is fuzz factor... Change 1e-10 to 1e-4 and it'll work...

[EDIT] : I've updated code in my post... Test it now... [/EDIT]
Ok, now is ok.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1025
  • Marco
Re: Fasted way to find a closed polyline by point inside
« Reply #22 on: October 06, 2014, 04:10:34 PM »
All these issues are taken into consideration with my code... Maybe that's why it's the slowest... Or I missed something in OP's request?
I find that your code does not work if a polyline is bisected by another and if I click a point that is internal to the first and external to the second. Note: I use BricsCAD.
For this i think Lee Mac and your KGA... are OK.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1025
  • Marco
Re: Fasted way to find a closed polyline by point inside
« Reply #23 on: October 06, 2014, 05:08:46 PM »
I don't know the context you want to use the code in, but I would not focus on speed just yet. All code examples have one or more issues:
- Bulges are not taken into account.
- Polylines may not be bisected by other polylines.
- The polyline must have an edge between the point and extmin.
- The polyline must be rectangular.
...
Sorry for the delay but I do not see my reply (about 5 hours ago) so I rewrite it:

The contest is my sample DWG:
ok - Bulges are not taken into account.
ok - Polylines may not be bisected by other polylines.
ok - The polyline must have an edge between the point and extmin.

No - The polyline must be rectangular.
Not true but many functions works in this situation.      If there is a function that satisfies all it is better...

Thanks

Lee Mac

  • Seagull
  • Posts: 12318
  • London, England
Re: Fasted way to find a closed polyline by point inside
« Reply #24 on: October 06, 2014, 05:22:33 PM »
The raycasting method has a fundamental flaw:
http://ww3.cad.de/foren/ubb/Forum145/HTML/000602.shtml#000008

A messy attempt to avoid such issues:

Code - Auto/Visual Lisp: [Select]
  1. (defun c:test ( / e p )
  2.     (if (setq p (getpoint "\nSpecify point: "))
  3.         (if (setq e (polyfrominsidepoint p))
  4.             (sssetfirst nil (ssadd e))
  5.             (princ "\nNo polyline found.")
  6.         )
  7.     )
  8.     (princ)
  9. )
  10. (defun polyfrominsidepoint ( p / e i r s )
  11.     (if
  12.         (setq i -1 s
  13.             (ssget "_X"
  14.                 (list '(0 . "LWPOLYLINE") '(-4 . "&=") '(70 . 1)
  15.                     (if (= 1 (getvar 'cvport))
  16.                         (cons 410 (getvar 'ctab))
  17.                        '(410 . "Model")
  18.                     )
  19.                 )
  20.             )
  21.         )
  22.         (while (and (null r) (setq e (ssname s (setq i (1+ i)))))
  23.             (if (pointinsidepoly-p p (vlax-ename->vla-object e))
  24.                 (setq r e)
  25.             )
  26.         )
  27.     )
  28.     r
  29. )
  30. (defun pointinsidepoly-p ( pnt obj )
  31.     (raycast
  32.         (vla-addray
  33.             (vla-objectidtoobject (vla-get-document obj) (vla-get-ownerid obj))
  34.             (vlax-3D-point pnt)
  35.             (vlax-3D-point (mapcar '+ pnt '(1.0 0.0 0.0)))
  36.         )
  37.         pnt obj (groupn (vlax-get obj 'coordinates) 2)
  38.     )
  39. )
  40. (defun raycast ( ray pnt obj vtx / lst )
  41.     (if (and (setq lst (groupn (vlax-invoke ray 'intersectwith obj acextendnone) 3))
  42.             (vl-some
  43.                '(lambda ( x )
  44.                     (or (vl-some '(lambda ( y ) (equal 0.0 (distance x y) 1e-8)) vtx)
  45.                         (equal 0.0
  46.                             (distance '(0.0 0.0 0.0)
  47.                                 (v^v (vlax-curve-getfirstderiv obj (vlax-curve-getparamatpoint obj x))
  48.                                      (mapcar '- x pnt)
  49.                                 )
  50.                             )
  51.                             1e-8
  52.                         )
  53.                     )
  54.                 )
  55.                 lst
  56.             )
  57.             (< (angle '(0.0 0.0 0.0) (vlax-get ray 'directionvector)) 6)
  58.         )
  59.         (progn
  60.             (vlax-invoke ray 'rotate pnt 0.17)
  61.             (raycast ray pnt obj vtx)
  62.         )
  63.         (progn
  64.             (vla-delete ray)
  65.             (= 1 (logand 1 (length lst)))
  66.         )
  67.     )      
  68. )
  69. (defun groupn ( l n / x r )
  70.     (repeat (/ (length l) n)
  71.         (repeat n
  72.             (setq x (cons (car l) x)
  73.                   l (cdr l)
  74.             )
  75.         )
  76.         (setq r (cons (reverse x) r)
  77.               x nil
  78.         )
  79.     )
  80.     (reverse r)
  81. )
  82. (defun v^v ( u v )
  83.     (list
  84.         (- (* (cadr u) (caddr v)) (* (cadr v) (caddr u)))
  85.         (- (* (car  v) (caddr u)) (* (car  u) (caddr v)))
  86.         (- (* (car  u) (cadr  v)) (* (car  v) (cadr  u)))
  87.     )
  88. )

Don't expect it to be fast though!

ribarm

  • Water Moccasin
  • Posts: 2226
  • Marko Ribar, architect
Re: Fasted way to find a closed polyline by point inside
« Reply #25 on: October 07, 2014, 07:05:50 AM »
Here is my newest version... It's much more simple than previous, and it satisfies all previously mentioned issues... And it's fast enough - for my standards...

Code - Auto/Visual Lisp: [Select]
  1. (defun selcllwbypt+lay-2 (pt         layer      /          insidep
  2.                           el         ss         lw         i
  3.                           lwe        e
  4.                          )
  5.  
  6.  
  7.   ;;======================================================================;;
  8.   ;;    DETERMINING IF A POINT LIES ON THE INTERIOR OF A CLOSED ENTITY      ;;
  9.   ;;======================================================================;;
  10.  
  11.   ;;  Idea was stoled from Eugeny Kalney
  12.   ;;  http://www.k-prof.com.ru/
  13.   ;;  written by Fatty The Old Horse
  14.   ;;  9/29/05 edited: 9/30/05
  15.  
  16.   (defun insidep (pt entn / big flag obj1 obj2 obj3 p1 p2 small)
  17.     (if (and pt entn)
  18.       (progn
  19.         (setq obj1 (vlax-ename->vla-object entn))
  20.         (setq obj2 (car (vlax-invoke obj1 'Offset 0.001))
  21.               obj3 (car (vlax-invoke obj1 'Offset -0.001))
  22.         )
  23.         (if (> (vla-get-area obj2) (vla-get-area obj3))
  24.           (progn
  25.             (set 'big obj2)
  26.             (set 'small obj3)
  27.           )
  28.           (progn
  29.             (set 'big obj3)
  30.             (set 'small obj2)
  31.           )
  32.         )
  33.         (setq p1 (vlax-curve-getClosestPointTo big pt)
  34.               p2 (vlax-curve-getClosestPointTo small pt)
  35.         )
  36.         (if (> (distance pt p1) (distance pt p2))
  37.           (setq flag T)
  38.           (setq flag nil)
  39.         )
  40.         (mapcar (function (lambda (x)
  41.                             (progn
  42.                               (vla-delete x)
  43.                               (vlax-release-object x)
  44.                             )
  45.                           )
  46.                 )
  47.                 (list big small)
  48.         )
  49.       )
  50.     )
  51.     flag
  52.   )
  53.  
  54.   (setq el (entlast))
  55.   (setq ss (ssget "_A"
  56.                   (list '(0 . "LWPOLYLINE")
  57.                         (cons 8 layer)
  58.                         '(-4 . "&=")
  59.                         '(70 . 1)
  60.                         (cons 410 (if (= 1 (getvar 'cvport)) (getvar 'ctab) "Model"))
  61.                   )
  62.            )
  63.   )
  64.   (command "_.SELECT" ss "")
  65.   (command "_.-BOUNDARY"     "_A"     "_B"     "_N"     "_P"
  66.            ""       "_I"     "_N"     ""       "_O"     "_P"
  67.            "_X"     pt       ""
  68.           )
  69.   (if (not (eq el (entlast)))
  70.     (progn
  71.       (setq lw (entlast))
  72.       (setq i -1)
  73.       (while (and (not e) (setq lwe (ssname ss (setq i (1+ i)))))
  74.         (if
  75.           (and
  76.             (vlax-invoke (vlax-ename->vla-object lw) 'intersectwith (vlax-ename->vla-object lwe) acextendnone)
  77.             (insidep pt lwe)
  78.           )
  79.           (setq e lwe)
  80.         )
  81.       )
  82.       (entdel (entlast))
  83.       (if e (sssetfirst nil (ssadd e)))
  84.     )
  85.   )
  86.   (princ)
  87. )
  88.  

Regards, M.R.
« Last Edit: October 25, 2014, 01:23:48 PM by ribarm »
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

roy_043

  • Water Moccasin
  • Posts: 1747
  • BricsCAD 18
Re: Fasted way to find a closed polyline by point inside
« Reply #26 on: October 07, 2014, 08:10:17 AM »
@ ribarm:
Your new function insidep creates two offset copies for every entity in ss. This must slow things down for large selection sets. Two other problems with this function are that the offset distance is hard-coded and that offset can create more than one new entity.

Another case to consider:
Two nested polylines without intersections and a point inside the biggest poyline only...

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1025
  • Marco
Re: Fasted way to find a closed polyline by point inside
« Reply #27 on: October 07, 2014, 08:29:26 AM »
Here is my newest version... It's much more simple than previous, and it satisfies all previously mentioned issues... And it's fast enough - for my standards...
...
Regards, M.R.
Tested on Bricscad V14: do not works. Later I will tet on AutoCAD.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1025
  • Marco
Re: Fasted way to find a closed polyline by point inside
« Reply #28 on: October 07, 2014, 08:33:49 AM »
A messy attempt to avoid such issues:
...
Don't expect it to be fast though!
Tested on Bricscad V15:
> test_Stefan do not works (?)
Code: [Select]
Elapsed milliseconds / relative speed for 2048 iteration(s):
    (GILE_TEST INTERNALPOINT LAYERNAME)...........1638 / 19.75 <fastest>
    (POLYFROMINSIDEPOINT INTERNALPOINT)...........6926 / 4.67
    (POLYFROMINSIDEPOINT_KGA INTERNALPOINT).......8580 / 3.77
    (POLYFROMINSIDEPOINT2 INTERNALPOINT).........13494 / 2.4
    (SELCLLWBYPT+LAY INTERNALPOINT LAYER...).....32355 / 1 <slowest>

Elapsed milliseconds / relative speed for 1024 iteration(s):
    (GILE_TEST INTERNALPOINT LAYERNAME).........1451 / 6.81 <fastest>
    (POLYFROMINSIDEPOINT INTERNALPOINT).........5382 / 1.83
    (POLYFROMINSIDEPOINT_KGA INTERNALPOINT).....7488 / 1.32
    (POLYFROMINSIDEPOINT2 INTERNALPOINT)........9875 / 1 <slowest>

Elapsed milliseconds / relative speed for 2048 iteration(s):
    (GILE_TEST INTERNALPOINT LAYERNAME)..........1825 / 11.39 <fastest>
    (POLYFROMINSIDEPOINT INTERNALPOINT).........12137 / 1.71
    (POLYFROMINSIDEPOINT_KGA INTERNALPOINT).....19641 / 1.06
    (POLYFROMINSIDEPOINT2 INTERNALPOINT)........20779 / 1 <slowest>
a little bit slower.

ribarm

  • Water Moccasin
  • Posts: 2226
  • Marko Ribar, architect
Re: Fasted way to find a closed polyline by point inside
« Reply #29 on: October 07, 2014, 08:44:17 AM »
@ ribarm:
Your new function insidep creates two offset copies for every entity in ss. This must slow things down for large selection sets. Two other problems with this function are that the offset distance is hard-coded and that offset can create more than one new entity.

Another case to consider:
Two nested polylines without intersections and a point inside the biggest poyline only...

Yes, it must slow things on large sel. set, but hard-coded offset value is small, so I don't think it may create more than 2 new lwpolylines... Look into OP's posted example *.dwg...

I've considered that case - updated code... Changed island detection to "_N" and chosen default ray casting method (+X)... Thanks for your remarks, Roy - they are wise...

M.R.
« Last Edit: October 07, 2014, 09:02:36 AM by ribarm »
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube