BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:

These questions are mostly intellectual curiosity rather than an immediate requirement; and possibly off topic, though the code below is taken from one of my programs that is under active development.

I have a clip region defined in terms of several partially overlapping ellipses.

I tried to draw a picture, but it defeated my ascii art skills, but think the interior space of the Olympic Rings and wanting to only show (or exclude) those pixels that fall within (or outside) the combined perimeter.

And for generality -- and because the formula isn't much more complex -- define the rings as ellipses rather than circles. So the individual components of the region are stored as:

my @clips = (
    { cx => $X * 0.500, cy => $Y * 0.4,   rx2 => ( $X * 0.295 )**2, ry
+2 => ( $Y * 0.40 )**2 },
    { cx => $X * 0.500, cy => $Y * 0.6,   rx2 => ( $X * 0.390 )**2, ry
+2 => ( $Y * 0.34 )**2 },
    { cx => $X * 0.428, cy => $Y * 0.748, rx2 => ( $X * 0.067 )**2, ry
+2 => ( $Y * 0.038)**2 },
    ...
};

[download]

So I have code that does something like:

sub clip {
    my( $x, $y ) = @_;
    return 1 if ( $x - $clips[0]{cx} )**2 / $clips[0]{rx2} + ( $y - $c
+lips[0]{cy} )**2 / $clips[0]{ry2} < 1;
    return 1 if ( $x - $clips[1]{cx} )**2 / $clips[1]{rx2} + ( $y - $c
+lips[1]{cy} )**2 / $clips[1]{ry2} < 1;
    return 1 if ( $x - $clips[2]{cx} )**2 / $clips[2]{rx2} + ( $y - $c
+lips[2]{cy} )**2 / $clips[2]{ry2} < 1;
    ...
    return 0;
}

[download]

If the point is within any of the rings, return true (draw it), otherwise return false (don't).

Without resorting to rasterising the whole thing, which requires more tests; more space and doesn't work with scaling, is there any (simple) way to combine the formulae of the ellipses that would result in less tests?

On a related, but probably fanciful note, imagine I was only interested in seeing the region of the interior that lies within half a minor axis of the perimeter of the combined region, can that be defined parametrically?

And finally, if I wanted to split the entire perimeter at one point, stretch it out to a straight horizontal line, and display the half minor axis region, above that line, what on earth would the transform look like?

(Some distortion would be involved -- similar to the poles under Mercator Projection -- but that is okay.)

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Replies are listed 'Best First'.
pixel in ellipsis:
by FreeBeerReekingMonk (Deacon) on Jun 03, 2015 at 18:37 UTC

    One way we did it in Sphere Game engine was to:
    1. Convert your ellipse to a low count polygon.
    2. Use this algorithm on each pixel in your object: inpoly.c

    So you probably would have a point (x,y) and test it against the 5 olympic rings to see if it is in or out.
    The algorithm is brilliant, fast and explained in: visibone inpoly

    But I think you probably wanted to have the formula equation, where you isolate y^^2 and substitute that in the other equation of the second ellipse, then solve the equation to get the boundaries. The problem with that is that you get non Hilbert spaces, that is, picture a U in cartoony baloon font. Drawing a vertical line, will give you multiple contact points where you are in and out the structure, this can not be represented by a single formula, you will need to either test against each primitive (rectangle, ellipe), and that is basically what you are doing. Now 2 ellipses is of course a special case where you get a () kind of figure (forgot the mathematical name for that) and that is Hilbert. But the olympic rings together are not.
    In any case, you should be able to modify the inpoly algorithm to get point in ellipse, and do that for all 5 ellipses. Or, just define 8 or 16 points in your ellipse and use the inpoly algorithm.

[reply]
      The algorithm is brilliant, fast and explained in: visibone inpoly

      Thank you for that. It is both a very interesting read; and highly entertaining. (You/the author (?) had me at: "The prime prerogative in this article is algorithmic simplicity.". My credo!)

      Of course, all I need now is an efficient algorithm for converting ellipses to an minimal optimum number of straight lines. But hey, maybe that already exists out there too :)

      And thankyou for giving my brain a whole new vista to explore.

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
      In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
      .
[reply]

        BrowserUk:

        Just a couple weeks ago I had to do something pretty similar (reduce a complex outline to a simpler one) and found a pretty simple starting point: Ramer Douglas Peucker algorithm. I'd suggest taking the leftmost and rightmost points to use as the endpoints, and make two paths (upper and lower). Then, if you're finding the error at the left and right ends to be apparent, then select a couple points near the left and right sides and run on the shorter paths. Then merge them. I didn't need to do that, so I contented myself with the upper and lower paths it created. Worked nicely, and pretty simple to code, too. It was actually *harder* to find the appropriate search terms than to code it.

        Update: forgot to mention it--the first step would be to provide a list of points defining the boundary. Then use the algorithm to cull the list of points to the most efficient set.

        ...roboticus

        When your only tool is a hammer, all problems look like your thumb.

