Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Facade visibility #4

Open
vvoovv opened this issue Mar 6, 2021 · 131 comments
Open

Facade visibility #4

vvoovv opened this issue Mar 6, 2021 · 131 comments

Comments

@vvoovv
Copy link
Member

vvoovv commented Mar 6, 2021

This issue is to discuss integration of the code that calculates facade visibility.

The code should be integrated into the dev branch.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 6, 2021

The majority of the code should go into the module action.facade_visibility.

The class FacadeVisibility is the base one, while the classes FacadeVisibilityBlender and FacadeVisibilityOther contain the code specific for Blender and the other environments (i.e. the command line).

The variable building in the cycle for building in buildings is an instance of the class building.Building.

The variable way in the cycle for way in self.app.managersById["ways"].getAllWays() is an instance of the class way.RealWay.

The Python list vertIndexToBldg is used for mapping between an index of the vertex and the index of the building in the Python list manager.buildings.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 6, 2021

The result with the measure of the visibility for each facade should be written into the Python list building.visibility. It's initialized with zeros. The total number of the elements in building.visibility is equal to the total number of the vertices of the building's polygon including the ones with the straight angle.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 6, 2021

Vertices of the building's footprint can be accessed via building.polygon where polygon is an instance of util.polygon.Polygon.

The order of vertices in building.polygon is forced to be counter clockwise. Also the vertices forming a straight angle are removed from the consideration. Vertices after the removal of the straight angles can be accessed via for vert in polygon.verts. Indices of those vertices can be access via for index in polygon.indices, where index points to the original Python list of the polygon vertices before the removal of the straight angles.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 6, 2021

Question.

The method getAllWays provides all OSM ways including footways and paths. Shall we use only roads?

@vvoovv
Copy link
Member Author

vvoovv commented Mar 6, 2021

I suggest moving the code that transforms the coordinates along an OSM way to the util package since the code can be reused elsewhere. In particular it can be used to cluster the OSM ways.

@polarkernel
Copy link
Collaborator

The class FacadeVisibility is the base one, while the classes FacadeVisibilityBlender and FacadeVisibilityOther contain the code specific for Blender and the other environments (i.e. the command line).

OK. In the method createKdTree() of the class FacadeVisibilityOther, the variable bldgVerts should be an attribute of the class (self.bldgVerts ). It is required later in calculateFacadeVisibility() of the base class. It will also be required when using the derived class FacadeVisibilityBlender.

The variable way in the cycle for way in self.app.managersById["ways"].getAllWays() ....

I assume that way is a complete way, consisting of way-segments. How can the individual segments be accessed? Am I right if I assume that ways are not circularly closed?

@polarkernel
Copy link
Collaborator

The result with the measure of the visibility for each facade should be written into the Python list building.visibility. It's initialized with zeros. The total number of the elements in building.visibility is equal to the total number of the vertices of the building's polygon including the ones with the straight angle.

In my code, following your proposition, visibility is the ratio of the facade width not hidden by other buildings. A value of 1.0 means, that the facade is completely visible (at least seen from one of the way-segments). Should it be converted to a boolean for building.visibility, for instance as visibility>0.5?

This final part in my code is not yet solved. Currently, I get these visibility values as a list of the same length and order as bldgVerts. Using vertIndexToBldg, I can find the associated buildings. But these vertices with the straight angle irritate me. How can I find the correct index, when these are not included in bldgVerts?

Am I right that the value in building.visibility belongs to the first vertice of the facade's edge?

@polarkernel
Copy link
Collaborator

Question.
The method getAllWays provides all OSM ways including footways and paths. Shall we use only roads?

Difficult to answer. Maybe it should be decided based on experiments. It would be associated with great effort, but shouldn't we try to create some kind of ground truth for different town districts, maybe based on StreetView data, where available? Another way could be to add some kind of importance value to the visibility, based on the type of ways.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 9, 2021

In the method createKdTree() of the class FacadeVisibilityOther, the variable bldgVerts should be an attribute of the class (self.bldgVerts ). It is required later in calculateFacadeVisibility() of the base class. It will also be required when using the derived class FacadeVisibilityBlender.

Added self.bldgVerts for FacadeVisibilityOther and FacadeVisibilityBlender and the related code to fill self.bldgVerts in.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 9, 2021

I assume that way is a complete way, consisting of way-segments. How can the individual segments be accessed? Am I right if I assume that ways are not circularly closed?

The variable way is an instance of the class way.RealWay. It's a very new class I introduced for the calculation of facade visibility and way clustering. It's nearly empty right now. It has the only variable element, which is an instance of the class parse.osm.way.Way.

To get projected data for a way in the body of the method calculateFacadeVisibility:

for coord in way.element.getData(manager.data):
    pass

An OSM way may be closed. For example, a mapper can draw 4 streets around a rectangular quater with a single OSM way. Use way.element.isClosed() to check it.

I suggest that the class way.RealWay should be structured in the similar way as the class building.Building. For example the latter class has the variable polygon (an instance of the class util.polygon.Polygon.) which performs some processing (ensures counter clockwise orientation, removes straight angles).

