<p>I called up an old officemate and CG expert, and after asking me a few questions he offered a simple solution.  I may have mangled a few details, but the basic idea follows:</p>

<p>Subsample the polar coordinates to whatever degree of accuracy needed, treating each subsample as a point.  It's then trivial to find the cartesian pixel that contains each point.  Sum up the sub-sampled points for each polar pixel to get its final value.</p>

<p>There's some subtlety in getting the weights right -- the guiding insight is that if the entire cartesian raster is flat gray, then each polar pixel should each have the same grayscale value.  And you could add on lots of other nuances, but the basic technique is intuitively and computationally straightforward.</p>

CC BY-SA 3.0
2016-06-24T06:02:30.477Z
2016-06-24T06:02:30.477Z
fearless_fool
<p>I have implemented the cartesian-to-polar-conversion and have used different interpolation methods:</p>

<p>1) nearest neighbor</p>

<p>2) a subsampling approach, which averages 81 subpixel locations</p>

<p>3) bilinear interpolation</p>

<p>The 2nd row in the image below shows detail magnifications of the output for the three approaches:</p>

<p><a href="https://i.sstatic.net/3o1vV.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3o1vV.png" alt="enter image description here"></a></p>

<p>Here is the GLSL shader code for approach 1 and 3:</p>

<pre><code>precision mediump float;
varying vec2 tc; // texture coordinate of current output pixel
uniform sampler2D inputImg; // input image
const float PI = 3.141592653589793238462643383;
void main() {
  float phi = tc.x; // phi is x-direction in output
  float r = tc.y;   // radius is y-direction in output
  float xx = r * cos(2.0 * PI * phi);  // unit circle in range [-1.0, 1.0]
  float yy = r * sin(2.0 * PI * phi);
  float x = xx * 0.5 + 0.5; // input texture coordinate in range [0.0, 1.0];
  float y = yy * 0.5 + 0.5;
  gl_FragColor = texture2D(inputImg, vec2(x,y));
}
</code></pre>

<p>This is the GLSL shader code for approach 2:</p>

<pre><code>precision mediump float;
varying vec2 tc; // texture coordinate of current output pixel
uniform sampler2D inputImg; // input image
uniform int outputWidth; // width of output image
uniform int outputHeight; // height of output image
const float PI = 3.141592653589793238462643383;
const int samplesPerSide = 4;
void main() {
  int samplesPerDirection = samplesPerSide * 2 + 1;
  // compute size of subsample step in texture coordinates
  float sampleStepX = 1.0 / float(outputWidth * samplesPerDirection); 
  float sampleStepY = 1.0 / float(outputHeight * samplesPerDirection);
  vec4 sampleSum = vec4(0); // init sum to zero
  for(int i = -samplesPerSide; i &lt;= samplesPerSide; i++) {
    for(int j = -samplesPerSide; j &lt;= samplesPerSide; j++) {
      float phi = tc.x + float(i) * sampleStepX; // phi is x-direction in output
      float r = tc.y + float(j) * sampleStepY;   // radius is y-direction in output
      float xx = r * cos(2.0 * PI * phi);  // unit circle in range [-1.0, 1.0]
      float yy = r * sin(2.0 * PI * phi);
      float x = xx * 0.5 + 0.5; // input texture coordinate in range [0.0, 1.0];
      float y = yy * 0.5 + 0.5;
      sampleSum += texture2D(inputImg, vec2(x,y));
    }
  }
  gl_FragColor += sampleSum / float(samplesPerDirection * samplesPerDirection);
}
</code></pre>

<p>Approach 2, which is approx. factor 81 slower than 1 and 3, is probably the one you are looking for but I also like the bilinear interpolation result.</p>

<p>With a WebGL capable browser you can try out these implementations here:</p>

<p><a href="https://www.gsn-lib.org/index.html#projectName=CartesianToPolar&amp;graphName=CartesianToPolar" rel="nofollow noreferrer">https://www.gsn-lib.org/index.html#projectName=CartesianToPolar&amp;graphName=CartesianToPolar</a></p>

