
    wg                     .   d Z ddlmZ ddlmZmZmZ ddlmZm	Z	m
Z
mZ ddlmZ ddlmZmZmZmZ ddlmZmZmZmZ ddlmZ d#d
d	ddZd Zd Zd#dZd#dZd Zd Z d Z!d Z"d Z#	 	 d$dZ$d Z%d%dZ&d#dZ'd Z(d Z)d&dZ*d'dZ+d Z,d Z-d  Z.d! Z/d" Z0y	)(a  
Module to implement integration of uni/bivariate polynomials over
2D Polytopes and uni/bi/trivariate polynomials over 3D Polytopes.

Uses evaluation techniques as described in Chin et al. (2015) [1].


References
===========

.. [1] Chin, Eric B., Jean B. Lasserre, and N. Sukumar. "Numerical integration
of homogeneous functions on convex and nonconvex polygons and polyhedra."
Computational Mechanics 56.6 (2015): 967-981

PDF link : http://dilbert.engr.ucdavis.edu/~suku/quadrature/cls-integration.pdf
    )
cmp_to_key)xyz)SdiffExprSymbol)_sympify)	Segment2DPolygonPointPoint2D)LCgcd_listdegree_listPoly)	nsimplifyNF)	clockwise
max_degreec          	         |r:t        | t              rt        t        | j                        ddi} nt	        d      t        | t              rt        |       }| j                  }nt        | d         dk(  rt        |       }t        | d   d         dk(  rlt        d|      D cg c]  }t        | |dz
  |z     | |   d       }}| }t        |      }	t        |	      D cg c]  }t        ||   ||dz   |	z            }}n>t        d      | d   }
| dd	 }t        ||
      }||t	        d
      t        |||
|      S |bi }|wg }|D ]n  }t        |      }t        |      dk(  r%|j                         d   s|j                  |       At!        |      j#                         |k  s^|j                  |       p |}t        |t$              s|t	        d      t        |d   d         dk(  rt        d|
||      }nt'        d|||      }||S |D ]  } t)        |       } | |vs| j*                  r"t,        j.                  |t,        j.                  <   At,        j.                  }t        | d      }|D ]&  }t1        |      }t3        |      \  }}|||   |z  z  }( ||| <    |S |t	        d
      t'        |||      S c c}w c c}w )a  Integrates polynomials over 2/3-Polytopes.

    Explanation
    ===========

    This function accepts the polytope in ``poly`` and the function in ``expr``
    (uni/bi/trivariate polynomials are implemented) and returns
    the exact integral of ``expr`` over ``poly``.

    Parameters
    ==========

    poly : The input Polygon.

    expr : The input polynomial.

    clockwise : Binary value to sort input points of 2-Polytope clockwise.(Optional)

    max_degree : The maximum degree of any monomial of the input polynomial.(Optional)

    Examples
    ========

    >>> from sympy.abc import x, y
    >>> from sympy import Point, Polygon
    >>> from sympy.integrals.intpoly import polytope_integrate
    >>> polygon = Polygon(Point(0, 0), Point(0, 1), Point(1, 1), Point(1, 0))
    >>> polys = [1, x, y, x*y, x**2*y, x*y**2]
    >>> expr = x*y
    >>> polytope_integrate(polygon, expr)
    1/4
    >>> polytope_integrate(polygon, polys, max_degree=3)
    {1: 1, x: 1/2, y: 1/2, x*y: 1/4, x*y**2: 1/6, x**2*y: 1/6}
    evaluateFz>clockwise=True works for only 2-PolytopeV-representation inputr         plane2Dz<Integration for H-representation 3Dcase not implemented yet.Nz1Input expression must be a valid SymPy expressionz-Input polynomials must be list of expressions   T)separate)
isinstancer   
point_sortvertices	TypeErrorhyperplane_parameterssideslenrangeintersectionr   NotImplementedErrormain_integrate3d	decomposepopitemappendr   total_degreelistmain_integrater   is_zeror   Zeror   strip)polyexprr   r   	hp_paramsfacetspleniintersectionslintsr    resultf_expre_result_dictintegral_valuemonomsmonomcoeffms                        \/home/mcse/projects/flask/flask-venv/lib/python3.12/site-packages/sympy/integrals/intpoly.pypolytope_integraterE      s   F dG$Jt}}5FFD 5 6 6 $ )$/		T!W	4ytAwqz?a ',Atn6!" *$A~*>Q*35 6M 6 I&E  %U|-  a 0 -q1uo >@ -F - & 'B C C 7ab)&(;	| STT#D&(IFFF %aLq6Q;qyy{1~MM!$!W))+z9MM!$% D$%$*:KLLy|A1$*1fh	+57K )FIzJK< 	.DD>D6!<<%&VVF166N!""4$7# =E%e,E$U|HE1"k!nu&<<N=  .t	. |KLL$	22A6
-s   # J>Kc                     | j                   r t        j                  t        j                  fS | j                  r| t        j                  fS t        |       }|| |z  fS N)r/   r   r0   	is_numberOner   )rA   rB   s     rD   r1   r1      sH    }}vvqvv~	aee|5	eem##    c                     t         t        f}t        |      }t        j                  }| D ]a  }t        j                  }d}|D ];  }	t        |||	d   |	d   | |   ||      }
||
|	d   t        |	d         z  z  z  }|dz  }= |||z   z  }||z  }c |S )Nr   r   )r   r   r$   r   r0   integration_reductionnorm)polynomialsr5   r4   dims
dim_lengthr?   degpoly_contributefacet_counthpvalue_over_boundarys              rD   _polynomial_integraterV      s    q6DTJVVN *&& 	B"78C8:1r!u8CC8H8<c	#C
 2bed2a5k6IJJO1K	 	J,-/)* rJ   c                 v   i }t         t        t        f}t        |      }|rt	        |d      }|D 	
