El algoritmo de elipse de punto medio se utiliza para dibujar una elipse en gráficos por computadora.
Consulte también: algoritmo de línea de punto medio , algoritmo de círculo de punto medio
El algoritmo de elipse de punto medio traza (encuentra) puntos de una elipse en el primer cuadrante dividiendo el cuadrante en dos regiones.
Luego, cada punto (x, y) se proyecta en otros tres cuadrantes (-x, y), (x, -y), (-x, -y), es decir, usa simetría de 4 vías.
Función de la elipse:
f elipse (x, y)=r y 2 x 2 +r x 2 y 2 -r x 2 r y 2
f elipse (x, y)<0 entonces (x, y) está dentro de la elipse.
f elipse (x, y)>0 entonces (x, y) está fuera de la elipse.
f elipse (x, y)=0 entonces (x, y) está en la elipse.
Parámetro de decisión:
Inicialmente, tenemos dos parámetros de decisión p1 0 en la región 1 y p2 0 en la región 2.
Estos parámetros se definen como: p1 0 en la región 1 se da como:
p1 0 =r y 2 +1/4r x 2 -r x 2 r y
Algoritmo de elipse de punto medio:
- Tome el radio de entrada a lo largo del eje x y el eje y y obtenga el centro de la elipse.
- Inicialmente, asumimos que la elipse está centrada en el origen y el primer punto como: (x, y 0 )= (0, r y ).
- Obtenga el parámetro de decisión inicial para la región 1 como: p1 0 =r y 2 +1/4r x 2 -r x 2 r y
- Para cada posición de x k en la región 1:
si p1 k <0, entonces el siguiente punto a lo largo de es (x k+1 , y k ) y p1 k+1 =p1 k +2r y 2 x k+1 +r y 2
Si no, el siguiente punto es (x k+1 , y k-1 )
Y p1 k+1 =p1 k +2r y 2 x k+1 – 2r x 2 y k+1 +r y 2 - Obtenga el valor inicial en la región 2 usando el último punto (x 0 , y 0 ) de la región 1 como: p2 0 =r y 2 (x 0 +1/2) 2 +r x 2 (y 0 -1) 2 – r x 2 r y 2
- En cada y k en la región 2 a partir de k = 0 realice la siguiente tarea.
Si p2 k >0 el siguiente punto es (x k , y k-1 ) y p2 k+1 =p2 k -2r x 2 y k+1 +r x 2 - De lo contrario, el siguiente punto es (x k+1 , y k -1 ) y p2 k+1 =p2 k +2r y 2 x k+1 -2r x 2 y k+1 +r x 2
- Ahora obtenga los puntos simétricos en los tres cuadrantes y trace el valor de las coordenadas como: x=x+xc, y=y+yc
- Repita los pasos para la región 1 hasta 2r y 2 x>=2r x 2 y
Implementación:
C++
// C++ program for implementing
// Mid-Point Ellipse Drawing Algorithm
#include <bits/stdc++.h>
using namespace std;
void midptellipse(int rx, int ry,
int xc, int yc)
{
float dx, dy, d1, d2, x, y;
x = 0;
y = ry;
// Initial decision parameter of region 1
d1 = (ry * ry) - (rx * rx * ry) +
(0.25 * rx * rx);
dx = 2 * ry * ry * x;
dy = 2 * rx * rx * y;
// For region 1
while (dx < dy)
{
// Print points based on 4-way symmetry
cout << x + xc << " , " << y + yc << endl;
cout << -x + xc << " , " << y + yc << endl;
cout << x + xc << " , " << -y + yc << endl;
cout << -x + xc << " , " << -y + yc << endl;
// Checking and updating value of
// decision parameter based on algorithm
if (d1 < 0)
{
x++;
dx = dx + (2 * ry * ry);
d1 = d1 + dx + (ry * ry);
}
else
{
x++;
y--;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d1 = d1 + dx - dy + (ry * ry);
}
}
// Decision parameter of region 2
d2 = ((ry * ry) * ((x + 0.5) * (x + 0.5))) +
((rx * rx) * ((y - 1) * (y - 1))) -
(rx * rx * ry * ry);
// Plotting points of region 2
while (y >= 0)
{
// Print points based on 4-way symmetry
cout << x + xc << " , " << y + yc << endl;
cout << -x + xc << " , " << y + yc << endl;
cout << x + xc << " , " << -y + yc << endl;
cout << -x + xc << " , " << -y + yc << endl;
// Checking and updating parameter
// value based on algorithm
if (d2 > 0)
{
y--;
dy = dy - (2 * rx * rx);
d2 = d2 + (rx * rx) - dy;
}
else
{
y--;
x++;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d2 = d2 + dx - dy + (rx * rx);
}
}
}
// Driver code
int main()
{
// To draw a ellipse of major and
// minor radius 15, 10 centered at (50, 50)
midptellipse(10, 15, 50, 50);
return 0;
}
// This code is contributed
// by Akanksha Rai
C
// C program for implementing
// Mid-Point Ellipse Drawing Algorithm
#include <stdio.h>
void midptellipse(int rx, int ry, int xc, int yc)
{
float dx, dy, d1, d2, x, y;
x = 0;
y = ry;
// Initial decision parameter of region 1
d1 = (ry * ry)
- (rx * rx * ry)
+ (0.25 * rx * rx);
dx = 2 * ry * ry * x;
dy = 2 * rx * rx * y;
// For region 1
while (dx < dy) {
// Print points based on 4-way symmetry
printf("(%f, %f)\n", x + xc, y + yc);
printf("(%f, %f)\n", -x + xc, y + yc);
printf("(%f, %f)\n", x + xc, -y + yc);
printf("(%f, %f)\n", -x + xc, -y + yc);
// Checking and updating value of
// decision parameter based on algorithm
if (d1 < 0) {
x++;
dx = dx + (2 * ry * ry);
d1 = d1 + dx + (ry * ry);
}
else {
x++;
y--;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d1 = d1 + dx - dy + (ry * ry);
}
}
// Decision parameter of region 2
d2 = ((ry * ry) * ((x + 0.5) * (x + 0.5)))
+ ((rx * rx) * ((y - 1) * (y - 1)))
- (rx * rx * ry * ry);
// Plotting points of region 2
while (y >= 0) {
// printing points based on 4-way symmetry
printf("(%f, %f)\n", x + xc, y + yc);
printf("(%f, %f)\n", -x + xc, y + yc);
printf("(%f, %f)\n", x + xc, -y + yc);
printf("(%f, %f)\n", -x + xc, -y + yc);
// Checking and updating parameter
// value based on algorithm
if (d2 > 0) {
y--;
dy = dy - (2 * rx * rx);
d2 = d2 + (rx * rx) - dy;
}
else {
y--;
x++;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d2 = d2 + dx - dy + (rx * rx);
}
}
}
// Driver code
int main()
{
// To draw a ellipse of major and
// minor radius 15, 10 centered at (50, 50)
midptellipse(10, 15, 50, 50);
return 0;
}
Java
// Java program for implementing
// Mid-Point Ellipse Drawing Algorithm
import java.util.*;
import java.text.DecimalFormat;
class GFG
{
static void midptellipse(float rx, float ry,
float xc, float yc)
{
float dx, dy, d1, d2, x, y;
x = 0;
y = ry;
// Initial decision parameter of region 1
d1 = (ry * ry) - (rx * rx * ry) +
(0.25f * rx * rx);
dx = 2 * ry * ry * x;
dy = 2 * rx * rx * y;
DecimalFormat df = new DecimalFormat("#,###,##0.00000");
// For region 1
while (dx < dy)
{
// Print points based on 4-way symmetry
System.out.println(df.format((x + xc)) +
", "+df.format((y + yc)));
System.out.println(df.format((-x + xc)) +
", "+ df.format((y + yc)));
System.out.println(df.format((x + xc)) +
", "+ df.format((-y + yc)));
System.out.println(df.format((-x + xc)) +
", "+df.format((-y + yc)));
// Checking and updating value of
// decision parameter based on algorithm
if (d1 < 0)
{
x++;
dx = dx + (2 * ry * ry);
d1 = d1 + dx + (ry * ry);
}
else
{
x++;
y--;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d1 = d1 + dx - dy + (ry * ry);
}
}
// Decision parameter of region 2
d2 = ((ry * ry) * ((x + 0.5f) * (x + 0.5f)))
+ ((rx * rx) * ((y - 1) * (y - 1)))
- (rx * rx * ry * ry);
// Plotting points of region 2
while (y >= 0) {
// printing points based on 4-way symmetry
System.out.println(df.format((x + xc)) +
", " + df.format((y + yc)));
System.out.println(df.format((-x + xc)) +
", "+ df.format((y + yc)));
System.out.println(df.format((x + xc)) +
", " + df.format((-y + yc)));
System.out.println(df.format((-x + xc)) +
", " + df.format((-y + yc)));
// Checking and updating parameter
// value based on algorithm
if (d2 > 0) {
y--;
dy = dy - (2 * rx * rx);
d2 = d2 + (rx * rx) - dy;
}
else {
y--;
x++;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d2 = d2 + dx - dy + (rx * rx);
}
}
}
// Driver code
public static void main(String args[])
{
// To draw a ellipse of major and
// minor radius 15, 10 centered at (50, 50)
midptellipse(10, 15, 50, 50);
}
}
// This code is contributed by
// Surendra_Gangwar
Python3
# Python3 program for implementing
# Mid-Point Ellipse Drawing Algorithm
def midptellipse(rx, ry, xc, yc):
x = 0;
y = ry;
# Initial decision parameter of region 1
d1 = ((ry * ry) - (rx * rx * ry) +
(0.25 * rx * rx));
dx = 2 * ry * ry * x;
dy = 2 * rx * rx * y;
# For region 1
while (dx < dy):
# Print points based on 4-way symmetry
print("(", x + xc, ",", y + yc, ")");
print("(",-x + xc,",", y + yc, ")");
print("(",x + xc,",", -y + yc ,")");
print("(",-x + xc, ",", -y + yc, ")");
# Checking and updating value of
# decision parameter based on algorithm
if (d1 < 0):
x += 1;
dx = dx + (2 * ry * ry);
d1 = d1 + dx + (ry * ry);
else:
x += 1;
y -= 1;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d1 = d1 + dx - dy + (ry * ry);
# Decision parameter of region 2
d2 = (((ry * ry) * ((x + 0.5) * (x + 0.5))) +
((rx * rx) * ((y - 1) * (y - 1))) -
(rx * rx * ry * ry));
# Plotting points of region 2
while (y >= 0):
# printing points based on 4-way symmetry
print("(", x + xc, ",", y + yc, ")");
print("(", -x + xc, ",", y + yc, ")");
print("(", x + xc, ",", -y + yc, ")");
print("(", -x + xc, ",", -y + yc, ")");
# Checking and updating parameter
# value based on algorithm
if (d2 > 0):
y -= 1;
dy = dy - (2 * rx * rx);
d2 = d2 + (rx * rx) - dy;
else:
y -= 1;
x += 1;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d2 = d2 + dx - dy + (rx * rx);
# Driver code
# To draw a ellipse of major and
# minor radius 15, 10 centered at (50, 50)
midptellipse(10, 15, 50, 50);
# This code is contributed by chandan_jnu
C#
// C# program for implementing
// Mid-Point Ellipse Drawing Algorithm
using System;
class GFG
{
static void midptellipse(double rx, double ry,
double xc, double yc)
{
double dx, dy, d1, d2, x, y;
x = 0;
y = ry;
// Initial decision parameter of region 1
d1 = (ry * ry) - (rx * rx * ry) +
(0.25f * rx * rx);
dx = 2 * ry * ry * x;
dy = 2 * rx * rx * y;
// For region 1
while (dx < dy)
{
// Print points based on 4-way symmetry
Console.WriteLine(String.Format("{0:0.000000}",
(x + xc)) + ", "+String.Format
("{0:0.000000}",(y + yc)));
Console.WriteLine(String.Format("{0:0.000000}",
(-x + xc)) + ", "+ String.Format
("{0:0.000000}",(y + yc)));
Console.WriteLine(String.Format("{0:0.000000}",
(x + xc)) + ", "+String.Format
("{0:0.000000}",(-y + yc)));
Console.WriteLine(String.Format("{0:0.000000}",
(-x + xc)) +", "+String.Format
("{0:0.000000}",(-y + yc)));
// Checking and updating value of
// decision parameter based on algorithm
if (d1 < 0)
{
x++;
dx = dx + (2 * ry * ry);
d1 = d1 + dx + (ry * ry);
}
else
{
x++;
y--;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d1 = d1 + dx - dy + (ry * ry);
}
}
// Decision parameter of region 2
d2 = ((ry * ry) * ((x + 0.5f) * (x + 0.5f)))
+ ((rx * rx) * ((y - 1) * (y - 1)))
- (rx * rx * ry * ry);
// Plotting points of region 2
while (y >= 0)
{
// printing points based on 4-way symmetry
Console.WriteLine(String.Format("{0:0.000000}",
(x + xc)) + ", " + String.Format
("{0:0.000000}",(y + yc)));
Console.WriteLine(String.Format("{0:0.000000}",
(-x + xc)) + ", "+ String.Format
("{0:0.000000}",(y + yc)));
Console.WriteLine(String.Format("{0:0.000000}",
(x + xc)) + ", " + String.Format
("{0:0.000000}",(-y + yc)));
Console.WriteLine(String.Format("{0:0.000000}",
(-x + xc)) + ", " + String.Format
("{0:0.000000}",(-y + yc)));
// Checking and updating parameter
// value based on algorithm
if (d2 > 0)
{
y--;
dy = dy - (2 * rx * rx);
d2 = d2 + (rx * rx) - dy;
}
else
{
y--;
x++;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d2 = d2 + dx - dy + (rx * rx);
}
}
}
// Driver code
static void Main()
{
// To draw a ellipse of major and
// minor radius 15, 10 centered at (50, 50)
midptellipse(10, 15, 50, 50);
}
}
// This code is contributed by mits
PHP
<?php
// PHP program for implementing
// Mid-Point Ellipse Drawing Algorithm
function midptellipse($rx, $ry, $xc, $yc)
{
$x = 0;
$y = $ry;
// Initial decision parameter of region 1
$d1 = ($ry * $ry) - ($rx * $rx * $ry) +
(0.25 * $rx * $rx);
$dx = 2 * $ry * $ry * $x;
$dy = 2 * $rx * $rx * $y;
// For region 1
while ($dx < $dy)
{
// Print points based on 4-way symmetry
echo "( ", $x + $xc, ", ", $y + $yc, " )\n";
echo "( ",-$x + $xc,", ", $y + $yc, " )\n";
echo "( ",$x + $xc,", ", -$y + $yc , " )\n";
echo "( ",-$x + $xc, ", ", -$y + $yc, " )\n";
// Checking and updating value of
// decision parameter based on algorithm
if ($d1 < 0)
{
$x++;
$dx = $dx + (2 * $ry * $ry);
$d1 = $d1 + $dx + ($ry * $ry);
}
else
{
$x++;
$y--;
$dx = $dx + (2 * $ry * $ry);
$dy = $dy - (2 * $rx * $rx);
$d1 = $d1 + $dx - $dy + ($ry * $ry);
}
}
// Decision parameter of region 2
$d2 = (($ry * $ry) * (($x + 0.5) * ($x + 0.5))) +
(($rx * $rx) * (($y - 1) * ($y - 1))) -
($rx * $rx * $ry * $ry);
// Plotting points of region 2
while ($y >= 0)
{
// printing points based on 4-way symmetry
echo "( ",$x + $xc,", ", $y + $yc ," )\n";
echo "( ",-$x + $xc,", ", $y + $yc , " )\n";
echo "( ",$x + $xc,", ", -$y + $yc, " )\n";
echo "( ",-$x + $xc,", ", -$y + $yc, " )\n";
// Checking and updating parameter
// value based on algorithm
if ($d2 > 0)
{
$y--;
$dy = $dy - (2 * $rx * $rx);
$d2 = $d2 + ($rx * $rx) - $dy;
}
else
{
$y--;
$x++;
$dx = $dx + (2 * $ry * $ry);
$dy = $dy - (2 * $rx * $rx);
$d2 = $d2 + $dx - $dy + ($rx * $rx);
}
}
}
// Driver code
// To draw a ellipse of major and
// minor radius 15, 10 centered at (50, 50)
midptellipse(10, 15, 50, 50);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript program for implementing
// Mid-Point Ellipse Drawing Algorithm
function midptellipse(rx, ry, xc, yc)
{
var dx, dy, d1, d2, x, y;
x = 0;
y = ry;
// Initial decision parameter of region 1
d1 = (ry * ry) - (rx * rx * ry) +
(0.25 * rx * rx);
dx = 2 * ry * ry * x;
dy = 2 * rx * rx * y;
// For region 1
while (dx < dy)
{
// Print points based on 4-way symmetry
document.write("(" + (x + xc).toFixed(5) +
" , " + (y + yc).toFixed(5) +
")" + "<br>");
document.write("(" + (-x + xc).toFixed(5) +
" , " + (y + yc).toFixed(5) +
")" + "<br>");
document.write("(" + (x + xc).toFixed(5) +
" , " + (-y + yc).toFixed(5) +
")" + "<br>");
document.write("(" + (-x + xc).toFixed(5) +
" , " + (-y + yc).toFixed(5) +
")" + "<br>");
// Checking and updating value of
// decision parameter based on algorithm
if (d1 < 0)
{
x++;
dx = dx + (2 * ry * ry);
d1 = d1 + dx + (ry * ry);
}
else
{
x++;
y--;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d1 = d1 + dx - dy + (ry * ry);
}
}
// Decision parameter of region 2
d2 = ((ry * ry) * ((x + 0.5) * (x + 0.5))) +
((rx * rx) * ((y - 1) * (y - 1))) -
(rx * rx * ry * ry);
// Plotting points of region 2
while (y >= 0)
{
// Print points based on 4-way symmetry
document.write("(" + (x + xc).toFixed(5) +
" , " + (y + yc).toFixed(5) +
" )" + "<br>");
document.write("(" + (-x + xc).toFixed(5) +
" , " + (y + yc).toFixed(5) +
")" + "<br>");
document.write("(" + (x + xc).toFixed(5) +
" , " + (-y + yc).toFixed(5) +
")" + "<br>");
document.write("(" + (-x + xc).toFixed(5) +
" , " + (-y + yc).toFixed(5) +
")" + "<br>");
// Checking and updating parameter
// value based on algorithm
if (d2 > 0)
{
y--;
dy = dy - (2 * rx * rx);
d2 = d2 + (rx * rx) - dy;
}
else
{
y--;
x++;
dx = dx + (2 * ry * ry);
dy = dy - (2 * rx * rx);
d2 = d2 + dx - dy + (rx * rx);
}
}
}
// Driver code
// To draw a ellipse of major and
// minor radius 15, 10 centered at (50, 50)
midptellipse(10, 15, 50, 50);
// This code is contributed by akshitsaxenaa09
</script>
Producción:
(50.000000, 65.000000) (50.000000, 65.000000) (50.000000, 35.000000) (50.000000, 35.000000) (51.000000, 65.000000) (49.000000, 65.000000) (51.000000, 35.000000) (49.000000, 35.000000) (52.000000, 65.000000) (48.000000, 65.000000) (52.000000, 35.000000) (48.000000, 35.000000) (53.000000, 64.000000) (47.000000, 64.000000) (53.000000, 36.000000) (47.000000, 36.000000) (54.000000, 64.000000) (46.000000, 64.000000) (54.000000, 36.000000) (46.000000, 36.000000) (55.000000, 63.000000) (45.000000, 63.000000) (55.000000, 37.000000) (45.000000, 37.000000) (56.000000, 62.000000) (44.000000, 62.000000) (56.000000, 38.000000) (44.000000, 38.000000) (57.000000, 61.000000) (43.000000, 61.000000) (57.000000, 39.000000) (43.000000, 39.000000) (57.000000, 60.000000) (43.000000, 60.000000) (57.000000, 40.000000) (43.000000, 40.000000) (58.000000, 59.000000) (42.000000, 59.000000) (58.000000, 41.000000) (42.000000, 41.000000) (58.000000, 58.000000) (42.000000, 58.000000) (58.000000, 42.000000) (42.000000, 42.000000) (59.000000, 57.000000) (41.000000, 57.000000) (59.000000, 43.000000) (41.000000, 43.000000) (59.000000, 56.000000) (41.000000, 56.000000) (59.000000, 44.000000) (41.000000, 44.000000) (59.000000, 55.000000) (41.000000, 55.000000) (59.000000, 45.000000) (41.000000, 45.000000) (60.000000, 54.000000) (40.000000, 54.000000) (60.000000, 46.000000) (40.000000, 46.000000) (60.000000, 53.000000) (40.000000, 53.000000) (60.000000, 47.000000) (40.000000, 47.000000) (60.000000, 52.000000) (40.000000, 52.000000) (60.000000, 48.000000) (40.000000, 48.000000) (60.000000, 51.000000) (40.000000, 51.000000) (60.000000, 49.000000) (40.000000, 49.000000) (60.000000, 50.000000) (40.000000, 50.000000) (60.000000, 50.000000) (40.000000, 50.000000)
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por roshalmoraes y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA