bl4ckb0ne / delaunay-triangulation Goto Github PK

Would be nice to download catch2's header at the build generation step if it is not found on the system.

Check wrapdb maybe.

It would be nice to have support for doubles instead of just floats.

I'm not sure what the form should be (should it be an extra class where you can give the type you want when you create it? Should the original class definition be changed so that you specify a type?). I'm using this for a project of mine and I ran into round-off issues with using floats, so I changed all occurrences to doubles.

Hello, all the header files fail to compile to lines that use this declaration:
static_assert(std::is_floating_point<Vector2::Type>::value, "Type must be floating-point");

with the following error:
'std::is_floating_point': 'dt::Vector2::Type' is not a valid template type argument for parameter '_Ty' d:\programming\delaunay-triangulation-master\dt_test\dt_test\vector2.h

Any idea how to fix it? Thanks

I imagine most people are using this to make a 3D mesh, not just trying to plot the result, and as such it would be nice to know which points in the input array make up each triangle. For example, if I know the input points are (0, 2) (.4, 0) (-.4, 0) (0, -2), I can run the algorithm and get two triangles. Suppose it tells me that the triangles are
(.4, 0) (-.4, 0) (0, -2) and (0, 2) (.4, 0) (-.4, 0). That's enough to draw lines, but if my goal is to tell OpenGL or something how to triangulate my points with an indexed VBO, I's like the answer in this form: 2,3,4 and 1,2,3. This allows me to reference the original vertex arrays if I want by iterating over the indices and doing vert[2], vert[3], vert[4].

I've tried doing pointer subtraction between the vertices array (both the original and the one owned by the Delauney class) and I'm getting out of bounds numbers:
for (const auto& tri : triangles) {
int index = tri.a - triangulation.getVertices();
// or
int index = std::distance(triangulation.getVertices(), tri.a);
}
I get negative numbers and things that indicate that the pointer doesn't point into that vector. If I'm not mistaken, I have to do a linear search through all of the input vertices for each point in the triangle and do floating point comparison to figure out the index. A linear search through each of the 4 points isn't a big deal, but O(N^2) isn't cool if I have a million. Am I missing something?

Thanks for writing this library, it does most of the heavy lifting for what I need.

Hi

I am developing c++ in windows and compiling your code by g++ in minGW. I have also downloaded SFML and placed inside the folder of the code. But I got an error say,

fatal error: SFML/Graphics.hpp: No such file or directory
#include < SFML/Graphics.hpp >
"compilation terminated."
"make: *** [main.o] Error 1"

I think I did not know where I should set the path to this header file. Do you know any idea?

May I compile the code in Visual Studio in windows?

One more question is that how long does it take to triangulate for 1 million points?

Thank you for your help in advance.

Hieu

#22 caused a few bugs

hi!
I run the program in VS2012，there are some problems In the following procedures
for(auto e = begin(edges); e != end(edges); e++)
{
lines.push_back({{
sf::Vertex(sf::Vector2f((_e).p1.x + 2, (_e).p1.y + 2)),
sf::Vertex(sf::Vector2f((_e).p2.x + 2, (_e).p2.y + 2))
}}
);
}
error：std::vector<_Ty>::push_back No overloaded functions to accept 0 parameters
Syntax error
can this code be run under VS2012? if not ,what should i do?
Thank you for your time and forgive me for interrupting！
Looking forward to your reply！
—— cassy

https://mesonbuild.com/

Reduces compilation time, increases precision, remove template overhead.

Hi,

Very nice work, I had to implement it recently for a school project and I have to say yours is way cleaner ^^

But I think there is a little bug, when I created a Visual Studio 2015 project, after I added SFML, I still had one error with std::array, and adding #include <array> on top of main.cpp fixed it.

how to build this program. No make file in it, so how we run the make command

Hi,

I use an older version of this library in my project LibrePCB and I was able to use qreal as template argument. The typedef qreal is provided by Qt and usually equals to double, but for embedded targets with only a single-precision FPU it might equal to float for performance reasons. This is very handy for application developers since we don't have to care much about this topic, just always use qreal for floating point operations and it should be working fine.

