pyx-devel

[PyX-devel] Re: [PyX-user] Some geometry thoughts

[Andre W. <wo...@us...>]

Hi,

I'm moving my posting to pyx-devel ... I think its a much better place
to post the following code. (Magnus, you're listing here, don't you? I
think I remember your name from when I looked at the subscriber list
quite some time ago.)

On 27.07.04, Andre Wobst wrote:
> Beside that my main concern is, whether its enough to stick on this
> strict assignments. This is quite a limitation. We can't compete to
> MetaPost by that (but we want, don't we?). I'm not sure whether its
> possible to cook it all down to an Equality-function:
> 
>     Equal(b, a + Point(10, 0))

I just couldn't resist: A linear equation solver can be easily build
like this. Find some code enclosed. You may consider to go along that
line (just in case you want to spend some time on this issue). I
think, a 2d-point can be build on top of this already by combining two
variables. The same for higher dimension points. I'm not totally sure
whether a transformation can be easily integrated in that concept. My
grasp tells me, that a transformation contains another set of
variables (6 for a 2d->2d affine transformation). When multiplying
with a (lazy) point (two variables) the system becomes non-linear. I'm
kind of confused at the moment ... ;-)


André

-- 
by  _ _      _    Dr. André Wobst
   / \ \    / )   wo...@us..., http://www.wobsta.de/
  / _ \ \/\/ /    PyX - High quality PostScript figures with Python & TeX
 (_/ \_)_/\_/           visit http://pyx.sourceforge.net/

Re: [PyX-devel] Re: [PyX-user] Some geometry thoughts

[Magnus L. H. <ma...@he...>]

Andre Wobst <wo...@us...>:
>
> Hi,
>=20
> I'm moving my posting to pyx-devel ... I think its a much better place
> to post the following code. (Magnus, you're listing here, don't you? I
> think I remember your name from when I looked at the subscriber list
> quite some time ago.)

Sure. I didn't quite remember myself, which is why I used pyx-user...
But, yes, I'm on pyx-devel as well.