Similarly, an instance of the class way.RealWay should have a variable polyline. The class util.polyline.Polyline to be created is supposed to at least remove the straight angles.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 9, 2021

In my code, following your proposition, visibility is the ratio of the facade width not hidden by other buildings. A value of 1.0 means, that the facade is completely visible (at least seen from one of the way-segments). Should it be converted to a boolean for building.visibility, for instance as visibility>0.5?

I'd prefer to keep the continuous value.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 9, 2021

This final part in my code is not yet solved.

Can you post your code? I'll try it integrate it.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 9, 2021

Maybe it should be decided based on experiments.

Ok, let's do the experiments first.

@polarkernel
Copy link
Collaborator

Can you post your code? I'll try it integrate it.

That would be a good solution, if you have the time. Shall I create a folder experimental_code and commit the code there (3 files)? It is heavily commented, I think you should be able to understand it. My vision is still to bad for real progress.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 9, 2021

I suggest to paste your code in this issue. One message for each file.

@polarkernel
Copy link
Collaborator

I suggest to paste your code in this issue. One message for each file.

OK. I'll put the files in the following order:

testFrontFacadeDetection.py: Run this file to test the code. I used a pickle file to cache the OSM data. Set useCache to False to get new data from overpass. The tuple searchRange = (10,100) determines the rectangular search range, 10m on both sides of the way-segment and 100m above and below in the actual setting

frontFaceDetection.py: This file contains the functions used for visibility detection. A small part of this code is already included in your classes.

dataFromOverpass.py: Contains the code to get the OSM-data for buildings and streets from overpass.

@polarkernel
Copy link
Collaborator

File testFrontFacadeDetection.py:

import numpy as np
from dataFromOverpass import *
from frontFaceDetection import *
import pickle

# bbox = (13.53213,52.48910,13.53552,52.49078)    # Berlin
# bbox = (13.54972,52.49592,13.55541,52.49824) # Berlin 2
# bbox = (9.43037,54.79421,9.43285,54.79555)  # Flensburg
# bbox = (9.04557,54.47506,9.04760,54.47570)  # Husum
# bbox = (9.05641,54.49095,9.05855,54.49194) # Husum Ecke
# bbox = (9.04687,54.47600,9.05528,54.47860) # Husum gross
# bbox = (9.04522,54.47646,9.04748,54.47801) # Husum lang
# bbox = (9.05232,54.48472,9.05418,54.48582) # Husum Kreisel
# bbox = (9.04626,54.49083,9.04937,54.49167) # Husum Schleife
bbox = (13.42697,52.51586,13.44132,52.52046) # Karl-Marx-Alle
useCache = False

if useCache:
    with open('objs_new.pkl','rb') as f:  
        buildingsOSM, streetsOSM = pickle.load(f)
else:
    buildingsOSM = getBuildings(*bbox)
    streetsOSM = getStreets(*bbox)
    with open('objs_new.pkl', 'wb') as f:
        pickle.dump([buildingsOSM, streetsOSM], f)

def iterCircularThisNext(lst):
    these,nexts = tee(lst)
    nexts = islice(cycle(nexts), 1, None)
    return zip(these,nexts)

def iterThisNext(lst):
    these, nexts = tee(lst)
    next(nexts, None)
    return zip(these,nexts)

# convert buildings to numpy data structure required for front facade detection
N = 0  # number of vertices in buildings
for _,b in buildingsOSM.items():
    N += len(b)
vertsB = np.zeros((N,2))
nextIndx = 0
buildings = {}
for key,b in buildingsOSM.items():
    # make polygon order counter-clockwise for buildings, using signed area
    area = 0.
    for p0,p1 in iterCircularThisNext(b):
        area += (p0[0]+p1[0]) * (p0[1]-p1[1])
    if area < 0.:
        b.reverse()
    n = len(b)
    vertsB[nextIndx:nextIndx+n,:] = np.array(b)
    buildings[key] = [nextIndx, nextIndx+n]
    nextIndx += n

# convert streets to numpy data structure required for front facade detection
N = 0  # number of vertices in streets
for _,b in streetsOSM.items():
    N += len(b)
vertsS = np.zeros((N,2))
nextIndx = 0
streets = {}
for key,b in streetsOSM.items():
    n = len(b)
    vertsS[nextIndx:nextIndx+n,:] = np.array(b)
    streets[key] = [nextIndx, nextIndx+n]
    nextIndx += n

# now detect front facades
searchRange = (10,100)
visibility = detectFrontFacades(streets, vertsS, buildings, vertsB, searchRange)

# visualize the result
def _iterPrevNext(lst):
    prevs, nexts = tee(lst)
    next(nexts, None)
    return zip(prevs,nexts)


import matplotlib.pyplot as plt
fig = plt.figure(figsize=[6,6])
ax = plt.Axes(fig, [0., 0., 1., 1.], )
ax.set_axis_off()
fig.add_axes(ax)
for _,street in streets.items():
    for i0,i1 in _iterPrevNext(range(*street)):
        plt.plot([vertsS[i0,0],vertsS[i1,0]],[vertsS[i0,1],vertsS[i1,1]],color='brown')
        plt.plot(vertsS[i0,0],vertsS[i0,1],'k.')
