TheSwamp
Code Red => VB(A) => Topic started by: havano 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?
-
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.
-
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).
-
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
-
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.
-
Have a look here, in the ARX forum
http://www.theswamp.org/index.php?topic=9145.0
-
havano
Check THIS (http://www.theswamp.org/lilly_pond/index.php?dir=juergmenzi/&file=GetBoundObjects.lsp) sample.
It's not a VBA solution, but LISP. Has some limitations, but works fast.
-
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.
-
..... 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. ?
-
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
-
Maybe this image will clarify what I meant.
(http://members.home.nl/hvolphen/temp/I-BEAM.JPG)
For the green vectors of the pline, the point is on one side, for the red vectors it is on the other.
-
This solution comes from one of our Russian friends here on the swamp, cant remember who it was.
(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
)
-
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...
-
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
-
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.
-
Thanks Bernd and Mick. Very creative, the offset method!
Meanwhile, I have set out an alternative course. The pline(s) will be created by joining rectangles (see my other topic (http://www.theswamp.org/index.php?topic=10506.0")). And finding out whether a point is inside a rectangle is dead easy!