Operation to check if two polygons overlap is inefficient

オープン
  • 何か問題がありますか？
#372 コメント 0 件 リアクション 0 件 担当者 1 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

@adybbroe がすでに取り組んでいます。

2021年7月20日 から。

評価

この issue はまだ評価されていません。

説明

Code Sample, a minimal, complete, and verifiable piece of code

I did a profiling of the below code. The input was a list of trollsched.satpass.Pass satellite passes with only two passes overlapping each other over the areas of interest.

The _bool_opermethod of SphPolygon class was called three times, each taking almost 5 seconds. In tot al the code ran for 19 seconds.

# Your code here
def derive_combined_coverage(passes, area_def):
    """From a sequence of satellite overpasses derived the total coverage of an area."""

    npasses = len(passes)
    if npasses == 0:
        print("No passes in time window!")
        return 0

    area_boundary = AreaDefBoundary(area_def, frequency=100)
    area_boundary = area_boundary.contour_poly

    list_of_polygons = []
    for mypass in passes:
        list_of_polygons.append(mypass.boundary.contour_poly)

    non_overlaps = GetNonOverlapUnions(list_of_polygons)
    non_overlaps.merge()

    polygons = non_overlaps.get_polygons()
    pass_ids = non_overlaps.get_ids()

    coverage = 0
    for polygon in polygons:
        isect = polygon.intersection(area_boundary)
        if isect:
            coverage = coverage + isect.area()

    area_cov = coverage / area_boundary.area()
    print("Area coverage = {0}".format(area_cov))
Problem description

In the newly merged PR #347 new functionality is added in order to for instance support the problem of deriving the total coverage of several (possibly overlapping) satellite overpasses over an area of interest. However, when checking if two polygons overlap in the function check_if_two_polygons_overlap a union is performed, and when performing this union operation with the _bool_oper method of the SphPolygon class a lot of (in this case) unnecessary calculations finding the new polygon is carried out. This takes time when we only need to know if the two polygons intersects.

In addition to solving this it would be beneficial to refactor the SphPolygon class a bit, so that the methods are smaller and do preferably only one thing.

Expected Output
Actual Result, Traceback if applicable
Versions of Python, package at hand and relevant dependencies
主要言語
Python
スター
388
フォーク
104
平均マージ
2日 16時間
マージ済み PR（30日）
3

環境構築

  • Dockerfile・Docker Compose ファイルなし
  • プルリクエストのテンプレートあり
  • コントリビューションガイドなし

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

pytroll/pyresample のほかの issue

pytroll/pyresample の issue をすべて見る

似ている issue

Python の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。