for _,building in buildings.items():
    for i0,i1 in iterCircularThisNext(range(*building)):
        if visibility[i0] > 0.5:
            plt.plot([vertsB[i0,0],vertsB[i1,0]],[vertsB[i0,1],vertsB[i1,1]],'g',linewidth=3)
        else:
            plt.plot([vertsB[i0,0],vertsB[i1,0]],[vertsB[i0,1],vertsB[i1,1]],'k',linewidth=1)
plt.gca().axis('equal')
plt.show()

@polarkernel
Copy link
Collaborator

File frontFaceDetection.py:

import numpy as np
from bisect import bisect_left
from itertools import *
from scipy.spatial import KDTree

def iterCircularThisNext(lst):
    these,nexts = tee(lst)
    nexts = islice(cycle(nexts), 1, None)
    return zip(these,nexts)

def iterThisNext(lst):
    these, nexts = tee(lst)
    next(nexts, None)
    return zip(these,nexts)

class prioEventQueue():
    def __init__(self):
        self.keys = []
        self.queue = []

    def push(self, key, item):
        i = bisect_left(self.keys, key) # Determine where to insert item.
        self.keys.insert(i, key)        # Insert key of item to keys list.
        self.queue.insert(i, item)      # Insert the item itself in the corresponding place.

    def pop(self):
        self.keys.pop(0)
        return self.queue.pop(0)

    def remove(self,indx):
        for i, item in enumerate(self.queue):
            if item['indx'] == indx:
                self.keys.pop(i)
                self.queue.pop(i)
                break

    def empty(self):
        return not self.queue

def processEvents(eventList,edgeList):
    prioQueue = prioEventQueue()
    activeEvent = None
    activeIn = None
    for event in eventList:
        if activeEvent is None:
            activeEvent = event
            activeIn = event['x']
        elif event['type'] == 'in':                         # start of a new edge
            if event['y'] <= activeEvent['y']:              # the new edges hides the active edge
                edgeList[activeEvent['indx']]['visibleX'] += event['x'] - activeIn
                prioQueue.push(activeEvent['y'], activeEvent)
                activeEvent = event
                activeIn = event['x']                       # the new edges is behind the active edge
            else: 
                prioQueue.push(event['y'], event)
        elif event['type'] == 'out':                        # edge ends
            if event['indx'] == activeEvent['indx']:        # the active edge ends
                edgeList[activeEvent['indx']]['visibleX'] += event['x'] - activeIn
                if not prioQueue.empty():                   # there is an hidden edge that already started                   
                    activeEvent = prioQueue.pop()
                    activeIn = event['x']
                else:
                    activeEvent = None
                    activeIn = None
                continue
            else:                                           # there must be an edge in the queue, that ended before
                prioQueue.remove(event['indx'])

    return edgeList

def detectVisibility(buildings, verts, search_Params):
    """
    Detects the visibility parameters of the buildings.

    Input: 
    ======
    buildings:      Dictionary with key: OSM id of building, content is [i0,i1]: i0: first index, and i1: last index + 1
                    of vertices in building with id. The vertices of the building are expected in  counter-clockwise order.
    verts:          numpy array[N,2] of vertices, transformed to the way-segment
    search_Params:  Parameters used for search of edges
                    search_Params = {
                        'searchRadius': Radius of search circle
                        'searchWidth' : Width of search rectangle
                        'searchHeight': Height of search rectangle
                    }
    Output:
    ======
    return:         List with all edges of the buildings, each a dictionary with
                        edge =  {
                                'i0'        : start index of edge in verts
                                'i1'        : end index +1 of edge in verts 
                                'dXY'       : np.array[dx,dy] slopes of edge
                                'visRatio'  : ratio of visibility of edge
                        }
                    A possible way do define a front facade could be for instance:
                    isFront = edge['ratio'] > 0.5 and abs(edge['dXY'][0,0]) > abs(edge['dXY'][0,1])
    """
    # preprocess egdes of buildings
    edgeRecList = []    # holds all edges and their parameters
    posEventList = []   # holds events above way-segment
    negEventList = []   # holds events below way-segment
    indx = 0
    for key, building in buildings.items():
        buildIndxs = [i for i in range(*building)]

        # check for way-segments that cross the building (or dead-ends at a building)
        Ys = verts[buildIndxs,1]
        crossesBuilding =  not (np.all(Ys > 0) if Ys[0] > 0 else np.all(Ys < 0))  # if signs of y-values are positive and negative

        for i0,i1 in iterCircularThisNext(range(*building)):   # indices i0,i1 of edge
            edge = verts[[i0,i1],:]                             # vertices of transformed edge  (counter-clockwise order)

            dXY = np.diff(edge,1,0)                             # dx,dy between endpoints of edge
            edgeRec = {'i0':i0, 'i1':i1, 'dXY':dXY, 'visibleX':0., 'crossBuild':crossesBuilding}
            edgeRecList.append(edgeRec) 

            # because the algorithm scans with increasing x, the first vertice has to get smaller x
            if np.argmin(edge[:,0]):
                edge[[1,0],:] = edge[[0,1],:]   # swap endpoints of edge

            # the visibility depends on the maximum distance to the way-segment
            max_y = np.max(np.abs(edge[:,1]))

            # prepare events: 
            # posEventList holds events above way-segment: use only edges that run from left to right
            # negEventList holds events below way-segment: use only edges that run from right to left
            if np.min(edge[:,1]) > 0.:
                    posEventList.append( {'indx':indx, 'type':'in', 'x':edge[0,0], 'y':max_y})
                    posEventList.append( {'indx':indx, 'type':'out', 'x':edge[1,0], 'y':max_y})
            else:
                    negEventList.append( {'indx':indx, 'type':'in', 'x':edge[0,0], 'y':max_y})
                    negEventList.append( {'indx':indx, 'type':'out', 'x':edge[1,0], 'y':max_y})
            indx += 1

    # sort event lists by increasing x and then by increasing y
    posEventList.sort(key=lambda item:(item['x'],item['y']))
    negEventList.sort(key=lambda item:(item['x'],item['y']))

    edgeRecList = processEvents(posEventList, edgeRecList)
    edgeRecList = processEvents(negEventList, edgeRecList)

    for edgeRec in edgeRecList:
        edge = verts[[edgeRec['i0'],edgeRec['i1']],:]
        # at least one vertice of the edge must be in rectangular search range
        if not np.any(np.all( np.array( (np.abs(edge[:,0])<search_Params['searchWidth'], np.abs(edge[:,1])<search_Params['searchHeight']) ), axis=0 ) ):
            edgeRec['visRatio'] = 0.
        # and the building shall not be crossed by the way-segment
        elif edgeRec['crossBuild']:
            edgeRec['visRatio'] = 0.
        else:
            vis = edgeRec['visibleX']
            edgeRec.pop('visibleX', None)
            edgeRec['visRatio'] = vis/abs(edgeRec['dXY'][0,0]) if not edgeRec['crossBuild'] else 0.

    return edgeRecList