> On 27.07.04, Andre Wobst wrote:
> > Beside that my main concern is, whether its enough to stick on this
> > strict assignments. This is quite a limitation. We can't compete to
> > MetaPost by that (but we want, don't we?). I'm not sure whether its
> > possible to cook it all down to an Equality-function:
> >=20
> >     Equal(b, a + Point(10, 0))
>=20
> I just couldn't resist: A linear equation solver can be easily build
> like this.

I know -- I've thought about this myself in the past, and I've even
found code that does this sort of thing. I don't remember exactly
where, but it had a variable class and did all the linear equations
behind the scenes.

Also, numarray (and Numeric) has support for the equation solving
part; I guess they could be optional mechanisms for speed, if this is
indeed the way to go.

> Find some code enclosed. You may consider to go along that line
> (just in case you want to spend some time on this issue).

I might. This is sort of an issue that crops up every now and then for
me (i.e. every time I want to create a figure, basically ;)

> I think, a 2d-point can be build on top of this already by combining
> two variables.

Certainly. It would also be neat to be able to use parametrized curves
in the same system, as in MetaPost; but I guess it's not quite that
critical, as you already have support for finding intersections
in PyX.

> The same for higher dimension points. I'm not totally sure whether a
> transformation can be easily integrated in that concept.

Well, if we use a general matrix-based version, it's all good.
(Haven't looked at your code -- it might work just as well.) That is,
an affine transform are basically just added terms to the linear
equations. And it would be *very* useful to allow them... E.g. "this
point rotated around that point by 60 degrees equals this point
rotated around that point by 30 degrees" and the like.

> My grasp tells me, that a transformation contains another set of
> variables (6 for a 2d->2d affine transformation). When multiplying
> with a (lazy) point (two variables) the system becomes non-linear.
> I'm kind of confused at the moment ... ;-)

Hm. No, I don't think so... If you say that one point, transformed by
an affine transform, equals another point, all you have is a linear
set of two equations in two variables -- no?

Not sure what you mean by "multiplying with a [...] point" here,
though. I may be missing something :]

Anyway, writing a system like this based on linear equations is a bit
more work than a one-way function-based one. I'll have a look but I
can't promise anything.

> Andr=E9

--=20
Magnus Lie Hetland     "Canned Bread: The greatest thing since sliced
http://hetland.org      bread!" [from a can in Spongebob Squarepants]

Re: [PyX-devel] Re: [PyX-user] Some geometry thoughts

[Andre W. <wo...@us...>]

Hi,

On 27.07.04, Magnus Lie Hetland wrote:
> > >     Equal(b, a + Point(10, 0))
> > 
> > I just couldn't resist: A linear equation solver can be easily build
> > like this.
> 
> I know -- I've thought about this myself in the past, and I've even
> found code that does this sort of thing. I don't remember exactly
> where, but it had a variable class and did all the linear equations
> behind the scenes.
> 
> Also, numarray (and Numeric) has support for the equation solving
> part; I guess they could be optional mechanisms for speed, if this is
> indeed the way to go.

BTW: I didn't wrote a linear equation solver, but what I did was
exactly a "variable class" and the "linear equations behind the
scenes", i.e. building up linear terms. To actually solve the linear
equations I used Numeric in my sample code already.

> Certainly. It would also be neat to be able to use parametrized curves
> in the same system, as in MetaPost; but I guess it's not quite that
> critical, as you already have support for finding intersections
> in PyX.

Finding intersections etc. is usually a nonlinear operation. But you
can define points by that ... sure. I guess it will be similar to
MetaPost in that respect (though I'm not quite sure right now).

> > My grasp tells me, that a transformation contains another set of
> > variables (6 for a 2d->2d affine transformation). When multiplying
> > with a (lazy) point (two variables) the system becomes non-linear.
> > I'm kind of confused at the moment ... ;-)
> 
> Hm. No, I don't think so... If you say that one point, transformed by
> an affine transform, equals another point, all you have is a linear
> set of two equations in two variables -- no?

Say p and p' are (2d) points, and t is a transformation (i.e. a 2x2
matrix + a 2d vector). Then you can write

p' = t(p)

Once you say p' and p are lazy vectors (i.e. they contain 2 variables)
as well as t is a lazy transformation (i.e. it contain 6 variables),
than the equation above is non-linear. There are non-linear terms in
matrix times vector when they both contain variables.

So I think what one has to do is to postpone this non-linear equation
until the non-linear terms are solved by other constraints. I guess,
thats what MetaPost does as well ... as soon as p or t gets defined
somewhere else, the equation above becomes linear.

> Anyway, writing a system like this based on linear equations is a bit
> more work than a one-way function-based one. I'll have a look but I
> can't promise anything.

Sure, nobody does. But we might have a starting point now ... and
maybe somebody is really interested in this. Its not top priority for
me, but well, on the other hand, I already like it ... we can get
something really funny quite quickly I guess.


André

-- 
by  _ _      _    Dr. André Wobst
   / \ \    / )   wo...@us..., http://www.wobsta.de/
  / _ \ \/\/ /    PyX - High quality PostScript figures with Python & TeX
 (_/ \_)_/\_/           visit http://pyx.sourceforge.net/

Re: [PyX-devel] Re: [PyX-user] Some geometry thoughts

[Magnus L. H. <ma...@he...>]

Andre Wobst <wo...@us...>:
>
[snip]
> BTW: I didn't wrote a linear equation solver, but what I did was
> exactly a "variable class" and the "linear equations behind the
> scenes", i.e. building up linear terms. To actually solve the linear
> equations I used Numeric in my sample code already.

I noticed that when I looked at the code :)

I've actually seens some similar code somewhere else before (the code
I mentioned earlier) -- and I've written similar things too (also
related to logic programming and the like). Seems like (possibly) a
reasonable approach.

> > Certainly. It would also be neat to be able to use parametrized curve=
s
> > in the same system, as in MetaPost; but I guess it's not quite that
> > critical, as you already have support for finding intersections
> > in PyX.
>=20
> Finding intersections etc. is usually a nonlinear operation. But you
> can define points by that ... sure. I guess it will be similar to
> MetaPost in that respect (though I'm not quite sure right now).

I don't know how MetaPost does it either. I know the curves are
non-linear... I just (na=EFvely ;) thought that, perhaps, through some
transformational magic the problem could be solved within the same
framework of linear equations. I guess finding out how MetaPost
actually does this might be quite useful.

[snip]
> Say p and p' are (2d) points, and t is a transformation (i.e. a 2x2
> matrix + a 2d vector). Then you can write
>=20
> p' =3D t(p)
>=20
> Once you say p' and p are lazy vectors (i.e. they contain 2 variables)
> as well as t is a lazy transformation (i.e. it contain 6 variables),
> than the equation above is non-linear. There are non-linear terms in
> matrix times vector when they both contain variables.

