Search code examples
c++boostcomputational-geometryboost-geometry

Finding a point inside a Boost::Geometry::Polygon

I have a Polygon object and I'm looking for an efficient way to find any point strictly inside it (not on its boundary). What is the best way to do so?

I had the following ideas, which I don't really like:

  1. Triangulating the polygon and reporting a point on one of the triangulation edges (too expensive).
  2. Checking the polygon's winding direction and reporting a point located in an epsilon-distance from one of the polygon's edges (doesn't work in edge-cases).
Solution

  • Given a polygon, you can find the first two points where the polygon crosses a line parallel to x axis and lies between the yMin & yMax of your polygon (0 & 1 in the image below).

    Any point between these points will be inside your polygon. The basic idea comes from scan converting a polygon —i.e. these are the points you would fill. The part of the line after the second point has a winding of 0 or 2, depending on your polygon.

    The first two crossings (or last) has to be taken, as the crossing points are sorted along the x-axis.

    Basic idea

    Some corner cases:

    1. If you omit all points of the polygon which just touches the line, in some cases this can fail (image below).
    2. If there are overlapping lines in your polygon, you have to resolve those.

    issue

    To avoid the first issue, make sure to take the first point as a definite crossing and the next one can be either a crossing or a point where polygon just touches the line.

    final

    This can be easily implemented without using any special functions in most languages. Since I am not familiar with Boost methods, I am posting a sketch of the basic idea in javascript.

    The drawing is done using paper.js —although, the code for the algorithm outlined here itself is self contained.

    You can translate this to C++ as long as you can enumerate through all points in a Boost::polygon

    Here is the demo.