Author Topic: Inside or outside a boundary? How to find out?  (Read 6515 times)

0 Members and 1 Guest are viewing this topic.

havano

  • Guest
Inside or outside a boundary? How to find out?
« on: June 03, 2006, 07:38:08 PM »
Let's assume you've got a drawing layer with a bunch of closed (sometimes partly overlapping) entities like closed 2D LWpolylines, arcs etc. Now, you want to find out if a given XY coordinate is within the enclosure of at least one of these drawing entities.

Could one of you think of an approach (which will be repeated for a large number of coordinates, so it had better be fast) to perform this task?

Bryco

  • Water Moccasin
  • Posts: 1882
Re: Inside or outside a boundary? How to find out?
« Reply #1 on: June 04, 2006, 11:05:44 AM »
See http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm for a good reason not to use the ray method. The formulae are included but in C++ so the conversion is not always that simple.

havano

  • Guest
Re: Inside or outside a boundary? How to find out?
« Reply #2 on: June 04, 2006, 12:12:33 PM »
Thanks Bryco. I have thought of a ray method. First, find the boundingbox for all geometry on the layer, next, scan this boundingbox area with a horizontal/vertical line or ray and use intersectwith to find out where the geometry borders are. It is surely possible to use that method, but it's SLOW. And confusing, when the scan ray hits an edge of a entity and thus returns only one hit (or an odd number of hits).
« Last Edit: June 04, 2006, 01:06:15 PM by havano »

DaveW

  • Guest
Re: Inside or outside a boundary? How to find out?
« Reply #3 on: June 06, 2006, 08:45:34 PM »
FYI,

I am a bit of a hakerr with coding... okay, a really bad hacker, but anyway I have had issues like this.

One solution I have found when working with complicated expoded 3dSolids is to:

get the bottom region
section the solid many times on the xy plane
move all the regions down
union them all together
explode the new region
run pedit

MickD

  • King Gator
  • Posts: 3619
  • (x-in)->[process]->(y-out) ... simples!
Re: Inside or outside a boundary? How to find out?
« Reply #4 on: June 06, 2006, 08:58:06 PM »
A very basic description of an algo but you could also try looping through each polygon edge, calculate whether the point is on the left (-) or right (+) side.
If your closed poly loops clockwise and your point 'is' inside, all checks would return positive.
This would also require a fuzz factor for points that are on or very close to an edge. This algo will also work for concave polys.

Another alternative is to use the managed wrappers and use the geometry classes (a surface comes to mind) which has these functions built in.
"Short cuts make long delays,' argued Pippin.”
J.R.R. Tolkien

LE

  • Guest
Re: Inside or outside a boundary? How to find out?
« Reply #5 on: June 06, 2006, 10:28:11 PM »
Have a look here, in the ARX forum

http://www.theswamp.org/index.php?topic=9145.0

Jürg Menzi

  • Swamp Rat
  • Posts: 599
  • Oberegg, Switzerland
Re: Inside or outside a boundary? How to find out?
« Reply #6 on: June 07, 2006, 07:35:09 AM »
havano

Check THIS sample.
It's not a VBA solution, but LISP. Has some limitations, but works fast.
A computer's human touch is its unscrupulousness!
MENZI ENGINEERING GmbH
Current A2k16... A2k24 - Start R2.18

havano

  • Guest
Re: Inside or outside a boundary? How to find out?
« Reply #7 on: June 09, 2006, 10:29:47 PM »
Thx Mr Menzi, but I have sworn never to use Lisp.

Thx LE. This is beyond my intellectual reach.

Thx MrMickD, but with some Pline shapes your assumption is incorrect. Take for example a Pline shaped like an I-beam crosssection. A point in the centre of the I-beam will not allways be on the same side of a contributing PL-edge, although it is inside the shape.

Thx DaveW, this may contribute to a solution.
 

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Inside or outside a boundary? How to find out?
« Reply #8 on: June 09, 2006, 11:02:59 PM »
.....  Take for example a Pline shaped like an I-beam crosssection. A point in the centre of the I-beam will not allways be on the same side of a contributing PL-edge, although it is inside the shape.