cg c]  }	|	D ]  }
|
D ]  }|   }}
}	}|D ]
  }d||d   <    t        |      D ]  \  }}|d   |d   }}|||   d      }t        |      D ]{  \  }}|\  } }}}}}}}||z   |z   }|j                  rt        j                  }nt        ||||| ||||||||||      }||d<   || xx   ||t        |      z  z  ||z   |z   |z   z  z  cc<   }  |S t        j                  }t        |       }|D ]  }t        j                  } d}t        |      D ]S  \  }}!||   }|d   j                  rt        |!||||| |      }"| |"|d   t        t        |d               z  z  z  } |dz  }U | ||z   z  } || z  } |S c c}}
}	w )aX  Function to translate the problem of integrating uni/bi/tri-variate
    polynomials over a 3-Polytope to integrating over its faces.
    This is done using Generalized Stokes' Theorem and Euler's Theorem.

    Parameters
    ==========

    expr :
        The input polynomial.
    facets :
        Faces of the 3-Polytope(expressed as indices of `vertices`).
    vertices :
        Vertices that constitute the Polytope.
    hp_params :
        Hyperplane Parameters of the facets.
    max_degree : optional
        Max degree of constituent monomial in given list of polynomial.

    Examples
    ========

    >>> from sympy.integrals.intpoly import main_integrate3d,     hyperplane_parameters
    >>> cube = [[(0, 0, 0), (0, 0, 5), (0, 5, 0), (0, 5, 5), (5, 0, 0),                (5, 0, 5), (5, 5, 0), (5, 5, 5)],                [2, 6, 7, 3], [3, 7, 5, 1], [7, 6, 4, 5], [1, 5, 4, 0],                [3, 1, 0, 2], [0, 4, 6, 2]]
    >>> vertices = cube[0]
    >>> faces = cube[1:]
    >>> hp_params = hyperplane_parameters(faces, vertices)
    >>> main_integrate3d(1, faces, vertices, hp_params)
    -125
    r   r   r      )r   r   r   r$   gradient_terms	enumerater/   r   r0   integration_reduction_dynamicrM   r)   polygon_integratetuple)#r3   r5   r    r4   r   r:   rO   rP   
grad_termsz_termsx_termterm	flat_listrS   rT   abx0r7   rA   x_dy_dz_dz_indexy_indexx_indexr=   degreevalue_over_facer?   rN   rQ   rR   facetpis#                                      rD   r(   r(      sp   D Fq!9DTJ#J2
)3 ) )g#*)!')  )T )T )	 )  	 DF47O	   )3 	COKa5"Q%qA&-a01B%i0 C5 EJAc3WgwsS99&'ffO 6fk167vt6=w6=r:672	G $ +ata[!"%/#%5%;c%A!C CC		C* o 	.CffOK%f- !5q\a5==&ub!VXtSQ2UT%1,//$1 1q ! 
S 01Oo-N	. [)s   F4c                    t         t        f}t        |      }i }|rg dgt        |      z   }t	        |      D ]  \  }}	|	d   |	d   }}
||   j
                  d   }t	        |      D ]  \  }}|\  }}}}|j                  |d      }t        j                  }|j                  rt        j                  }n||z   }t        |||
||||||||||      }||d<   |#||xx   ||t        |
      z  z  ||z   z  z  cc<   ||t        |
      z  z  ||z   z  ||<     |S t        | t              st        |       }t        |||      S | D ci c]  }|t        t        |      ||       c}S c c}w )ay  Function to translate the problem of integrating univariate/bivariate
    polynomials over a 2-Polytope to integrating over its boundary facets.
    This is done using Generalized Stokes's Theorem and Euler's Theorem.

    Parameters
    ==========

    expr :
        The input polynomial.
    facets :
        Facets(Line Segments) of the 2-Polytope.
    hp_params :
        Hyperplane Parameters of the facets.
    max_degree : optional
        The maximum degree of any monomial of the input polynomial.

    >>> from sympy.abc import x, y
    >>> from sympy.integrals.intpoly import main_integrate,    hyperplane_parameters
    >>> from sympy import Point, Polygon
    >>> triangle = Polygon(Point(0, 3), Point(5, 3), Point(1, 1))
    >>> facets = triangle.sides
    >>> hp_params = hyperplane_parameters(triangle)
    >>> main_integrate(x**2 + y**2, facets, hp_params)
    325/6
    )r   r   r   r   r   r   Nr   )r   r   r$   rY   rZ   pointsgetr   r0   r/   r[   rM   r   r-   r)   rV   )r3   r5   r4   r   rO   rP   r:   r^   rS   rT   rc   rd   re   r7   rA   rC   rf   rg   r=   valuerl   rU   rN   r<   s                           rD   r.   r.     s   6 q6DTJF"^nZ&@@