def transfToWayCoords(way,vertices):
    """
    Transforms the vertices to a coordinate system given by the way-segment way.
    The mid-point of the way-segment becomes the origin of the new system. The x-axis points to the second
    point of the way-segment. The y-axis is positive on the left of the way-segment (right-handed system)

    Input: 
    ======
    way:            start and end-point of the way-segment
    vertices:       numpy array[N,2] of vertices to be transformed

    Output:
    ======
    return:         numpy array[N,2] of transformed vertices

    """
    p0, p1  = (way[0,:], way[1,:])
    sV = p1-p0                                          # vector of way-segment
    sL = np.linalg.norm(sV)                             # length of way-segment

    # compute transform matrix T
    Vu = sV/sL                                          # unit vector of way-segment
    Vp = np.array( (Vu[1],-Vu[0]) )                     # perpendicular vector to Vu
    T = np.array([np.transpose(Vu),np.transpose(Vp)])   # transform matrix

    c0 = (p0+p1)/2                                      # center of new coordinate system

    vertices[:,:2] -= c0                                # shift origin to c0 (center of way-segment)
    vertices[:,:2] = np.matmul( vertices[:,:2], T )     # rotated vertices
    return vertices

def detectFrontFacades(streets, vertsS, buildings, vertsB, searchRange):
    """
    Detects the front facades of the buildings.

    Input: 
    ======
    streets:        Dictionary with key: OSM id of street, [i0,i1]: i0: first index,  and i1: last index + 1
                    of vertices in building with id.
    vertsS:         numpy array[N,2] of way nodes
    buildings:      Dictionary with key: OSM id of building, content is [i0,i1]: i0: first index, and i1: last index + 1
                    of vertices in building with id. The vertices of the building are expected in 
                    counter-clockwise order.
    vertsB:         numpy array[N,2] of building vertices
    searchRange:    tuple (dx,dy), where dx: range on left and right of way-segment
                                         dy: Range above and below way-segment

    Output:
    ======
    return:         list of visibility ratios in the same order as vertsB. 
    """
    # back associations, buildings OSM ID for vertice index
    buildingForIndex = []
    for key, building in buildings.items():
        buildingForIndex.extend( [key for i in range(*building)] )

    # prepare kd-tree 
    tree = KDTree(vertsB)

    # prepare result list. Its index corresponds to index of the first vertex of a facade in vertsB
    visibility = [0.0 for i in range(vertsB.shape[0])]

    # iterate over streets
    for key, street in streets.items():
        # iterate over street segments
        for s0,s1 in iterThisNext(range(*street)):         # indices of way-segment indices
            p0, p1  = (vertsS[s0,:], vertsS[s1,:])
            sV = p1-p0                                      # vector of way-segment
            sL = np.linalg.norm(sV)                         # length of way-segment

            # compute transform matrix T
            Vu = sV/sL                                          # unit vector of way-segment
            Vp = np.array( (Vu[1],-Vu[0]) )                     # perpendicular vector to Vu
            T = np.array([np.transpose(Vu),np.transpose(Vp)])   # transform matrix

            # compute search circle parameters
            searchWidth  = sL/2. + searchRange[0]
            searchHeight = searchRange[1]
            searchRadius = np.sqrt(searchWidth*searchWidth+searchHeight*searchHeight)
            searchCenter = (p0+p1)/2

            # get indices of vertices in search circle
            idxs_in_circle = tree.query_ball_point(searchCenter, searchRadius)

            # get all OSM-IDs of buildings associated with these vertices, remove duplicates
            buildIds_in_circle = list(dict.fromkeys([buildingForIndex[i] for i in idxs_in_circle]))

            # compute the list of the indices of all vertices of these buildings
            indcs_all_buildings = []
            buildings_selected = {}
            for build_id in buildIds_in_circle:
                building = buildings[build_id]                              # index range [i0,i1] of building
                # create new dictionary of building vertices between [i0,i1], similar to buildongs, but only of selected buildings 
                buildings_selected[build_id] = [len(indcs_all_buildings), len(indcs_all_buildings)+building[1]-building[0]]
                indcs_all_buildings.extend( [i for i in range(*building)] ) # indices of all vertices in selected buildings

            # transform these vertices to way-segement coordinates, trasnform also way-segment
            rangeVertsT = transfToWayCoords( vertsS[[s0,s1],:], vertsB[indcs_all_buildings,:])
            search_Params = {'searchRadius':searchRadius, 'searchWidth':searchWidth, 'searchHeight':searchHeight,'segmentLength':sL/2.}

            # detect visibility records of all edges of the transformed buildings in search range
            visibilityRecords = detectVisibility(buildings_selected, rangeVertsT, search_Params)

            # check if the result votes for a front facade and put the result in frontFacades list
            for edgeRec in visibilityRecords:
                # as an example of a check: At least 50% of edge visible and angle to way-segment < 45°
                isFront = edgeRec['visRatio']>0.5 and abs(edgeRec['dXY'][0,0]) > abs(edgeRec['dXY'][0,1])
                # the index in frontFacades corresponds to index of the first vertex of a facade in vertsB
                if abs(edgeRec['dXY'][0,0]) > abs(edgeRec['dXY'][0,1]): # abs of angle to way-segment < 45°
                    indx = indcs_all_buildings[edgeRec['i0']]
                    visibility[indx] = max(visibility[indx], edgeRec['visRatio'])

    return visibility

