{"id":209,"date":"2026-10-23T12:25:18","date_gmt":"2026-10-23T10:25:18","guid":{"rendered":"https:\/\/schwarzers.com\/?page_id=209"},"modified":"2026-10-23T13:06:11","modified_gmt":"2026-10-23T11:06:11","slug":"algorithms","status":"publish","type":"page","link":"https:\/\/schwarzers.com\/?page_id=209","title":{"rendered":"Algorithms"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"209\" class=\"elementor elementor-209\">\n\t\t\t\t<div class=\"elementor-element elementor-element-2a920e7 e-con-boxed e-flex e-con e-parent\" data-id=\"2a920e7\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-4780f8c elementor-widget elementor-widget-heading\" data-id=\"4780f8c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h1 class=\"elementor-heading-title elementor-size-default\">Drawing circles - Jesko's-Method<br>So far \"Fastest Algorithm Drawing Rasterized Circles\"<\/h1>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-33d8480 e-con-boxed e-flex e-con e-parent\" data-id=\"33d8480\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-0539989 elementor-widget elementor-widget-heading\" data-id=\"0539989\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\">Preface<\/h2>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-aec6233 e-con-boxed e-flex e-con e-parent\" data-id=\"aec6233\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-3f1883e elementor-widget elementor-widget-text-editor\" data-id=\"3f1883e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p>I developed a superior (in terms of &#8222;less-operations&#8220;) &#8222;Circle-Algorithm&#8220; in 1985\/1986.<br \/>This now is a gift to the community.<br \/>Enjoy!<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-a443368 e-con-boxed e-flex e-con e-parent\" data-id=\"a443368\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-bfdc5de elementor-widget elementor-widget-heading\" data-id=\"bfdc5de\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\">PreKnowledge, PriorArt<\/h2>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-1a58baa e-con-boxed e-flex e-con e-parent\" data-id=\"1a58baa\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-816b1cf elementor-widget elementor-widget-text-editor\" data-id=\"816b1cf\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<ol><li><a href=\"https:\/\/web.archive.org\/web\/20120422045142\/https:\/\/banu.com\/blog\/7\/drawing-circles\/\">Drawing rasterized circles explained (link from WayBackMachine)<\/a><\/li><li>Wikipedia<ol><li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Midpoint_circle_algorithm\">English-Version (Only-Midpoint algorithm)<\/a><\/li><li><a href=\"https:\/\/de.wikipedia.org\/wiki\/Rasterung_von_Kreisen\">German-Version (with Metzger, MidPoint and Horn-Method)<\/a><\/li><\/ol><\/li><\/ol>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-410f42b e-con-boxed e-flex e-con e-parent\" data-id=\"410f42b\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-a518b63 elementor-widget elementor-widget-text-editor\" data-id=\"a518b63\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p><b>From Wikipedia (I cite it because the description have several algorithms in common):<\/b><br \/>The objective of the algorithm is to approximate the curve <img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/37dd4f282df84a83620f71dc52345122e0e3a514\" alt=\"x^2 + y^2 = r^2\" aria-hidden=\"true\" \/> using pixels; Every pixel should be approximately the same distance from the center.<br \/>At each step, the path is extended by choosing the adjacent pixel which satisfies <img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/1f5bea3f347a2000cab838a9d443b6cc8edfea5a\" alt=\"{\\displaystyle x^{2}+y^{2}\\leq r^{2}}\" aria-hidden=\"true\" \/> but maximizes <img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/f455605b597282c27d7cf2238821bc331479a7e9\" alt=\"x^2 + y^2 \" aria-hidden=\"true\" \/>. Since the candidate pixels are adjacent, the arithmetic to calculate the latter expression is simplified.<\/p><p>These algorithms<\/p><ul><li>&#8230; draw all eight octants simultaneously, starting from each cardinal direction (0\u00b0, 90\u00b0, 180\u00b0, 270\u00b0) and extend both ways to<br \/>reach the nearest multiple of 45\u00b0 (45\u00b0, 135\u00b0, 225\u00b0, 315\u00b0). They can determine where to stop because when y = x, they have reached 45\u00b0.<br \/>Start (at iteration #0) of all 8 pixels is easy to find (laying on one axis). If drawing 8 pixels around the origin ( midpoint=( 0; 0 ) ): ( x; 0 ), ( x; 0 ), ( -x; 0 ), ( -x; 0 ), ( y; 0 ), ( y; 0 ), ( -y; 0 ), ( -y; 0 ). Don&#8217;t wonder: In the first iteration 4 pixels are duplicates.<\/li><li>&#8230; work iterativly.<\/li><li>&#8230; depend in their performance difference only on number of calculculations done to get the next pixel position.<\/li><\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-a8e5840 e-con-boxed e-flex e-con e-parent\" data-id=\"a8e5840\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-74dd1e8 elementor-widget elementor-widget-heading\" data-id=\"74dd1e8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\">Motivation<\/h2>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-cb60a12 e-con-boxed e-flex e-con e-parent\" data-id=\"cb60a12\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-c40c230 elementor-widget elementor-widget-heading\" data-id=\"c40c230\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">History<\/h3>\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-794c044 elementor-widget elementor-widget-text-editor\" data-id=\"794c044\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p>Decades ago in 1985, I experimented with Bresenhams line algorithm as a pupil on my Commodore 64 (I still love it). Without the Internet and relevant literature I was limited in all directions having only my C64 and some bit-knowledge, knowing how to optimize my assembler programs. In these times an extremly fast line subroutine was created by me drawing from both sides, taking in account the octants, reducing conditionals, saving in between results etc. 35k points per second on a machine capable of doing about ~490k operations per second, this is 14 operations (max.) per pixel including address calculation and bit operations to set it finally.<br \/>This was &#8222;Line-Algorithm&#8220;, but my circles I drew calculating points with sin\/cos and drawing with these quick lines in between. Later with some square-root function &#8230;<br \/><b>My problem was a mixture of missing accuracity and speed.<\/b> I didn&#8217;t want to accept, that lines could by drawn such fast and accurate, but circles not.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-7330183 e-con-boxed e-flex e-con e-parent\" data-id=\"7330183\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-6174845 elementor-widget elementor-widget-heading\" data-id=\"6174845\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\">The experiment ...<\/h2>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-f518b75 e-con-boxed e-flex e-con e-parent\" data-id=\"f518b75\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t<div class=\"elementor-element elementor-element-099eace e-con-boxed e-flex e-con e-child\" data-id=\"099eace\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t<div class=\"elementor-element elementor-element-6c96886 e-con-full e-flex e-con e-child\" data-id=\"6c96886\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t<div class=\"elementor-element elementor-element-ec66008 elementor-widget elementor-widget-text-editor\" data-id=\"ec66008\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p>So I experimented with my line algorithm &#8230; after reordering some variables, trying here and there I destroyed somehow the line algorithm, but I got an interesting figure:<\/p><p>\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-19297c1 e-con-full e-flex elementor-invisible e-con e-child\" data-id=\"19297c1\" data-element_type=\"container\" data-e-type=\"container\" data-settings=\"{&quot;animation&quot;:&quot;fadeInRight&quot;}\">\n\t\t\t\t<div class=\"elementor-element elementor-element-f665d31 elementor-widget elementor-widget-image\" data-id=\"f665d31\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img fetchpriority=\"high\" decoding=\"async\" width=\"258\" height=\"348\" src=\"https:\/\/schwarzers.com\/wp-content\/uploads\/2022\/02\/1985-First-Experiment-BigPixels.png\" class=\"attachment-large size-large wp-image-228\" alt=\"\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-0913886 e-con-boxed e-flex e-con e-child\" data-id=\"0913886\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t<div class=\"elementor-element elementor-element-2a36c92 e-con-full e-flex e-con e-child\" data-id=\"2a36c92\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t<div class=\"elementor-element elementor-element-db51e94 elementor-widget elementor-widget-text-editor\" data-id=\"db51e94\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p>As one could see there is something circular and a straigt line in 45\u00b0 down to the lower left. Looking at the code I couldn&#8217;t understand it directly, but what I found out relatively quick was to kill the straigt line extension. I compared two variables for equality and stopped my loop then.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-6296ffc e-con-full e-flex elementor-invisible e-con e-child\" data-id=\"6296ffc\" data-element_type=\"container\" data-e-type=\"container\" data-settings=\"{&quot;animation&quot;:&quot;fadeInRight&quot;}\">\n\t\t\t\t<div class=\"elementor-element elementor-element-2d6e684 elementor-widget elementor-widget-image\" data-id=\"2d6e684\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"258\" height=\"348\" src=\"https:\/\/schwarzers.com\/wp-content\/uploads\/2022\/02\/1985-First-Experiment-BigPixels-LineRed.png\" class=\"attachment-large size-large wp-image-229\" alt=\"\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-6788bcd e-con-boxed e-flex e-con e-child\" data-id=\"6788bcd\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t<div class=\"elementor-element elementor-element-17f12e9 e-con-full e-flex e-con e-child\" data-id=\"17f12e9\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t<div class=\"elementor-element elementor-element-58e23b8 elementor-widget elementor-widget-text-editor\" data-id=\"58e23b8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<div>I simply tried to mirror the pixels, et voil\u00e1 &#8230;<\/div><div>But hmm, there were some holes at multiple 45\u00b0 positions &#8230; ok, write a pixel more &#8211; on all octants so that at least 4 pixels are overdrawn (painted twice) &#8230;<\/div>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-89b0959 e-con-full e-flex elementor-invisible e-con e-child\" data-id=\"89b0959\" data-element_type=\"container\" data-e-type=\"container\" data-settings=\"{&quot;animation&quot;:&quot;fadeInRight&quot;}\">\n\t\t\t\t<div class=\"elementor-element elementor-element-6fa706a elementor-widget elementor-widget-image\" data-id=\"6fa706a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"369\" height=\"381\" src=\"https:\/\/schwarzers.com\/wp-content\/uploads\/2022\/02\/1985-First-Experiment-BigPixels-FullCircleWithHoles.png\" class=\"attachment-large size-large wp-image-230\" alt=\"\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-c01c057 e-con-boxed e-flex e-con e-child\" data-id=\"c01c057\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t<div class=\"elementor-element elementor-element-fb216d4 e-con-full e-flex e-con e-child\" data-id=\"fb216d4\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t<div class=\"elementor-element elementor-element-865a77a elementor-widget elementor-widget-text-editor\" data-id=\"865a77a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p>Finally:<\/p><p>\u00a0<\/p><p>This looked like a perfectly drawn circle on a raster display \ud83d\ude42<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-ea56d84 e-con-full e-flex elementor-invisible e-con e-child\" data-id=\"ea56d84\" data-element_type=\"container\" data-e-type=\"container\" data-settings=\"{&quot;animation&quot;:&quot;fadeInRight&quot;}\">\n\t\t\t\t<div class=\"elementor-element elementor-element-ba41bee elementor-widget elementor-widget-image\" data-id=\"ba41bee\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img loading=\"lazy\" decoding=\"async\" width=\"303\" height=\"324\" src=\"https:\/\/schwarzers.com\/wp-content\/uploads\/2022\/02\/1985-First-Experiment-BigPixels-FullCircleWithoutHoles.png\" class=\"attachment-large size-large wp-image-231\" alt=\"\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-0766119 e-con-boxed e-flex e-con e-parent\" data-id=\"0766119\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-84a88c5 elementor-widget elementor-widget-heading\" data-id=\"84a88c5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\">Comparison of Methods<\/h2>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-2d6a99c e-con-boxed e-flex e-con e-parent\" data-id=\"2d6a99c\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-6fc79b9 elementor-widget elementor-widget-text-editor\" data-id=\"6fc79b9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p>Beside Bresenham some others have tried to draw circles on raster displays and plotters.\u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-8dad0e9 e-con-boxed e-flex e-con e-parent\" data-id=\"8dad0e9\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-1c718ff elementor-widget elementor-widget-heading\" data-id=\"1c718ff\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Method of Horn\u200b<\/h3>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-5424553 e-con-boxed e-flex e-con e-parent\" data-id=\"5424553\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t<div class=\"elementor-element elementor-element-f5133f7 e-con-full e-flex e-con e-child\" data-id=\"f5133f7\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t<div class=\"elementor-element elementor-element-97e3d19 elementor-widget elementor-widget-text-editor\" data-id=\"97e3d19\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p>If we want to estimate the performance, we can concentrate on counting the arithmetic operations which are part of the loop:<\/p><ol><li>( y &gt; x ): 1 Operation &#8211; substraction<\/li><li>Pixel(): 0 Operation<\/li><li>d = d + 2 * y + 1: 3 Operations &#8211; 2 additions and a shift or 3 additions<\/li><li>y++: 1 Operation &#8211; addition<\/li><li>( d &gt; 0 ): 1 Operation &#8211; substraction (use of &gt;= 0 would only be check only sign bit)<\/li><li>d = d &#8211; 2 * x + 2: 3 Operations &#8211; 1 substraction, 1 additions, a shift and an addition or 1 substraction, 2 additions<\/li><li>x&#8211;: 1 operation &#8211; 1 substraction<\/li><\/ol><div><strong>Count of operations: 10<\/strong><\/div>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-00a2a7d e-con-full e-flex e-con e-child\" data-id=\"00a2a7d\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t<div class=\"elementor-element elementor-element-973231c elementor-widget elementor-widget-text-editor\" data-id=\"973231c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<pre><i>d<\/i> = \u2212r\n<i>x<\/i> = r\n<i>y<\/i> = 0\n<b>Repeat until<\/b> <i>y<\/i> &gt; <i>x<\/i>\n    Pixel (x, y) and symmetrical pixel are colored\n    <i>d<\/i> = <i>d<\/i> + 2\u00d7<i>y<\/i> + 1\n    <i>y<\/i>++\n    <b>If<\/b> <i>d<\/i> &gt; 0\n        <i>d<\/i> = <i>d<\/i> - 2\u00d7<i>x<\/i> + 2\n        <i>x<\/i>--<\/pre>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-947f4f3 e-con-boxed e-flex e-con e-parent\" data-id=\"947f4f3\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-f6465d6 elementor-widget elementor-widget-heading\" data-id=\"f6465d6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Midpoint Method<\/h3>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-1c3af6c e-con-boxed e-flex e-con e-parent\" data-id=\"1c3af6c\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t<div class=\"elementor-element elementor-element-9c02ca2 e-con-full e-flex e-con e-child\" data-id=\"9c02ca2\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t<div class=\"elementor-element elementor-element-2d499df elementor-widget elementor-widget-text-editor\" data-id=\"2d499df\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p>If we want to estimate the performance, we can concentrate on counting the arithmetic operations which are part of the loop:<\/p><ol><li>( x &gt; y ): 1 Operation &#8211; substraction<\/li><li>Pixel(): 0 Operation<\/li><li>y++: 1 Operation &#8211; addition<\/li><li>( P &lt;= 0 ): 1 Operation &#8211; substraction<\/li><li>P = P + 2*y + 1: 3 Operations &#8211; 2 additions and a shift or 3 additions<\/li><li>x&#8211;: 1 Operation &#8211; 1 substraction<\/li><li>\u00a0P = P + 2*y + 1 &#8211; 2*x: 2 (additional) operations (-2x) &#8211; 1 substraction and shift or 2 substractions<\/li><\/ol><p><strong>Count of operations: 9<\/strong><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-23fdbc8 e-con-full e-flex e-con e-child\" data-id=\"23fdbc8\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t<div class=\"elementor-element elementor-element-c7d8403 elementor-widget elementor-widget-text-editor\" data-id=\"c7d8403\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<pre>x = r\ny = 0\nP = 1 - r\n<strong>while ( x &gt; y )<\/strong>\n    Pixel (x, y) and symmetrical pixel are colored\n    y++\n    if ( P &lt;= 0 )\n        \/\/ Mid-point is inside or on the perimeter\n        P = P + 2*y + 1\n    else\n        \/\/ Mid-point is outside the perimeter\n        x--\n        P = P + 2*y - 2*x + 1\n<\/pre>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-3dde21e e-con-boxed e-flex e-con e-parent\" data-id=\"3dde21e\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-348b0ad elementor-widget elementor-widget-heading\" data-id=\"348b0ad\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Jesko's Method<\/h3>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-859fcac e-con-boxed e-flex e-con e-parent\" data-id=\"859fcac\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t<div class=\"elementor-element elementor-element-670e189 e-con-full e-flex e-con e-child\" data-id=\"670e189\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t<div class=\"elementor-element elementor-element-251d973 elementor-widget elementor-widget-text-editor\" data-id=\"251d973\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p>If we want to estimate the performance, we can concentrate on counting the arithmetic operations which are part of the loop:<\/p><ol><li>( y &gt;= x ): 1 Operation &#8211; substraction<\/li><li>Pixel(): 0 Operation<\/li><li>y++: 1 operation &#8211; addition<\/li><li>t1 += y: 1 Operation &#8211; addition<\/li><li>t2 = t1 &#8211; x: 1 Operation &#8211; substraction<\/li><li>( t2 &gt;= 0 ): 0 Operation &#8211; (check only sign bit)<\/li><li>t1 = t2: 0 Operations<\/li><li>x&#8211;: 1 operation &#8211; 1 substraction<\/li><\/ol><div><strong>Count of operations: 5<br \/><\/strong><\/div>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-2fddbea e-con-full e-flex e-con e-child\" data-id=\"2fddbea\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t<div class=\"elementor-element elementor-element-2298376 elementor-widget elementor-widget-text-editor\" data-id=\"2298376\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<pre>y = 0;\nt1 = r &gt;&gt; 4;\nx = r;\n<strong>while ( x &gt;= y )      \/\/ 1st op<\/strong>\n    Pixel (x, y) and symmetrical pixel are colored\n    y++               \/\/ 2nd op\n    t1 += y           \/\/ 3rd op\n    t2 = t1 - x       \/\/ 4th op\n    if ( t2 &gt;= 0 )    \/\/ does not count, no calculation, only positive check from result above\n        t1 = t2       \/\/ does not count either, register swap or similar\n        x--           \/\/ 5th op\n<\/pre>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-31d891c e-con-boxed e-flex e-con e-parent\" data-id=\"31d891c\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-ea52d66 elementor-widget elementor-widget-heading\" data-id=\"ea52d66\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\">Thougths<\/h2>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-9bf1398 e-con-boxed e-flex e-con e-parent\" data-id=\"9bf1398\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-f4122c8 elementor-widget elementor-widget-text-editor\" data-id=\"f4122c8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p>As I already told, I wasn&#8217;t aware of it @1985\/86. I simply had to use my brain and eyes.<\/p>\n<p>Looking back now reveals that some activities happened, but I still do not know, whether my algorithm is &#8222;beaten&#8220; in some way (less operations per 8 pixels). Maybe this can be clarified by my publication to the community now.<\/p>\n<p>Basically this arithmetic progression is used:<br>n\u00b2 = 1 + 3 + 5 + 7 + &#8230; + (2n &#8211; 1 )<br><br>Making algorithms fast means for normal, that we have less to calculate or less memory accesses. In the case of the circles I want to show here, that we only have less mathematical operations or can use meta information of already done calculations to hint\/support other calculations.<\/p>\n<p>Impact on current hardware is probably low, but maybe it helps to save transistors, FPGA space, keeps on living on embedded systems, or simply can show how algorithms may be optimized to a minimum of operations.<\/p>\n<p>Thanks for reading!<\/p>\n<p>\/Jesko Schwarzer<br>2022-Feb-13<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-519267a e-con-boxed e-flex e-con e-parent\" data-id=\"519267a\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-aeedf2f elementor-widget elementor-widget-heading\" data-id=\"aeedf2f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\">Publications<\/h2>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-2c9aa0a e-con-boxed e-flex e-con e-parent\" data-id=\"2c9aa0a\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-8cfb323 elementor-widget elementor-widget-text-editor\" data-id=\"8cfb323\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<ul><li><a href=\"https:\/\/de.wikipedia.org\/wiki\/Rasterung_von_Kreisen#Methode_von_Jesko\">Wikipedia (DE): https:\/\/de.wikipedia.org\/wiki\/Rasterung_von_Kreisen#Methode_von_Jesko<\/a><\/li><\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t<div class=\"elementor-element elementor-element-2258e28 e-con-boxed e-flex e-con e-parent\" data-id=\"2258e28\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-de0c1d2 elementor-widget elementor-widget-heading\" data-id=\"de0c1d2\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\">Appendix: Small C-Program<\/h2>\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-4d9288c elementor-widget elementor-widget-text-editor\" data-id=\"4d9288c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t\t\t\t\t\t<p>Here a small C-Program. Store the text as &#8222;main.c&#8220; and compile it. It outputs the coordinates of a circle with radius 10.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-e54c274 elementor-widget elementor-widget-html\" data-id=\"e54c274\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"html.default\">\n\t\t\t\t\t<pre>\n#include &ltstdio.h&gt\n\nvoid\nplot( int x, int y )\n{\n    printf( \"x=%3d, y=%3d\\n\", x, y );\n}\n\nvoid\ncircle( int mx, int my, int r )\n{\n    int t1 = r \/ 16;\n    int t2 = 0;\n    int x  = r;\n    int y  = 0;\n    while ( x >= y )\n    {\n        plot( mx + x, my + y );\n        plot( mx + x, my - y );\n        plot( mx - x, my + y );\n        plot( mx - x, my - y );\n        plot( mx + y, my + x );\n        plot( mx + y, my - x );\n        plot( mx - y, my + x );\n        plot( mx - y, my - x );\n        y  = y + 1;\n        t1 = t1 + y;\n        t2 = t1 - x;\n        if ( t2 >= 0 )\n        {\n            t1 = t2;\n            x  = x - 1;\n        }\n    }\n}\n\nint\nmain()\n{\n    circle( 20, 30, 10 );\n    return 0;\n}\n<\/pre>\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"elementor_header_footer","meta":{"ocean_front_end_style_editor":"no","ocean_post_layout":"right-sidebar","ocean_both_sidebars_style":"","ocean_both_sidebars_content_width":0,"ocean_both_sidebars_sidebars_width":0,"ocean_sidebar":"","ocean_second_sidebar":"","ocean_disable_margins":"default","ocean_add_body_class":"","ocean_shortcode_before_top_bar":"","ocean_shortcode_after_top_bar":"","ocean_shortcode_before_header":"","ocean_shortcode_after_header":"","ocean_has_shortcode":"","ocean_shortcode_after_title":"","ocean_shortcode_before_footer_widgets":"","ocean_shortcode_after_footer_widgets":"","ocean_shortcode_before_footer_bottom":"","ocean_shortcode_after_footer_bottom":"","ocean_display_top_bar":"on","ocean_display_header":"default","ocean_header_style":"","ocean_center_header_left_menu":"","ocean_custom_header_template":"","ocean_custom_logo":0,"ocean_custom_retina_logo":0,"ocean_custom_logo_max_width":0,"ocean_custom_logo_tablet_max_width":0,"ocean_custom_logo_mobile_max_width":0,"ocean_custom_logo_max_height":0,"ocean_custom_logo_tablet_max_height":0,"ocean_custom_logo_mobile_max_height":0,"ocean_header_custom_menu":"","ocean_menu_typo_font_family":"","ocean_menu_typo_font_subset":"","ocean_menu_typo_font_size":0,"ocean_menu_typo_font_size_tablet":0,"ocean_menu_typo_font_size_mobile":0,"ocean_menu_typo_font_size_unit":"px","ocean_menu_typo_font_weight":"","ocean_menu_typo_font_weight_tablet":"","ocean_menu_typo_font_weight_mobile":"","ocean_menu_typo_transform":"","ocean_menu_typo_transform_tablet":"","ocean_menu_typo_transform_mobile":"","ocean_menu_typo_line_height":0,"ocean_menu_typo_line_height_tablet":0,"ocean_menu_typo_line_height_mobile":0,"ocean_menu_typo_line_height_unit":"","ocean_menu_typo_spacing":0,"ocean_menu_typo_spacing_tablet":0,"ocean_menu_typo_spacing_mobile":0,"ocean_menu_typo_spacing_unit":"","ocean_menu_link_color":"","ocean_menu_link_color_hover":"","ocean_menu_link_color_active":"","ocean_menu_link_background":"","ocean_menu_link_hover_background":"","ocean_menu_link_active_background":"","ocean_menu_social_links_bg":"","ocean_menu_social_hover_links_bg":"","ocean_menu_social_links_color":"","ocean_menu_social_hover_links_color":"","ocean_disable_title":"default","ocean_disable_heading":"default","ocean_post_title":"","ocean_post_subheading":"","ocean_post_title_style":"default","ocean_post_title_background_color":"","ocean_post_title_background":0,"ocean_post_title_bg_image_position":"","ocean_post_title_bg_image_attachment":"","ocean_post_title_bg_image_repeat":"","ocean_post_title_bg_image_size":"","ocean_post_title_height":0,"ocean_post_title_bg_overlay":0.5,"ocean_post_title_bg_overlay_color":"","ocean_disable_breadcrumbs":"default","ocean_breadcrumbs_color":"","ocean_breadcrumbs_separator_color":"","ocean_breadcrumbs_links_color":"","ocean_breadcrumbs_links_hover_color":"","ocean_display_footer_widgets":"on","ocean_display_footer_bottom":"on","ocean_custom_footer_template":"","footnotes":""},"class_list":["post-209","page","type-page","status-publish","hentry","entry"],"_links":{"self":[{"href":"https:\/\/schwarzers.com\/index.php?rest_route=\/wp\/v2\/pages\/209","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/schwarzers.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/schwarzers.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/schwarzers.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/schwarzers.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=209"}],"version-history":[{"count":2,"href":"https:\/\/schwarzers.com\/index.php?rest_route=\/wp\/v2\/pages\/209\/revisions"}],"predecessor-version":[{"id":689,"href":"https:\/\/schwarzers.com\/index.php?rest_route=\/wp\/v2\/pages\/209\/revisions\/689"}],"wp:attachment":[{"href":"https:\/\/schwarzers.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=209"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}