vkit.element.polygon

  1# Copyright 2022 vkit-x Administrator. All Rights Reserved.
  2#
  3# This project (vkit-x/vkit) is dual-licensed under commercial and SSPL licenses.
  4#
  5# The commercial license gives you the full rights to create and distribute software
  6# on your own terms without any SSPL license obligations. For more information,
  7# please see the "LICENSE_COMMERCIAL.txt" file.
  8#
  9# This project is also available under Server Side Public License (SSPL).
 10# The SSPL licensing is ideal for use cases such as open source projects with
 11# SSPL distribution, student/academic purposes, hobby projects, internal research
 12# projects without external distribution, or other projects where all SSPL
 13# obligations can be met. For more information, please see the "LICENSE_SSPL.txt" file.
 14from typing import cast, Optional, Tuple, Union, Sequence, Iterable, List
 15import logging
 16import math
 17
 18import attrs
 19import numpy as np
 20import cv2 as cv
 21from shapely.geometry import (
 22    Polygon as ShapelyPolygon,
 23    MultiPolygon as ShapelyMultiPolygon,
 24    CAP_STYLE,
 25    JOIN_STYLE,
 26)
 27from shapely.ops import unary_union
 28import pyclipper
 29
 30from vkit.utility import attrs_lazy_field
 31from .type import Shapable, ElementSetOperationMode
 32
 33logger = logging.getLogger(__name__)
 34
 35_T = Union[float, str]
 36
 37
 38@attrs.define
 39class PolygonInternals:
 40    bounding_box: 'Box'
 41    np_self_relative_points: np.ndarray
 42
 43    _area: Optional[float] = attrs_lazy_field()
 44    _self_relative_polygon: Optional['Polygon'] = attrs_lazy_field()
 45    _np_mask: Optional[np.ndarray] = attrs_lazy_field()
 46    _mask: Optional['Mask'] = attrs_lazy_field()
 47
 48    def lazy_post_init_area(self):
 49        if self._area is not None:
 50            return self._area
 51
 52        self._area = float(ShapelyPolygon(self.np_self_relative_points).area)
 53        return self._area
 54
 55    @property
 56    def area(self):
 57        return self.lazy_post_init_area()
 58
 59    def lazy_post_init_self_relative_polygon(self):
 60        if self._self_relative_polygon is not None:
 61            return self._self_relative_polygon
 62
 63        self._self_relative_polygon = Polygon.from_np_array(self.np_self_relative_points)
 64        return self._self_relative_polygon
 65
 66    @property
 67    def self_relative_polygon(self):
 68        return self.lazy_post_init_self_relative_polygon()
 69
 70    def lazy_post_init_np_mask(self):
 71        if self._np_mask is not None:
 72            return self._np_mask
 73
 74        np_mask = np.zeros(self.bounding_box.shape, dtype=np.uint8)
 75        cv.fillPoly(np_mask, [self.self_relative_polygon.to_np_array()], 1)
 76        self._np_mask = np_mask.astype(np.bool8)
 77        return self._np_mask
 78
 79    @property
 80    def np_mask(self):
 81        return self.lazy_post_init_np_mask()
 82
 83    def lazy_post_init_mask(self):
 84        if self._mask is not None:
 85            return self._mask
 86
 87        self._mask = Mask(mat=self.np_mask.astype(np.uint8))
 88        self._mask = self._mask.to_box_attached(self.bounding_box)
 89        return self._mask
 90
 91    @property
 92    def mask(self):
 93        return self.lazy_post_init_mask()
 94
 95
 96@attrs.define(frozen=True, eq=False)
 97class Polygon:
 98    points: 'PointTuple'
 99
