GSoC 2014 Application Akshay Geometry Module

Akshay edited this page Mar 20, 2014 · 9 revisions
Clone this wiki locally

About me

Hi, I am a second year undergraduate student at Bits-Pilani, India pursuing dual degree in B.E(Hons) Electronics and Instrumentation and M.Sc (Hons) Economics.

Contact Information

Name : Akshay

Email : akshaynukala95@gmail.com

Github : akshayah3

Programming Background and Environment

I have been using Python for a year now and I am quite comfortable working with it.Apart from that I have a decent knowledge of Java and C++.I use Ubuntu 13.10 as my work machine and have been using git for 3 months now ,so I would say that I have grasped it's basics.Sublime Text 2 is my primary choice for editors.

##Contributions to Sympy(From earliest to latest) Most of my work has been on the Geometry module, so I am well acquainted with the codebase. ###Merged:

  • Normal Lines to Ellipse #2811 merged in #2828

  • Intersection method of an Ellipse #2857

  • Reflect method extended for all lines #2896

  • Blocking Imaginary Points #2912

  • Intersection method of a Line #2930

  • Distance method of the Ray returns wrong results #2950

###Issues reported:

###Unmerged(Closed)

  • Extending the is_parallel method to more than two lines #2843

##Why this project Extending the Geometry module to 3 Dimensions would be a great addition to sympy as most of the complex geometric computations involves entities present in a 3-D space. And note that currently there are no computational geometry libraries in Pure Python which support 3-D objects which I plan on implementing.This would help sympy in the long run if there are plans for implementing things like optics to sympy.physics and also in plotting of simple 3-D objects.And the classes like GeometryResult(explained in detail below) would increase the flexibility of the geometry module as a computational algebraic geometry system.

Project Idea

##Abstract ###3-Dimensional Geometry The current geometry module restricts the functionality of it's entities to a 2-dimensional space.I would like to extend the 3-dimensional functionality to some of the currently supported entities like Point, Line, Segment, Ray and implement a separate class for Planes as they are an important part of 3-D. As the algorithms used for 2-D cannot be extended to include the 3-D functionality so all the algorithms should be implemented from scratch.

###Conics Currently the geometry module only supports 2 conics i.e Ellipse and Circle.So I would like to extend this to include Parabola and Hyperbola(including Rectangular Hyperbola) classes.

###GeometryResult Many a times in Geometry when one is dealing with symbolic entities,assertions cannot be guaranteed and for these cases presently Sympy simply returns False.Instead of this it would be better to return an expression which might help the user in further calculations.This class would contain the following methods, to name a few:

  • is_similar
  • is_parallel
  • is_concyclic
  • is_perpendicular
  • encloses_point
  • is_tangent
  • is_convex
  • contains
  • collinear
  • are_coplanar

##Classes These are the classes I am planning on implementing

  • Point
  • Line
  • Plane
  • Parabola
  • Hyperbola
  • GeometryResult

Existing classes which have to be changed

  • Polygon
  • Entity
  • Utils
  • Curve
  • Ellipse

##Implementation ###Point Currently the point class strictly supports points in 2-D. My task here would be to support 3-D points and implement all the methods currently in the point class for both 2-D and 3-D points as most of them cannot be generally extended to 3-D points. Apart from that some new methods specifically for 3-D points. ###Class Structure

####Constructor Method:

  • __new__
  • __hash__
  • __eq__
  • __lt__
  • __contains__

####Attributes:

  • x
  • y
  • z
  • length
  • direction_cosines
  • direction_ratios

####Methods

  • is_collinear
  • is_concyclic
  • is_coplanar
  • distance
  • midpoint
  • intersection
  • rotate
  • translate
  • scale
  • transform
  • __add__
  • __sub__
  • __mul__
  • __div__

###Line My task here would be to extend the current line class to include lines , rays and segments in both 2-D and 3-D. Firstly the linearentity class should be changed to support both 2-D and 3-D linear entities, all of it's methods should be altered and new ones should be added. All the methods which are unique to lines, rays and segments should be added to their respective classes.This class should be extensively tested and should integrate well with other classes and entities. ###Class Structure (Contains some important methods, just meant to give an idea about the class structure) ###LinearEntity(Base class for all Line, Segment, Ray)

  • Constructor Method: Currently it supports 2-D Lines and has to be changed to support 3-D entities

####Attributes:

  • p1
  • p2
  • p3(Optional, If not mentioned z co-ordinate will be taken as 0 by default)
  • Slope(for 2-D lines)
  • Direction Cosines(for 3-D lines)
  • Coefficients for 2-D lines *Points