(3 	FOKa5"Q%qA$++A.B%j1 F5 "'3Q

1d+99*+&&' 3YF5fk167FD#69:r6@!E (
 /a$1I!4)*T!W"69Cf9L"N NI !4!"T!W!.1;f1D!FF1I)F		F4 $%#D/K(fiHHW[\RSA,Yq\69MM\\\s   E$c                 
   t        |      }|j                  rt         j                  S t         j                  }|| d      }t        |       }	t	        |       D ];  \  }
}||   || |
dz   |	z        f}|t        |||d         t        | |
|||      z  z  }= |j                  s[t        |t              |d   z  t        |t              |d   z  z   t        |t              |d   z  z   }|t        | ||||||dz
        z  }||dz   z  }|S )a  Helper function to integrate the input uni/bi/trivariate polynomial
    over a certain face of the 3-Polytope.

    Parameters
    ==========

    facet :
        Particular face of the 3-Polytope over which ``expr`` is integrated.
    index :
        The index of ``facet`` in ``facets``.
    facets :
        Faces of the 3-Polytope(expressed as indices of `vertices`).
    vertices :
        Vertices that constitute the facet.
    expr :
        The input polynomial.
    degree :
        Degree of ``expr``.

    Examples
    ========

    >>> from sympy.integrals.intpoly import polygon_integrate
    >>> cube = [[(0, 0, 0), (0, 0, 5), (0, 5, 0), (0, 5, 5), (5, 0, 0),                 (5, 0, 5), (5, 5, 0), (5, 5, 5)],                 [2, 6, 7, 3], [3, 7, 5, 1], [7, 6, 4, 5], [1, 5, 4, 0],                 [3, 1, 0, 2], [0, 4, 6, 2]]
    >>> facet = cube[1]
    >>> facets = cube[1:]
    >>> vertices = cube[0]
    >>> polygon_integrate(facet, [(0, 1, 0), 5], 0, facets, vertices, 1, 0)
    -25
    r   r   r   )r   r/   r0   r$   rZ   distance_to_sidelineseg_integraterH   r   r   r   r   r\   )rn   hp_paramindexr5   r    r3   rl   r:   re   	facet_lenr7   facsides                rD   r\   r\   K  s&   D T7D||vvVVF	%(	BE
IE" <3xq1u	.A(BCD"2tXa[9eQdF;< 	<< >>D!}r!u$tD!}r!u'<<qMBqE!"#E8UFH$(&1*6 	6
vzFMrJ   c                   	
 |\  }}|D cg c]  }dt        |      z  t        |      z   }}t        dd      D cg c]  }||   ||   z
   }}t        dd      D cg c]  }||   t        |      z   }}t        d||      	t        dd      D cg c]  }|d   |   | |   z
   c}
t	        	
fdt        dd      D              }|S c c}w c c}w c c}w c c}w )ax  Helper function to compute the signed distance between given 3D point
    and a line segment.

    Parameters
    ==========

    point : 3D Point
    line_seg : Line Segment

    Examples
    ========

    >>> from sympy.integrals.intpoly import distance_to_side
    >>> point = (0, 0, 0)
    >>> distance_to_side(point, [(0, 0, 1), (0, 1, 0)], (1, 0, 0))
    -sqrt(2)/2
    r   r   )r   r   r   c              3   4   K   | ]  }|   |   z    y wrG    ).0r7   n_sidevectorx0s     rD   	<genexpr>z#distance_to_side.<locals>.<genexpr>  s     C!hqkF1I-C   )r   rM   r%   cross_productsum)pointline_segAx1x2r7   
rev_normalvectordot_productr   r   s            @@rD   ru   ru     s    $ FB-./"qt)DG#/J/%*1a[1bebem1F1.3Aqk:fQiV$:F:9j&9F38A;?aAq)?HCuQ{CCK 01: @s   !CCCCc           
      j   t        |      }|j                  rt        j                  S t        j                  }|d   }t	        t        t        d      D cg c]  }|d   |   |d   |   z
   c}            }t        |t              r>t        |d   d   t        |d   d   t        |d   d   i}	|||j                  |	      z  z  }n|||z  z  }t        |t              |d   z  t        |t              |d   z  z   t        |t              |d   z  z   }|t        | ||||dz
        z  }||dz   z  }|S c c}w )a  Helper function to compute the line integral of ``expr`` over ``line_seg``.

    Parameters
    ===========

    polygon :
        Face of a 3-Polytope.
    index :
        Index of line_seg in polygon.
    line_seg :
        Line Segment.

    Examples
    ========

    >>> from sympy.integrals.intpoly import lineseg_integrate
    >>> polygon = [(0, 5, 0), (5, 5, 0), (5, 5, 5), (0, 5, 5)]
    >>> line_seg = [(0, 5, 0), (5, 5, 0)]
    >>> lineseg_integrate(polygon, 0, line_seg, 1, 0)
    5
    r   r   r   r   )r   r/   r   r0   rM   r]   r%   r   r	   r   r   r   subsr   rv   )
polygonrx   r   r3   rl   r:   re   r7   distance	expr_dicts
             rD   rv   rv     s@   , D>D||vvVVF	!BE 8%q8A;q>HQKN: % & 'H$AAA(	 	(TYYy111(T/!a=2a5 4a=2a5#88T11D $
KKF
vzFM%s   D0c                    t        |      }|j                  r|S t        j                  }| |   j                  d   }t        |       }	t        t        f}
t        ||
d         |d   z  t        ||
d         |d   z  z   }|dk7  r|t        | ||||||dz
        z  }|t        |	|| |||
      z  }|t        |      |z   dz
  z  S )a  Helper method for main_integrate. Returns the value of the input
    expression evaluated over the polytope facet referenced by a given index.

    Parameters
    ===========

    facets :
        List of facets of the polytope.
    index :
        Index referencing the facet to integrate the expression over.
    a :
        Hyperplane parameter denoting direction.
    b :
        Hyperplane parameter denoting distance.
    expr :
        The expression to integrate over the facet.
    dims :
        List of symbols denoting axes.
    degree :
        Degree of the homogeneous polynomial.

    Examples
    ========

    >>> from sympy.abc import x, y
    >>> from sympy.integrals.intpoly import integration_reduction,    hyperplane_parameters
    >>> from sympy import Point, Polygon
    >>> triangle = Polygon(Point(0, 3), Point(5, 3), Point(1, 1))
    >>> facets = triangle.sides
    >>> a, b = hyperplane_parameters(triangle)[0]
    >>> integration_reduction(facets, 0, a, b, 1, (x, y), 0)
    5
    r   r   )r   r/   r   r0   rq   r$   r   r   r   rL   left_integral2D)r5   rx   rc   rd   r3   rO   rl   rs   re   rC   gensinner_products               rD   rL   rL     s    F D>D||FFE			a	 BFAq6DtAw'"Q%/$tT!W2E12MMM&vua'4dFQJH 	H 
_Qvr4>>E#d)f$q())rJ   c           
         t         j                  }t        |       D ]  }d}||dz
  | z  |dz   | z  fv rt        ||   ||   d      }|s-t	        t        t        d ||                  }	t        |      sYt        |t              rSt        |      dk(  r|d   |d   |d   |d   |d   |d   i}