100    _internals: Optional[PolygonInternals] = attrs_lazy_field()
101
102    def __attrs_post_init__(self):
103        assert self.points
104
105    def lazy_post_init_internals(self):
106        if self._internals is not None:
107            return self._internals
108
109        np_self_relative_points = self.to_smooth_np_array()
110
111        y_min = np_self_relative_points[:, 1].min()
112        y_max = np_self_relative_points[:, 1].max()
113
114        x_min = np_self_relative_points[:, 0].min()
115        x_max = np_self_relative_points[:, 0].max()
116
117        np_self_relative_points[:, 0] -= x_min
118        np_self_relative_points[:, 1] -= y_min
119
120        bounding_box = Box(
121            up=round(y_min),
122            down=round(y_max),
123            left=round(x_min),
124            right=round(x_max),
125        )
126
127        object.__setattr__(
128            self,
129            '_internals',
130            PolygonInternals(
131                bounding_box=bounding_box,
132                np_self_relative_points=np_self_relative_points,
133            ),
134        )
135        return cast(PolygonInternals, self._internals)
136
137    ###############
138    # Constructor #
139    ###############
140    @classmethod
141    def create(cls, points: Union['PointList', 'PointTuple', Iterable['Point']]):
142        return cls(points=PointTuple(points))
143
144    ############
145    # Property #
146    ############
147    @property
148    def num_points(self):
149        return len(self.points)
150
151    @property
152    def internals(self):
153        return self.lazy_post_init_internals()
154
155    @property
156    def area(self):
157        return self.internals.area
158
159    @property
160    def bounding_box(self):
161        return self.internals.bounding_box
162
163    @property
164    def self_relative_polygon(self):
165        return self.internals.self_relative_polygon
166
167    @property
168    def mask(self):
169        return self.internals.mask
170
171    ##############
172    # Conversion #
173    ##############
174    @classmethod
175    def from_xy_pairs(cls, xy_pairs: Iterable[Tuple[_T, _T]]):
176        return cls(points=PointTuple.from_xy_pairs(xy_pairs))
177
178    def to_xy_pairs(self):
179        return self.points.to_xy_pairs()
180
181    def to_smooth_xy_pairs(self):
182        return self.points.to_smooth_xy_pairs()
183
184    @classmethod
185    def from_flatten_xy_pairs(cls, flatten_xy_pairs: Sequence[_T]):
186        return cls(points=PointTuple.from_flatten_xy_pairs(flatten_xy_pairs))
187
188    def to_flatten_xy_pairs(self):
189        return self.points.to_flatten_xy_pairs()
190
191    def to_smooth_flatten_xy_pairs(self):
192        return self.points.to_smooth_flatten_xy_pairs()
193
194    @classmethod
195    def from_np_array(cls, np_points: np.ndarray):
196        return cls(points=PointTuple.from_np_array(np_points))
197
198    def to_np_array(self):
199        return self.points.to_np_array()
200
201    def to_smooth_np_array(self):
202        return self.points.to_smooth_np_array()
203
204    @classmethod
205    def from_shapely_polygon(cls, shapely_polygon: ShapelyPolygon):
206        xy_pairs = cls.remove_duplicated_xy_pairs(shapely_polygon.exterior.coords)  # type: ignore
207        return cls.from_xy_pairs(xy_pairs)
208
209    def to_shapely_polygon(self):
210        return ShapelyPolygon(self.to_xy_pairs())
211
212    def to_smooth_shapely_polygon(self):
213        return ShapelyPolygon(self.to_smooth_xy_pairs())
214
215    ############
216    # Operator #
217    ############
218    def get_center_point(self):
219        shapely_polygon = self.to_smooth_shapely_polygon()
220        centroid = shapely_polygon.centroid
221        x, y = centroid.coords[0]
222        return Point.create(y=y, x=x)
223
224    def get_rectangular_height(self):
225        # See Box.to_polygon.
226        assert self.num_points == 4
227        (
228            point_up_left,
229            point_up_right,
230            point_down_right,
231            point_down_left,
232        ) = self.points
233        left_side_height = math.hypot(
234            point_up_left.smooth_y - point_down_left.smooth_y,
235            point_up_left.smooth_x - point_down_left.smooth_x,
236        )
237        right_side_height = math.hypot(
238            point_up_right.smooth_y - point_down_right.smooth_y,
239            point_up_right.smooth_x - point_down_right.smooth_x,
240        )
241        return (left_side_height + right_side_height) / 2
242
243    def get_rectangular_width(self):
244        # See Box.to_polygon.
245        assert self.num_points == 4
246        (
247            point_up_left,
248            point_up_right,
249            point_down_right,
250            point_down_left,
251        ) = self.points
252        up_side_width = math.hypot(
253            point_up_left.smooth_y - point_up_right.smooth_y,
254            point_up_left.smooth_x - point_up_right.smooth_x,
255        )
256        down_side_width = math.hypot(
257            point_down_left.smooth_y - point_down_right.smooth_y,
258            point_down_left.smooth_x - point_down_right.smooth_x,
259        )
260        return (up_side_width + down_side_width) / 2
261
262    def to_clipped_points(self, shapable_or_shape: Union[Shapable, Tuple[int, int]]):
263        return self.points.to_clipped_points(shapable_or_shape)
264
265    def to_clipped_polygon(self, shapable_or_shape: Union[Shapable, Tuple[int, int]]):
266        return Polygon(points=self.to_clipped_points(shapable_or_shape))
267
268    def to_shifted_points(self, offset_y: int = 0, offset_x: int = 0):
269        return self.points.to_shifted_points(offset_y=offset_y, offset_x=offset_x)
270
271    def to_relative_points(self, origin_y: int, origin_x: int):
272        return self.points.to_relative_points(origin_y=origin_y, origin_x=origin_x)
273
274    def to_shifted_polygon(self, offset_y: int = 0, offset_x: int = 0):
275        return Polygon(points=self.to_shifted_points(offset_y=offset_y, offset_x=offset_x))
276
277    def to_relative_polygon(self, origin_y: int, origin_x: int):
278        return Polygon(points=self.to_relative_points(origin_y=origin_y, origin_x=origin_x))
279
280    def to_conducted_resized_polygon(
281        self,
282        shapable_or_shape: Union[Shapable, Tuple[int, int]],
283        resized_height: Optional[int] = None,
284        resized_width: Optional[int] = None,
285    ):
286        return Polygon(
287            points=self.points.to_conducted_resized_points(
288                shapable_or_shape=shapable_or_shape,
289                resized_height=resized_height,
290                resized_width=resized_width,
291            ),
292        )
293
294    def to_resized_polygon(
295        self,
296        resized_height: Optional[int] = None,
297        resized_width: Optional[int] = None,
298    ):
299        return self.to_conducted_resized_polygon(
300            shapable_or_shape=self.bounding_box.shape,
301            resized_height=resized_height,
302            resized_width=resized_width,
303        )
304
305    def to_bounding_rectangular_polygon(self, shape: Tuple[int, int]):
306        shapely_polygon = self.to_smooth_shapely_polygon()
307
308        assert isinstance(shapely_polygon.minimum_rotated_rectangle, ShapelyPolygon)
309        polygon = self.from_shapely_polygon(shapely_polygon.minimum_rotated_rectangle)
310        assert polygon.num_points == 4
311
312        # NOTE: Could be out-of-bound.
313        polygon = polygon.to_clipped_polygon(shape)
314
315        return polygon
316
317    def to_bounding_box(self):
318        return self.bounding_box
319
320    def fill_np_array(
321        self,
322        mat: np.ndarray,
323        value: Union[np.ndarray, Tuple[float, ...], float],
324        alpha: Union['ScoreMap', np.ndarray, float] = 1.0,
325        keep_max_value: bool = False,
326        keep_min_value: bool = False,
327    ):
328        self.mask.fill_np_array(
329            mat=mat,
330            value=value,
331            alpha=alpha,
332            keep_max_value=keep_max_value,
333            keep_min_value=keep_min_value,
334        )
335
336    def extract_mask(self, mask: 'Mask'):
337        return self.mask.extract_mask(mask)
338
339    def fill_mask(
340        self,
341        mask: 'Mask',
342        value: Union['Mask', np.ndarray, int] = 1,
343        keep_max_value: bool = False,
344        keep_min_value: bool = False,
345    ):
346        self.mask.fill_mask(
347            mask=mask,
348            value=value,
349            keep_max_value=keep_max_value,
350            keep_min_value=keep_min_value,
351        )
352
353    def extract_score_map(self, score_map: 'ScoreMap'):
354        return self.mask.extract_score_map(score_map)
355
356    def fill_score_map(
357        self,
358        score_map: 'ScoreMap',
359        value: Union['ScoreMap', np.ndarray, float],
360        keep_max_value: bool = False,
361        keep_min_value: bool = False,
362    ):
363        self.mask.fill_score_map(
364            score_map=score_map,
365            value=value,
366            keep_max_value=keep_max_value,
367            keep_min_value=keep_min_value,
368        )
369
370    def extract_image(self, image: 'Image'):
371        return self.mask.extract_image(image)
372
373    def fill_image(
374        self,
375        image: 'Image',
376        value: Union['Image', np.ndarray, Tuple[int, ...], int],
377        alpha: Union['ScoreMap', np.ndarray, float] = 1.0,
378    ):
379        self.mask.fill_image(
380            image=image,
381            value=value,
382            alpha=alpha,
383        )
384
385    @classmethod
386    def remove_duplicated_xy_pairs(cls, xy_pairs: Sequence[Tuple[int, int]]):
387        xy_pairs = tuple(map(tuple, xy_pairs))
388        unique_xy_pairs = []
389
390        idx = 0
391        while idx < len(xy_pairs):
392            unique_xy_pairs.append(xy_pairs[idx])
393
394            next_idx = idx + 1
395            while next_idx < len(xy_pairs) and xy_pairs[idx] == xy_pairs[next_idx]:
396                next_idx += 1
397            idx = next_idx
398
399        # Check head & tail.
400        if len(unique_xy_pairs) > 1 and unique_xy_pairs[0] == unique_xy_pairs[-1]:
401            unique_xy_pairs.pop()
402
403        assert len(unique_xy_pairs) >= 3
404        return unique_xy_pairs
405
406    def to_vatti_clipped_polygon(self, ratio: float, shrink: bool):
407        assert 0.0 <= ratio <= 1.0
408        if ratio == 1.0:
409            return self, 0.0
410
411        xy_pairs = self.to_smooth_xy_pairs()
412
413        shapely_polygon = ShapelyPolygon(xy_pairs)
414        if shapely_polygon.area == 0:
415            logger.warning('shapely_polygon.area == 0, this breaks vatti_clip.')
416
417        distance: float = shapely_polygon.area * (1 - np.power(ratio, 2)) / shapely_polygon.length
418        if shrink:
419            distance *= -1
420
421        clipper = pyclipper.PyclipperOffset()  # type: ignore
422        clipper.AddPath(xy_pairs, pyclipper.JT_ROUND, pyclipper.ET_CLOSEDPOLYGON)  # type: ignore
423
424        clipped_paths = clipper.Execute(distance)
425        assert clipped_paths
426        clipped_path: Sequence[Tuple[int, int]] = clipped_paths[0]
427
428        clipped_xy_pairs = self.remove_duplicated_xy_pairs(clipped_path)
429        clipped_polygon = self.from_xy_pairs(clipped_xy_pairs)
430
431        return clipped_polygon, distance
432
433    def to_shrank_polygon(
434        self,
435        ratio: float,
436        no_exception: bool = True,
437    ):
438        try:
439            shrank_polygon, _ = self.to_vatti_clipped_polygon(ratio, shrink=True)
440
441            shrank_bounding_box = shrank_polygon.bounding_box
442            vert_contains = (
443                self.bounding_box.up <= shrank_bounding_box.up
444                and shrank_bounding_box.down <= self.bounding_box.down
445            )
446            hori_contains = (
447                self.bounding_box.left <= shrank_bounding_box.left
448                and shrank_bounding_box.right <= self.bounding_box.right
449            )
450            if not (shrank_bounding_box.valid and vert_contains and hori_contains):
451                logger.warning('Invalid shrank_polygon bounding box. Fallback to NOP.')
452                return self
453
454            if 0 < shrank_polygon.area <= self.area:
455                return shrank_polygon
456            else:
457                logger.warning('Invalid shrank_polygon.area. Fallback to NOP.')
458                return self
459
460        except Exception:
461            if no_exception:
462                logger.exception('Failed to shrink. Fallback to NOP.')
463                return self
464            else:
465                raise
466
467    def to_dilated_polygon(
468        self,
469        ratio: float,
470        no_exception: bool = True,
471    ):
472        try:
473            dilated_polygon, _ = self.to_vatti_clipped_polygon(ratio, shrink=False)
474
475            dilated_bounding_box = dilated_polygon.bounding_box
476            vert_contains = (
477                dilated_bounding_box.up <= self.bounding_box.up
478                and self.bounding_box.down <= dilated_bounding_box.down
479            )
480            hori_contains = (
481                dilated_bounding_box.left <= self.bounding_box.left
482                and self.bounding_box.right <= dilated_bounding_box.right
483            )
484            if not (dilated_bounding_box.valid and vert_contains and hori_contains):
485                logger.warning('Invalid dilated_polygon bounding box. Fallback to NOP.')
486                return self
487
488            if dilated_polygon.area >= self.area:
489                return dilated_polygon
490            else:
491                logger.warning('Invalid dilated_polygon.area. Fallback to NOP.')
492                return self
493
494        except Exception:
495            if no_exception:
496                logger.exception('Failed to dilate. Fallback to NOP.')
497                return self
498            else:
499                raise
500
501
502# Experimental operations.
503# TODO: Might add to Polygon class.
504def get_line_lengths(shapely_polygon: ShapelyPolygon):
505    assert shapely_polygon.exterior is not None
506    points = tuple(shapely_polygon.exterior.coords)
507    for idx, p0 in enumerate(points):
508        p1 = points[(idx + 1) % len(points)]
509        length = math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)
510        yield length
511
512
513def estimate_shapely_polygon_height(shapely_polygon: ShapelyPolygon):
514    length = max(get_line_lengths(shapely_polygon))
515    return float(shapely_polygon.area) / length
516
517
518def calculate_patch_buffer_eps(shapely_polygon: ShapelyPolygon):
519    return estimate_shapely_polygon_height(shapely_polygon) / 10
520
521
522def patch_unionized_unionized_shapely_polygon(unionized_shapely_polygon: ShapelyPolygon):
523    eps = calculate_patch_buffer_eps(unionized_shapely_polygon)
524    unionized_shapely_polygon = unionized_shapely_polygon.buffer(
525        eps,
526        cap_style=CAP_STYLE.round,
527        join_style=JOIN_STYLE.round,
528    )  # type: ignore
529    unionized_shapely_polygon = unionized_shapely_polygon.buffer(
530        -eps,
531        cap_style=CAP_STYLE.round,
532        join_style=JOIN_STYLE.round,
533    )  # type: ignore
534    return unionized_shapely_polygon
535
536
537def unionize_polygons(polygons: Iterable[Polygon]):
538    shapely_polygons = [polygon.to_smooth_shapely_polygon() for polygon in polygons]
539
540    unionized_shapely_polygons = []
541
542    # Patch unary_union.
543    unary_union_output = unary_union(shapely_polygons)
544    if not isinstance(unary_union_output, ShapelyMultiPolygon):
545        assert isinstance(unary_union_output, ShapelyPolygon)
546        unary_union_output = [unary_union_output]
547
548    for unionized_shapely_polygon in unary_union_output:
549        unionized_shapely_polygon = patch_unionized_unionized_shapely_polygon(
550            unionized_shapely_polygon
551        )
552        unionized_shapely_polygons.append(unionized_shapely_polygon)
553
554    unionized_polygons = [
555        Polygon.from_xy_pairs(unionized_shapely_polygon.exterior.coords)
556        for unionized_shapely_polygon in unionized_shapely_polygons
557    ]
558
559    scatter_indices: List[int] = []
560    for shapely_polygon in shapely_polygons:
561        best_unionized_polygon_idx = None
562        best_area = 0.0
563        conflict = False
564
565        for unionized_polygon_idx, unionized_shapely_polygon in enumerate(
566            unionized_shapely_polygons
567        ):
568            if not unionized_shapely_polygon.intersects(shapely_polygon):
569                continue
570            area = unionized_shapely_polygon.intersection(shapely_polygon).area
571            if area > best_area:
572                best_area = area
573                best_unionized_polygon_idx = unionized_polygon_idx
574                conflict = False
575            elif area == best_area:
576                conflict = True
577
578        assert not conflict
579        assert best_unionized_polygon_idx is not None
580        scatter_indices.append(best_unionized_polygon_idx)
581
582    return unionized_polygons, scatter_indices
583
584
585def generate_fill_by_polygons_mask(
586    shape: Tuple[int, int],
587    polygons: Iterable[Polygon],
588    mode: ElementSetOperationMode,
589):
590    if mode == ElementSetOperationMode.UNION:
591        return None
592    else:
593        return Mask.from_polygons(shape, polygons, mode)
594
595
596# Cyclic dependency, by design.
597from .point import Point, PointList, PointTuple  # noqa: E402
598from .box import Box  # noqa: E402
599from .mask import Mask  # noqa: E402
600from .score_map import ScoreMap  # noqa: E402
601from .image import Image  # noqa: E402