@polarkernel
Copy link
Collaborator

File dataFromOverpass.py:

import requests
import json
import math

# adapted from blender-osm
earthRadius = 6378137.
halfEquator = math.pi * earthRadius
equator = 2. * halfEquator
overpassURL = "http://overpass-api.de/api/interpreter"

# from blender-osm
def toSphericalMercator(lat, lon, moveToTopLeft=False):
    lat = earthRadius * math.log(math.tan(math.pi/4 + lat*math.pi/360))
    lon = earthRadius * lon * math.pi / 180
    # move zero to the top left corner
    if moveToTopLeft:
        lat = halfEquator - lat
        lon = lon + halfEquator
    return (lon, lat)

def buildingQuery(minLon, minLat, maxLon, maxLat):
    coordString = "%s,%s,%s,%s" % (minLat,minLon,maxLat,maxLon)
    query = """
    [out:json];
    (node["building"](%s);
    way["building"](%s);>;
    );
    out geom qt;
    """ % (coordString,coordString)
    return query

def streetsQuery(minLon, minLat, maxLon, maxLat):
    coordString = "%s,%s,%s,%s" % (minLat,minLon,maxLat,maxLon)
    query = """
    [out:json];
    (node["highway"](%s);
    way["highway"](%s);>;
    /*relation["highway"](%s);>>;*/
    );
    out geom qt;
    """ % (coordString,coordString,coordString)
    return query

_allWays = (
    "motorway",
    "trunk",
    "primary",
    "secondary",
    "tertiary",
    "unclassified",
    "residential",
    "service",
    "pedestrian",
    "track",
    "footway",
    "steps",
    "cycleway",
    "bridleway",
    "other"
)

_motorWays = (
    'motorway',
    'trunk',
    'primary',
    'secondary',
    'tertiary',
    'primary_link',
    'secondary_link',
    'tertiary_link',
    'residential',
    'living_street',
    'road'
)

def getBuildings(minLon, minLat, maxLon, maxLat):
    query = buildingQuery(minLon, minLat, maxLon, maxLat)
    response = requests.get(overpassURL, params={'data': query})
    if not response.ok:
        raise Exception("No response on query for buildings")
    data = response.json()

    buildings = {}
    for element in data['elements']:
        if element['type'] == 'way' and 'building' in element['tags']:
            coords = []
            for node in element['nodes'][:-1]:
                v = next((item for item in data['elements'] if item["id"] == node), None)
                coords.append( toSphericalMercator(v['lat'], v['lon'])  )
            buildings[element['id']] = coords
    return buildings

def getStreets(minLon, minLat, maxLon, maxLat):
    query = streetsQuery(minLon, minLat, maxLon, maxLat)
    response = requests.get(overpassURL, params={'data': query})
    if not response.ok:
        raise Exception("No response on query for streets")
    data = response.json()

    streets = {}
    for element in data['elements']:
        if element['type'] == 'way' and 'highway' in element['tags']:
            # if element['tags']['highway'] in _motorWays:
            if element['tags']['highway'] in _motorWays:
                coords = []
                for node in element['nodes']:
                    v = next((item for item in data['elements'] if item["id"] == node), None)
                    coords.append( toSphericalMercator(v['lat'], v['lon'])  )
                streets[element['id']] = coords
    return streets