Right -- you're basically saying that this isn't linear in the
elements of the transform? But if we freeze the transform it is linear
in p' and p...?

> So I think what one has to do is to postpone this non-linear equation
> until the non-linear terms are solved by other constraints. I guess,
> thats what MetaPost does as well ... as soon as p or t gets defined
> somewhere else, the equation above becomes linear.

Well, you certainly can't solve an underdetermined set of equations
anyway, whether they're linear or not :)

I guess the problem will be writing it up as a set of linear equations
(i.e. in matrix form). What you're saying is that we can't really do
this before either p, p' of t has been determined by other means?

This seems quite muddled. I'm not very tempted to read the MetaPost
source code to find out how they do it either; I guess maybe I can
snoop around and see if I find some other pointers on how to do this
sort of thing.

Does anyone know of any other systems/sources of information than
MetaPost?

> > Anyway, writing a system like this based on linear equations is a
> > bit more work than a one-way function-based one. I'll have a look
> > but I can't promise anything.
>=20
> Sure, nobody does. But we might have a starting point now ... and
> maybe somebody is really interested in this.

Well, I'd be very interested in having it available :]

> Its not top priority for me, but well, on the other hand, I already
> like it ... we can get something really funny quite quickly I guess.

I guess. The problem is laying the foundation in such a way as not to
proclude the kind of future development we might want (e.g. full
linear equation solver linked to parametric curves and transforms)
without falling into the paralyzing trap of hypergeneralization (which
I know all to well -- and I've got the scars to prove it ;)

I'll think a bit about whether it's possible to a very simple thing
here (a "Smallest Thing That Could Possibly Work" kind of thing) --
beyond what we already have, of course.

> Andr=E9

--=20
Magnus Lie Hetland     "Canned Bread: The greatest thing since sliced
http://hetland.org      bread!" [from a can in Spongebob Squarepants]

Re: [PyX-devel] Re: [PyX-user] Some geometry thoughts

[Andre W. <wo...@us...>]

Hi,

On 27.07.04, Magnus Lie Hetland wrote:
> I know the curves are
> non-linear... I just (naïvely ;) thought that, perhaps, through some
> transformational magic the problem could be solved within the same
> framework of linear equations.

I don't think so. The intersection of two bezier curves is solved
numerically. (Or may be by solving a polynom of grad three.) In case
you want to take a look into MetaPost (I would like to learn more
about that). Is it really possible to say: transform a path by a not
yet completely defined transformation, so that an intersection point
with another path is located at a y coordinate with a certain value?

I just think you can't transform a path with a not yet completely
defined transformation. It becomes too complicated. But, of course,
what you can do for sure is to transform a point by a not yet
completely defined transformation. This is how you can define a
transformation by saying this point goes into this and a second one
into another one etc.

> [snip]
> > Say p and p' are (2d) points, and t is a transformation (i.e. a 2x2
> > matrix + a 2d vector). Then you can write
> > 
> > p' = t(p)
> > 
> > Once you say p' and p are lazy vectors (i.e. they contain 2 variables)
> > as well as t is a lazy transformation (i.e. it contain 6 variables),
> > than the equation above is non-linear. There are non-linear terms in
> > matrix times vector when they both contain variables.
> 
> Right -- you're basically saying that this isn't linear in the
> elements of the transform? But if we freeze the transform it is linear
> in p' and p...?

Ok, lets do some ASCII art (is it art?):

/x'\   /a b\/x\   /e\
|  | = |   || | + | |
\y'/   \c d/\y/   \f/

If you do not define the transformation matrix (i.e. the variables a,
b, c, and d) and you also keep the point p, i.e. x and y, variable,
the left hand side contains terms like a*x, which is non-linear.

