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.

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.

I took a look at this, but it requires at least 8 lines segments to even vaguely approximate a circle or ellipse -- and double that to get somewhat close.

Even once several are combined, the inflection points created by compound curves crossing compound curves mean that there is very little scope for reduction in the total number of lines without loosing even the general shape.

And in the end, the point in polygon algorithm requires substantially more work/runtime than using one formula per ellipse; even when there is considerable overlap between them.

I knew it was a long shot from the outset; but I've been pleasantly surprised by such stabs in the dark before.

---

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

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.