En este artículo, veremos cómo discretizar una elipse (o un círculo) en un polígono. Dado que un círculo es solo un caso específico de una elipse, ¡no discutiremos por separado cómo discretizar un círculo en un polígono!
¿Por qué discretizar una elipse a un polígono?
La discretización tiene varias aplicaciones, siendo las dos más importantes:
- Representación de curvas: las curvas no se pueden representar directamente en la pantalla. Primero deben aproximarse a polígonos (en el caso de círculos y elipses) o segmentos de línea enstringdos (en el caso de curvas Bézier y splines) y la discretización cumple ese propósito. *
- Detección de colisiones: mientras que verificar la intersección de curvas como Circle y Bezier curve es simple, algunas curvas como Ellipses son demasiado complicadas y verificar la intersección con precisión es muy ineficiente. Por lo tanto, primero se discretizan en formas simples como rectángulo, polígono, etc., ¡para las cuales la colisión se puede detectar de manera eficiente!
* Si bien uno puede representar curvas píxel por píxel con el algoritmo de Bresengham, ¡a menudo no es la mejor práctica! ¡Dado que las GPU modernas se han vuelto mucho más poderosas, pueden renderizar una serie de píxeles sin ninguna hinchazón! ¡También dibujar cualquier curva píxel por píxel elimina cualquier posibilidad de procesamiento por lotes y «memorización» de GPU! ¡Y debido a la forma en que funcionan las CPU modernas, las funciones trigonométricas ya no son «computacionalmente costosas» (al menos la mayor parte del tiempo)!
Prueba de concepto: Entonces, la idea principal de discretizar una elipse es dividir la elipse en vértices que representan un polígono, por lo que el número de segmentos del polígono se calcularía automáticamente o lo daría el usuario del cliente. Para este ejemplo, ¡no calcularemos el número de segmentos automáticamente!
Usaremos la API de gráficos de C Borland, ¡pero los mismos principios se pueden aplicar a cualquier biblioteca de gráficos! ¡ Los usuarios de Linux pueden querer usar SDL libgraph como reemplazo de Borland Graphics Library! ¡También usaremos C++ en lugar de C para usar la estructura de pairdatos incorporada que proporciona STL (y también para la sobrecarga de funciones que será útil más adelante)!
Representación de polígonos:
¡Resulta que la API de gráficos de Borland en realidad no tiene una función de representación de polígonos multiformato como la que tienen las bibliotecas de gráficos modernas! Hay drawPoly y fillPoly, pero la representación del polígono puede no tener sentido para algunas personas y también puede conducirnos a algunos problemas con el puntero. ¡Así que implementaremos nuestra propia función de renderizado de polígonos! ¡Representaremos un polígono como un vector de pares de enteros que representan los vértices del polígono! El principal beneficio de esto es que un vector siempre sabe su tamaño, a diferencia de las arrays que, bajo el capó, son solo un puntero desconocido de sus límites.
En cualquier caso, aquí está nuestro código para renderizar un polígono en la Biblioteca de gráficos de Borland:
#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);
}
Producción:
Discretizando Elipse a Polígono:
¡Ahora que podemos renderizar polígonos, estamos listos para convertir una elipse en un polígono!
Entonces, la clave para discretizar una elipse es tener un punto móvil que se mueva a través de la elipse en intervalos iguales y crear un vértice en cada punto (¡cada punto por donde pasa el punto móvil)! Para esto, se debe conocer la forma paramétrica de una elipse, que es: –
Basado en la fórmula anterior, aquí está el fragmento de código que discretiza nuestra elipse en un polígono:
#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;
}
¡Lo último que queda por hacer es sobrecargar la función de manera que el último parámetro no sea necesario! Podemos establecer segmentsun valor predeterminado, ¡pero nos gustaría que se calculara en función de las dimensiones de la elipse! Así que aquí está la segunda sobrecarga: –
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);
}
Para finalizar este artículo, aquí está el código fuente completo:
#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);
}
Producción: