Introduction

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.

What is a Convex Hull?

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
2D convex hull 3D convex hull

Here are a few sites that explain convex hulls …

What is a Concave 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
Convex Hull Concave Hull

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

Convex Hull: Setting the Scene for MicroStation

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 …

An arbitrary set of points in a DGN model

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

A selection set of points

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

A convex hull generated for the selected points

MicroStation Selection Idioms

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>).

Convex Hull Algorithms

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

MicroStationAPI Computational Geometry

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

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 #includes 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.

Boost Convex Hull class

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;
}

Third-Party Computational Geometry Libraries

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

Download Convex Hull Source Code

Download CSearchTypes Source Code

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 …

Load the app. using MicroStation key-in
mdl load ConvexHull
With the app. loaded, you have the following key-ins available …

Convex Hull Commands
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.