n|d   |d   |d   |d   i}
||	|j                  |
      z  z  }||	|z  z  } |S )a  Computes the left integral of Eq 10 in Chin et al.
    For the 2D case, the integral is just an evaluation of the polynomial
    at the intersection of two facets which is multiplied by the distance
    between the first point of facet and that intersection.

    Parameters
    ==========

    m :
        No. of hyperplanes.
    index :
        Index of facet to find intersections with.
    facets :
        List of facets(Line Segments in 2D case).
    x0 :
        First point on facet referenced by index.
    expr :
        Input polynomial
    gens :
        Generators which generate the polynomial

    Examples
    ========

    >>> from sympy.abc import x, y
    >>> from sympy.integrals.intpoly import left_integral2D
    >>> from sympy import Point, Polygon
    >>> triangle = Polygon(Point(0, 3), Point(5, 3), Point(1, 1))
    >>> facets = triangle.sides
    >>> left_integral2D(3, 0, facets, facets[0].points[0], 1, (x, y))
    5
    r   r   	segment2Dc                     | |z
  S rG   r   )r   r   s     rD   <lambda>z!left_integral2D.<locals>.<lambda>)  s
    !a% rJ   r   r   r   )r   r0   r%   r&   rM   r]   map	is_vertexr   r	   r$   r   )rC   rx   r5   re   r3   r   rs   j	intersectdistance_originr   s              rD   r   r     s   B FFE1X 4	%!)q519/22$VE]F1I{KI"5-?-6*< $= >O#dD)4yA~%)!Wil%)!Wil%)!Wil%<	 &*!Wil%)!Wil%<	_tyy/CCCE_t33E%4& LrJ   c           	         t         j                  }t        |       }|t         j                  k(  r|S t        |      dk(  rr|j                  sR||   \  }}}}|dkD  r||	z
  |z   dz
  nd}|dkD  r|dz
  nd}||   d   ||   d   }}|||z  |
d   z  ||z  |
d   z  z   z  }|t	        ||| |
||      z  }n|	}|j                  s|||z
  |z
  |}}}|dkD  r||dz
     |dz
     |   d   nd}|dkD  r||dz
     |   |   d   nd}|dkD  r||dz
     |   |dz
     d   nd}|||z  |
d   z  ||z  |
d   z  z   ||z  |
d   z  z   z  }|t        | |||||      z  }|t        |      |z   dz
  z  S )a  The same integration_reduction function which uses a dynamic
    programming approach to compute terms by using the values of the integral
    of previously computed terms.

    Parameters
    ==========

    facets :
        Facets of the Polytope.
    index :
        Index of facet to find intersections with.(Used in left_integral()).
    a, b :
        Hyperplane parameters.
    expr :
        Input monomial.
    degree :
        Total degree of ``expr``.
    dims :
        Tuple denoting axes variables.
    x_index :
        Exponent of 'x' in ``expr``.
    y_index :
        Exponent of 'y' in ``expr``.
    max_index :
        Maximum exponent of any monomial in ``monomial_values``.
    x0 :
        First point on ``facets[index]``.
    monomial_values :
        List of monomial values constituting the polynomial.
    monom_index :
        Index of monomial whose integration is being found.
    vertices : optional
        Coordinates of vertices constituting the 3-Polytope.
    hp_param : optional
        Hyperplane Parameter of the face of the facets[index].

    Examples
    ========

    >>> from sympy.abc import x, y
    >>> from sympy.integrals.intpoly import (integration_reduction_dynamic,             hyperplane_parameters)
    >>> from sympy import Point, Polygon
    >>> triangle = Polygon(Point(0, 3), Point(5, 3), Point(1, 1))
    >>> facets = triangle.sides
    >>> a, b = hyperplane_parameters(triangle)[0]
    >>> x0 = facets[0].points[0]
    >>> monomial_values = [[0, 0, 0, 0], [1, 0, 0, 5],                           [y, 0, 1, 15], [x, 1, 0, None]]
    >>> integration_reduction_dynamic(facets, 0, a, b, x, 1, (x, y), 1, 0, 1,                                      x0, monomial_values, 3)
    25/2
    r   r   r   r   rX   )r   r0   r$   rH   r   left_integral3D)r5   rx   rc   rd   r3   rl   rO   rk   rj   	max_indexre   monomial_valuesmonom_indexr    rw   rs   rC   r=   x_degreey_degreex_valuey_valueri   z_degreez_values                            rD   r[   r[   :  s%   r FFEFAqvv~
4yA~~~'6{'C$Ax1'!| "I-12 )1AkAo1G(+_W-Ea-H G X'"Q%/(W2Dr!u2LLLEE62tTBB ~~+2+2W+<w+F !)hH a< &gk27Q;?HK%&  a< &gk27;GDQG%&  a< &gk27;GaKHK%&  X'"Q%/(W2Dr!u2LLW$r!u,- -E 	!)8V= 	=CI&*++rJ   c           
          t         j                  }| |   }||d      }t        |      }	t        |      D ];  \  }
}||   |||
dz   |	z        f}|t	        |||d         t        ||
|||      z  z  }= |S )a  Computes the left integral of Eq 10 in Chin et al.

    Explanation
    ===========

    For the 3D case, this is the sum of the integral values over constituting
    line segments of the face (which is accessed by facets[index]) multiplied
    by the distance between the first point of facet and that line segment.

    Parameters
    ==========

    facets :
        List of faces of the 3-Polytope.
    index :
        Index of face over which integral is to be calculated.
    expr :
        Input polynomial.
    vertices :
        List of vertices that constitute the 3-Polytope.
    hp_param :
        The hyperplane parameters of the face.
    degree :
        Degree of the ``expr``.

    Examples
    ========

    >>> from sympy.integrals.intpoly import left_integral3D
    >>> cube = [[(0, 0, 0), (0, 0, 5), (0, 5, 0), (0, 5, 5), (5, 0, 0),                 (5, 0, 5), (5, 5, 0), (5, 5, 5)],                 [2, 6, 7, 3], [3, 7, 5, 1], [7, 6, 4, 5], [1, 5, 4, 0],                 [3, 1, 0, 2], [0, 4, 6, 2]]
    >>> facets = cube[1:]
    >>> vertices = cube[0]
    >>> left_integral3D(facets, 3, 1, vertices, ([0, -1, 0], -5), 0)
    -50
    r   r   )r   r0   r$   rZ   ru   rv   )r5   rx   r3   r    rw   rl   rs   rn   re   ry   r7   rz   r{   s                rD   r   r     s    N FFE5ME	%(	BE
IE" <3xq1u	.A(BCD!"dHQK8eQdF;< 	<< LrJ   c                 (   |dk(  rld}dgt        | dz  d| z  z   dz   dz        z  }t        d| dz         D ]8  }t        d| |z
  dz         D ]!  }t        |z  t        |z  z  ||dg||<   |dz  }# : |S t        d| dz         D cg c]r  }t        d|dz         D cg c]U  }t        ||z
  dd      D cg c]9  }t        |z  t        |z  z  t        ||z
  |z
  z  z  ||||z
  |z
  ||||z
  |z
  dg; c}W c}}t }}}}|S c c}w c c}}w c c}}}w )an  Returns a list of all the possible monomials between
    0 and y**binomial_power for 2D case and z**binomial_power
    for 3D case.

    Parameters
    ==========

    binomial_power :
        Power upto which terms are generated.
    no_of_gens :
        Denotes whether terms are being generated for 2D or 3D case.

    Examples
    ========

    >>> from sympy.integrals.intpoly import gradient_terms
    >>> gradient_terms(2)
    [[1, 0, 0, 0], [y, 0, 1, 0], [y**2, 0, 2, 0], [x, 1, 0, 0],
    [x*y, 1, 1, 0], [x**2, 2, 0, 0]]
    >>> gradient_terms(2, 3)
    [[[[1, 0, 0, 0, 0, 0, 0, 0]]], [[[y, 0, 1, 0, 1, 0, 0, 0],
    [z, 0, 0, 1, 1, 0, 1, 0]], [[x, 1, 0, 0, 1, 1, 0, 0]]],
    [[[y**2, 0, 2, 0, 2, 0, 0, 0], [y*z, 0, 1, 1, 2, 0, 1, 0],
    [z**2, 0, 0, 2, 2, 0, 2, 0]], [[x*y, 1, 1, 0, 2, 1, 0, 0],
    [x*z, 1, 0, 1, 2, 1, 1, 0]], [[x**2, 2, 0, 0, 2, 2, 0, 0]]]]
    r   r   Nr   r   r}   )intr%   r   r   r   )binomial_power
