Computational geometry in the plane: in Sage?

[Ed Scheinerman]

Does Sage have, or is there a package I can add, that implements basic plane geometry objects and operations. The sort of thing I'd like to do is, given two points, construct the line that contains them. Or given two circles, intersect them yielding 0, 1, or 2 points. Given a set of points, determine which are on the convex hull, construct that polygon, and return its area. And, ultimately, after working with various geometric objects, perhaps visualize them on the screen (but that comes later). 

Extra bonus if I can do this in both the Euclidean plane and the Hyperbolic plane (and in the latter case visualize either in the Poincare disk or the upper half plane models). 

Thanks.

[Nathann Cohen]

I already told Ed that I did not know if sub a thing was possible in Sage, but thought of it a little bit since.. If we were to implement that, it would be cool to have short notations for these sets, with set.<tab> thing.

Like :

sets.Circle(xo,xo,radius)
sets.Rectangle(xo,yo,x1,y1)

We could have finite sets described by the point they contain, and infinite sets described by equations. We would then potentially be able to intersect them as we want. We could have different constructors for different geometries, and we could have constructors for object in various dimensions. I do not know exactly how object from different dimensions should be made to interact together though :-)

Nathann

[Dima Pasechnik]

On 2014-04-20, Ed Scheinerman <edward.sc...@gmail.com> wrote:
> Does Sage have, or is there a package I can add, that implements basic
> plane geometry objects and operations. The sort of thing I'd like to do is,
> given two points, construct the line that contains them. Or given two
> circles, intersect them yielding 0, 1, or 2 points. Given a set of points,
> determine which are on the convex hull, construct that polygon, and return
> its area.

for the convex hull and area, you can use Polyhedron(). E.g.
sage: p=Polyhedron(vertices = [[1, 1], [0, 0], [1, -1], [-1, 1], [-1, -1]])
sage: p.volume()
4
sage: p.vertices()
(A vertex at (-1, -1),
A vertex at (-1, 1),
A vertex at (1, 1),
A vertex at (1, -1))

[Thierry Dumont]

Le 21/04/2014 10:39, Dima Pasechnik a écrit :
> p=Polyhedron(vertices = [[1, 1], [0, 0], [1, -1], [-1, 1], [-1, -1]])

I wanted to try this -^.. but, entering exactly that line, I get a problem.

I am in 6.1.1; as far as as know, I have built sage from source, using
the system Atlas blas....and I have just upgraded from Ubuntu 13.10 to
14.04. Could the problem be here?

The error message:

/usr/local/sage-6.1/local/lib/python2.7/site-packages/sage/modules/free_module.pyc
in element_class(self)
893 except AttributeError:
894 pass
--> 895 C = element_class(self.base_ring(), self.is_sparse())
896 self._element_class = C
897 return C
...
/2/home/moi/vector_real_double_dense.pyx in init
sage.modules.vector_real_double_dense
(sage/modules/vector_real_double_dense.c:5523)()

/2/home/moi/numpy.pxd in init sage.modules.vector_double_dense
(sage/modules/vector_double_dense.c:11558)()

/usr/local/sage-6.1/local/lib/python2.7/site-packages/numpy/__init__.pyc
in <module>()
135 return loader(*packages, **options)
136
--> 137 import add_newdocs
138 __all__ = ['add_newdocs']
139

/usr/local/sage-6.1/local/lib/python2.7/site-packages/numpy/add_newdocs.py
in <module>()
7 # core/fromnumeric.py, core/defmatrix.py up-to-date.
8
----> 9 from numpy.lib import add_newdoc
10
11
###############################################################################

/usr/local/sage-6.1/local/lib/python2.7/site-packages/numpy/lib/__init__.py
in <module>()
11
12 import scimath as emath
---> 13 from polynomial import *
14 #import convertcode
15 from utils import *

/usr/local/sage-6.1/local/lib/python2.7/site-packages/numpy/lib/polynomial.py
in <module>()
15 from numpy.lib.function_base import trim_zeros, sort_complex
16 from numpy.lib.type_check import iscomplex, real, imag
---> 17 from numpy.linalg import eigvals, lstsq, inv
18
19 class RankWarning(UserWarning):

/usr/local/sage-6.1/local/lib/python2.7/site-packages/numpy/linalg/__init__.py
in <module>()
46 from info import __doc__
47
---> 48 from linalg import *
49
50 from numpy.testing import Tester

/usr/local/sage-6.1/local/lib/python2.7/site-packages/numpy/linalg/linalg.py
in <module>()
21 isfinite, size, finfo, absolute, log, exp
22 from numpy.lib import triu
---> 23 from numpy.linalg import lapack_lite
24 from numpy.matrixlib.defmatrix import matrix_power
25 from numpy.compat import asbytes

ImportError: /usr/local/sage-6.1/local/lib/libptcblas.so.3: undefined
symbol: ATL_cttrmm

[Volker Braun]

On Tuesday, April 22, 2014 4:43:43 PM UTC+1, tdumont wrote:

I am in 6.1.1; as far as as know, I have built sage from source, using
the system Atlas blas....and I have just upgraded from Ubuntu 13.10 to
14.04. Could the problem be here?

