So, some long time ago when ChatGPT first came out, the first really cool thing I somehow made, was my Golden Ticket algorithm.
I’m going to discuss the Golden Ticket code and the production method I used with the original ChatGPT. This is an easy task because my chat history is saved by Open Ai.
The idea for the Golden Ticket algorithm was inspired by a drawing method called Dyson Hatching, which can be learned about here: https://www.redblobgames.com/x/1947-dyson-hatching/. The first step in creating Dyson Hatching, according to the Google, was to first create a: Delaunay mesh.
So, I set off to create Dyson Hatching neural networks and before long I was talking to the new thing: ChatGPT.
By the time I had finished with a ChatGPT chat session, I was able to create Dyson Hatching images, and later, went on to create my Golden Ticket algorithm.
If you are at all curious about the adventure of Dyson Hatching and Golden Ticket, here’s ChatGPT and me, working to chat out the future, more than a year ago.
Nick:
Let’s generate a Delaunay algorithm in C++. We will start with the following code:
int main(){
struct Vertex {
float mX, mY;
std::vector< Vertex* > mConnections;
Vertex(float x, float y)
:mX(x), mY(y)
{}
};
std::vector< Vertex > points(20, { 0,0 });
std::mt19937 random;
std::uniform_real_distribution<float> reals(-1.0, 1.0);
std::generate(points.begin(), points.end(), [&]()->Vertex {
return { reals(random), reals(random) }; });
std::cout << "\nProgram finished\n";
}
ChatGPT:
Sure, we’ll write a simple Delaunay triangulation algorithm. The first step in this is to find the super triangle, which contains all other points. After that, we’ll add each point one by one and locally rearrange the triangles to meet the Delaunay condition.
Here’s a simple implementation:
#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
struct Triangle {
struct Vertex* a;
struct Vertex* b;
struct Vertex* c;
Triangle(Vertex* a, Vertex* b, Vertex* c)
: a(a), b(b), c(c) {}
bool containsVertex(Vertex* v) {
return a == v || b == v || c == v;
}
};
struct Vertex {
float x, y;
std::vector<Vertex*> connections;
Vertex(float x, float y) : x(x), y(y) {}
};
int main() {
std::vector<Vertex> vertices(20);
std::vector<Triangle> triangles;
std::mt19937 random;
std::uniform_real_distribution<float> reals(-1.0, 1.0);
std::generate(vertices.begin(), vertices.end(), [&]()->Vertex {
return { reals(random), reals(random) }; });
// Find super triangle
float minX = vertices[0].x, minY = vertices[0].y;
float maxX = minX, maxY = minY;
for (const auto& vertex : vertices) {
minX = std::min(minX, vertex.x);
minY = std::min(minY, vertex.y);
maxX = std::max(maxX, vertex.x);
maxY = std::max(maxY, vertex.y);
}
float dx = maxX - minX;
float dy = maxY - minY;
float deltaMax = std::max(dx, dy);
float midX = (minX + maxX) / 2;
float midY = (minY + maxY) / 2;
Vertex p1(midX - 20 * deltaMax, midY - deltaMax);
Vertex p2(midX, midY + 20 * deltaMax);
Vertex p3(midX + 20 * deltaMax, midY - deltaMax);
triangles.push_back({&p1, &p2, &p3});
// Add each point one at a time to the triangulation.
for (auto& v : vertices) {
std::vector<Triangle> badTriangles;
std::vector<Edge> polygon;
for (auto& t : triangles) {
if (circumCircleContains(&t, &v)) {
badTriangles.push_back(t);
}
}
// TODO: implement logic to find polygon from badTriangles
// TODO: remove badTriangles from triangles list
// TODO: create new triangles from polygon and v, and add
// them to triangles list
}
// TODO: Remove triangles that contain vertices from the super triangle
std::cout << "\nProgram finished\n";
}
Please note this is a high-level outline of the algorithm and you’ll need to fill in the missing steps, like the circumcircle test (function circumCircleContains), and creating the polygon from bad triangles. These details require more code than fits here.
Nick:
What is the source of the 20 constant in the p1, p2, p3 area?
ChatGPT:
The super triangle is defined by points p1, p2, and p3. These points are deliberately chosen to be very far away from the input points to ensure that they encapsulate all the points that are going to be triangulated. The constant 20 is an arbitrary factor chosen to make sure that the super triangle is sufficiently large.
We take the maximum dimension of the point set (deltaMax) and multiply it by 20 when determining the coordinates of p1, p2, and p3. The 20 is just a safety factor, and it’s assumed that this will be large enough for any reasonable input.
However, this method has its limitations. If your points are extremely spread out or the number 20 is not large enough to encapsulate all points, the super triangle would not include all the points and the algorithm would not function correctly. In such a case, you would need to increase this number or find a better way to compute the bounds of the super triangle.
The coordinates for the super triangle’s vertices are made by taking the midpoint of the bounding box of the input points (midX and midY), and then displacing it by some multiple of the largest dimension of the bounding box. This forms a super triangle that is guaranteed to contain all input points, which is necessary for the algorithm to work.
Nick:
Write circumCircleContains function
ChatGPT:
Sure, here is a basic implementation of the circumCircleContains function. This function checks if a point p lies inside the circumcircle defined by a triangle t.
This function uses the mathematical properties of the circumcircle. For a triangle with vertices (x1, y1), (x2, y2), and (x3, y3), and a point (x, y), the point lies in the circumcircle of the triangle iff the determinant of the following matrix is positive:
|x1 - x y1 - y (x1^2 - x^2 + y1^2 - y^2)|
|x2 - x y2 - y (x2^2 - x^2 + y2^2 - y^2)|
|x3 - x y3 - y (x3^2 - x^2 + y3^2 - y^2)|
Here is the implementation of circumCircleContains in C++:
bool circumCircleContains(Triangle* t, Vertex* p) {
float ax = t->a->x - p->x;
float ay = t->a->y - p->y;
float bx = t->b->x - p->x;
float by = t->b->y - p->y;
float cx = t->c->x - p->x;
float cy = t->c->y - p->y;
float detAB = ax * ax + ay * ay;
float detBC = bx * bx + by * by;
float detCA = cx * cx + cy * cy;
float det = ax * (by * detCA - detBC * cy)
- ay * (bx * detCA - detBC * cx)
+ detAB * (bx * cy - by * cx);
return det > 0;
}
This function calculates the determinant and returns true if the determinant is positive (indicating that the point lies within the circumcircle of the triangle). This is a direct implementation of the mathematical concept.
Nick:
We will make this a method of the triangle object and proceed. What does badTriangles describe?
ChatGPT:
badTriangles refers to a list of triangles that violate Delaunay’s condition after the insertion of a new point into the triangulation.
In the context of a Delaunay triangulation, a triangle is considered “bad” if the new point being inserted into the triangulation falls within its circumcircle. Delaunay’s condition dictates that no point should lie within the circumcircle of any triangle.
So, in each step of the algorithm, for a newly inserted point, you check against each existing triangle in the triangulation. If the new point lies within a triangle’s circumcircle, that triangle is classified as a ‘bad’ triangle and added to the badTriangles list.
These ‘bad’ triangles are later removed and new triangles are created by connecting the new point with the vertices of the polygon formed by the edges of the ‘bad’ triangles (excluding the internal edges between two ‘bad’ triangles).
Therefore, badTriangles is a temporary list that aids in maintaining the Delaunay condition when new points are inserted into the triangulation.
Nick:
So, the initial super triangle created should immediately be rendered bad and worked on? Proceed to implement logic to find polygon from badTriangles
ChatGPT:
Not exactly. The initial super triangle is not immediately considered “bad”. It initially includes all the points in the set. The idea is to begin with a valid triangulation (the super triangle) and then insert one point at a time, maintaining the Delaunay condition at each step.
When a point is inserted, some triangles may become “bad” if they violate the Delaunay condition with respect to this new point. The super triangle might also become “bad” if the new point is within its circumcircle.
After all points have been inserted and the triangulation is complete, any triangles that include vertices from the original super triangle are removed. The super triangle was only a tool for the algorithm, and its edges are not part of the final Delaunay triangulation.
Now, regarding the polygon creation from badTriangles, you are essentially forming the boundary of the hole created by removing all the badTriangles. The boundary edges form a polygon which is used to create new triangles.
This can be implemented as follows:
std::vector<std::pair<Vertex*, Vertex*>> edges;
// Find all edges of bad triangles
for (const auto& triangle : badTriangles) {
edges.push_back({triangle.a, triangle.b});
edges.push_back({triangle.b, triangle.c});
edges.push_back({triangle.c, triangle.a});
}
// Remove duplicates - if an edge appears twice, it's an inner edge and not part of the polygon
std::sort(edges.begin(), edges.end());
std::vector<std::pair<Vertex*, Vertex*>> polygon;
for (int i = 0; i < edges.size(); ++i) {
if (i + 1 == edges.size() || edges[i] != edges[i + 1]) {
polygon.push_back(edges[i]);
} else {
++i; // skip the next edge because it's the same as the current one
}
}
In the above code, we first gather all the edges from all the badTriangles. Since each triangle contributes three edges, some of the edges will be duplicates, as each edge is shared by two triangles. We then sort the edges and iterate through the sorted list, only adding edges to the polygon if they don’t have a duplicate next to them.
Nick:
I don’t understand, the circumcircle of the super triangle contains all vertices, why would the det be <= 0?
ChatGPT begins to hallucinate…
ChatGPT:
Apologies for any confusion. In the implementation provided, we are using a Delaunay condition that checks if a point is within the circumcircle of a triangle. If it is, the determinant would be greater than 0 (as calculated in the circumCircleContains function), and the triangle becomes “bad”.
The super triangle’s circumcircle indeed contains all the vertices initially, but remember that we are inserting points one at a time. So, for the first point that we insert, the super triangle becomes “bad” because this point will fall within its circumcircle. Then the super triangle is divided into smaller triangles that satisfy Delaunay’s condition with respect to this new point.
Each subsequent point insertion could create more “bad” triangles that need to be replaced. This ensures that the Delaunay condition (no other points within the circumcircle of a triangle) is met after each point insertion. The super triangle is merely a tool to kick-start the algorithm and its vertices are not part of the final triangulation.
Nick:
The current circumCircleContains function is not causing the super triangle to become bad, this is an error?
ChatGPT:
I apologize for the confusion. You’re right that the current circumCircleContains function might not always return true for points within the super triangle’s circumcircle due to floating point precision errors, especially when the super triangle is very large.
This happens because the determinant calculation involves subtraction of very large and very small numbers, which can lead to precision loss.
As such, it’s a common practice in Delaunay triangulation implementations to handle the super triangle (and its removal at the end of the triangulation process) as a special case, rather than relying on the circumCircleContains function to always correctly identify it as a bad triangle.
For example, you could mark the super triangle and simply remove it at the end of the process, or you could add a separate check for the super triangle when you’re testing for bad triangles.
Nick:
I mean to say that with the following code:
for (auto& v : vertices) {
std::vector<Triangle> badTriangles;
// std::vector<Edge> polygon;
for (auto& t : triangles) {
if (t.circumCircleContains(&v)) {
badTriangles.push_back(t);
}
}
}
badTriangles is never populated, this seems to be an error
ChatGPT is still hallucinating…
ChatGPT:
I see, thank you for clarifying. I apologize for the confusion. The main problem here is indeed related to floating point precision, as I mentioned earlier, but there’s more to it than that.
The issue is that we are using vertices of the super triangle that are “artificial” and don’t correspond to actual points in the triangulation. When we create a new vertex, its address will not match the address of any of the vertices in the super triangle. Because the containsVertex function checks for pointer equality (i.e., it checks if the addresses match), it will not recognize that the new vertex is within the super triangle.
To fix this, we could adjust the circumCircleContains function to always return true when one of the vertices of the triangle is a vertex of the super triangle. However, a more robust solution would be to rethink the data structure and avoid using these artificial points.
Here’s an alternative approach that might work better:
// Step 1: Generate random points.
std::vector<Vertex> vertices(numPoints);
std::generate(vertices.begin(), vertices.end(), [&](){
return Vertex(reals(random), reals(random)); });
// Step 2: Sort the points lexicographically.
std::sort(vertices.begin(), vertices.end(), [](const Vertex& a, const Vertex& b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
});
// Step 3: Remove duplicates.
vertices.erase(std::unique(vertices.begin(), vertices.end()
, [](const Vertex& a, const Vertex& b) {
return a.x == b.x && a.y == b.y;
}), vertices.end());
// Step 4: Create the super triangle.
float xmin = vertices[0].x, ymin = vertices[0].y;
float xmax = xmin, ymax = ymin;
for (const auto& v : vertices) {
if (v.x < xmin) xmin = v.x;
if (v.y < ymin) ymin = v.y;
if (v.x > xmax) xmax = v.x;
if (v.y > ymax) ymax = v.y;
}
float dx = xmax - xmin, dy = ymax - ymin;
float dmax = std::max(dx, dy);
float xmid = xmin + dx * 0.5f, ymid = ymin + dy * 0.5f;
vertices.push_back(Vertex(xmid - 20 * dmax, ymid - dmax));
vertices.push_back(Vertex(xmid, ymid + 20 * dmax));
vertices.push_back(Vertex(xmid + 20 * dmax, ymid - dmax));
std::vector<Triangle> triangles;
triangles.push_back(Triangle(vertices.size() - 1
, vertices.size() - 2, vertices.size() - 3));
// Now proceed with the Delaunay triangulation, starting from the first point.
The key here is that the vertices of the super triangle are now also part of the vertices array. This ensures that when we add a new vertex to vertices, its address could match the address of a vertex of the super triangle.
This change might require some adjustments in the rest of your code, for example to handle vertices and triangles by index rather than by pointer. But overall, it should make the algorithm more robust and easier to understand.
Remember that you need to remove the super triangle from the final triangulation at the end of the process. With this new approach, you could do this by simply ignoring the last three triangles in the triangles array.
Nick:
Googling, Googling…
I think the issue is that the clockwiseness of the triangle is not being considered
ChatGPT stops hallucinating…
ChatGPT:
Ah, I see. You’re absolutely correct. The orientation of the triangle is important when computing the circumcircle. The determinant calculation assumes that the vertices of the triangle are provided in counterclockwise order. If they are not, it could cause problems and potentially indicate that a point is outside of the circumcircle when it is actually inside.
You could correct for this by ensuring that the vertices of each triangle are ordered counterclockwise when you construct the triangle. Here is a simple way to check the orientation of a triangle:
bool isClockwise(Vertex* a, Vertex* b, Vertex* c) {
return (b->y - a->y) * (c->x - b->x) > (b->x - a->x) * (c->y - b->y);
}
Then, when constructing a triangle, you could use it like this:
if (isClockwise(a, b, c)) {
return Triangle(a, c, b);
} else {
return Triangle(a, b, c);
}
This will ensure that all triangles are counterclockwise, and thus the circumcircle test should work correctly. Remember to apply this to both the initial super triangle and all subsequent triangles you create.
Nick:
OK, we are going to work with clockwise triangles, therefore circumCircleContains returns true if the det is < 0, here is the current code:
#include <iostream>
#include <random>
#include <algorithm>
#include <vector>
int main(){
struct Vertex {
float x, y;
std::vector< Vertex* > connections;
Vertex(float x, float y)
:x(x), y(y)
{}
};
std::vector< Vertex > vertices(20, { 0,0 });
struct Triangle {
Vertex* a{ nullptr };
Vertex* b{ nullptr };
Vertex* c{ nullptr };
Triangle(Vertex* a, Vertex* b, Vertex* c) : a(a), b(b), c(c) {
makeClockwise();
}
bool containsVertex(Vertex* v) {
return a == v || b == v || c == v;
}
bool circumCircleContains(Vertex* p) {
//must be clockwise
float ax = a->x - p->x;
float ay = a->y - p->y;
float bx = b->x - p->x;
float by = b->y - p->y;
float cx = c->x - p->x;
float cy = c->y - p->y;
float detAB = ax * ax + ay * ay;
float detBC = bx * bx + by * by;
float detCA = cx * cx + cy * cy;
float det = ax * (by * detCA - detBC * cy)
- ay * (bx * detCA - detBC * cx)
+ detAB * (bx * cy - by * cx);
return det < 0;
}
bool isClockwise(Vertex* a, Vertex* b, Vertex* c) {
return (b->y - a->y) * (c->x - b->x) > (b->x - a->x) * (c->y - b->y);
}
void makeClockwise() {
if (!isClockwise(a, b, c))
std::swap(b, c);
}
};
std::vector< Triangle > triangles;
std::mt19937 random;
std::uniform_real_distribution<float> reals(-1.0, 1.0);
std::generate(vertices.begin(), vertices.end(), [&]()->Vertex {
return { reals(random), reals(random) }; });
// Find super triangle
float minX = vertices[0].x, minY = vertices[0].y;
float maxX = minX, maxY = minY;
for (const auto& vertex : vertices) {
minX = std::min(minX, vertex.x);
minY = std::min(minY, vertex.y);
maxX = std::max(maxX, vertex.x);
maxY = std::max(maxY, vertex.y);
}
float dx = maxX - minX;
float dy = maxY - minY;
float deltaMax = std::max(dx, dy);
float midX = (minX + maxX) / 2;
float midY = (minY + maxY) / 2;
Vertex p1(midX - 20 * deltaMax, midY - deltaMax);
Vertex p2(midX, midY + 20 * deltaMax);
Vertex p3(midX + 20 * deltaMax, midY - deltaMax);
triangles.push_back( { &p1, &p2, &p3 } );
for (auto& v : vertices) {
std::vector<Triangle> badTriangles;
// std::vector<Edge> polygon;
for (auto& t : triangles) {
if (t.circumCircleContains(&v)) {
badTriangles.push_back(t);
}
}
// TODO: implement logic to find polygon from badTriangles
// TODO: remove badTriangles from triangles list
// TODO: create new triangles from polygon and v, and add
// them to triangles list
}
// TODO: Remove triangles that contain vertices from the
// super triangle
std::cout << "\nProgram finished\n";
}
This lengthy work is going to be completed in a series of exciting segments, until next time, for the next TODO.
Spot C++ 