no_of_genscounttermsx_county_countz_counts          rD   rY   rY     s   6 Qn1A4FFJaOPPQ 23 	G NW$<q$@A  !7
1g: 5 '! 5e
	 L !&a!); <> >  !&a1 57
  !&g&7R @	B 	 L1</'G+g567Wg&7'&AWg&7'&A1F B 7 > > LB 7 >s*   DD3>D1D6DDDc                    t        | t              rt        | j                        | j                  d   gz   }dgt	        |      dz
  z  }t        t	        |      dz
        D ]{  }||   ||dz      }d   |d   z
  }|d   d   z
  }|d   d   z  |d   d   z  z
  }t        |||g      }t        |      |z  }t        |      |z  t        |      |z  f}	|	|f||<   } |S dgt	        |       z  }t        |       D ]  \  }}
|
dd D cg c]  }||   	 c}\  }}t        ||      t        fdt        dd      D              }t              }|j                  rd}D cg c]  }||z  	 c}||z  }|f||<    |S c c}w c c}w )a  A helper function to return the hyperplane parameters
    of which the facets of the polytope are a part of.

    Parameters
    ==========

    poly :
        The input 2/3-Polytope.
    vertices :
        Vertex indices of 3-Polytope.

    Examples
    ========

    >>> from sympy import Point, Polygon
    >>> from sympy.integrals.intpoly import hyperplane_parameters
    >>> hyperplane_parameters(Polygon(Point(0, 3), Point(5, 3), Point(1, 1)))
    [((0, 1), 3), ((1, -2), -1), ((-2, -1), -3)]
    >>> cube = [[(0, 0, 0), (0, 0, 5), (0, 5, 0), (0, 5, 5), (5, 0, 0),                (5, 0, 5), (5, 5, 0), (5, 5, 5)],                [2, 6, 7, 3], [3, 7, 5, 1], [7, 6, 4, 5], [1, 5, 4, 0],                [3, 1, 0, 2], [0, 4, 6, 2]]
    >>> hyperplane_parameters(cube[1:], cube[0])
    [([0, -1, 0], -5), ([0, 0, -1], -5), ([-1, 0, 0], -5),
    ([0, 1, 0], 0), ([1, 0, 0], 0), ([0, 0, 1], 0)]
    r   Nr   r   c              3   4   K   | ]  }|   |   z    y wrG   r   )r   r   normalv1s     rD   r   z(hyperplane_parameters.<locals>.<genexpr>+  s     ;!F1I1%;r   )r   r   r-   r    r$   r%   r   r   rZ   r   r   r/   )r2   r    paramsr7   v2a1a2rd   factorrc   r   vertexv3rz   r   r   r   s                  @@rD   r"   r"     s   6 $ &$--*:);;3x=1,-s8}q() 	A!B!a%BAABAAB1111-Ar2qk*F!vA220AAF1I	2 M #d)##D/ 		$JAw9@!Ev(6*EJBB"2r2.F;uQ{;;A6"C{{'-.!a#g.FCAF1I		$ M F /s   	F%F	c                 &   t        dd      D cg c]  }||   | |   z
   }}t        dd      D cg c]  }||   | |   z
   }}|d   |d   z  |d   |d   z  z
  |d   |d   z  |d   |d   z  z
  |d   |d   z  |d   |d   z  z
  gS c c}w c c}w )zeReturns the cross-product of vectors (v2 - v1) and (v3 - v1)
    That is : (v2 - v1) X (v3 - v1)
    r   r   r   r   )r%   )r   r   r   r   s       rD   r   r   5  s     "'q!	-A"Q%"Q%-	-B	-!&q!	-A"Q%"Q%-	-B	-qEBqEMBqEBqEM)qEBqEMBqEBqEM)qEBqEMBqEBqEM)+ + 