@polarkernel
Copy link
Collaborator

That's it. Naturally you may change and optimize the code wherever you like.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 9, 2021

Thank you. I'll post questions here as I'll proceed through your code.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 11, 2021

Regarding the priority queue. Python provides an implementation of the priority queue known as heapq:
https://docs.python.org/3/library/heapq.html#basic-examples (see the second example with tuples).

@polarkernel
Copy link
Collaborator

polarkernel commented Mar 11, 2021

Regarding the priority queue.

I know, this was my first attempt for this queue. But we need a priority queue that allows to remove an element, and I was not able to realize that for tuples with heapq. Should there be a solution for that, it should be preferred, as it would be O(N) in contrast to O(N*log(N)) for the current solution.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 12, 2021

Would it be possible to provide a high level description of the algoritm of the function processEvents(..)?

@polarkernel
Copy link
Collaborator

Would it be possible to provide a high level description of the algoritm of the function processEvents(..)?

The function starts with a sorted list eventList of events, created in detectVisibility(). The value indx of every such event is the index of an edge in egdeList, which holds the visibility results for every facade edge. The events are processed from left to right by ascending x-values in the way-segment coordinate system, therefore the event list is sorted by the x-value and then by the y-value, which is the distance to the way-segment. During this process, there are two types of events: in and out. in is the event when an edge starts and out is the event, when it ends.

processEvents() maintains two variables:

  • activeEvent is the event of the edge that is currently visible.
  • activeIn is the x-value of the moment, when the active edge became visible. When the edge disappears, the difference between the current x-value and activeIn is a measure for the visibility of a part of this edge.

The loop in processEvents() processes one event from eventList after the other, from left to right, as it is sorted. It keeps track of the edge nearest to the way-segment as visible (active) edge.

for event in eventList:

  • if there is no activeEvent :
    • The edge of this event becomes for sure visible. Set it as activeEvent and mark its x-value as activeIn .
  • else if the type of event is in: (a new edge starts here)
    • if the new edge is nearer to the way-segment than the active edge :
      • The new edge is in front of the active edge and hides it.
      • Add the part of the active edge, that was visible until here to the visibility value of this edge in egdeList.
      • The active edge did not yet end and may become visible again later. Therefore push it into the priority queue for later use.
      • The current event becomes now activeEvent and its visibility start is set into activeIn.
    • else:
      • The new edge is not visible, but may become visible later. Push it into the priority queue for later use.
  • else if the type of event is out: (this edge ends here)
    • if it is the active edge that ends here:
      • Add the part of the active edge, that was visible until here to the visibility value of this edge in egdeList.
      • if there are edges in the priority queue, that did not yet end:
        • Pop the top one (the one nearest to the way-segment) and make it the active element. It must be visible now (eventually again). Mark its x-value as activeIn .
      • else:
        • Set activeEvent to None (there is no more an active event after, until a new one is created).
    • else:
      • An edge, that is currently invisible, ended here. Remove it from the priority queue.

The summed visible parts in the elements of the egdeList are the sum of the visible x-ranges of the corresponding edge. To compute the visibility ratio, it has to be divided by the total x-width of this edge.

I hope this description makes the process understandable. If not, I will create some drawings.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 13, 2021

I hope this description makes the process understandable. If not, I will create some drawings.

Please illustrate that case:

* if there are edges in the priority queue, that did not yet end:
  
  * Pop the top one (the one nearest to the way-segment) and make it the active element. It must be visible now (eventually again). Mark its x-value as _activeIn_ .

@polarkernel
Copy link
Collaborator

Please illustrate that case: ...

This case happens at the x-position E4 in the following drawing:

But let me explain some part of the process history before this event. Just before the event position E1, the facade F1 (red) is the active facade and F3 is on top of the priority queue.

  • At E1, the first event ist the in type of the facade F5. As it is behind F1, it is pushed on the queue. The order in the queue is now F3, F5.
  • The next event, still at E1, is the in type of the facade F8. As its y-value is larger than that of F5, it appears after F5 in the event list. Again it is behind the active facade and therefore pushed on the queue. The order in the queue is now F3, F5, F8.
  • Similarly, at E2, the in type of the facade F7 results in a push to the queue. The order in the queue is now F3, F5, F8, F7.
  • Still at E2, the out event of F8 is encountered. As F8 is not the active facade, it is removed from the queue. The order in the queue is now F3, F5, F7.
  • At E3, the next event is the out event of F3. As F3 is not the active facade, it is removed from the queue. The order in the queue is now F5, F7.
  • Still at E3, the facade F2 get psushed to the queue, but as the y-distance is smaller than that of the other facades, it ends at the top of the queue. The order in the queue is now F2, F5, F7.
  • At E4, we have the out event of the active facade. This is now the case requested to be illustrated. As there are facades in the queue, the top one (F2) becomes the active facade. The order in the queue is now F5, F7.
  • The next event, still at E4, is the out event of F2. This facade has no visibility, as its active range has been zero (in and out at the same x-value). But as it was the active facade at this event, we have again the case requested to be illustrated. There are still facades in the queue and therefore, F5 is extracted and gets the active facade. It remains active until its out event and its green part is added to the visibility value of its edge in the edge list.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 13, 2021

