RE: things often done in geometrical applications

Hi group.

I've not seen a lot going on here, but that doesn't mean the topic is not
important, I figure.

Take a look at the program at http://cs.sru.edu/~ddailey/fonts/circlesY.svg
.

Draw two circles. It finds the four lines tangent to both. This involves
several things including finding the places where two other circles meet. 

Click on "circles" in the menu at right (to hide them) and then on polygons.
The underlying line segments are then traversed successfully by the code to
find the polygons associated with a line arrangement.

We're interested in offering the underlying code as open source to anyone
who would like to use it with proper attribution!

Cheers
David

-----Original Message-----
From: Dailey, David P. [mailto:david.dailey@sru.edu] 
Sent: Friday, July 26, 2013 9:00 AM
To: Doug Schepers; David Dailey
Cc: public-geometryapi@w3.org
Subject: RE: things often done in geometrical applications

A couple of other things that would be nice 1. Given an arbitrary convex
quadrilateral, return the unique ellipse tangent to the four sides:
http://chrisjones.id.au/Ellipses/ellipse.html -- useful for perspective
drawing.

2. Given two circles return the four lines tangent to both (in the typical
situation of disjoint circles)

http://jwilson.coe.uga.edu/emt669/Student.Folders/Kertscher.Jeff/Essay.3/Tan
gents.html
and
http://cs.sru.edu/~ddailey/svg/circlesX.svg
(Jim Wilson at UGA tells me that this technique was undoubtedly known by
Euclid and students)

3.  Given a line arrangement (
https://en.wikipedia.org/wiki/Arrangement_of_lines ) return the collection
of polygons into which the lines have divided the viewport.

4. Given three (nonoverlapping) circles, return the eight Apollonian circles
tangent to all three http://en.wikipedia.org/wiki/Problem_of_Apollonius

That these problems and their solutions have endured for millennia is plenty
of justification for their utility to me. 

cheers
David
________________________________________
From: Doug Schepers [schepers@w3.org]
Sent: Monday, July 01, 2013 1:25 AM
To: David Dailey
Cc: public-geometryapi@w3.org
Subject: Re: things often done in geometrical applications

Hi, David-

On 6/28/13 4:06 PM, David Dailey wrote:
>
> Thanks for getting this going. Coincidentally, as it's creation was 
> being discussed, I in the midst of a project that could have used the 
> fruits of this labor (assuming they might exist in a couple of years).

I've seen so many requests for something like this over the years that it
was bound to overlap several people's projects that need it. :)


Thanks for this list to help us get started. I have a few comments on
specific items, inline...


> Here's just a quick list of things that come to mind that one might 
> often wish to do
>
> Intersecting things, as per Kevin Lindsay's work (wasn't some of this 
> already in SVG 1.2?):
>
>                  Lines, circles, ellipses, bezier (c and q) all with 
> one another

I've added this to the use cases and requirements page [1]. Note that Kevin
has pointed out some flaws and limitations in his library, and in using it,
I've found that you have to know the segment/line type before performing an
intersection test, which limits its usefulness.

This makes it a good candidate for addressing in a browser-native API, in my
opinion.


> Points closest to one another  on various pairs of curves (simplest 
> being two non parallel lines or a line and circle)
>
> Lines tangent to a given curve
>
>                  Closest to a point
>
>                  At a point
>
>                  Passing through a poin
>
> Lines tangent to each of two
>
>                  Circles (see
> http://jwilson.coe.uga.edu/emt669/Student.Folders/Kertscher.Jeff/Essay
> .3/Tangents.html
> )
>
>                  Ellipses

I could see some of this being useful in a drawing tool.


> Tweening - interpolating curves that are intermediate in shape between 
> two given curves (see the code that comes with <replicate>

Kevin had a library (or script) for this as well, but I agree it could spawn
some good requirements.


> Extrapolation - given curves A and B produce C so that B is 1/nth of 
> the way from A to C.
>
> Given a set of n lines that divide the plane into (n^2 + n +2)/2 
> regions - convert those regions to convex polygons returning a 
> collection of polygons
>
> Given a smooth path, convert it to a polygon having n edges for given
> n>2 most closely resembling the path.
>
> Given a polygon (convex or concave) or more generally,
>
>                  Form a triangulation of its interior
>
>                  Form a slight deformation of it (for glyphs we might 
> consider arbitrary  svg <path>s rather than just polygons

You've lost me here. What sort of use cases would these address? Even just
some illustrative examples would help.


>                  Produce a smoothed version (see 
> http://srufaculty.sru.edu/david.dailey/svg/Draw018.html -- draw a 
> rectangle, select it (by clicking on it) and then choose Smooth from 
> the menu that appears)

Smoothing curves/shapes is really useful for drawing apps, especially those
that have a distributed shared canvas, since it results in simpler paths to
exchange.


> Given n points
>
>                  Find a polygon passing through them
>
>                  Produce a Voronoi diagram
>
> Produce random
>
>                  N-gon
>
>                  Smooth Bezier curves that pass through N control 
> points and preserve continuous first derivatives
>
>                  Tessellations (polygonal, or rectangular - think HTML 
> tables with colspan and rowspan)

These seem more like things you'd do in script, maybe using a geometry API
for parts, rather than operations of a geometry API itself. But maybe I'm
missing something.


> That such things are useful (hence implying the existence of use 
> cases) seems obvious through a simple glance at the last 2500 years of 
> progress in algebra, mensuration and geometry.

We'll have a much stronger case to bring to the browser implementers if we
reinforce our requirements with explicit use cases. It will also help us
focus on the highest-priority items.


> BTW, Inkscape has some of this stuff already, as does <replicate>, 
> neither of which I saw in the script library listed in the wiki.

Like it says on the wiki, that page was a rough first draft, and anyone in
the Community Group can edit it.

(That said, Inkscape isn't a script library... but all those links were just
for inspiration anyway.)


[1] http://www.w3.org/community/geometryapi/wiki/Use_Cases_and_Requirements

Regards-
-Doug

Received on Sunday, 6 April 2014 19:52:44 UTC