But now I'd like to update to the latest version of this library and realized that the template parameter was removed, so it's no longer possible to use qreal resp. float. That's a real pity...

Do you see any chance to revert this change so the library gets useful again for platforms with single-precision FPU?

Thanks!

This test:

TEST_CASE( "Delaunay triangulation should be able to handle 3 almost colinear points", "[DelaunayTest]" ) {
	std::vector<Vector2<double>> points;
	points.push_back(Vector2<double>{0.0, 0.0});
	points.push_back(Vector2<double>{1000.0, 0.0});
	points.push_back(Vector2<double>{2000.0, 40.0});
	Delaunay<double> triangulation;
	const std::vector<Triangle<double>> triangles = triangulation.triangulate(points);
	REQUIRE(1 == triangles.size());
}

Fails because no triangle is found. Note that this is just one example - it's very easy to interactively generate arbitrary input data which doesn't get triangulated properly. It also happens with more than three points, then some triangles are generated, but some of the points are left unconnected.

Although three colinear points are not a valid triangle, I still see two critical issues:

1. Compared to floating point accuracy, these points are not really almost a triangle. It's even obvious for a human eye that this is a totally valid triangle:
   
2. The library does not report any failure if it did not connect some of the input points. Depending on the use case, it is extremely important to know if the triangulation failed (e.g. to use an alternative fallback algorithm to still handle all points somehow). But the library silently ignores some of the input points so the user is not able to detect and handle this situation properly.

For example, a test case from: delaunay-triangulation/tests/tests.cpp:

TEST_CASE("Delaunay triangulation should be able to handle 10000 points as float", "[DelaunayTest]") {
    std::vector<Vector2<float> > points(1e4);
    srand(666);
    for (size_t i=0; i < 1e4; ++i)
    {
        float x = (float)rand() / (float)RAND_MAX;
        float y = (double)rand() / (float)RAND_MAX;
        points.at(i) = Vector2<float>(x, y);
    }
    REQUIRE(10000 == points.size());
    Delaunay<float> triangulation;
    const std::vector<Triangle<float> > triangles = triangulation.triangulate(points);
}

Why not test the result, including const std::vector<Triangle<float> > triangles? The test case only guarantees that there is no run-time error but not the correctness of the triangulation result.

Considering the size of vector2.h, numeric.h, triangle.h and edge.h, these could fit into delaunay.h easily and would allow people to easily add delaunay.h to their projects without dragging four other header files with it.

Hi,
I liked your library and I added how to get indices so that people use OpenGL or DirectX Get Benefits.

	                int index = 0;
			for (auto p = begin(vertices); p != end(vertices); p++)
			{
				Vector2<float> f = *p;
				if (coordinate_indices.find(f) == coordinate_indices.end()) {
					coordinate_indices[f] = index++;
					indx.push_back(index);
				}

			}

		std::map<VertexType, unsigned int> coordinate_indices;

void writeObj(std::string &name)
		{
			std::ofstream objFile;
			objFile.open(name);
			objFile << "o " << "mesh" << "\n";
			for (auto p = begin(getVertices()); p != end(getVertices()); p++)
			{
				Vector2<float> f = *p;
				objFile << "v " << f.x << " " << f.y << "\n";
			}
			for (auto t = begin(getTriangles()); t != end(getTriangles()); t++) {

				Vector2<float> t1 = t->p1;
				Vector2<float> t2 = t->p2;
				Vector2<float> t3 = t->p3;

				int index1 = coordinate_indices[t1] + 1;
				int index2 = coordinate_indices[t2] + 1;
				int index3 = coordinate_indices[t3] + 1;

				objFile << "f " << index1 << " " << index2 << " " << index3 << "\n";
			}
			objFile.close();

I try to embed it into some algorithms, but the experimental time/#points result of this library is ~O(n^3), (e.g: ~30s for ~2000 pts), which is not fast enough compared to others . But this library is good as no dependency at all.