.	-s
   B	Bc                    |j                   d   \  }}d }d }t        t        f}i }	|D ]  }
t        j                  |	|
<    t        |      dkD  rt        |      dk(  rX| d   dk(  r$ ||      rt        j                  || d   z  fS ||fS | d   dk(  r$ ||      r|| d   z  t        j                  fS ||fS t        |t              r|j                  r|j                  D ]  }|j                  r:|j                  d   |v s!|	|j                  d   xx   |j                  d   z  cc<   I|j                  D ]m  }t        |j                        }|dk(  r||v r|	|xx   dz  cc<   /|dk(  s5|j                  d   |v sG|	|j                  d   xx   |j                  d   z  cc<   o  n|j                  r}|j                  D ]m  }t        |j                        }|dk(  r||v r|	|xx   dz  cc<   /|dk(  s5|j                  d   |v sG|	|j                  d   xx   |j                  d   z  cc<   o nJ|j                  r |j                  d   |	|j                  d   <   n|j                  r|	|xx   dz  cc<   n||fS t        |	j                         d       }	|	d   d   |	d   d   k\  rJ ||      rt        j                  || d   z  f}|S  ||      r|| d   z  t        j                  f}|S ||f}|S  ||      r|| d   z  t        j                  f}|S  ||      rt        j                  || d   z  f}|S ||f}|S || d   z  }|S )a  Helper method for polytope_integrate. Currently not used in the main
    algorithm.

    Explanation
    ===========

    Returns a point on the lineseg whose vector inner product with the
    divergence of `expr` yields an expression with the least maximum
    total power.

    Parameters
    ==========

    a :
        Hyperplane parameter denoting direction.
    b :
        Hyperplane parameter denoting distance.
    lineseg :
        Line segment on which to find the origin.
    expr :
        The expression which determines the best point.

    Algorithm(currently works only for 2D use case)
    ===============================================

    1 > Firstly, check for edge cases. Here that would refer to vertical
        or horizontal lines.

    2 > If input expression is a polynomial containing more than one generator
        then find out the total power of each of the generators.

        x**2 + 3 + x*y + x**4*y**5 ---> {x: 7, y: 6}

        If expression is a constant value then pick the first boundary point
        of the line segment.

    3 > First check if a point exists on the line segment where the value of
        the highest power generator becomes 0. If not check if the value of
        the next highest becomes 0. If none becomes 0 within line segment
        constraints then pick the first boundary point of the line segment.
        Actually, any point lying on the segment can be picked as best origin
        in the last case.

    Examples
    ========

    >>> from sympy.integrals.intpoly import best_origin
    >>> from sympy.abc import x, y
    >>> from sympy import Point, Segment2D
    >>> l = Segment2D(Point(0, 3), Point(1, 1))
    >>> expr = x**3*y**7
    >>> best_origin((2, 1), 3, l, expr)
    (0, 3.0)
    r   c                    | j                   \  }}|j                  j                  rt        |      S |j                  j                  rt        |      S |j                  |j                  z  t        j
                  k  r]|j                  |j                  |j                  z
  z  |j                  |j                  z
  z  |j                  z   t        j
                  fS y)zReturns the point where the input line segment
        intersects the x-axis.

        Parameters
        ==========

        ls :
            Line segment
        r   )rq   r   r/   r]   r   r0   r   lspqs      rD   
x_axis_cutzbest_origin.<locals>.x_axis_cuty  s     yy133;;8OSS[[8OSSWqvv33!##)$accACCi01336>>rJ   c                    | j                   \  }}|j                  j                  rt        |      S |j                  j                  rt        |      S |j                  |j                  z  t        j
                  k  r]t        j
                  |j                  |j                  |j                  z
  z  |j                  |j                  z
  z  |j                  z   fS y)zReturns the point where the input line segment
        intersects the y-axis.

        Parameters
        ==========

        ls :
            Line segment
        r   )rq   r   r/   r]   r   r0   r   r   s      rD   
