Flutter多边形三角剖分插件dart_earcut的使用

dart_earcut 是一个用于Flutter项目的库，它实现了从其他项目（如 earcut4j/earcut4j 和 mapbox/earcut）移植过来的耳切（Ear-clipping）三角剖分算法。该库还包含了来自 mapbox/earcut#91 的修复。

使用方法

2D (x/y) 坐标，不带孔洞

• triangulateRaw: 期望点以 [x0, y0, x1, y1, x2, y2, ...] 格式提供
• triangulateFromPoints: 期望的是 ‘dart:math’ 的 Point 对象

final triangles = Earcut.triangulateRaw([10,0, 0,50, 60,60, 70,10]);
final triangles = Earcut.triangulateFromPoints([Point(10, 0), Point(0,50), Point(60,60), Point(70,10)]);
// Both return [1,0,3, 3,2,1]

带孔洞

孔洞由一个索引列表表示。例如，对于12个顶点的输入，[5, 8] 表示一个孔洞由顶点5-7组成，另一个由顶点8-11组成。如果传递单个顶点作为孔洞，Earcut会将其视为Steiner点。

final List<int> triangles = Earcut.triangulateRaw([0, 0, 100, 0, 100, 100, 0, 100, 20, 20, 80, 20, 80, 80, 20, 80], holeIndices: [4]);
// Returns [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2]

triangulateFromPointsAndHolePoints 方法会在多边形轮廓和孔洞轮廓分别以点的形式提供时生成 holeIndices。

更多维度

支持三维坐标，格式为 [x0, y0, z0, x1, y1, z1, x2, y2, z2, ...]。

final List<int> triangles = Earcut.triangulateRaw([10, 0, 1, 0, 50, 2, 60, 60, 3, 70, 10, 4], dimensions: 3);
// Returns [1,0,3, 3,2,1]

算法原理

该库实现了一种经过改进的耳切算法，通过 Z-order 曲线哈希进行优化，并扩展以处理孔洞、扭曲多边形、退化情况和自交问题。虽然不能完全保证剖分结果的正确性，但该算法旨在尽可能地产生可接受的结果。

此算法基于以下研究：

• FIST: Fast Industrial-Strength Triangulation of Polygons by Martin Held
• Triangulation by Ear Clipping by David Eberly

完整示例代码

下面是一个完整的示例代码，展示了如何在Flutter中使用 dart_earcut 进行三角剖分：

import 'package:flutter/material.dart';
import 'package:dart_earcut/dart_earcut.dart';
import 'dart:math';

void main() {
  runApp(MyApp());
}

class MyApp extends StatelessWidget {
  @override
  Widget build(BuildContext context) {
    return MaterialApp(
      home: Scaffold(
        appBar: AppBar(title: Text('Dart Earcut Example')),
        body: Center(child: PolygonDrawer()),
      ),
    );
  }
}

class PolygonDrawer extends StatelessWidget {
  final List<double> polygon = [
    0, 0, 100, 0, 100, 100, 0, 100, // Outer square
    20, 20, 80, 20, 80, 80, 20, 80  // Inner square as a hole
  ];
  final List<int> holeIndices = [8]; // Index where the hole starts

  @override
  Widget build(BuildContext context) {
    final List<int> triangles = Earcut.triangulateRaw(polygon, holeIndices: holeIndices);

    return CustomPaint(
      size: Size(200, 200),
      painter: PolygonPainter(triangles, polygon),
    );
  }
}

class PolygonPainter extends CustomPainter {
  final List<int> triangles;
  final List<double> vertices;

  PolygonPainter(this.triangles, this.vertices);

  @override
  void paint(Canvas canvas, Size size) {
    final Paint paint = Paint()
      ..color = Colors.blue
      ..style = PaintingStyle.fill;

    for (int i = 0; i < triangles.length; i += 3) {
      final Path path = Path();
      path.moveTo(vertices[triangles[i] * 2], vertices[triangles[i] * 2 + 1]);
      path.lineTo(vertices[triangles[i + 1] * 2], vertices[triangles[i + 1] * 2 + 1]);
      path.lineTo(vertices[triangles[i + 2] * 2], vertices[triangles[i + 2] * 2 + 1]);
      path.close();
      canvas.drawPath(path, paint);
    }
  }

  @override
  bool shouldRepaint(covariant CustomPainter oldDelegate) => false;
}

这段代码创建了一个简单的Flutter应用程序，其中包含一个带有孔洞的多边形，并使用 dart_earcut 库对其进行了三角剖分，然后将结果绘制到屏幕上。