####Methods:

  • is_concurrent: currently implemented taking into account only the permutations of 2-D entities should be extended to include all 2-D and 3-D entities.(Note that the algorithms of 2-D entities cannot be extended for 3-D entities hence both the algorithms should be jointly implemented and this applies for all the methods mentioned below)
  • is_parallel
  • is_perpendicular
  • angle_between
  • parallel_line
  • perpendicular_line
  • are_coplanar
  • Projection:of a point, Line , Ray, Segment(both 2-D and 3-D) onto a plane or another linear entity
  • intersection : of any entity with any other entity or plane or other geometrical entities like Ellipse, Hyperbola etc
  • arbitrary_point
  • random_point

###Line

  • This inherits the LinearEntity class
  • Constructor method: This will undergo major changes as it currently supports 2-D lines

####Methods:

  • plot_interval
  • equation (for 2-D and 3-D accordingly)
  • distance: shortest distance between line and point
  • skew_distance : shortest distance between two 3-D skew lines
  • __hash__
  • __eq__

###Ray

  • This also inherits the LinearEntity class
  • Constructor method has to be implemented

####Attributes:

  • source
  • x-direction
  • y-direction
  • Direction_vector in the case of a 3-D ray

####Methods

  • Distance
  • Plot_interval
  • contains
  • __eq__
  • __hash__

###Segment

  • This as well inherits the LinearEntity class
  • Constructor Method has to be implemented

####Attributes

  • p1
  • p2
  • length
  • midpoint
  • positionvector

####Methods

  • Distance
  • Plot_interval
  • contains
  • __eq__
  • __hash__
  • Perpendicular_bisector

###Plane This class would support the general(linear and infinitely extending) planes.It would involve all the functionalities like intersection between planes and also between all the other existing geometric entities, Distance between all the geometric entities and the plane and between two planes, Reflection of geometric entities by the plane, Angle between linear entities and the plane to name a few important ones.

###Class Structure

####Constructor Method:

  • __new__
  • __hash__
  • __eq__
  • __lt__
  • __contains__

####Attributes

  • normal_vector
  • p1
  • p2

####methods

  • equation
  • projection
  • reflect
  • distance
  • translate
  • rotate
  • intersection_planes (intersection of 2 and 3 planes)
  • intersection (linear entities and conics)
  • equation (equation of a line perpendicular or parallel to the plane, equation of a plane parallel or perpendicular to this plane)
  • angle_between
  • arbitrary_point
  • arbitrary_line
  • Plot_interval
  • contains
  • __eq__
  • __hash__

###GeometryResult Consider the example of is_perpendicular method of a line, GeometryResult will contain a is_perpendicular method which will be triggered if a symbolic entity is encountered by the is_perpendicular method of the line and will return the result accordingly.

###Hyperbola ,Rectangular Hyperbola and Parabola All the above classes will have a similar structure to that of the ellipse.After implementing these classes I should make sure that they integrate well with other classes, For example intersection method of line takes only ellipse into account but now this should be extended to include these entities.

###Changes in other existing classes As explained above to make the geometry module a complete integrated package all the existing classes like Ellipse, Entity, Curve, Utils have to be changed accordingly and tested.Apart from these I plan on implementing some new methods to these existing classes and also change the algorithms if necessary.

###A Few useful methods which are currently not implemented:

  • Finding tangent and normal lines at a given point to any curve.
  • A method which checks whether the two curves intersect orthogonally
  • Minimum distance between a point and a ellipse, and a line and a ellipse.

#Prototype ###Point >>>a = Point(1,2,3) >>>b = Point(2,3,4) >>>a.distance(b) Output: sqrt(3) >>>c = Point(2,3) #Whenever only 2 co-ordinates are specified the z co-ordinate is taken as zero by default >>>a.distance(c) Output: sqrt(11)

###Line >>>a = Line(Point(1,2,3), Point(2,3,4)) >>>a.equation() Output: x - 1/1 = y-2/1 = z-3/1 = t #Note that the default parameter is t >>>a.arbitrary_point('k') Output: Point(k + 1, k+2, k+3) >>>a.direction_ratios() Output: [1,1,1] >>>b = Line(Point(1,2,3),Point(1,2)) #Z co-ordinate of the second point is by default 0 ,if not mentioned >>>b.equation() Output: x-1/0 = y-2/0 = z-3/-3 = t >>>b.direction_ratios() Output: [0,0,-3] >>>a = Line(Point(1,2,3),Point(2,3,4)) >>>b = Line(Point(5,5,5),Point(-8,-6,-3)) >>>a.intersection(b) Output: Point(-1.5, -0.5, 0.5)

###Ray and Line Segments >>>a = Segment(Point(1,2,3), Point(2,2,1)).intersection(Ray(Point(1,1,3), Point(3,5,2)) Output: Point(5/3, 2, 5/3) >>>a = Ray(Point(1,2,3), Point(1,3,4)) >>>a.direction_vector Output: [0,1,1] >>>a.source Output: Point(1,2,3)