CC BY-SA 3.0
2016-07-02T07:14:18.663Z
Use a indented block for code in future please. Nice answer
joojaa
CC BY-SA 3.0
2016-07-01T21:08:00.613Z
2016-07-02T07:02:48.307Z
2016-07-02T07:02:48.307Z
NodeCode
<p>(I've largely revamped this entire question, though the motivation remains the same.)</p>

<h3>revised question</h3>

<p>I want to convert a raster of cartesian pixels into polar pixels.  Is there a sensible algorithm for doing this?  For example, how do I compute the value of the shaded (polar) pixel in the image below, given the value of the three (cartesian) pixels that it overlaps?</p>

<p><a href="https://i.sstatic.net/c2Lh0.png" rel="noreferrer"><img src="https://i.sstatic.net/c2Lh0.png" alt="enter image description here"></a> </p>

<h3>original question</h3>

<p>Is there a reasonable way to compute the area of the intersection of a square and an annular section, as shown in the orange section below?</p>

<p><a href="https://i.sstatic.net/Tz312.png" rel="noreferrer"><img src="https://i.sstatic.net/Tz312.png" alt="enter image description here"></a></p>

<p>The motivation: I have a raster of square pixels, and I'm converting it to "polar pixels" -- I want to find out the contribution of each cartesian pixel to each polar pixel.</p>

CC BY-SA 3.0
2016-06-22T01:42:17.693Z
the alignment of your left border of the toroidal slice with  the rectangle axis is purely coincidental ?
v.oddou
CC BY-SA 3.0
2016-06-22T05:44:05.863Z
Is this a coverage calculation? Why would you choose to implement a very ineficient box filter?
joojaa
CC BY-SA 3.0
2016-06-22T08:33:15.223Z
@joojaa Agree but if it makes it easier, an approx, say, Gaussian could be built from a few of these coverage calculations.
Simon F
CC BY-SA 3.0
2016-06-22T14:52:59.153Z
@trichoplax: points well taken!  I'll take down the question on Maths.SE - thank you for that guidance.
fearless_fool
CC BY-SA 3.0
2016-06-22T15:00:48.383Z
@joojaa: yes, this is exactly a coverage calculation.  Does your comment mean that there's an efficient box filter to calculate this?
fearless_fool
CC BY-SA 3.0
2016-06-22T15:08:19.370Z
Something like that. Box filtering in general is the worst filter you could choose. Pixels are **not** really squares but point samples (read a [pixel is not a square x 3](http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf)) By using a standard function reconstruction you can do the same with a finite sampling which results in a better image than a box filter would with less work since your box filtering algorithm is so incredibly convoluted and expensive.
joojaa
CC BY-SA 3.0
2016-06-22T15:23:53.630Z
@joojaa: duly noted.  in fact, your comment motivated me to entirely reword  the question.  now: how do I design a sensible filter for this?  :)
fearless_fool
CC BY-SA 3.0
2016-06-22T15:32:55.153Z
Dont delete answer your own question to let somebody else answer with this info and then ask a new one. Its useful for others to see that people before them also made mistakes. Now that we know your scope isnt intentional we can start to answer the question at hand. But you could ass a note saying that you do not really require this sort of filtering just something thats good for the problem at hand.
joojaa
CC BY-SA 3.0
2016-06-22T15:42:28.927Z
True -- that's why I kept the original question un-edited.
fearless_fool
CC BY-SA 3.0
2016-06-23T05:44:26.993Z
very interesting article about sources pixels to consider for filtering. by Nathan http://www.reedbeta.com/blog/2014/11/15/antialiasing-to-splat-or-not/
v.oddou
<polygon><2d-graphics>
Converting cartesian pixels to polar pixels
fearless_fool
# Converting cartesian pixels to polar pixels

(Asked by: username_0 on 2016-06-22)

