triangulateShape()
的函数。现在我遇到了使用Javascript Clipper简化多边形时无法三角剖分的问题。在Clipper中进行简化是通过Unioning完成的。维基百科文章将联合定义为查找包含两个简单多边形内部区域的简单多边形或多边形。同一篇文章说,在简单多边形中,“每个顶点恰好有两条边相交”,并确定了弱简单多边形,其中边可以相交,但未提及边缘不相交的情况,但某些或许多个顶点相交。因此,这种情况是否为简单多边形还有些不清楚。
Clipper选择了宽容的方法:简单多边形可以具有这些类似接触(或伪重复)的顶点。这种Clipper风格的宽容方法导致生成的简单多边形不符合three.js的triangulateShape()
所期望的简单多边形的含义。
triangulateShape()
在这些情况下会失败,因为它在数组allPointsMap
中跟踪点并从那里检查点是否重复。为了删除这些类似的重复项,我有两个选择:
选项1.
更改Javascript Clipper内部代码,使用额外参数来处理这些问题,例如breakPolygonByWeakDuplicates
用于SimplifyPolygon()
和SimplifyPolygons()
。正如Angus Johnson在他的帖子中所描述的那样,更改将类似于:
在IntersectEdges()方法中,将以下内容更改为...
if ( e1Contributing && e2contributing ) { if ( e1stops || e2stops || (e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) || (e1->polyType != e2->polyType && m_ClipType != ctXor) ) AddLocalMaxPoly(e1, e2, pt); else DoBothEdges( e1, e2, pt ); }
变成...
如果 ( e1Contributing && e2contributing ) { AddLocalMaxPoly(e1, e2, pt); AddLocalMinPoly(e1, e2, pt); }这个更改非常简单,但原始的Angus Johnson Clipper和Javascript Clipper将不再兼容。当然,如果原始Clipper进行更改,Javascript Clipper将跟随它。
选项 2.
将 three.js 的 triangulateShape()
源代码更改为接受伪重复内容。
我的问题是:这种额外的简化程序应该在哪一端进行?第一个端点是创建端(Clipper),另一个端点是三角剖分端(three.js)。 我不知道各种3D库中的多边形三角剖分程序,因此无法想象通常情况下三角剖分程序有多宽松。如果有人了解这个领域,他/她可以给出更复杂的答案。
此外,我不知道其他布尔库如何处理联合或简化类似伪重复的内容。毫无疑问,Clipper在简单多边形方面很宽容(例如与其他布尔库的兼容性),但这绝对会在三.js中对多边形进行三角剖分时造成问题。
以下是three.js的三角剖分代码供参考:
triangulateShape: function ( contour, holes ) {
var shapeWithoutHoles = THREE.Shape.Utils.removeHoles( contour, holes );
var shape = shapeWithoutHoles.shape,
allpoints = shapeWithoutHoles.allpoints,
isolatedPts = shapeWithoutHoles.isolatedPts;
var triangles = THREE.FontUtils.Triangulate( shape, false ); // True returns indices for points of spooled shape
// To maintain reference to old shape, one must match coordinates, or offset the indices from original arrays. It's probably easier to do the first.
//console.log( "triangles",triangles, triangles.length );
//console.log( "allpoints",allpoints, allpoints.length );
var i, il, f, face,
key, index,
allPointsMap = {},
isolatedPointsMap = {};
// prepare all points map
for ( i = 0, il = allpoints.length; i < il; i ++ ) {
key = allpoints[ i ].x + ":" + allpoints[ i ].y;
if ( allPointsMap[ key ] !== undefined ) {
console.log( "Duplicate point", key );
}
allPointsMap[ key ] = i;
}
// check all face vertices against all points map
for ( i = 0, il = triangles.length; i < il; i ++ ) {
face = triangles[ i ];
for ( f = 0; f < 3; f ++ ) {
key = face[ f ].x + ":" + face[ f ].y;
index = allPointsMap[ key ];
if ( index !== undefined ) {
face[ f ] = index;
}
}
}
// check isolated points vertices against all points map
for ( i = 0, il = isolatedPts.length; i < il; i ++ ) {
face = isolatedPts[ i ];
for ( f = 0; f < 3; f ++ ) {
key = face[ f ].x + ":" + face[ f ].y;
index = allPointsMap[ key ];
if ( index !== undefined ) {
face[ f ] = index;
}
}
}
return triangles.concat( isolatedPts );
}, // end triangulate shapes
更新:我制作了一个SVG http://jsbin.com/ugimab/1,其中有一个多边形具有点(150,150),这是一个弱重复或伪重复。以下展示了表示此多边形的各种方式:
var weakDuplicate1 = [{"X":100,"Y":200},{"X":150,"Y":150},{"X":100,"Y":100},{"X":200,"Y":100},{"X":150,"Y":150},{"X":200,"Y":200}];
var weakDuplicate2 = [100,200, 150,150, 100,100, 200,100, 150,150, 200,200];
var weakDuplicate3 = "M100,200 L150,150 L100,100 L200,100 L150,150 L200,200Z";
更新:如果有人已经成功找到了解决方法来三角化那些具有弱重复点的多边形,如果您能公开您的发现,那将非常有帮助。
更新:测试了选项1,但没有成功:http://jsbin.com/owivew/1。多边形仍然是一个整体,尽管它应该被分成两部分。也许Angus Johnson(Clipper的创建者)有更好的解决方案提供。
更新: 这里有一个更复杂的“简单”多边形(在 Clipper 中简化之后)。所有看起来在一起的点都是完全相同的。要将其分割成真正的简单多边形,需要将其分成片段。我的眼睛说这里有4个底部多边形和一个(更大的)上部多边形,它有一个洞,因此总体上简化会产生5个外多边形和1个洞。或者另外一个外多边形有5个洞。或者可能是其他组合的外围和孔。它可以以许多不同的方式简化。
代码演示在http://jsbin.com/ugimab/3中(也有多边形的 JSON 版本)。
这里是从0到25编号的点:
在图像中,顶点2、11、14、25具有相同的坐标,因此它是一个“伪多重顶点”。顶点3不是重复的,但它与边6-7相接触。更新:
基于移动重复点的建议方法似乎有效。如果用距离重复坐标一定距离的两个点替换重复点,会产生“破碎钢笔尖”效果,三角剖分可以工作,因为产生的多边形是真正的简单多边形,这是三角剖分器的要求。轮廓和孔之间以及孔与孔之间也不允许有重复。下面的图像显示了该方法的效果。距离此处为10px以显示效果,但实际上0.001就足以使多边形简单。另外,Three.js r58中的默认三角剖分器无法按预期工作,但如果将其更改为Poly2tri,则一切都正常。该过程在这份相当长的错误报告中有描述:https://github.com/mrdoob/three.js/issues/3386。