Whoa ! ... say again. ?
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

Jürg Menzi

  • Swamp Rat
  • Posts: 599
  • Oberegg, Switzerland
Re: Inside or outside a boundary? How to find out?
« Reply #9 on: June 10, 2006, 04:29:10 AM »
Thx Mr Menzi, but I have sworn never to use Lisp. (...)
There is no must to use LISP. You may use the idea behind the proggi...

Cheers
A computer's human touch is its unscrupulousness!
MENZI ENGINEERING GmbH
Current A2k16... A2k24 - Start R2.18

havano

  • Guest
Re: Inside or outside a boundary? attn K. Brown
« Reply #10 on: June 10, 2006, 09:15:39 AM »
Maybe this image will clarify what I meant.



For the green vectors of the pline, the point is on one side, for the red vectors it is on the other.

Amsterdammed

  • Guest
Re: Inside or outside a boundary? How to find out?
« Reply #11 on: June 10, 2006, 03:33:37 PM »
This solution comes from one of our Russian friends here on the swamp, cant remember who it was.

Code: [Select]
(defun insidep (pt ent / big flag obj1 obj2 obj3 p1 p2 small)
  (vl-load-com)
  (if (and pt ent)
    (progn
      (setq obj1 (vlax-ename->vla-object ent))
      (setq obj2 (car (vlax-invoke obj1 'Offset 0.001))
            obj3 (car (vlax-invoke obj1 'Offset -0.001))
            ) ;_ end of setq
      (if (> (vla-get-area obj2) (vla-get-area obj3))
        (progn
          (set 'big obj2)
          (set 'small obj3)
          ) ;_ end of progn
        (progn
          (set 'big obj3)
          (set 'small obj2)
          ) ;_ end of progn
        ) ;_ end of if
      (setq p1 (vlax-curve-getClosestPointTo big pt)
            p2 (vlax-curve-getClosestPointTo small pt)
            ) ;_ end of setq
      (if (> (distance pt p1) (distance pt p2))
        (setq flag T)
        (setq flag nil)
        ) ;_ end of if
      (mapcar (function (lambda (x)
                          (progn
                            (vla-delete x)
                            (vlax-release-object x)
                            ) ;_ end of progn
                          ) ;_ end of lambda
                        ) ;_ end of function
              (list big small)
              ) ;_ end of mapcar
      ) ;_ end of progn
    ) ;_ end of if
  flag
  )


havano

  • Guest
Re: Inside or outside a boundary? How to find out?
« Reply #12 on: June 10, 2006, 05:09:09 PM »
That's why I dislike Lisp: it's Russian to me. I can't figure out what happens. The code looks compact enough, but I wouldn't know how to embed it in a VBA macro, let alone a VB executable.
My fault, I'm sure...

Amsterdammed

  • Guest
Re: Inside or outside a boundary? How to find out?
« Reply #13 on: June 12, 2006, 08:37:49 PM »
The idea is that you  make an offset of the boundary you have in both directions from 0,001. Than you search for the closest point to your pt on both new polylines. And you look which one is closer to your point. Is it the neg. offset it is inside, otherwise not.

I hope i could help,

Bernd

MickD

  • King Gator
  • Posts: 3619
  • (x-in)->[process]->(y-out) ... simples!
Re: Inside or outside a boundary? How to find out?
« Reply #14 on: June 12, 2006, 09:00:41 PM »
For the green vectors of the pline, the point is on one side, for the red vectors it is on the other.

Ok, concave polygons are a different ball game. You can still use the neg/pos routine but you would have to use set theory/boolean logic to combine the halfspaces created by the edges, this creates a surface which can be described as a parametric equation which you can plug in a point and find out if it's in or out - this is not a trivial matter though.

Another option is to break your polygon up into simple convex shapes (triangulate for example) and do the neg/pos test on each new shape, as soon as you get a 'pos' hit it has to be inside the polygon.

There are many many ways to do this but you need to weigh up complexity and accuracy against speed.

Cheers,
Mick.
"Short cuts make long delays,' argued Pippin.”
J.R.R. Tolkien