[弹指神通]：求復線內部一點的几何算法

舟自横

前段時間研究了一下几何算法則，發覺求復線內部點是有精確算法的。以前一直用offset和region的方法去判斷效率實在太差而且容易出錯。現借鑒前人的思路寫了一段程序求復線內部點復線可以包含弧線。。
思路:
  以點P為端點，向左方作射線L，由於多邊形是有界的，所以射線L的左端一定在多邊形外，考慮沿著L從無窮遠處開始自左向右移動，遇到和多邊形的第一個交點的時候，進入到了多邊形的內部，遇到第二個交點的時候，離開了多邊形，……所以很容易看出當L和多邊形的交點數目C是奇數的時候，P在多邊形內，是偶數的話P在多邊形外。
借此判斷點在復線的內部或者外部。
在復線上取一點（不要取節點）作為參考點，由該點的法向做一直線(xline)取得直線和復線的所有交點，如果交點只有兩個那么兩交點的中點一定在內部，如果交點超過2點那么取得最靠近參考點的前后各一點此兩點中必有一點和參考的中點在復線內部。
[PHP]
(defun hy_getptinpline(pol / ALISTP1 ANG BLISTP1 DEV1 INP
                       LISTP1 P1 P2 PA PB PO X XLINE Y old1);;取得復線中一點
  (setq old1 (getvar "osmode"))
  (setvar "osmode" 0)
  (setq p1 (vlax-curve-getpointatparam pol 1.5))
  (setq dev1 (vlax-curve-getfirstderiv pol 1.5))
  (setq ang (atan (* -1 (/ (car dev1) (cadr dev1)))))
  (setq p2 (polar  p1 ang 1))
  (setq xline (vla-addxline (vla-Get-ModelSpace(vla-Get-ActiveDocument (vlax-Get-Acad-Object)))
              (vlax-3D-Point (trans p1 1 0)) (vlax-3D-Point (trans p2 1 0))))
  (setq listp1 (hy_GetInters xline pol acExtendNone))
  (vla-delete xline)
  (setvar "osmode" old1)
  (if (> (length listp1) 2)
    (progn
  (setq alistp1 nil blistp1 nil)
  (foreach item (vl-remove p1 listp1) (if (or (equal 0
                                                     (abs (/ (- ang (angle p1 item)) pi))
                                                     1e-8)
                                              (equal 2
                                                     (abs (/ (- ang (angle p1 item)) pi))
                                                     1e-8))
                                             
                                        (setq alistp1 (cons item alistp1))
                                        (setq blistp1 (cons item blistp1))
                                        )
    )
  (setq pa (car(vl-sort alistp1 '(lambda(x y) (< (distance x p1) (distance y p1))))))
  (setq pb (car(vl-sort blistp1 '(lambda(x y) (< (distance x p1) (distance y p1))))))
  (if (= (hy_ptinoutofpline1
                             (setq po (mapcar '(lambda(x y) (/ (+ x y) 2))
                                     p1 pa))
                             pol) t)
                           (setq inp po)
    (setq inp (mapcar '(lambda(x y) (/ (+ x y) 2))
                                     p1 pb)
                         )
    )
  inp
  )
    (mapcar '(lambda(x y) (/ (+ x y) 2))
                                     (car listp1)
            (cadr listp1))
    )
  )
(defun hy_ptinoutofpline1(pt pol / DO LISTP1 P1 RAY old);pol must be vla object;;判斷點在復線段內部
(if (not (vlax-curve-getparamatpoint pol pt))
   (progn
  (setq old (getvar "osmode"))
  (setvar "osmode" 0)
  (setq p1 (vlax-curve-getpointatparam pol 1.5))
  (setq ray (vla-addray (vla-Get-ModelSpace(vla-Get-ActiveDocument (vlax-Get-Acad-Object)))
              (vlax-3D-Point (trans pt 1 0)) (vlax-3D-Point (trans p1 1 0))))
  (setq listp1 (hy_GetInters ray pol acExtendNone))
  (if (= 0 (rem (length listp1) 2)) (setq do nil) (setq do t))
  (vla-delete ray)
  (setvar "osmode" old)
  do
  )
   1
   )
  )
(defun hy_GetInters (Fst Nxt Mde / IntLst PntLst);;取得兩對象的所有交點
(cond ((= (type Fst) 'ENAME) (SETQ Fst (vlax-ename->vla-object Fst)))
       ((= (type Fst) 'VLA-OBJECT) (SETQ Fst Fst))
       (t (setq olderror *error*)))
(cond ((= (type Nxt) 'ENAME) (SETQ Nxt (vlax-ename->vla-object Nxt)))
       ((= (type Nxt) 'VLA-OBJECT) (SETQ Nxt Nxt))
       (t (setq olderror *error*)))
(setq IntLst (vlax-invoke Fst 'IntersectWith Nxt Mde))
(cond
  (IntLst
   (repeat (/ (length IntLst) 3)
    (setq PntLst (cons
                  (list
                   (car IntLst)
                   (cadr IntLst)
                   (caddr IntLst)
                  )
                  PntLst
                 )
          IntLst (cdddr IntLst)
    )
   )
   (reverse PntLst)
  )
  (T nil)
)
)
[/PHP] 測試
(defun c:tesk()
(setvar "osmode" 0)
  (setq   pol
         (vlax-ename->vla-object (car (entsel)))
          )
(setq pk (hy_getptinpline pol))
(command "line" pk pause)
)
附效果avi

雨箭风刀

不知道锐角处的法线会指向哪里

舟自横

取的參考點實在參數1.5處,不會在頂點....所以不管有沒有銳角都沒有關系..

oyxx_1023

如何求外部的任一点？

snoopychen

能否用vla-offset来得到内外点呢

oyxx_1023

vla-offset主要是不能适应很小面积的PL线，因为不知道最大可以向内偏移多少.但是可以得到外部一点，谢谢提醒。

aeo

最初由 舟自横 发布
[B]取的參考點實在參數1.5處,不會在頂點....所以不管有沒有銳角都沒有關系.. [/B]

那会不会在 圆弧的切线上呢?

舟自横

由該點的法向做一直線(xline)取得是不可能是圓弧的切線應該是圓弧的法線。所以也沒有問題。。
另回復4樓：求復線外部的點是很簡單的，只要在vla-GetBoundingBox以外的點都是外部點,所以并沒有列出來

雨箭风刀

给楼主提一点:
用param取1.5不好,应该取一个小数点后复杂一点的数,因为有个特例.当1.5par法线正对着多义线某段(如par 3~4直线段),会有bug. 如半个酒杯的形状,已经测试过.
[php]
(defun getinpt (e / par an ms xl pts pts2)
  (if (vlax-curve-isclosed e)
    (progn
      (setq par        (* 0.2 PI)
            pt        (vlax-curve-getpointatparam e par)   
      )
      (setq an (+ (* 0.5 PI)
                  (angle '(0. 0. 0.) (vlax-curve-getfirstderiv e par))
               )
            ms (vla-get-modelspace
                 (vla-Get-ActiveDocument (vlax-get-acad-object))
               )
            xl (vla-addxline ms
                             (vlax-3d-point pt)
                             (vlax-3d-point (polar pt an 100))
               )
      )
      (setq pts        (vlax-invoke (vlax-ename->vla-object e)
                             'IntersectWith
                             xl
                             acExtendNone
                )
      )
      (vla-delete xl)
      (while pts
        (setq pts2 (cons (list (car pts) (cadr pts) (caddr pts)) pts2)
              pts  (cdddr pts)
        )
      )
      (setq pts2
             (vl-sort (vl-sort pts2 '(lambda (x y) (< (car x) (car y))))
                      '(lambda (x y) (< (cadr x) (cadr y)))
             )
      )
      (setq ptin (mapcar '(lambda (x y) (* 0.5 (+ x y)))
                         (car pts2)
                         (cadr pts2)
                 )
      )
    )
  )
)
测试:
(defun c:xx (/)
  (command ".line" (getinpt (car (entsel))) pause "")
)
[/php]

所说的特例:

oyxx_1023

我仔细想了这个问题好几天，发现情况远比楼主说的要复杂。必须要分很多种情况：PL含圆弧，PL三点或多点共线，正凸N边形，齿轮状的，花朵状的，等等。
楼主的程序我试验过了，存在很多不能正确解出的情况，如PL第二点与第一点连线垂直X轴的就不行，三点共线的　不行，齿轮状的不行，，，，，欢迎大家继续跟贴发表看法。

aeo

看图

oyxx_1023

不知楼上欲说明何事?

雨箭风刀

是对"如果交點超過2點那么取得最靠近參考點的前后各一點此兩點中必有一點和參考的中點在復線內部。"的反证