You may, at a later point, find out, that you already know the value
of x, for example. Than the term becomes linear ...

And I think, that's what needs to be coded.

> This seems quite muddled. I'm not very tempted to read the MetaPost
> source code to find out how they do it either; I guess maybe I can
> snoop around and see if I find some other pointers on how to do this
> sort of thing.

Or just think what we can code right now after thinking about the
problem. I think its not that complex. Those non-linear terms might be
hidden in some additional "non-linear variable" in a code along the
lines I've started. Should be possible. Just replace a*x by AX and
keep on going. Once a or x becomes available by other means, the
"non-linear variable" can be resolved and a linear equation is
restored. What's also needed are equations for 2d points etc., but
those might be build on top of the term class as well. So I think,
yes, we can really get this working ...

I've worked on my solver code a bit further. You can find an updated
version enclosed. It solves equations "on the fly" and it also tries
to solve equations as soon as possible (it searches for decoupled
systems of equations). I've just checked it into the CVS under
test/experimental/solve.py as well ...


André

PS: I've also seen your comment about isinstance. Right. Currently I'm
    using it in this solver code to differenciate in __add__ etc.
    between the different types. Not yet perfect, right ... ;-)
    (I've the Python Cookbook and read about isstring, yes.)

-- 
by  _ _      _    Dr. André Wobst
   / \ \    / )   wo...@us..., http://www.wobsta.de/
  / _ \ \/\/ /    PyX - High quality PostScript figures with Python & TeX
 (_/ \_)_/\_/           visit http://pyx.sourceforge.net/

Re: [PyX-devel] Re: [PyX-user] Some geometry thoughts

[Magnus L. H. <ma...@he...>]

Andre Wobst <wo...@us...>:
>
> Hi,
>=20
[snip]
> Ok, lets do some ASCII art (is it art?):
>=20
> /x'\   /a b\/x\   /e\
> |  | =3D |   || | + | |
> \y'/   \c d/\y/   \f/
>=20
> If you do not define the transformation matrix (i.e. the variables a,
> b, c, and d) and you also keep the point p, i.e. x and y, variable,
> the left hand side contains terms like a*x, which is non-linear.
>=20
> You may, at a later point, find out, that you already know the value
> of x, for example. Than the term becomes linear ...

Ah, right. Indeed. Intuitively it just seems underdetermined if you're
trying to find out the transform *and* the points, even if you know
enough to make it, say, a quadratic problem (or something).

In practical applications I guess you'd always(?) know enough about
the points to get rid of such non-linear terms.

> And I think, that's what needs to be coded.

Right. I have no idea (off the top of my head, at least) how one would
deal with that; just a bit of book-keeping, perhaps? ;)

[snip]
> Or just think what we can code right now after thinking about the
> problem. I think its not that complex.

Sounds good.

> Those non-linear terms might be hidden in some additional
> "non-linear variable" in a code along the lines I've started. Should
> be possible. Just replace a*x by AX and keep on going.

Sounds like a clever move.

> Once a or x becomes available by other means, the "non-linear
> variable" can be resolved and a linear equation is restored.

Yeah -- a bit of book-keeping, still...

> What's also needed are equations for 2d points etc., but those might
> be build on top of the term class as well.

I'm dealing with these email out of order, so I guess this part is
already solved (by your vector equation code).

> So I think, yes, we can really get this working ...

Wohoo! :)

[snip]
> Andr=E9
>=20
> PS: I've also seen your comment about isinstance. Right. Currently I'm
>     using it in this solver code to differenciate in __add__ etc.
>     between the different types. Not yet perfect, right ... ;-)
>     (I've the Python Cookbook and read about isstring, yes.)

Heh. It works, for now; just thought I'd mention it. Perhaps the code
can be made more generic at some later stage (so that I can, for
example, multiply terms by a number-like class without having to
subclass int or the like).

BTW: Unless you're targeting old Pythons (maybe you are?) you don't
have to use types.IntType and the like; just use int (and float and
long). e.g. isinstance(foo, (int, float, long)). (No big point, as
types.IntType is simply int and so forth.)

--=20
Magnus Lie Hetland     "Canned Bread: The greatest thing since sliced
http://hetland.org      bread!" [from a can in Spongebob Squarepants]