A note.

T = np.array([np.transpose(Vu),np.transpose(Vp)])

Is the transpose neccessary here? Vu and Vp are one-dimensional arrays. Transposing a 1-D array returns an unchanged view of the original array.

@polarkernel
Copy link
Collaborator

Is the transpose neccessary here?

No, it's not. This seems to be a relict from the begin of the development.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 15, 2021

Question.

There are two events at E3. Both of them have the same Y defined as the maximum Y coordinate of the vertices of the related edge.

Then the position of the edges F3 and F2 in the event queue is ambiguous. Isn't it?

@vvoovv
Copy link
Member Author

vvoovv commented Mar 29, 2021

These are partially visible.

But the other ones (1 and 2 on the image below) aren't visible at all:
image

@vvoovv
Copy link
Member Author

vvoovv commented Mar 29, 2021

It gets eliminated to to the 45° condition in line194, as the streets at this corner are not perpendicular.

What if we remove that line?

@vvoovv
Copy link
Member Author

vvoovv commented Mar 29, 2021

What if we remove that line?

Instead of the removal the condition should be somehow modified.

@polarkernel
Copy link
Collaborator

But the other ones (1 and 2 on the image below) aren't visible at all:

I will check what happens there.

What if we remove that line?

Then, edges that are almost perpendicular to the way-segment may get 100% visibility, if they are not hidden by any other edges.

Instead of the removal the condition should be somehow modified.

What about some kind of weighting by the angle, so that the current visibility remains what it actually is, as long as the angle is between 0°...45°, and then gets decreased to zero in the range of 45°...XX°?

@polarkernel
Copy link
Collaborator

I will check what happens there.

Edge 1: The two buildings overlap each other and the edge from the outer building is partly visible:

Edge 2: There is an issue in my concept that I am not yet able to solve. There are two buildings that are crossed by the way segment, where one runs behind the other partly. No idea hw to solve until now.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 29, 2021

Edge 1: The two buildings overlap each other and the edge from the outer building is partly visible:

I didn't notice that the blue edge has a small unhidden part nearly the upper way. Anyway, I am going to solve this issue by detecting shared edges. But right now I am working on the category of the way.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 30, 2021

Could the streets in computation and visualization get synchronized?

Done.

Also a way category can be accessed as way.category.

A preferable way of using it in a condition is

from way import Category

if way.category is Category.footprint:
    ...

@vvoovv
Copy link
Member Author

vvoovv commented Mar 30, 2021

However, making such tags accessible could eventually help.

It can be done with way.tunnel. It's a bool variable.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 30, 2021

The buildings at the bottom row have been designed with an inner border, tagged as manmade=courtyards

Just a note. manmade=courtyards is an abandoned propoposal. We shouldn't rely on it.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 30, 2021

What about some kind of weighting by the angle, so that the current visibility remains what it actually is, as long as the angle is between 0°...45°, and then gets decreased to zero in the range of 45°...XX°?

The angle can another factor for scoring along with way category and distance to a building edge.

@polarkernel
Copy link
Collaborator

Edge 2: There is an issue in my concept that I am not yet able to solve.

Was difficult to find, but now I committed a solution for this issue. Let me explain its reason and my solution. First a simple example that shows the behavior for crossed buildings of the old solution. Lets assume that we have a simple building (left image), that is crossed by a way-segment axis. The edges in posEvents are depicted in the right image. Because the contour is now open, the upper edge gets visibility. However, because the edges are ordered counter-clockwise, the visibility of this edge was removed, as for buildings in the positive area edges can't be visible when they run from right to left.

Now a more complicated example, that symbolizes this issue (the real case was more complicated). On the left we have two buildings, both crossed by by a way-segment axis. These buildings have a common edge. Again, the edges in posEvents are depicted in the right image. Common edges are normally not a problem, because they are always hidden by the buildings. But in this case, they are visible both from the way-segment.

In the sorted event list, these common edges have a ambigious order, and for manhattan_01.osm, the wrong one from the upper building was taken first and got visibility in processEvents(). Because it runs from left to right, it was not eliminated.

In my new solution I introduced dummy edge events between the intersection points of the way-segment axis (red in the image below). For both examples, the building gets closed now and the edges are no more visible. The code that tested the edge direction could now be removed. This soulution runs fine and can be tested now.

@polarkernel
Copy link
Collaborator

Just a note. manmade=courtyards is an abandoned propoposal. We shouldn't rely on it.

I didn't use it. Where can the "official" tags be found, is there some Wiki somewhere?

@vvoovv
Copy link
Member Author

vvoovv commented Mar 30, 2021

I didn't use it. Where can the "official" tags be found, is there some Wiki somewhere?

For buildings: https://wiki.openstreetmap.org/wiki/Key:building
For ways: https://wiki.openstreetmap.org/wiki/Key:highway

