多边形的布尔运算（intersection交集, union并集, difference差异, xor 异或）_多边形布尔运算_苏一恒的博客

link之家

链接快照平台

输入网页链接，自动生成快照
标签化管理网页链接

相关文章推荐

不拘小节的单车 · 为什么我的 JavaScript ...· 4 月前 ·

稳重的肉夹馍 · C# ...· 1 年前 ·

淡定的猕猴桃 · C# Stream篇（五） -- ...· 1 年前 ·

稳重的钥匙 · MS Windows ...· 1 年前 ·

绅士的拖把 · vue3 使用refs - ...· 1 年前 ·

这是工作中的一个需求，要求使用PixiJS来进行绘制，所以这里就不使用原生Canvas或是其他绘制工具了。但归根结底，原理都是一样的。

多边形的布尔运算（ boolean operation on polygons）包括: intersection交集, union并集, difference差异, xor 异或。

具体表现如，Photoshop中的 选区操作 ：
Photoshop中的**选区操作**
Sketch中的 图形叠加效果 ：
Sketch中的**图形叠加效果**

根据两个多边形的所有顶点的坐标组成 GeoJSON ，然后通过 martinez 这个库计算出布尔运算之后的GeoJSON，再解析生成最终效果的多边形定点数组，最后绘制数组生成图像。（下面我使用了PIXI来绘制图形）

.intersection(<Geometry>, <Geometry>) => <Geometry> .union(<Geometry>, <Geometry>) => <Geometry> .diff(<Geometry>, <Geometry>) => <Geometry> .xor(<Geometry>, <Geometry>) => <Geometry>

关于由顶点数组绘制多边形，可参阅博文【绘制】HTML5 Canvas 实现任意圆角多边形

只能应用于直线边，对于圆角/弧度边无法计算

本身我是不打算贴出代码的，因为代码中复用了之前的文章的“圆角多边形”的radius效果，产生了一定的代码冗余，但是考虑到读者可能会在某些地方有所顾虑，还是贴上了，请大家有选择的翻阅。

index.js

