如何使用CGAL获取MultiPolygon的中轴？

Great question! You’re right that CGAL doesn’t expose a direct "medial axis" function for MultiPolygons, but the straight skeleton you found is actually the key to deriving it. The medial axis is a subset of the straight skeleton—we just need to filter out the right edges. Let’s break this down step by step:

Background: Straight Skeleton vs. Medial Axis #

For simple (and multi-component) polygons, the medial axis consists of all interior points equidistant to at least two edges of the polygon. The straight skeleton includes this, plus additional edges that lie directly on the polygon’s boundary. Our job is to strip those boundary edges away.

Step 1: Prepare Your MultiPolygon Input #

First, make sure your MultiPolygon is represented correctly in CGAL:

• Use CGAL::Polygon_with_holes_2 for each connected component (outer boundary + any holes).
• Ensure the outer boundary is counterclockwise and holes are clockwise—this is required for the straight skeleton builder. Use reverse_orientation() to fix orientation if oriented_side() shows it’s wrong.
• Validate your input with is_valid() to catch self-intersections or invalid geometry before proceeding.

Step 2: Compute the Straight Skeleton #

Use CGAL’s Straight_skeleton_builder_2 to generate the skeleton for each component. Here’s a minimal code example:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Straight_skeleton_builder_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <memory>
#include <vector>

// Define kernel and types
typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Polygon_with_holes_2<K> PolygonWithHoles;
typedef CGAL::Straight_skeleton_2<K> StraightSkeleton;
typedef CGAL::Straight_skeleton_builder_2<K> SkeletonBuilder;

int main() {
  // Assume you've already created a valid PolygonWithHoles instance
  PolygonWithHoles my_poly;

  // Build the straight skeleton
  SkeletonBuilder builder;
  builder.build(my_poly.outer_boundary(), my_poly.holes_begin(), my_poly.holes_end());
  std::unique_ptr<StraightSkeleton> skeleton = builder.construct_skeleton();

  // Continue to extract medial axis...
}

Step 3: Filter to Get the Medial Axis #

The medial axis is made up of the straight skeleton’s interior edges. We just need to exclude edges marked as BOUNDARY type:

// Collect medial axis segments
std::vector<K::Segment_2> medial_axis;

for (const auto& edge : skeleton->edges()) {
  // Skip boundary edges (they lie on the original polygon)
  if (edge.type() != StraightSkeleton::EDGE_TYPE::BOUNDARY) {
    const auto& src_pt = edge.source()->point();
    const auto& tgt_pt = edge.target()->point();
    medial_axis.emplace_back(src_pt, tgt_pt);
  }
}

Step 4: Handle Full MultiPolygons #

If your input has multiple disconnected components (a true MultiPolygon), repeat steps 2-3 for each PolygonWithHoles in your collection, then combine all the medial_axis segment lists into one.

Key Tips #

• Use Exact Kernels: Always use Exact_predicates_exact_constructions_kernel (not a floating-point kernel) to avoid precision errors, especially with complex or small polygons.
• Visualize to Verify: Use CGAL’s CGAL::draw() function to render both the straight skeleton and your extracted medial axis—this helps confirm you’ve filtered correctly.
• Edge Cases: For convex polygons, the straight skeleton’s interior edges will form the medial axis (a tree of bisectors), which is exactly what you need. For concave polygons, the reflex vertex bisectors are included automatically.

Quick Note: If you need the medial axis as a planar graph (not just a list of segments), you can build a graph structure from the filtered edges using the skeleton’s vertex pointers instead of just extracting points.

内容的提问来源于stack exchange，提问作者Richard