3
$\begingroup$

I am given the the coefficients for an ellipse in the form: $$Ax^2 + Bxy + Cy^2 + Dx + Ey + F=0.$$

I have a 2 dimensional array of point objects (in Python) called "pixels", and I need to give each point a "count" if they lie inside the ellipse.

I initially tried iterating through every point with a loop like:

for row in pixels:
    for pixel in rows:
        x=point.get(pixel)[0]
        z=point.get(pixel)[1]
        if a*(x)**2 + b*(x*z) + c*(z)**2 + d*(x) + e*(z) + f >0:
            pixel.addpcount()

But this is taking way too long because I have several thousand ellipses I need to do this for. Is there a way I can efficiently do this?

(If this is not the right place to ask this question, I apologize.)

Edit: (I don't have enough reputation to comment). The Python is mostly irrelevant to my question at hand. I just want a better algorithm instead of iterating through every point.

In order to determine whether something is inside an ellipse, I am actually using this test https://math.stackexchange.com/questions/817130/how-to-determine-if-arbitrary-point-lies-inside-or-outside-a-conic.

The user Evil suggested using Axis Aligned Bounding Box. Does this mean finding the box which bounds an ellipse, and then testing only those points inside the box? That would seem a lot more efficient.

Greybeard, I am not sure what the Bresenham algorithm is, but I will take a look.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Have you considered reversing the problem? For each ellipse calculate Axis Aligned Bounding Box and check only for these points. Alternatively you can transform ellipse to circle to speed up tests (but the transform is rather costly, so it depends on orientation of ellipses and the size), could you give more info? For the tests: Point inside ellipse. In the current form your question seems to be Python dependent, which renders it off-topic here. But I assume that you are looking for better algorithm, right? $\endgroup$ – Evil Jan 22 '18 at 5:11
  • $\begingroup$ Note that Python is offtopic here. $\endgroup$ – Raphael♦ Jan 22 '18 at 6:03
  • $\begingroup$ Can you adapt the Bresenham algorithm to draw one quarter of an ellipse? One eighth? $\endgroup$ – greybeard Jan 22 '18 at 7:32
  • 4
    $\begingroup$ This seems to be a completely reasonable computational geometry question. The Python is irrelevant and the code fragment can be read perfectly well as pseudocode. $\endgroup$ – David Richerby Jan 22 '18 at 10:43
  • $\begingroup$ I missed - twice - that you have to "do something" for every pixel inside: if/as the complexity of checking isInside is constant, operating on every pixel inside a (tight) bounding box is asymptotically optimal, the ellipse covering more than three quarters of it. Are you interested in minimising/replacing isInside checks? $\endgroup$ – greybeard Jan 23 '18 at 14:51
2
$\begingroup$

Following @Evil's comment, I suggest two steps. For each ellipse $E$:

(1) Computing a bounding box $B$ for $E$.

(2) For each row of pixels in $B$, walk left-to-right until a pixel $p_1$ is discovered to be inside $E$. Then walk right-to-left until $p_2$ is in $E$. Then all the pixels from $p_1$ to $p_2$ are in $E$ (because of convexity).

      EllipseFill

The most difficult step is computing a bounding box for the ellipse. You likely don't need it exactly. Here are two sources:

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is a very nice approach, especially the walking left then walking right. $\endgroup$ – Jbag1212 Jan 23 '18 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.