import React, {useEffect, useState} from "react";
import * as PIXI from 'pixi.js'
import {intersection, union, xor, diff, drawAll} from './utils.js'
export default function PloygonsBooleanDemo() {
    const [json1, setJson1] = useState([
        // 正方形
            x: 20,
            y: 20,
            radius: 0
            x: 110,
            y: 10,
            radius: 0
            x: 90,
            y: 90,
            radius: 0
            x: 20,
            y: 80,
            radius: 0
    ]);
    const [json2, setJson2] = useState([
            x: 50,
            y: 50,
            radius: 0
            x: 110,
            y: 50,
            radius: 0
            x: 110,
            y: 110,
            radius: 0
            x: 50,
            y: 110,
            radius: 0
    ]);
    const app = new PIXI.Application({
        antialias: true,    // default: false
    });
    let graphics;
    useEffect(() => {
        document.body.appendChild(app.view);
        graphics = new PIXI.Graphics();
        app.stage.addChild(graphics);
    }, []);
    // 初始化图形
    let initGraphics = () => {
        app.stage.removeChild(graphics);
        graphics = new PIXI.Graphics();
        app.stage.addChild(graphics);
    return (<div>
        <button onClick={() => {
            initGraphics();
            drawAll(intersection(json1, json2), graphics);
        </button>
        <button onClick={() => {
            initGraphics();
            drawAll(union(json1, json2), graphics);
        }}>并集
        </button>
        <button onClick={() => {
            initGraphics();
            drawAll(diff(json1, json2), graphics);
        }}>除去一层1
        </button>
        <button onClick={() => {
            initGraphics();
            drawAll(diff(json2, json1), graphics);
        }}>除去一层2
        </button>
        <button onClick={() => {
            initGraphics();
            drawAll(xor(json1, json2), graphics);
        }}>差集
        </button>
    </div>)
utils.js 
import * as martinez from "martinez-polygon-clipping";
export function geoJSON2RadiusShapeJSON(geoJSON) {
    let radiusShapeJSON = [];
    geoJSON.geometry.coordinates.forEach((element)=>{
        let childRadiusShapeJSON = [];
        element[0].forEach((element, index, array) => {
            if (index !== array.length - 1) {
                childRadiusShapeJSON.push({x: element[0], y: element[1], radius: 0});
        });
        radiusShapeJSON.push(childRadiusShapeJSON)
    return radiusShapeJSON;
// 将绘制所用的json转化为GoeJSON
export function radiusShapeJSON2GeoJSON(radiusShapeJSON) {
    let coordinatesArr = [];
    radiusShapeJSON.forEach((element) => {
        coordinatesArr.push([element.x, element.y]);
    });
    coordinatesArr.push([radiusShapeJSON[0].x, radiusShapeJSON[0].y]);
    return {
        "type": "Feature",
        "geometry": {
            "type": "Polygon", "coordinates": [
                coordinatesArr
export function intersection(radiusShapeJSON1, radiusShapeJSON2) {
    return geoJSON2RadiusShapeJSON(
            "type": "Feature",
            "geometry": {
                "type": "Polygon", "coordinates":
                    martinez.intersection(
                        radiusShapeJSON2GeoJSON(radiusShapeJSON1).geometry.coordinates,
                        radiusShapeJSON2GeoJSON(radiusShapeJSON2).geometry.coordinates
export function diff(radiusShapeJSON1, radiusShapeJSON2) {
    return geoJSON2RadiusShapeJSON(
            "type": "Feature",
            "geometry": {
                "type": "Polygon", "coordinates":
                    martinez.diff(
                        radiusShapeJSON2GeoJSON(radiusShapeJSON1).geometry.coordinates,
                        radiusShapeJSON2GeoJSON(radiusShapeJSON2).geometry.coordinates
export function union(radiusShapeJSON1, radiusShapeJSON2) {
    return geoJSON2RadiusShapeJSON(
            "type": "Feature",
            "geometry": {
                "type": "Polygon", "coordinates":
                    martinez.union(
                        radiusShapeJSON2GeoJSON(radiusShapeJSON1).geometry.coordinates,
                        radiusShapeJSON2GeoJSON(radiusShapeJSON2).geometry.coordinates
export function xor(radiusShapeJSON1, radiusShapeJSON2) {
    return geoJSON2RadiusShapeJSON(
            "type": "Feature",
            "geometry": {
                "type": "Polygon", "coordinates":
                    martinez.xor(
                        radiusShapeJSON2GeoJSON(radiusShapeJSON1).geometry.coordinates,
                        radiusShapeJSON2GeoJSON(radiusShapeJSON2).geometry.coordinates
 * 已知A、B、C三点坐标，求半径为r的内切圆与AC的切点坐标
 * @param A
 * @param B
 * @param C
 * @param r
 * @returns {{x: *, y: *}}
export function _toOrigin(A, B, C, r) {
    let {pow, acos, tan} = Math;
    //ab的长度
    const ab = pow(pow(A.x - B.x, 2) + pow(A.y - B.y, 2), 0.5);
    //bc的长度
    const bc = pow(pow(C.x - B.x, 2) + pow(C.y - B.y, 2), 0.5);
    //B的角度
    const angleB = acos(((A.x - B.x) * (C.x - B.x) + (A.y - B.y) * (C.y - B.y)) / (ab * bc));
    //BM的长度,即B到切线的长度
    const M = r / tan(angleB / 2);
    const k = (C.y - B.y) / (C.x - B.x);
    if (k === '-Infinity') {
        return {
            x: B.x,
            y: B.y - M
    } else if (k === 'Infinity') {
        return {
            x: B.x,
            y: B.y + M
    } else {
        let i = 1;
        if (1 / k === '-Infinity') {
            i = -1;
        if (k < 0) {
            if ((C.y - B.y) < 0) {
                i = 1;
            } else {
                i = -1;
        if (k > 0) {
            if (C.y - B.y < 0) {
                i = -1;
        return {
            x: B.x + (1 / pow(1 + k * k, 0.5)) * M * i,
            y: B.y + (k / pow(1 + k * k, 0.5)) * M * i
 * 将json点集转化为可操作点handlePoints
export function json2HandlePoint(json) {
    //矫正radius
    fixRadius(json);
    //将所有可操作点保存handlePoint变量中
    let handlePoints = [];
    //第一个点
    handlePoints.push({
        start: {x: json[json.length - 1].x, y: json[json.length - 1].y},
        middle: {x: json[0].x, y: json[0].y},
        end: {x: json[1].x, y: json[1].y},
        radius: json[0].radius
    });
    //中间所有点
    for (let i = 1; i < json.length - 1; i++) {
        handlePoints.push({
            start: {x: json[i - 1].x, y: json[i - 1].y},
            middle: {x: json[i].x, y: json[i].y},
            end: {x: json[i + 1].x, y: json[i + 1].y},
            radius: json[i].radius
        });
    //最后一个点
    handlePoints.push({
        start: {x: json[json.length - 2].x, y: json[json.length - 2].y},
        middle: {x: json[json.length - 1].x, y: json[json.length - 1].y},
        end: {x: json[0].x, y: json[0].y},
        radius: json[json.length - 1].radius
    });
    return handlePoints;
 * 将异常json的radius按照Sketch模式矫正
 * sketch圆角异常数据处理方法：
 用户可设定radius值，当出现不合法值的时候，原值不变，图像自行优化
 说明：如100*50的矩形，可以在50像素的边对应的角，各设置成radius=25，也可以其中一个设为0，另一个设为50，总之就是radius1+radius2=50。当radius1+radius2>50的时候，在绘制里，radius_min不变，radius_max = 50/2,而在json数据中不改变这些数据，已保存用户的数据记录
export function fixRadius(json) {
    //第一个点
    _fixRadius(json[json.length - 1], json[0], json[1]);
    for (let i = 1; i < json.length - 1; i++) {
        _fixRadius(json[i - 1], json[i], json[i + 1]);
    //最后一个点
    _fixRadius(json[json.length - 2], json[json.length - 1], json[0]);
export function _fixRadius(left, curr, right) {
    let {pow, acos, tan} = Math;
    const leftLine = pow(pow(left.x - curr.x, 2) + pow(left.y - curr.y, 2), 0.5);
    const rightLine = pow(pow(right.x - curr.x, 2) + pow(right.y - curr.y, 2), 0.5);
    //两边最短边
    const minLine = leftLine < rightLine ? leftLine : rightLine;
    //中间角度
    const angleCurr = acos(((left.x - curr.x) * (right.x - curr.x) + (left.y - curr.y) * (right.y - curr.y)) / (leftLine * rightLine));
    //理论上能实现的最大弧度半径
    let maxRadius = minLine * tan(angleCurr / 2);
        当左右都为0且，当前radius超过理论最大弧度半径时
        将radius缩减到最大弧度半径
    if (left.radius === 0 && right.radius === 0) {
        if (curr.radius > maxRadius) {
            curr.radius = maxRadius;
        当左右任意一边有值，且radius超过理论最大弧度半径的一半时
        将radius缩减到最大弧度半径的一半
    if (left.radius > 0 || right.radius > 0) {
        if (curr.radius > maxRadius / 2) {
            curr.radius = maxRadius / 2;
export function drawShape(handlePoints,graphics) {
    //重置路径
    graphics.beginFill(0x66CCFF);
    let currPoint = undefined;
    const origin = _toOrigin(handlePoints[0].start, handlePoints[0].middle, handlePoints[0].end, handlePoints[0].radius);
    graphics.moveTo(origin.x, origin.y);
    for (let i = 1; i < handlePoints.length; i++) {
        currPoint = handlePoints[i];
        //绘制圆弧
        graphics.arcTo(currPoint.middle.x, currPoint.middle.y, currPoint.end.x, currPoint.end.y, currPoint.radius);
    currPoint = handlePoints[0];
    graphics.arcTo(currPoint.middle.x, currPoint.middle.y, currPoint.end.x, currPoint.end.y, currPoint.radius);
    graphics.endFill();
    graphics.closePath();
//绘制经布尔运算后的图形
export function drawAll(arr,graphics) {
    arr.forEach(element => {
        drawShape(json2HandlePoint(element),graphics)
                    文章目录前言正文实现思路效果展示缺点代码实现前言这是工作中的一个需求，要求使用PixiJS来进行绘制，所以这里就不使用原生Canvas或是其他绘制工具了。但归根结底，原理都是一样的。正文多边形的布尔运算（ boolean operation on polygons）包括: intersection交集, union并集, difference差异, xor 异或。具体表现如，Photos...
				简单多边形的相交、合并算法。仅支持简单凹凸多边形。所谓简单多边形即多边形内部不含环的多边形。这个demo程序只是介绍了多边形相交、合并的算法，针对简单凹凸多边形可以正常处理。算法仅供参考！
如需要支持内部有环的复杂多边形相交合并，请使用boost::polygon。
 或者，对于浏览器，在目录中查找单个文件。 当包含在页面中时，它将公开全局PolyBool 。
var PolyBool = require ( 'polybooljs' ) ;
PolyBool . intersect ( {
    regions : [
      [ [ 50 , 50 ] 
				多边形的布尔运算
@ flatten-js / boolean-op是一个JavaScript库，可对多边形执行快速可靠的布尔运算。 它提供二进制布尔操作：
多边形实际上是可以由多个面组成的多多边形。 面的方向（顺时针或逆时针）很重要，因为算法的实现方式是永远不会改变边的原始方向。 为了正确执行布尔运算，面必须符合以下规则：
 每个面都是一个非退化的简单闭合多边形。 换句话说，面对shouhttps：//badge.fury.io/js/flatten-boolean-op.svgld没有自相交，其方向应该是可定义的。
 如果一个面完全在另一面内，则其方向应与外部面的方向相反。 然后我们将外表面称为“岛” ，将内表面称为“Kong” 。 因此，规则是“岛内无岛，洞内无Kong”。
 多边形的面不应相互重叠
布尔运算算法不检查多边形是否符合这些规则，这由调用者负责。
 布尔运算的结果也是一个
Clipper演示了Wyler-Atherton算法，并进行了修改以查找两个多边形的并集。 多边形可以是非凸的，并且可以包含“Kong”（内部的其他多边形）。 您可以在应用程序窗口中绘制两个多边形，也可以对其进行编辑（添加/删除点）。 Clipper找到多边形的并集并将其绘制在工作窗口中。 多边形及其联合可以打印，保存和加载（在本地数据库或磁盘上的文件中，由您选择）。
 应用程序设计的简要说明：
 多边形类：将多边形表示为几何形状，存储多边形的状态并提供编辑方法；
 PolygonValidater类：包含用于检查几何形状是否符合问题条件的方法（检查自相交，“Kong”的正确位置等）；
 实用程序类：提供了一组用于解决计算子任务的静态方法（确定点是否位于多边形，线段的相交点，图形的面积）;
 PolygonMerger类：实现Wyler-Atherton算法以合并两条路径；
				多边形裁剪
对您的Polygons＆MultiPolygons应用boolean Polygon裁剪操作（ intersection ， union ， difference ， xor ）。
const polygonClipping = require ( 'polygon-clipping' )
const poly1 = [ [ [ 0 , 0 ] , [ 2 , 0 ] , [ 0 , 2 ] , [ 0 , 0 ] ] ]
const poly2 = [ [ [ - 1 , 0 ] , [ 1 , 0 ] , [ 0 , 1 ] , [ - 1 , 0 ] ] ]
polygonClipping . union       ( poly1 , poly2 /* , poly3, ... */ )
polygonClipping . intersection ( pol
				python 并集union, 交集intersection, 差集difference, 对称差集symmetric_difference
a,b,c = [1,2,3],[2,3,4],[3,4,5]
print('------>union')
print('a,b取并集：',set(a).union(b))
print('a,b取并集：',set(a)|set(b))
print('a,b,c取并集：',set(a).union(b,c))
print('a,b,c取并集：',set(a)|set(b)|set(c))
print('------>intersection')
print
				Martinez-Rueda多边形裁剪算法
该算法特别快速，并且能够处理所有类型的多边形：多多边形（无级联），带Kong的多边形，自相交多边形以及具有重叠边缘的退化多边形。
 import * as martinez from 'martinez-polygon-clipping' ;
const gj1 = { "type" : "Feature" , ... , "geometry" : { "type" : "Polygon" , "coordinates" : [ [ [ x , y ] , ... ] ] } ;
const gj2 = { "type" : "Feature" , ... , "geometry" : { "type" : "MultiPolygon" , "coordinates" : [ [ [ [ x , y ] , ... ] ] ] 
不到20行代码即可生成一个强大的多边形布尔库！ （不包括依赖项）与任何种类的多边形一起使用，结果对机器精度都是准确的，并且在任何情况下有效输入都不会崩溃或产生错误的输出。
 var polybool = require ( 'poly-bool' )
var a = [ [ [ - 1 , - 1 ] , [ - 1 , 1 ] , [ 1 , 1 ] , [ 1 , - 1 ] ] ]
var b = [ [ [ 0 , 0 ] , [ 0 , 2 ] , [ 2 , 2 ] , [ 2 , 0 ] ] ]
console . log ( polybool ( a , b , 'sub' ) )
 [ [ [ 1 , 1 ] , [ 1 , 0 ] , [ 2 , 0 ] , [ 2 , 2 ] , [ 0 , 2 ] , [ 0 , 1 ] ] ]
set2 = {2, 3, 4}
symmetric_difference_set = set1 ^ set2
print(symmetric_difference_set)
输出结果为：{1, 4}