most likely, you switched out the system ATLAS library and now it crashes in the ATLAS library.

[Volker Braun]

On Tuesday, April 22, 2014 4:43:43 PM UTC+1, tdumont wrote:

I am in 6.1.1; as far as as know, I have built sage from source, using
the system Atlas blas....and I have just upgraded from Ubuntu 13.10 to
14.04. Could the problem be here?

[leif]

Well, presumably, but not much of an issue. "Simply" reinstalling the
ATLAS spkg (with SAGE_ATLAS_LIB set appropriately) and rebuildung every
package that depends on ATLAS /should/^TM be sufficient:

$ env SAGE_ATLAS_LIB=/path/to/system/atlas/libs ./sage -f atlas

$ env SAGE_UPGRADING=yes make build

(Note sure whether some Cython extension modules need to get
rebuilt/relinked as well, and if so, whether the dependencies are
complete in that the above would automatically rebuild them.)


-leif

--
() The ASCII Ribbon Campaign
/\ Help Cure HTML E-Mail

[John H Palmieri]

This is perhaps not the most helpful answer -- you can decide for yourself. But tkz-euclide (a TeX package, see http://www.ctan.org/pkg/tkz-euclide) can do a lot of these calculations, in particular with a focus on drawing the relevant pictures. You might be able to use this on its own, or in combination with sagetex, or (maybe with some tinkering) in Sage itself. As the name of the package implies, it only works in Euclidean geometry, not hyperbolic.

  John

[Thierry Dumont]

Le 22/04/2014 18:33, leif a écrit :
> Volker Braun wrote:
>> On Tuesday, April 22, 2014 4:43:43 PM UTC+1, tdumont wrote:
>>
>> I am in 6.1.1; as far as as know, I have built sage from source,
>> using
>> the system Atlas blas....and I have just upgraded from Ubuntu
>> 13.10 to
>> 14.04. Could the problem be here?
>>
>>
>> most likely, you switched out the system ATLAS library and now it
>> crashes in the ATLAS library.
>
> Well, presumably, but not much of an issue. "Simply" reinstalling the
> ATLAS spkg (with SAGE_ATLAS_LIB set appropriately) and rebuildung every
> package that depends on ATLAS /should/^TM be sufficient:
>
> $ env SAGE_ATLAS_LIB=/path/to/system/atlas/libs ./sage -f atlas
>

Yes, this is enough... now it works.
Yours
t.

[Dominique Laurain]

I need same packages that Ed asked for.
Nowadays I do geometry coding myself basic functions in SAGE worksheets (to do intersection of lines etc).
I do this using the "Rational Trigonometry philosophy" :-)..see njwilderger youtube videos and book.
Previously I played a little with Tex tools (pst-tricks and pst-eucl)..check about pstricks too...at that time and until now, I
was interested with tilings.
In SAGE we have the basics tools (vectors,matplotlib...) but I feel there are not the "intermediate" tools : convex hull, rules and compass constructions, origami tools and so on.
I can code some (for example, convex hull: I know an algorithm "paquet cadeau" ...but everytime I feel to reinvent wheel.
What is not enough with Tex is that all is static : for example, you cannot have the generic solution of two lines AB and CD where A,B,C,D are 2D points with variables coordinates...because it is no more static geometry but symbolic computations (solving equations / inequations).

[Volker Braun]

We do have convex hull and lines. What would be lacking for your application are discs and their intersection with polyhedra.

sage: line = Polyhedron(vertices=[(0,-1)], lines=[(1,1)])

sage: (triangle & line).vertices()

(A vertex at (8/5, 3/5), A vertex at (3/2, 1/2))

[Ed Scheinerman]

Glad to see this has gained some traction. Here is an illustration of the immediate issue for which this would have been helpful. I wanted to produce an illustration explaining lines in the hyperbolic plane using the Poincare disk model. It's the arc of a circle whose end points are on a given circle and the arc meets the given circle at right angles. (That's a lot to say but a picture makes it so much easier.) 

It took me a long time and a good deal of coding in Sage to get this how I wanted. My "gut" tells me there's go to be a better way!

--
You received this message because you are subscribed to a topic in the Google Groups "sage-support" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-support/Y0t4ShFLXJ4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sage-support...@googlegroups.com.
To post to this group, send email to sage-s...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

--
Ed Scheinerman (e...@scheinerman.net)

[Peter Bruin]

A certain amount of work on adding functionality for hyperbolic geometry to Sage has been done in recent years, see here:

http://trac.sagemath.org/ticket/9439

There seem to be several different implementations by different authors; I am not sure about the status of all this work and how much of it is relevant to what you want to do.

Peter


Op donderdag 24 april 2014 18:54:32 UTC+1 schreef Ed Scheinerman:

[Ed Scheinerman]

Thanks. I've seen some of that, but it looks like they use the upper half-plane model for visualization (while my preference is for Poincare disk). Also, I want to do other geometric constructions/visualizations in Sage (see attached pics) for which commands to create segments, then get perpentidular bisecting lines  or angle trisectors, would make life much easier. (I did this in Sage, but had to work from scratch.)