a J5dH@sDddlmZmZddlmZddlmZGdddZd dd Zd S) )heappopheappush)TopologicalError)Pointc@sPeZdZdZddZddZddZdd Zd d Zd d Z ddZ ddZ dS)CellaNA `Cell`'s centroid property is a potential solution to finding the pole of inaccessibility for a given polygon. Rich comparison operators are used for sorting `Cell` objects in a priority queue based on the potential maximum distance of any theoretical point within a cell to a given polygon's exterior boundary. cCs>||_||_||_t|||_|||_|j|d|_dS)Ng;f?)xyhrcentroid_distdistance max_distance)selfrr r polygonrX/var/www/html/django/DPS/env/lib/python3.9/site-packages/shapely/algorithms/polylabel.py__init__s   z Cell.__init__cCs |j|jkSNrrotherrrr__lt__sz Cell.__lt__cCs |j|jkSrrrrrr__le__sz Cell.__le__cCs |j|jkSrrrrrr__eq__"sz Cell.__eq__cCs |j|jkSrrrrrr__ne__%sz Cell.__ne__cCs |j|jkSrrrrrr__gt__(sz Cell.__gt__cCs |j|jkSrrrrrr__ge__+sz Cell.__ge__cCsF||j}|j|j}|jD]}t||j|}q |r@|S| S)zSigned distance from Cell centroid to polygon outline. The returned value is negative if the point is outside of the polygon exterior boundary. )containsr r ZexteriorZ interiorsmin)rrZinsider Zinteriorrrrr .s  z Cell._distN) __name__ __module__ __qualname____doc__rrrrrrrr rrrrrs r?cCs|jstd|j\}}}}||}||}t||}|d} g} |jjd\} } t| | d|} t||d||dd|}|j| jkr|} |} | |kr|} | |krt| t| | | | | || |7} q| |7} q| rt | }|j| jkr|} |j | j|krq|j d} t| t|j | |j | | |t| t|j | |j | | |t| t|j | |j | | |t| t|j | |j | | |q| jS)aFinds pole of inaccessibility for a given polygon. Based on Vladimir Agafonkin's https://github.com/mapbox/polylabel Parameters ---------- polygon : shapely.geometry.Polygon tolerance : int or float, optional `tolerance` represents the highest resolution in units of the input geometry that will be considered for a solution. (default value is 1.0). Returns ------- shapely.geometry.Point A point representing the pole of inaccessibility for the given input polygon. Raises ------ shapely.errors.TopologicalError If the input polygon is not a valid geometry. Example ------- >>> from shapely import LineString >>> polygon = LineString([(0, 0), (50, 200), (100, 100), (20, 50), ... (-100, -20), (-150, -200)]).buffer(100) >>> polylabel(polygon, tolerance=10).wkt 'POINT (59.35615556364569 121.83919629746435)' zInvalid polygong@rr)Zis_validrZboundsrr Zcoordsrr rrrr rr )rZ toleranceZminxZminyZmaxxZmaxywidthheight cell_sizer Z cell_queuerr Z best_cellZ bbox_cellcellrrr polylabel<s@         "r)N)r$) heapqrrerrorsrZgeometryrrr)rrrrs  5