y_axis_cutzbest_origin.<locals>.y_axis_cut  s     yy133;;8OSS[[8OSSWqvv66133!##),accACCi8133>>>rJ   r   r   c                     t        | d         S Nr   )str)ks    rD   r   zbest_origin.<locals>.<lambda>  s    c!A$i rJ   key)rq   r   r   r   r0   r$   r   r	   is_Addargsis_Powis_Mul	is_Symbolsorteditems)rc   rd   linesegr3   r   b1r   r   r   
power_gensr7   monomial
univariate	term_typera   re   s                   rD   best_originr   @  sg   n ^^AFB(( q6DJ 
1 4y1}t9>tqyg&661QqT6>)r6M1g&QqT6166>)r6MdD!{{ $		 >H#==+t3&x}}Q'78HMM!<LL8*2-- >J(+JOO(<I(A~*2D *: 6! ; 6!*aJOOA4F$4N *:??1+= >+5??1+=!> >>>  II AD #DIII A~$$,"4(A-("aDIIaLD,@"499Q<0DIIaL@0A +/99Q<
499Q<(4 A% r6M J,,.4GH
a=z!}Q//'"ffa!A$h' I G$!A$h' I "X I '"!faff% I G$ffa!f%
 I "X I !fIrJ   c           	         i }t        | t              r3| j                  s&| j                  r| |d<   n| j                  r| j                  t              }| j                  D cg c]  }t        t        |g|       |f }}|r|D ch c]  }|d   	 c}S |D ]+  }|\  }}|j                  |      r||xx   |z  cc<   '|||<   - n| j                  r| j                  \  }}| ||<   nbd}| j                  D ]F  }t        |j                        }	|	dk(  r|j                  r|dz  }/|	dk(  s5||j                  d   z  }H | ||<   n| |d<   |rt        |j                               S |S c c}w c c}w )aX  Decomposes an input polynomial into homogeneous ones of
    smaller or equal degree.

    Explanation
    ===========

    Returns a dictionary with keys as the degree of the smaller
    constituting polynomials. Values are the constituting polynomials.

    Parameters
    ==========

    expr : Expr
        Polynomial(SymPy expression).
    separate : bool
        If True then simply return a list of the constituent monomials
        If not then break up the polynomial into constituent homogeneous
        polynomials.

    Examples
    ========

    >>> from sympy.abc import x, y
    >>> from sympy.integrals.intpoly import decompose
    >>> decompose(x**2 + x*y + x + y + x**3*y**2 + y**5)
    {1: x + y, 2: x**2 + x*y, 5: x**3*y**2 + y**5}
    >>> decompose(x**2 + x*y + x + y + x**3*y**2 + y**5, True)
    {x, x**2, y, y**5, x*y, x**3*y**2}
    r   r   r   )r   r	   rH   r   r   atomsr
   r   r   r   rr   r   r$   setvalues)
r3   r   	poly_dictsymbolsrA   degreesrl   ra   r=   r   s
             rD   r)   r)     sy   < I$dnn>>IaL[[jj(G$(II/  K8895A /G /.56Ua66$ 1E#(LFD }}V,!&)T1),0	&)1 [[		IAv $IfF		 +		N	>dnnaKF!^diil*F+ !%If	!9##%&&9/ 7s   #E)	E.c                 <  	 t        | t              r| j                  n| }t        |      }|dk  rt	        |      S |rt
        j                  nt
        j                  	t        |d         }|dk(  r3t        t        d |D              |z  t        d |D              |z        nFt        t        d |D              |z  t        d |D              |z  t        d |D              |z        	fd}	fd	}t        |t        |dk(  r|      
      S |      
      S )aF  Returns the same polygon with points sorted in clockwise or
    anti-clockwise order.

    Note that it's necessary for input points to be sorted in some order
    (clockwise or anti-clockwise) for the integration algorithm to work.
    As a convention algorithm has been implemented keeping clockwise
    orientation in mind.

    Parameters
    ==========

    poly:
        2D or 3D Polygon.
    normal : optional
        The normal of the plane which the 3-Polytope is a part of.
    clockwise : bool, optional
        Returns points sorted in clockwise order if True and
        anti-clockwise if False.

    Examples
    ========

    >>> from sympy.integrals.intpoly import point_sort
    >>> from sympy import Point
    >>> point_sort([Point(0, 0), Point(1, 0), Point(1, 1)])
    [Point2D(1, 1), Point2D(1, 0), Point2D(0, 0)]
    r   r   c              3   4   K   | ]  }|j                     y wrG   r   r   r   s     rD   r   zpoint_sort.<locals>.<genexpr>O       7FHH7   c              3   4   K   | ]  }|j                     y wrG   r   r   s     rD   r   zpoint_sort.<locals>.<genexpr>P       8&VXX8r   c              3   4   K   | ]  }|j                     y wrG   r   r   s     rD   r   zpoint_sort.<locals>.<genexpr>R  r   r   c              3   4   K   | ]  }|j                     y wrG   r   r   s     rD   r   zpoint_sort.<locals>.<genexpr>S  r   r   c              3   4   K   | ]  }|j                     y wrG   )r   r   s     rD   r   zpoint_sort.<locals>.<genexpr>T  r   r   c                    | j                   j                   z
  t        j                  k\  r-|j                   j                   z
  t        j                  k  r S | j                   j                   z
  dk  r|j                   j                   z
  dk\  rS | j                   j                   z
  dk(  r|j                   j                   z
  dk(  rt| j                  j                  z
  dk\  s|j                  j                  z
  dk\  r| j                  |j                  kD  r S S |j                  | j                  kD  r S S | j                   j                   z
  |j                  j                  z
  z  |j                   j                   z
  | j                  j                  z
  z  z
  }|dk  r S |dkD  rS | j                   j                   z
  | j                   j                   z
  z  | j                  j                  z
  | j                  j                  z
  z  z   }|j                   j                   z
  |j                   j                   z
  z  |j                  j                  z
  |j                  j                  z
  z  z   }||kD  r S S r   )r   r   r0   r   )rc   rd   detfirstsecondcenterorders        rD   comparezpoint_sort.<locals>.compareV  s   33>QVV#fhh(?6MSS688^aACC&((Na$7LSS688^q QSS688^q%8ssVXX~"accFHHn&9!"qssv55SS133YE61E1ssVXX~!##.1ssVXX~!##.1276M1WLvxxACC&((N3vxxACC&((N34##.QSS688^4##.QSS688^45v2U2rJ   c                 ~    t        | |      t        fdt        dd      D              }|dk  r S |dkD  rS y )Nc              3   4   K   | ]  }|   |   z    y wrG   r   )r   r7   r   r   s     rD   r   z0point_sort.<locals>.compare3d.<locals>.<genexpr>o  s     B#a&6!9,Br   r   r   )r   r   r%   )rc   rd   r   r   r   r   r   s      @rD   	compare3dzpoint_sort.<locals>.compare3dm  sF    FAq)BeAqkBB?6M1_L rJ   r   )r   r   r    r$   r-   r   rI   NegativeOner   r   r   r   )