(I've largely revamped this entire question, though the motivation remains the same.)

### revised question

I want to convert a raster of cartesian pixels into polar pixels. Is there a sensible algorithm for doing this? For example, how do I compute the value of the shaded (polar) pixel in the image below, given the value of the three (cartesian) pixels that it overlaps?

[![enter image description here](https://i.sstatic.net/c2Lh0.png)](https://i.sstatic.net/c2Lh0.png)

### original question

Is there a reasonable way to compute the area of the intersection of a square and an annular section, as shown in the orange section below?

[![enter image description here](https://i.sstatic.net/Tz312.png)](https://i.sstatic.net/Tz312.png)

The motivation: I have a raster of square pixels, and I'm converting it to "polar pixels" -- I want to find out the contribution of each cartesian pixel to each polar pixel.

**Tags:** polygon, 2d-graphics

> **Comments:**
> **username_1**: the alignment of your left border of the toroidal slice with  the rectangle axis is purely coincidental ?  
> **username_2**: Is this a coverage calculation? Why would you choose to implement a very ineficient box filter?  
> **username_3**: @username_2 Agree but if it makes it easier, an approx, say, Gaussian could be built from a few of these coverage calculations.  
> **username_0**: @trichoplax: points well taken!  I'll take down the question on Maths.SE - thank you for that guidance.  
> **username_0**: @username_2: yes, this is exactly a coverage calculation.  Does your comment mean that there's an efficient box filter to calculate this?  
> **username_2**: Something like that. Box filtering in general is the worst filter you could choose. Pixels are **not** really squares but point samples (read a [pixel is not a square x 3](http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf)) By using a standard function reconstruction you can do the same with a finite sampling which results in a better image than a box filter would with less work since your box filtering algorithm is so incredibly convoluted and expensive.  
> **username_0**: @username_2: duly noted.  in fact, your comment motivated me to entirely reword  the question.  now: how do I design a sensible filter for this?  :)  
> **username_2**: Dont delete answer your own question to let somebody else answer with this info and then ask a new one. Its useful for others to see that people before them also made mistakes. Now that we know your scope isnt intentional we can start to answer the question at hand. But you could ass a note saying that you do not really require this sort of filtering just something thats good for the problem at hand.  
> **username_0**: True -- that's why I kept the original question un-edited.  
> **username_1**: very interesting article about sources pixels to consider for filtering. by Nathan http://www.reedbeta.com/blog/2014/11/15/antialiasing-to-splat-or-not/  

---

## 2 answers

### Answer by username_4 on 2016-07-01. Score: 6 | Accepted answer

I have implemented the cartesian-to-polar-conversion and have used different interpolation methods:

1) nearest neighbor

2) a subsampling approach, which averages 81 subpixel locations

3) bilinear interpolation

The 2nd row in the image below shows detail magnifications of the output for the three approaches:

[![enter image description here](https://i.sstatic.net/3o1vV.png)](https://i.sstatic.net/3o1vV.png)

Here is the GLSL shader code for approach 1 and 3:

```
precision mediump float;
varying vec2 tc; // texture coordinate of current output pixel
uniform sampler2D inputImg; // input image
const float PI = 3.141592653589793238462643383;
void main() {
  float phi = tc.x; // phi is x-direction in output
  float r = tc.y;   // radius is y-direction in output
  float xx = r * cos(2.0 * PI * phi);  // unit circle in range [-1.0, 1.0]
  float yy = r * sin(2.0 * PI * phi);
  float x = xx * 0.5 + 0.5; // input texture coordinate in range [0.0, 1.0];
  float y = yy * 0.5 + 0.5;
  gl_FragColor = texture2D(inputImg, vec2(x,y));
}

```

This is the GLSL shader code for approach 2:

```
precision mediump float;
varying vec2 tc; // texture coordinate of current output pixel
uniform sampler2D inputImg; // input image
uniform int outputWidth; // width of output image
uniform int outputHeight; // height of output image
const float PI = 3.141592653589793238462643383;
const int samplesPerSide = 4;
void main() {
  int samplesPerDirection = samplesPerSide * 2 + 1;
  // compute size of subsample step in texture coordinates
  float sampleStepX = 1.0 / float(outputWidth * samplesPerDirection); 
  float sampleStepY = 1.0 / float(outputHeight * samplesPerDirection);
  vec4 sampleSum = vec4(0); // init sum to zero
  for(int i = -samplesPerSide; i <= samplesPerSide; i++) {
    for(int j = -samplesPerSide; j <= samplesPerSide; j++) {
      float phi = tc.x + float(i) * sampleStepX; // phi is x-direction in output
      float r = tc.y + float(j) * sampleStepY;   // radius is y-direction in output
      float xx = r * cos(2.0 * PI * phi);  // unit circle in range [-1.0, 1.0]
      float yy = r * sin(2.0 * PI * phi);
      float x = xx * 0.5 + 0.5; // input texture coordinate in range [0.0, 1.0];
      float y = yy * 0.5 + 0.5;
      sampleSum += texture2D(inputImg, vec2(x,y));
    }
  }
  gl_FragColor += sampleSum / float(samplesPerDirection * samplesPerDirection);
}

```

Approach 2, which is approx. factor 81 slower than 1 and 3, is probably the one you are looking for but I also like the bilinear interpolation result.

With a WebGL capable browser you can try out these implementations here:

<https://www.gsn-lib.org/index.html#projectName=CartesianToPolar&graphName=CartesianToPolar>

> **Comments:**
> **username_2**: Use a indented block for code in future please. Nice answer  

---

### Answer by username_0 on 2016-06-24. Score: 0

I called up an old officemate and CG expert, and after asking me a few questions he offered a simple solution. I may have mangled a few details, but the basic idea follows:

Subsample the polar coordinates to whatever degree of accuracy needed, treating each subsample as a point. It's then trivial to find the cartesian pixel that contains each point. Sum up the sub-sampled points for each polar pixel to get its final value.

There's some subtlety in getting the weights right -- the guiding insight is that if the entire cartesian raster is flat gray, then each polar pixel should each have the same grayscale value. And you could add on lots of other nuances, but the basic technique is intuitively and computationally straightforward.


---

