The *MicroStationAPI* provides an API for developers wanting to
create custom applications for MicroStation^{®} from
Bentley Systems.

We usually create a MicroStation application as a DLL, written using C++ and built with
the Microsoft C++ compiler and linker.
You can choose whether to use
Microsoft Visual Studio
or the Bentley Systems make (*bmake*) tools.

This example uses the MicroStationAPI and
Boost.Geometry
in a C++ project.
The project is built using Bentley make (*bmake*).
While it uses the C++ compiler and linker provided by
Visual Studio,
it doesn't use Visual Studio itself.

A *convex hull* is a shape (2D) or surface (3D) that wholly encloses a set of points.
It's easier to visualise than to describe …

2D convex hull | 3D convex hull |

Here are a few sites that explain convex hulls …

- Wikipedia: Convex Hull
- Wolfram Mathworld: Convex Hull
- (PDF) University of Glasgow School of Computing Science: Convex Hull

A *concave hull* is a shape (2D) or surface (3D) that wholly encloses a set of points.
Unlike a convex hull, the concave hull follows the path of the outmost points of the set.
It's easier to visualise than to describe …

Convex Hull | Concave Hull |

Here are some links to sites that describe the concave hull …

- Spatial Techniques
- Concave Hull
- What are Definition, Algorithms and Practical Solutions for Concave Hull?
- The Concave Hull of a Set of Points

In MicroStation terms, we want to start with a set of points.
MicroStation points might be obtained, for example, from *point cells*, *text elements*, *shared cells* or *zero length lines*.
Then we want to create a *shape element* (2D) that encloses that set of points.
We want to provide a tool that enables a user to select the points, text elements or shape element using the
MicroStation idioms of *fence*, *selection set* or user *pick* operation.

After selecting the points, the user instructs the tool to calculate the convex hull. We convert that result to a MicroStation shape element and add it to the DGN model.

Here's an arbitrary set of points in a DGN model …

User has placed a fence to select the points to be evaluated …

The tool creates a convex hull as a MicroStation shape element …

The
MicroStationAPI
is a C++ class library.
Its base class for implementing the user selection idioms is `DgnElementSetTool`

.
It provides a framework for *fence*,* selection set* and* user pick* operations,
which is exactly what we want.

In this example, our `PickPointsTool`

, `PickTextTool`

and `PickShapeTool`

classes inherit from `DgnElementSetTool`

.
Whichever selection method the user chooses, the result is a collection of data points (`std::vector<DPoint3d>`

).

You could write your own algorithm to calculate a *convex hull*.
Fortunately, others have done that work for you.
You have several choices that I know of …

The question that this example answers was posted on the
*Be Communities*
MicroStation Programming Forum.
The questioner asked for an algorithm (or *magic wand*) that would answer his question.
I was unaware that a solution existed, until a Bentley Systems staffer mentioned the
MicroStationAPI Computational Geometry API, supplied in header file `mscompge.fdf`

(*MicroStation Computational Geometry*),
which you will find in folder
`../SDK/include/Mstn/MdlApi`

.

That header file provides a number of functions that appear fascinating.
If only they were documented!
The one that interests us here is `mdlCompGeom_convexHull2d`

.
You'll notice the *2d* suffix.
As with most of the functions declared in that header, that *2d* suffix indicates that
the algorithm works with planar 2D arrays of points, lines, polygons or whatever.
That is, the algorithm won't work with non-planar sets of objects in 3D.

MDL is a C library, so `mdlCompGeom_convexHull2d`

function is also a C function.
It works in a typical C-style, taking a C-style array of `DPoint3d`

and storing its result
in another array of `DPoint3d`

.
The developer is responsible for memory allocation and deallocation of dynamic arrays.

*Boost.Geometry* is a template library, as is most of Boost.
It's supplied in source-code header (`*.hpp`

) files; there are no binary library files.
All you need to do is `#include`

the appropriate headers, and the C++ compiler does the rest.

Including the *appropriate headers* is the problem: what are the right headers?
We've figured that out for you, and the `#include`

s in our source code demonstrate what you need to know.

Possibly the trickiest part, at least if you are lost in the somewhat terse but voluminous documentation of *Boost.Geometry*,
is how to use MDL's `DPoint3d`

with the *Boost.Geometry* library.
We've also figured out how to do that (termed as *registering* the point with *Boost.Geometry*).
The
registration technique
is described elsewhere on this web site.

Our class named `BoostConvexHull`

wraps the *Boost.Geometry* library algorithm `convex_hull`

.
There's not a lot to it …

```
class BoostConvexHull
{
public:
bool Create (DPoint3dCollection& hull, DPoint3dCollection const& vertices) const;
BoostConvexHull ();
~BoostConvexHull ();
private:
// No copy or assignment
BoostConvexHull (BoostConvexHull const& );
BoostConvexHull& operator=(BoostConvexHull const& );
};
```

The method that does the work is `BoostConvexHull.Create`

.
It takes a set of unordered vertices, computes a *convex hull*, and returns
the points that define that convex hull.
Here's how we use it …

```
bool ConvexHullCreator::MakeBoostConvexHull () const
{
bool rc = false;
BoostConvexHull bch;
DPoint3dCollection hull;
if (bch.Create (hull, points_))
{
// Create a MicroStation shape element from an array of points
CreateShape (&hull [0], hull.size ());
}
return rc;
}
```

There is a number of third-party libraries that deal with computational geometry and related topics.

Download the Convex Hull Source Code.
Unpack the ZIP file, retaining the folder structure.
The pack includes a Bentley make (*bmake*) file.

In addition to the MicroStation SDK, you need the following to be installed on your development computer …

- Visual Studio 2015 in order to compile and link this code for MicroStation CONNECT Update 7 or later
- The Boost libraries for C++, if you want to build the Boost version of this project. We built this example using Boost 1.64

Load the app. using MicroStation key-in

`mdl load ConvexHull`

With the app. loaded, you have the following key-ins available …

Command Root | Command Word 1 | Command Word 2 |
---|---|---|

`CONVEXHULL` | `CREATE` | `POINTS` |

`CONVEXHULL` | `CREATE` | `SHAPE` |

`CONVEXHULL` | `CREATE` | `TEXT` |

`CONVEXHULL` | `HELP` | `ABOUT` |

`CONVEXHULL` | `FILE` | `EXIT` |

Return to MicroStationAPI articles index.