r2   r   r   ptsndimr   r   r   r   s
    `      @@rD   r   r   +  s    8 &dG4$--$CCA1uCyAEEAMME
c!f+C
axs73781<8C89A=? s73781<8C89A=8C89A=?3. #:agGHHYGHHrJ   c                    t         j                  }t        | t        t        f      rt        d | D              |z  S t        | t              rat        | t              r"| j                  dz  | j                  dz  z   |z  S | j                  dz  | j                  dz  z   | j                  z   |z  S t        | t              r#t        d | j                         D              |z  S y)a/  Returns the Euclidean norm of a point from origin.

    Parameters
    ==========

    point:
        This denotes a point in the dimension_al spac_e.

    Examples
    ========

    >>> from sympy.integrals.intpoly import norm
    >>> from sympy import Point
    >>> norm(Point(2, 7))
    sqrt(53)
    c              3   &   K   | ]	  }|d z    ywr   Nr   )r   coords     rD   r   znorm.<locals>.<genexpr>  s     1%5A:1   r   c              3   &   K   | ]	  }|d z    ywr  r   )r   r7   s     rD   r   znorm.<locals>.<genexpr>  s     0A1a40r  N)r   Halfr   r-   r]   r   r   r   r   r   r   dictr   )r   halfs     rD   rM   rM   x  s    " 66D%$'1511T99	E5	!eW%GGqL577a</D88GGqL577a</%''9dBB	E4	 000D88 
!rJ   c                    |dd dk(  r|dk(  rI| j                   d   \  }}| j                   d   \  }}|j                   d   \  }}|j                   d   \  }	}
nQ|dk(  rL| j                   d   \  }}}| j                   d   \  }}}|j                   d   \  }}}|j                   d   \  }	}
}z
  
z
  z  z
  	z
  z  z
  }|rP||z  ||z  z
  }||
z  |	|z  z
  }t        |||	z
  z  |||z
  z  z
        |z  t        |||
z
  z  |||z
  z  z
        |z  fS |dd dk(  r\|d	k(  rV| d   \  }}|d   \  }}| d   |d   }}||z  ||z  z
  }|r.t        ||z  ||z  z
        |z  t        ||z  ||z  z
        |z  fS yyy)
al  Returns intersection between geometric objects.

    Explanation
    ===========

    Note that this function is meant for use in integration_reduction and
    at that point in the calling function the lines denoted by the segments
    surely intersect within segment boundaries. Coincident lines are taken
    to be non-intersecting. Also, the hyperplane intersection for 2D case is
    also implemented.

    Parameters
    ==========

    geom_1, geom_2:
        The input line segments.

    Examples
    ========

    >>> from sympy.integrals.intpoly import intersection
    >>> from sympy import Point, Segment2D
    >>> l1 = Segment2D(Point(1, 1), Point(3, 5))
    >>> l2 = Segment2D(Point(2, 0), Point(2, 5))
    >>> intersection(l1, l2, "segment2D")
    (2, 3)
    >>> p1 = ((-1, 0), 0)
    >>> p2 = ((0, 1), 1)
    >>> intersection(p1, p2, "plane2D")
    (0, 1)
    Nsegmentr   r   r   	segment3Dplaner   )rq   r   )geom_1geom_2intersection_typer   y1r   y2x3y3x4y4z1z2z3z4denomt1t2a1xa1ya2xa2yr   b2s                           rD   r&   r&     s   @ "*+]]1%FB]]1%FB]]1%FB]]1%FB+-q)JBBq)JBBq)JBBq)JBBbR"W%bR"W(==b27"Bb27"BbBGnrR"W~56>bBGnrR"W~56>@ @"(	)ayHCayHCAYq	B#Ic	)E"s(R#X-.6"s(R#X-.68 8  * )rJ   c                 d    t        | t              rt        |       dv ryyt        | t              ryy)au  If the input entity is a vertex return True.

    Parameter
    =========

    ent :
        Denotes a geometric entity representing a point.

    Examples
    ========

    >>> from sympy import Point
    >>> from sympy.integrals.intpoly import is_vertex
    >>> is_vertex((2, 3))
    True
    >>> is_vertex((2, 3, 6))
    True
    >>> is_vertex(Point(2, 3))
    True
    )r   r   TF)r   r]   r$   r   )ents    rD   r   r     s4    * #us8v  
C	rJ   c                    ddl m}m} | j                  D cg c]  }|j                   }}| j                  D cg c]  }|j
                   }}|j                  | j                  d   j                         |j                  | j                  d   j
                          |||      } ||d      }|j                          yc c}w c c}w )zPlots the 2D polytope using the functions written in plotting
    module which in turn uses matplotlib backend.

    Parameter
    =========

    poly:
        Denotes a 2-Polytope.
    r   )PlotList2DSerieszlabel_axes=True)axesN)sympy.plotting.plotr&  r'  r    r   r   r+   show)r2   r&  r'  r   xlyll2dsr   s           rD   plot_polytoper.    s     7!%	/v&((	/B	/!%	/v&((	/B	/IIdmmA  !IIdmmA  !BDT)*AFFH 
0	/s
   CCc                 j    ddl m}m} | j                  }t	        |      dk(  r	 ||        y ||        y)zPlots the polynomial using the functions written in
    plotting module which in turn uses matplotlib backend.

    Parameter
    =========

    expr:
        Denotes a polynomial(SymPy expression).
    r   )plot3dplotr   N)r)  r0  r1  free_symbolsr$   )r3   r0  r1  r   s       rD   plot_polynomialr3    s+     1D
4yA~tT
rJ   rG   )NN)r   r   )F)NT)1__doc__	functoolsr   	sympy.abcr   r   r   
sympy.corer   r   r	   r
   sympy.core.sympifyr   sympy.geometryr   r   r   r   sympy.polys.polytoolsr   r   r   r   sympy.simplify.simplifyr   rE   r1   rV   r(   r.   r\   ru   rv   rL   r   r[   r   rY   r"   r   r   r)   r   rM   r&   r   r.  r3  r   rJ   rD   <module>r<     s   " !   , , ' = = A A -r3Ut r3j$*TnB]J2j<*Z4*n5t JN+/],@/d+\8v+dNAHJIZ9:;8|:.rJ   