Is Shape1 inside Shape2

Hi John,

in general, "something in something" is complex topology task. When it's about polygons, it makes the problem even more complicated and the situation "polygon edge on another edge" cannot be solved without limiting conditions (because of problem with "precision" term and used math). VBA is definitely not right tool to do such analysis, so be prepared for limitations and restrictions.

I have no time to analyze the code (sorry, it's reserved for commercial customers), but I think the simplest solution is to use fence as analysis tool. Outer polygon have to linearized (but because of maximum number of points the precision of such transformation is typically good enough). The analysis can be e.g. to use "outside" mode and when there is no result, the second polygon is inside.

With regards,

  Jan

John Davidson said:

my problem is determining if shape1 is inside shape2

Polygon Numerical Analysis

While, to a human, it's pretty obvious when one polygon is inside another, that is — as Jan comments — a hard calculation.  For some insights, search the web.  For example...

• Stack Exchange: Polygon-in-polygon testing
• Stack Overflow: Check if polygon is inside a polygon
• allegro cc: Algorithm to determine if one polygon is inside another polygon

One approach, therefore, is to get the points from shape1 and shape2 and implement one of the above algorithms on those sets of points.

Boolean Operations

Another approach is to use VBA's Boolean Operations on Closed Elements and Planar Regions.  Use one of GetIntersectionShapes, GetDifferenceShapes or GetUnionShapes and examine the ElementEnumerator result.  For example, if shape1 is inside shape2, then I expect that the result of the union of those shapes will be shape2.  You should experiment.

Hi Jon/Jan,

Thanks for your very good explanations of why I am getting the results I have got using the methods I have, It looks like I have got about as good a result as possible with vba. I had a look at the links supplied and most refer to polygons with straight lines (no arcs) so not really much help, but thanks all the same.

I would have thought that a complexshape made with the flood option would have vertices exactly on top of the bounding vertices and therefore should be deemed ON the boundary shape but not knowing how the Point3dInPolygonXY creates the bounding shape, or how the flood option calculates the vertices, I guess leaves this unsolved.

Thanks again for your valued help.

Regards,

John.

Hi John,

John Davidson said:

It looks like I have got about as good a result as possible with vba.

Yes. And maybe even in other languages also (without writing own code to solve your requirements).

John Davidson said:

I had a look at the links supplied and most refer to polygons with straight lines (no arcs) so not really much help

You should be aware that many topology libraries linearize (convert to line strings) geometry before topology analysis. It's often the only possible general approach. For specific cases (e.g. data with known parameters and structure are processed), more advanced solutions can be used, but often special code have to be implemented.

John Davidson said:

I would have thought that a complexshape made with the flood option would have vertices exactly on top of the bounding vertices

Well, unfortunately this assumption is completely wrong. To explain it is complicated and it requires a good knowledge of several math areas (calculation with real numbers, numerical mathematics...) plus how numbers are implemented in processors (representation of decimal number using binary storage) and consequently how they are implemented in software (IEEE 754 is the place where to start).

Without going too deep (which would require to define terminology at first ;-), because of limited precision (we have no infinite space to represent numbers) and internal representation (decimal numbers are transformed into binary representation), nothing is "exact", but "rounded". Always, no exception.

John Davidson said:

and therefore should be deemed ON the boundary shape

How you want to define "on the boundary shape" in math, and use it in reality? See this picture:

Are lines at lef t coincident? Yes, for sure ... for human. But when you will check them from math perspective, they are not! Because even when calculated right, the calculation is not exact and when stored, vertices coordinates are rounded. This imperfection is really small, but when people use "something on something", they typically mean P1 = P2, which does not make sense, because never happen during computation (in general, every time you will see anything like x = y with decimal numbers, it's wrong code ;-) .

John Davidson said:

but not knowing how the Point3dInPolygonXY creates the bounding shape, or how the flood option calculates the vertices, I guess leaves this unsolved.

The problem is not in the "point in polygon" test. To test "polygon in polygon" is far more complex and always requires to define expected precision (e.g. anything under 0.1 mm is "equal"), which consequently allows to chose proper algorithm.

Unfortunately VBA is not tool to do anything from the mentioned :-(

With regards,

  Jan

John Davidson said:

not knowing how the Point3dInPolygonXY creates the bounding shape

That method is ignorant of bounding shapes.  It accepts an array of points...

Point3dInPolygonXY (Point, PolygonVertices [, Tolerance]) 

PolygonVertices: A Point3d () expression. The array of points comprising the polygon

That's pure geometry, and nothing to do with MicroStation.

John Davidson said:

most refer to polygons with straight lines (no arcs)

By definition, a polygon has straight edges.   They could be arcs in a non-Euclidian space (math joke)!

John Davidson said:

it still sometimes finds elements with vertices outside the boundary

Another approach might be to use a Fence.  Represent your point with a zero-length line, and create a fence using mode inside True and overlap False.  Then evaluate the fence contents: if your point element is included, then it's inside the fence.

Jan Šlegr said:

You should be aware that many topology libraries linearize (convert to line strings) geometry before topology analysis

Jan's comment applies to fences.  When you place a circular fence in MicroStation, for example, what you get is a many-sided polygon.

Taking a quick look at your code the tolerance for you specify for the ConstructVertex method is way too large.

   'Get vertices for oelem1
    Points = oElem1.ConstructVertexList(1)

You have it set to 1, try setting it to .01 and see if that changes your results.

My other question is why are you iterating through each sub element of complex shapes individually, getting those verticies, and appending to an array? You can just do a ConstructVertexList on the Complex Shape element and not have to go through those gyrations.

Hi Jan,Jon,Rod,

Thanks for your valued information, the project is related to subdivision stages and I exhausted the use of fences using many different combinations also using the copy parallel options so that the fence was outside the actual boundary but it can't be done with vba as the copy parallel options cannot be guaranteed to copy to the correct side, and where the stage boundaries are adjoining it is impossible to tell if you have the correct boundary.

Other problems encountered were, the property shapes could be abutting the boundary on both inside and outside the stage boundary. Complexshapes containing arcs can have vertices quite obviously inside or outside the actual shape elements and that is the reason I have cycled through each element in both the inner and outer shapes, which made quite an improvement.

I also found the reason for the few shapes that were missed, it was due to property corner vertices on the stage boundary at part of an arc in the boundary where the bounding shape would be tested with a straight line between the points on the arc either side of the property corner point. I guess I could calculate more points along each arc to make it more accurate, but that would probably slow the processing down considerable and still not get those missing shapes.

There is probably other implications also, and what I have so far is sometimes only missing a few shapes, and I can get the user to process them manually.

So thanks once again for you valued help.

Best Regards,

John.

John Davidson said:

The project is related to subdivision stages ... the property shapes could be abutting the boundary

It looks like you're trying to reinvent the GIS wheel using VBA.  That's not a road I would choose to take.

GIS products, such as OpenCities Map (formerly Bentley Map) provide heaps of tools for spatial analysis, including the kind of work you want to perform.  I don't know how much time you have spent on this, and other related tasks, but if it has taken more than a few weeks then your organisation has already spent the license fee for Map in salary.

Hi John,

John Davidson said:

the project is related to subdivision stages

as Jon wrote, your explanation sounds like GIS operation.

In general, there are two (quite opposite) approaches when working with data (not graphical only):

• To check data quality (topology in the discussed case) from very beginning, when data are captured, and through complete life cycle, when data are modified. It's the only way how to ensure some operations (e.g. topology analysis, modifications like areas split etc.) can be done in predictable way.
  It's the way how GIS system work. Originally only lines were allowed, now many systems allows to work with curves also, but often with some limitations like not all types are supported or for specific operations, geometry is converted to line strings (with defined precision).
• Allow to work with any data and to try to find the best way how to process them later. This approach cannot ensure the problem can be solved, because when data are dirty, some operations are not possible, or to implement code requires a lot of work.

Because you are in the second situation. It does not mean it cannot be solved (or at least, an approach able to process 99% of situations, but not all), but VBA is really bad tool to try to reach such goal. It's both because of MicroStation VBA API limitations (both NET and C++ APIs provides rich topology structures, even when MicroStation is not GIS), but also because of VBA itself. Both C# and C++ allows to write more efficient code, because perfectly implemented libraries are available for any task you can imagine.

John Davidson said:

but that would probably slow the processing down considerable

I do not think it's true. Even when VBA is slow and not very efficient "by definition", 99% of performance problems I saw were caused by wrong algorithm, not because VBA was used.

John Davidson said:

So thanks once again for you valued help.

It's my pleasure, but I dislike the situation when good final solution is not found (and unfortunately, in the discussed case, cannot be found).

With regards,

  Jan

Thanks Jon/Jan,

This app is just a small step to a much bigger picture of the processes we undertake and will be looking at Open Cities and other ways to improve our productivity. There are so many new technologies available now and we need to continually review how we do things, but this process has been ignored for too long and needed something to kick off the inspiration of our users to think outside the box.

Thanks again for your help.

John.