Comments (9)
Thanks - when you say "don't work", do you mean it crashes or you get the wrong output? Any chance you can toss a few screenshots in?
from manifold.
@elalish My apologies, I've been looking at it too long.
By fail, I mean incorrect output... if you run the script, it will produce test.svg which will show you an incorrect result.
With segment size fixed, the number of verts should be the same no matter what the x, y or radius.
The working ones have 40 (proper for 36 segments). The broken ones have a number of verts other than 40.
from manifold.
Here's a screen shot from the _save_svg in the code above.
from manifold.
I wouldn't bet on having exactly the same number of verts - floating point error, etc. But those big gouges look like a serious problem. We use quickhull for this, so maybe an upstream bug? There's also been talk of switching to a better dependency for more numerically-stable hulls - this may be good impetus.
from manifold.
You use quick hull for a 3D hull. The example I am giving is 2D as is written in cross_section.cpp.
It is not a part of Clipper2.
Here's an implementation I made of a Graham scan for CSharpCAD.
I use a fake atan2 which greatly speeds the algorithm.
namespace CSharpCAD;
public static partial class CSCAD
{
private class pt
{
internal readonly Vec2 point;
internal readonly double angle;
internal readonly double distSq;
internal pt(Vec2 point, double angle, double distSq)
{
this.point = point;
this.angle = angle;
this.distSq = distSq;
}
};
/*
* Create a convex hull of the given geom2 geometries.
* Uses https://en.wikipedia.org/wiki/Graham_scan
*/
internal static Geom2 HullGeom2(params Geom2[] geometries)
{
// Extract unique points from the geometries.
// To avoid a second pass, also determine the minimum point.
var uniquePoints = new HashSet<Vec2>();
var min = new Vec2(double.PositiveInfinity, double.PositiveInfinity);
foreach (var g in geometries)
{
var outlines = g.ToOutlines();
foreach (var outline in outlines)
{
foreach (var point in outline)
{
uniquePoints.Add(point);
if (point.Y < min.Y || (point.Y == min.Y && point.X < min.X))
{
min = point;
}
}
}
}
// Returned "angle" is really 1/tan (inverse of slope) made negative to increase with angle.
// This function is strictly for sorting in this algorithm.
double fakeAtan2(double y, double x)
{
// The "if" is a special case for when the minimum vector found in loop above is present.
// We need to insure that it sorts as the minimum point. Otherwise this becomes NaN.
if (y == 0 && x == 0) { return double.NegativeInfinity; }
return -(x / y);
}
// Gather information for sorting by polar coordinates.
var points = new List<pt>(uniquePoints.Count);
foreach (var v in uniquePoints)
{
// Use of fakeAtan2 avoids use of Math.Atan2 which slows things down.
// A simple timing test suggests it saves about 10% of total time.
var angle = fakeAtan2((v.Y - min.Y), (v.X - min.X));
//var angle = Math.Atan2((v.Y - min.Y), (v.X - min.X));
var distSq = min.SquaredDistance(v);
points.Add(new pt(v, angle, distSq));
}
points.Sort((pt pt1, pt pt2) => pt1.angle < pt2.angle ? -1 : pt1.angle > pt2.angle ? 1 :
pt1.distSq < pt2.distSq ? -1 : pt1.distSq > pt2.distSq ? 1 : 0);
// ccw returns: < 0 clockwise, 0 colinear, > 0 counter-clockwise.
double ccw(Vec2 v1, Vec2 v2, Vec2 v3) => (v2.X - v1.X) * (v3.Y - v1.Y) - (v2.Y - v1.Y) * (v3.X - v1.X);
var stack = new List<Vec2>(); // Start with empty stack
foreach (var point in points)
{
var cnt = stack.Count;
while (cnt > 1 && ccw(stack[cnt - 2], stack[cnt - 1], point.point) <= C.EPSILON)
{
stack.RemoveAt(stack.Count - 1); // Pop - gets rid of colinear and interior (clockwise) points.
cnt = stack.Count;
}
stack.Add(point.point); // Push
}
if (stack.Count < 3) return new Geom2();
return new Geom2(stack);
}
}
from manifold.
Actually, that would be the fault of the simple 2D hull algorithm (or my porting of it) used in CrossSection
, we don't use quickhull there. I don't have time to contribute to a fix for it right now though unfortunately.
from manifold.
Ah, good to know. Well, now that we have quickhull as a dependency, perhaps we should switch to that (assuming it does 2D as well as 3D?). Or whatever other dependency we decide to switch to. I'd rather not maintain our own 2D hulling code if I can avoid it.
from manifold.
@elalish QuickHull is 3D only. The 2D algorithm is simple as you can see above. If you like I can take a stab at a PR.
from manifold.
Yeah, ideally see if you can fix our existing code, rather than replace it wholesale, but whatever works. Thanks!
from manifold.
Related Issues (20)
- Python created object reports as non-manifold. HOT 3
- Watertightness of Mesh with an Edge Shared by 4 Faces
- vertex halfedge iterator
- Manifold 2.4.5 release tar.gz is incomplete HOT 3
- Vec out of Range HOT 8
- Python binding needs two import call HOT 4
- Manifold Decompose doesn't preserve vertex properties HOT 4
- memory leak when TBB and PSTL is enabled HOT 27
- Triangulate bug: Two separate polygons HOT 5
- [Question] robust geometric predicates, polygon triangulation
- Warning comparison of integer expressions of different signedness
- Modularize Manifold HOT 25
- Build without exceptions HOT 3
- Remove Thrust HOT 19
- How to figure out required size of mem in the C-API? HOT 1
- Crash in Project() HOT 4
- gcc14 build failure HOT 7
- Triangulation issue: Zebra HOT 3
- BSD compiler error HOT 1
- Another Zebra Triangulation issue HOT 6
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from manifold.