@vvoovv
Copy link
Member Author

vvoovv commented Mar 30, 2021

This solution runs fine and can be tested now.

Is it already commited?

@polarkernel
Copy link
Collaborator

Is it already commited?

Yes.

@vvoovv
Copy link
Member Author

vvoovv commented Mar 31, 2021

I added a couple of OSM files to test very wide street:

They look ok for me

@vvoovv
Copy link
Member Author

vvoovv commented Apr 28, 2021

I introduced the class VisibilityInfo.
It is now possible to implement a more complex algorithm to determine a winning way-segment in the method gt.

What would be the distance for a crossed edge in the line 239?

@polarkernel
Copy link
Collaborator

What would be the distance for a crossed edge in the line 239?

I would let it almost as it is. The sum of a positive and a negative value will result in a small, maybe negative, value. Using the absolute value of this sum should do it.

@vvoovv
Copy link
Member Author

vvoovv commented Apr 29, 2021

I would let it almost as it is. The sum of a positive and a negative value will result in a small, maybe negative, value. Using the absolute value of this sum should do it.

I changed it to abs(Y1+Y2).

@vvoovv
Copy link
Member Author

vvoovv commented Aug 31, 2021

I want to skip the visibility calculation for curved facades.

There are currently four places in the module action/facade_visibility.py where the iteration through the polygon edges is done.

Line 137:
Polygon edges crosses by way segments are found here. The curved features aren't needed there since the visibility isn't calculated for them. Is it correct?

Line 180:
Polygon edges forming a curved feature are needed here since they may hide other edges from a way-segment. Is it correct?

Line 215:
visInfo is set there, so curved features aren't needed there. Is it correct?

Line 267:
visInfo is set there, so curved features aren't needed there. Is it correct?

@polarkernel
Copy link
Collaborator

Line 137:
Polygon edges crosses by way segments are found here. The curved features aren't needed there since the visibility isn't calculated for them. Is it correct?

I am not sure. The curved features may cross the axis of the way-segment. They have to be split in a part that is checked in positive events and another part by negative events. A dummy edge closes the gap between them. Curved features are at least required to construct this dummy edge in this case. An illustration is here.

Line 180:
Polygon edges forming a curved feature are needed here since they may hide other edges from a way-segment. Is it correct?

Yes.

Line 215:
visInfo is set there, so curved features aren't needed there. Is it correct?

Yes.

Line 267:
visInfo is set there, so curved features aren't needed there. Is it correct?

Yes.

@vvoovv
Copy link
Member Author

vvoovv commented Nov 11, 2021

Found an issue with the visibility calculation.

File feature_detection/tula_bay_windows_01.osm. Edge 259 located in the middle of the screenshot below.

image

The winning way-segment is perpendicular to the building edge 259. That leads later to the incorrect assignment of the facade class side to the building edge 259. The winning way-segment for the building edge 259 should the way-segment 58 or 59.

To get that result execute the command:

python.exe -m script.command_line --buildings --highways --detectFeatures --simplifyPolygons --facadeVisibility --showAssoc --showIDs --setupScript setup/mpl_blosm.py --osmFilepath ../osm_extracts/feature_detection/tula_bay_windows_01.osm

@polarkernel
Copy link
Collaborator

To get that result execute the command:

Which branch did you use?

@vvoovv
Copy link
Member Author

vvoovv commented Nov 11, 2021

dev

@polarkernel
Copy link
Collaborator

Sorry for the late answer, I had to recover my system after a crash. Recovering using a backup system-image takes about 3 hours. Fortunately, the backup was quite new.

Found an issue with the visibility calculation.

The perpendicular way-segment generates a classification of edge 259 as FacadeClass.deadend already in the visibility computation, as it is nearer than 10m to the way-segment (defined in line 18 of defs/facade_classification.py.

@vvoovv
Copy link
Member Author

vvoovv commented Nov 11, 2021

But the way-segments 58 and 59 parallel to the building edge 259 should take precedence over the perpendicular way-segment. One of them should be the winning one.

@polarkernel
Copy link
Collaborator

You are right. The method to treat dead-ends by classification already in facade_visibility.py is the wrong way. This has already caused many problems. Tomorrow I will provide a better solution.

@polarkernel
Copy link
Collaborator

Tomorrow I will provide a better solution.

A fixed version is committed. Using a test file check_deadend.osm (added to osm_extracts/facade_visibility/) and added --classifyFacades to execute the command, I get the following behavior:

At top left, the only dead-end way leads to the front facade. At top right, both ways have the same wayLevel and again, the dead-end way dominates. At bottom left, the way parallel to the building has the lower wayLevel and therefore determines the facade classification. Finally, at the bottom right, the dead-end way has the lower wayLevel. Note that a comparison of visibility is not possible, as a dead-end way never produces visibility.

@vvoovv
Copy link
Member Author

vvoovv commented Nov 12, 2021

At top right, both ways have the same wayLevel and again, the dead-end way dominates.

It isn't a big issue here. But the parallel way should win for that case, I think.

@polarkernel
Copy link
Collaborator

But the parallel way should win for that case, I think.

Fixed and committed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants