How to discretize an Ellipse or Circle to a Polygon using C++ Graphics?
Why discretize an ellipse to a polygon?
- Rendering Curves: Curves cannot be rendered directly on the screen. They first need to be approximated to polygons (in case of Circles and ellipses) or chained-line-segments (in case of Bezier curves and splines) and discretization serves that purpose! *
- Collision-Detection: While checking intersection for curves like Circle and Bezier curve is simple, some curves like Ellipses are way too complicated and checking intersection for them precisely is very inefficient! Hence they are first discretized to simple shapes like rectangle, polygon, etc for which collision can be detected efficiently!
* While one can render curves pixel by pixel with Bresengham’s algorithm, it is often not the best practice! Since modern GPUs have become much more powerful they can render a series of the pixel without any bloat! Also drawing any curve pixel by pixel strips any possibility of batching and GPU “memorization”! And because of the way modern CPUs work trigonometric functions are no longer “computationally expensive” (atleast most of the time)!
Proof-of-concept:
pair
Rendering Polygons:
#include <algorithm> #include <graphics.h> using namespace std; typedef pair<int, int> vertex; void polygon(vector<vertex>& vertices) { for (int i = 0, n = vertices.size(); i < n; i++) { vertex current = vertices[i], next; next = vertices[(i == n - 1) ? 0 : i + 1]; int x1 = current.first, y1 = current.second; int x2 = next.first, y2 = next.second; line(x1, y1, x2, y2); } } // Driver code int main() { int gd = DETECT, gm; // initialize graphics library initgraph(&gd, &gm, ""); vector<vertex> vertices; vertices.push_back(vertex(340, 150)); vertices.push_back(vertex(220, 250)); vertices.push_back(vertex(340, 350)); polygon(vertices); delay(5000); } |
Output:
Discretizing Ellipse to Polygon:
#define TWO_PI 44 / 7.0f vector<vertex> discretizeEllipse( int x, int y, int a, int b, int seg) { float angle_shift = TWO_PI / seg, phi = 0; vector<vertex> vertices; for (int i = 0; i < seg; ++i) { phi += angle_shift; vertices .push_back( vertex( x + a * cos(phi), y + b * sin(phi))); } return vertices; } |
overload
segments
vector<vertex> discretizeEllipse( int x, int y, int a, int b) { int segments = max((int)floor( sqrt(((a + b) / 2) * 20)), 8); return discretizeEllipse( x, y, a, b, segments); } |
#include <algorithm> #include <graphics.h> #define TWO_PI 44 / 7.0f typedef pair<int, int> vertex; void polygon(vector<vertex> vertices) { for (int i = 0, n = vertices.size(); i < n; i++) { vertex current = vertices[i], next; next = vertices[(i == n - 1) ? 0 : i + 1]; int x1 = current.first, y1 = current.second; int x2 = next.first, y2 = next.second; line(x1, y1, x2, y2); } } vector<vertex> discretizeEllipse( int x, int y, int a, int b, int seg) { float angle_shift = TWO_PI / seg, phi = 0; vector<vertex> vertices; for (int i = 0; i < seg; ++i) { phi += angle_shift; vertices.push_back( vertex( x + a * cos(phi), y + b * sin(phi))); } return vertices; } vector<vertex> discretizeEllipse( int x, int y, int a, int b) { int segments = max((int)floor( sqrt(((a + b) / 2) * 20)), 8); return discretizeEllipse( x, y, a, b, segments); } int main() { int gd = DETECT, gm; // initialize graphics library initgraph(&gd, &gm, ""); polygon(discretizeEllipse(320, 240, 200, 100)); polygon(discretizeEllipse(320, 240, 200, 100, 8)); delay(5000); } |
Output:
Contact Us