[reply]

        You are welcome. No, I was still learning about computers at the time that article came out in the Linux Journal. I can take credit however, for stealing adding that code to Sphere. Too bad a new build never came out (due to the fact we never got it stable enough with the new MSVC... maybe I can retry that, there is a new spidermonkey, and a new MSVC).

        Sphere is a game engine build in C with Javascript bindings. Use cases were testing javascript code, running javascript applications (and thanks to the bindings, you could read/write files, do some network connections, do things imagemagick can, play mod's and create ogg's, generate sounds. Similar to what node.js is now, but with a much more stronger focus on graphics... and games, of course).

        As for the ellipsis to poly... remember that a quarter of an ellipse is the same to the rest, so you would need to calculate some points (expensive calculation) on that quarter segment, and then mirror in x-axis and/or y-axis (just changing the sign + to -, and then sum, not expensive) to get the other points.

[reply]
Re: Graphics math.
by MidLifeXis (Monsignor) on Jun 03, 2015 at 17:43 UTC

    I don't know about simplifying the number of tests, but if you are just looking to minimize the number of tests run at execution time, Would a bounding box be a possibility? 

    sub clip {
  if ( within_bounding_box ) {
    return 1 if ....
  }
  return 0;
}

    [download]

    --MidLifeXis

[reply]
[d/l]
      Would a bounding box be a possibility?

      It certainly cuts down on the runtime tests for those points outside the bounding box, but if you imagine that there is nothing of interest outside the bounding box; it becomes the edges of the image.

      Ie. The image is scaled so that the bounding box of the clipped region becomes coincident with the screen or viewport. Then you back to square (or rectangle :) one.

      I'm just wondering if there is any mathematical way to "combine" the formulae of two or more partially overlapping ellipses? Trouble is, I haven't a clue what to search for.

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
      In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]
Re: Graphics math.
by Limbic~Region (Chancellor) on Jun 04, 2015 at 14:55 UTC
    BrowserUk,
    Is what you are asking:

    Given two equations for ellipses, is there a way to construct a third equation that only represents the intersection/overlap of the two ellipses?

    I know in your real problem you are dealing with more than two ellipses but I want to make sure I understand the question before I invest any additional effort.

    Cheers - L~R

[reply]
      Is what you are asking: Given two equations for ellipses, is there a way to construct a third equation that only represents the intersection/overlap of the two ellipses?

      No. Not the intersection; but rather the entire combined area. Without the first notion of how that might be possible.

      I'm a mathematician in the same way that I'm a plumber or electrician or car mechanic; I generally have the ability to lookup enough information to allow me to solve my immediate problem; but ask me about it a month or so from now and I probably can't explain how I did it.

      Years ago I was asked to give a financial type help with a spreadsheet he was developing for shares. He wanted to isolate the intersections/overlaps between 3 or more spot price curves. He had an line-fitting algorithm that approximated a given curve by producing some kind of multi-term polynomial. The first term approximated the line crudely; the second term refined it; the third refined the results of the second and so on. His task was to combine the polynomials from the 3 or more spot-price curves into a single polynomial, and then iterate it between predefined limits. It was complex stuff that I won't pretend to understand.

      However, what I was able to do was help him redefine his formulae, extracting common sub-terms and the like, that resulted in a 8 times reduction in his spreadsheet run times (measured in hours). Then, when he'd proven that what he was doing had some merit, I coded up a program in C to do the same calculations, that cut that time by almost another order of magnitude. I didn't have to understand the formulae; just be able to code up the parts and execute them in the right order to produce the same output for the given inputs.

      From 4+ hours to just over 3 minutes. Still too slow to inform spot price dealers; but with today's hardware they are probably doing the same stuff millisecond by millisecond in automated traders.

      And it was with that in mind that I thought that there might be some way to pre-process the equations of a bunch of ellipses into a polynomial whereby the first term would put (say)90% of points in or out; then the second term 90% of what's left; and so on. With short circuiting, that might be faster than testing every point against every ellipse individually.

      I still think there is some possibility of deriving the polynomial; but I am simply not equipped with the tuits to see how to even begin such a thing.

      Similarly for the two ancillary questions at the bottom of the OP.

      I can, by projection of stuff I've seen done in other fields (maps and the like), see that both are probably feasible -- if a blind mathematician can turn a sphere inside-out without breaking the surface (topologically speaking); then mapping a multi-segment curve to a straight line is probably child's play. If you're the right child. I'm not. (Either a child or the right one :)

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
      In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]
        BrowserUk,
        I think I understand now. The financial stuff you were talking about was probably some form of regression analysis using the least squares method. I don't think that would work for your problem because your lines curve back under themselves though you might treat them as a few lines and have it work.

        My apologies for not providing anything more concrete but a post to one of the math related reddits may provide insight (/r/math, /r/learnmath, /r/matheducation, /r/EngineeringStudents, /r/AskEngineers

        Cheers - L~R

[reply]
Re: Graphics math.
by Anonymous Monk on Jun 04, 2015 at 08:52 UTC

    Eureka! exstatica! There is a better way, The ellipse has 2 focal points F1 and F2 and a "length", where the pencil is, when drawing ellipses the classical way. If the point you are checking is further away from that length, then it is outside the ellipse. So: segment length from (x,y) to F1(x,y) PLUS segment length from (x,y) to F2(x,y) must not exceed "length", if it does, it is outside. Thus, the length is 4 sums and an abs, much much faster than polygons... will elaborate later (at work right now)

[reply]

      That's what I'm doing now. See the second code block in the OP.

      My question is: Given two (or more) overlapping ellipses, can I combine their formulae mathematically somehow so as to reduce the cost of testing for inclusion/exclusion?

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
      In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]

Back to Seekers of Perl Wisdom