###Plane >>>a = Plane(Point(1,-2,0),Point(3,1,4),Point(0,-1,2)) >>>a.equation() Output: 2x-8y+5z = 18 >>>a.normal_vectors() Output: [2,8,5] >>>b = Line(Point(5,5,5),Point(6,6,6)) >>>a.intersection(b) Output:Point(-18,-18,-18) >>>a.is_parallel(b) Output:False >>>a.is_perpendicular(b) Output:False >>>a = Plane(Point(2,-1,0),normal_vectors=[1,1,0]) >>>a.equation() Output: x+y-1= 0 >>>a.angle_between(Line(Point(1,-1),direction_ratios=[2,1,2]) Output: pi/4

###Geometry Result >>>x,y,z = map(Symbol,'xyz') >>>p1,p2,p3 = Point(x,y),Point(y,z),Point(2xy,y) >>>Point.is_collinear(p1,p2,p3)# As the points are symbolic the is_collinear method of the point will call the is_collinear method of the GeometryResult class Output:Points will be collinear if z - y - 2yz + 2*y**2 == 0 >>>a,b,c,d = map(Symbol,'abcd') >>>l = Line(Point(a,b),Point(c,d)) >>>e = Circle(Point(0,0),1).is_tangent(l) Output:The line is tangent if [{a == c} and [{b == d}]] # Instead of False

###Hyperbola >>>a = Hyperbola(Point(0,0),2,3) >>>a.equation() Output:x2/4 - y/9 = 1 >>>a.eccentricity() Output: sqrt(13)/2 >>>a.asymptotes() Output: [Line(Point(0,0),Point(1,1.5)),Line(Point(0,0),Point(-1,1.5))]

###Parabola >>>a = Parabola(Point(0,0),a).equation() Output: y**2 = 4ax # The default parabola is symmetric/parallel to the y axis. >>>a = Parabola(Point(2,3),2,x).equation() #The argument x makes the parabola parallel to the x-axis Output: (x-2)**2 = 8(y-3) >>>a = Parabola(Point(0,0),0.5).tangent_lines(-1,2) Output: Line(Point(0,-2),Point(-0.5,0)

###General >>>a = Ellipse(Point(0,0),1,2).intersection(Line(Point(1,1,1),Point(2,2,2)) #Similar to intersection of a line and a plane Output: Point(0,0,0) >>>a = Ellipse(Point(0,0),1,2).intersection(Hyperbola(Point(0,0),1,2)) Output: [Point(1,0), Point(-1,0)] >>>a = Plane(Point(0,1,1),Point(0,2,3),Point(0,5,6)).contains(Ellipse(Point(0,0),1,2)) Output: False

###Note This is just a prototype which includes two or three methods of any given class.

#Timeline This timeline has been made keeping in mind the 40 hour requirement.I am not planning on taking any vacations during the summer and would dedicatedly work on the project.

###Community Bonding period Objectives-

  • Note the methods to be implemented in each class.
  • Decide the structure of all the classes.

###Week 1 Objectives-

  • Implement the Point class(Includes the functionality for 2-D and 3-D Points)
  • Write unit tests.
  • Submit my first PR

###Week 2-4 Objectives-

  • Line class(Includes the functionality for all lines, segments, rays in 2-D and 3-D with a common Linear entity class)
  • Write unit tests
  • Submit a PR

###Week 5 Objectives-

  • Make sure that the code for the classes like Polygon , Curve, Geometric entities doesn't break because of the implementation of the above classes.
  • Adding tests
  • Submit a PR

###Week 6-7 Objectives-

  • Implementation of the Plane class.
  • Make sure that it integrates properly with the existing Geometry module.
  • Write unit tests.
  • Submit a PR

###Week 8-9 Hyperbola and Rectangular Hyperbola Class Objectives-

  • Implementing the Hyperbola class
  • Implementing the Rectangular Hyperbola class
  • Write unit tests
  • Submit a PR

###Week 10 Objectives-

  • Implementing the Parabola class
  • Write unit tests
  • Submit a PR

Week 11

Objectives-

  • Implementing the GeometryResult class and integrating it with the code.
  • Adding tests
  • Submit a PR

###Week 12 Objectives-

  • Make sure that the module works well as a whole
  • Make sure that the code is extensively tested
  • Make sure that the code is properly documented

###Week 13

  • Buffer period.
  • Removing bugs.

##Post Gsoc I would love to work not only on the geometry module but for sympy as a whole.There are a few things on top of my priority list

  • Adding classes for some basic 3-D solids like Cube, Sphere and for curves like Ellipsoid and Hyperboloid
  • Adding a class for finding area between any two curves.This is the implementation by Wolfram alpha

####I will begin implementing these if my project gets over before the specified timeline

##References

  • The elements of coordinate geometry, by S. L. Loney
  • Analytical Geometry of Three Dimensions by William H Mccrea
  • Geometry: A Comprehensive Course by Dan Pedoe
  • Technical Calculus with Analytic Geometry by Judith L Gersting