Operation to check if two polygons overlap is inefficient

Abierto
  • ¿Algo no está bien?
#372 0 comentarios 0 reacciones 1 asignado Ver en GitHub

Los mantenedores suelen responder en 1 día

@adybbroe ya está trabajando en esto.

Desde el 20/7/2021.

Evaluación

Este issue todavía no se ha evaluado.

Descripción

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
Lenguaje dominante
Python
Estrellas
388
Forks
104
Merge medio
2 d 16 h
PR fusionados (30 d)
3

Preparar el entorno

  • Sin Dockerfile ni archivo de Docker Compose
  • Tiene una plantilla de pull request
  • Sin guía de contribución

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de pytroll/pyresample

Todos los issues de pytroll/pyresample

Issues similares

Más issues de Python

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.