# Visibility polygons

I’m wondering if anyone knows any tricks in building visibility polygons?

This is what I got so far (the blue wireframe ‘star’ is what I’m after):

For every point I want to construct a visibility polygon I’ve got a collision ray, the walls also have collisions enabled. I spin the rays 360 deg. and record all the surface points hits, then filter out unneeded points (I take 3 point and check if the area of a triangle made from them is bigger then 0.001) and finally make triangles out of what’s left.

It works, but it’s painfully slow.
So any ideas? Preferably ideas that won’t make my brain melt or with some code if lots of math is involved.

Maybe this link will be usable code.google.com/p/visibility-po … polygon.js
Java Script, but I think it’s not too difficult to translate it to python code. One thing: you need to make additional data to pass your geometry to the script.

Also there C++ library with python binding, but you should able to compile it by yourself visilibity.org/

Thanks for the links!
Compiling C++ code looks scary for me, with the bindings I’m probably missing some important step (all I got is a ImportError), so I’m trying to translate the javascript to python, but so far with little success
I’m not sure what I did wrong, cause I’m not sure how the code actually works, just making a line by line translation.
I got it to run without errors, but it only returns one point, not a list.
I think I got a loop wrong.
The original code looks more or less like this:

``````for (var i = 0; i < sorted.length;) {
//some code here
do {
//some code here
++1;
if (i == sorted.length) break;
} while SomeCondition();
//some code here
}``````

There’s no do-while loop in python, and a for loop looks a bit different. I wrote it down as:

``````i=0
while i < (len(sorted)):
#some code
while True:
#some code
i+=1
if (i == len(sorted)):
break
if SomeCondition():
break
#some code``````

…now that I look at this, it probably should be ‘if not SomeCondition():’, but that makes the whole thing freez.

This is what I have:

``````import math

class VisibilityPolygon():
def compute(self, position, segments):
polygon = []
sorted = self.sortPoints(position, segments);
map=[]
for i in segments:
map.append(-1)
heap = []
start = [position[0] + 1, position[1]]
for i in xrange(len(segments)):
a1 = self.angle(segments[i][0], position)
a2 = self.angle(segments[i][1], position)
active = False
if (a1 > -180 and a1 <= 0 and a2 <= 180 and a2 >= 0 and a2 - a1 > 180):
active = True
if (a2 > -180 and a2 <= 0 and a1 <= 180 and a1 >= 0 and a1 - a2 > 180):
active = True
if active:
self.insert(i, heap, position, segments, start, map)
i=0
while i < (len(sorted)):
extend = False
shorten = False
orig = i
vertex = segments[sorted[i][0]][sorted[i][1]]
old_segment = heap[0]
while True:
if (map[sorted[i][0]] != -1):
if (sorted[i][0] == old_segment):
extend = True;
vertex = segments[sorted[i][0]][sorted[i][1]]
self.remove(map[sorted[i][0]], heap, position, segments, vertex, map);
else:
self.insert(sorted[i][0], heap, position, segments, vertex, map)
if (heap[0] != old_segment):
shorten = True
i+=1
if (i == len(sorted)):
break
if  (sorted[i][2] < (sorted[orig][2] + self.epsilon())):
break
if extend:
polygon.append(vertex)
cur = self.intersectLines(segments[heap[0]][0], segments[heap[0]][1], position, vertex)
if not self.equal(cur, vertex):
polygon.append(cur)
elif shorten:
polygon.append(self.intersectLines(segments[old_segment][0], segments[old_segment][1], position, vertex));
polygon.append(self.intersectLines(segments[heap[0]][0], segments[heap[0]][1], position, vertex));
return polygon

def sortPoints(self, position, segments):
points=range(len(segments)*2)
for i in xrange(len(segments)):
for j in range(2):
a=self.angle(segments[i][j], position)
points[2*i+j] = [i, j, a]
points.sort(key=lambda x: x[2]) # is this the same?? points.sort(function(a,b) {return a[2]-b[2];});
return points

def angle (self, a, b):
return math.atan2(b[1]-a[1], b[0]-a[0]) * 180 / math.pi

def insert (self, index, heap, position, segments, destination, map):
intersect = self.intersectLines(segments[index][0], segments[index][1], position, destination)
if len(intersect) == 0:
return
cur = len(heap)
heap.append(index)
map[index] = cur
while (cur > 0):
parent = self.parent(cur)
if not self.lessThan(heap[cur], heap[parent], position, segments, destination):
break
map[heap[parent]] = cur
map[heap[cur]] = parent
temp = heap[cur]
heap[cur] = heap[parent]
heap[parent] = temp
cur = parent

def intersectLines(self, a1, a2, b1, b2):
ua_t = (b2[0] - b1[0]) * (a1[1] - b1[1]) - (b2[1] - b1[1]) * (a1[0] - b1[0])
ub_t = (a2[0] - a1[0]) * (a1[1] - b1[1]) - (a2[1] - a1[1]) * (a1[0] - b1[0])
u_b  = (b2[1] - b1[1]) * (a2[0] - a1[0]) - (b2[0] - b1[0]) * (a2[1] - a1[1])
if (u_b != 0):
ua = ua_t / u_b
ub = ub_t / u_b
return [a1[0] - ua * (a1[0] - a2[0]), a1[1] - ua * (a1[1] - a2[1])]
return []

def parent (self, index):
return int(math.floor((index-1)/2))

def lessThan (self, index1, index2, position, segments, destination):
inter1 = self.intersectLines(segments[index1][0], segments[index1][1], position, destination)
inter2 = self.intersectLines(segments[index2][0], segments[index2][1], position, destination)
if not self.equal(inter1, inter2):
d1 = self.distance(inter1, position)
d2 = self.distance(inter2, position)
return d1 < d2

end1 = 0
if (self.equal(inter1, segments[index1][0])):
end1 = 1
end2 = 0
if (self.equal(inter2, segments[index2][0])):
end2 = 1
a1 = self.angle2(segments[index1][end1], inter1, position)
a2 = self.angle2(segments[index2][end2], inter2, position)
if (a1 < 180):
if (a2 > 180):
return True
#return a2 < a1
return a1 < a2

def equal (self, a, b):
if (abs(a[0] - b[0]) < self.epsilon() and abs(a[1] - b[1]) < self.epsilon()):
return True
return False

def epsilon (self):
return 0.0000001  #is this crazy, or what?

def distance (self, a, b):
return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])

def angle2(self, a, b, c):
a1 = self.angle(a,b)
a2 = self.angle(b,c)
a3 = a1 - a2;
if (a3 < 0):
a3 += 360
if (a3 > 360):
a3 -= 360
return a3

def remove (self, index, heap, position, segments, destination, map):
map[heap[index]] = -1
if (index == len(heap) - 1):
heap.pop()
return
heap[index] = heap.pop()
map[heap[index]] = index
cur = index
parent = self.parent(cur)
if (cur != 0 and self.lessThan(heap[cur], heap[parent], position, segments, destination)):
while (cur > 0):
parent = self.parent(cur)
if not self.lessThan(heap[cur], heap[parent], position, segments, destination):
break
map[heap[parent]] = cur
map[heap[cur]] = parent
temp = heap[cur]
heap[cur] = heap[parent]
heap[parent] = temp
cur = parent
else:
while True:
left = self.child(cur);
right = left + 1;
if (left < len(heap) and self.lessThan(heap[left], heap[cur], position, segments, destination) and
(right == len(heap) or self.lessThan(heap[left], heap[right], position, segments, destination))):
map[heap[left]] = cur
map[heap[cur]] = left
temp = heap[left]
heap[left] = heap[cur]
heap[cur] = temp
cur = left
elif (right < len(heap) and self.lessThan(heap[right], heap[cur], position, segments, destination)):
map[heap[right]] = cur
map[heap[cur]] = right
temp = heap[right]
heap[right] = heap[cur]
heap[cur] = temp
cur = right
else:
break

def child (self,index):
return 2*index+1

def convertToSegments (self, polygons):
segments = []
for i in xrange(len(polygons)):
for j in xrange(len(polygons[i])):
k = j+1
if (k == len(polygons[i])):
k = 0
segments.append([polygons[i][j], polygons[i][k]])
return segments``````

Can be tested like this:

``````from vis import VisibilityPolygon

VP=VisibilityPolygon()
polygons = []

polygons.append([[-1,-1],[501,-1],[501,501],[-1,501]])
polygons.append([[240,240],[260,240],[260,260],[240,260]])
polygons.append([[240,260],[260,260],[260,280],[240,280]])
polygons.append([[260,240],[280,240],[280,260],[260,260]])
polygons.append([[440,240],[460,240],[460,260],[440,260]])
polygons.append([[250,100],[260,140],[240,140]])
polygons.append([[280,100],[290,60],[270,60]])
polygons.append([[310,100],[320,140],[300,140]])
polygons.append([[50,450],[60,370],[70,450]])
polygons.append([[450,450],[460,370],[470,450]])
polygons.append([[50,50],[60,30],[70,50]])
polygons.append([[450,50],[460,30],[470,50]])
polygons.append([[140,340],[160,240],[180,340],[360,340],[360,360],[250,390],[140,360]])
polygons.append([[140,140],[150,130],[150,145],[165,150],[160,160],[140,160]])

segments = VP.convertToSegments(polygons)
position = [109, 109]

print VP.compute(position, segments)``````

Much kudos for any help

``````import math

class VisibilityPolygon1():
def compute(self, position, segments):
polygon = []
sorted = self.sortPoints(position, segments);
map=[-1] * len(segments)
heap = []
start = [position[0] + 1, position[1]]
for i in xrange(len(segments)):
a1 = self.angle(segments[i][0], position)
a2 = self.angle(segments[i][1], position)
active = False
if (a1 > -180 and a1 <= 0 and a2 <= 180 and a2 >= 0 and a2 - a1 > 180):
active = True
if (a2 > -180 and a2 <= 0 and a1 <= 180 and a1 >= 0 and a1 - a2 > 180):
active = True
if active:
self.insert(i, heap, position, segments, start, map)
i=0
while i < (len(sorted)):
extend = False
shorten = False
orig = i
vertex = segments[sorted[i][0]][sorted[i][1]]
old_segment = heap[0]
while (sorted[i][2] < sorted[orig][2] + self.epsilon()):
if (map[sorted[i][0]] != -1):
if (sorted[i][0] == old_segment):
extend = True;
vertex = segments[sorted[i][0]][sorted[i][1]]
self.remove(map[sorted[i][0]], heap, position, segments, vertex, map);
else:
self.insert(sorted[i][0], heap, position, segments, vertex, map)
if (heap[0] != old_segment):
shorten = True
i+=1
if (i == len(sorted)):
break
if extend:
polygon.append(vertex)
cur = self.intersectLines(segments[heap[0]][0], segments[heap[0]][1], position, vertex)
if not self.equal(cur, vertex):
polygon.append(cur)
elif shorten:
polygon.append(self.intersectLines(segments[old_segment][0], segments[old_segment][1], position, vertex));
polygon.append(self.intersectLines(segments[heap[0]][0], segments[heap[0]][1], position, vertex));
return polygon

def sortPoints(self, position, segments):
points=[-1] * (len(segments)*2)
for i in xrange(len(segments)):
for j in range(2):
a=self.angle(segments[i][j], position)
points[2*i+j] = [i, j, a]
points.sort(key=lambda x: x[2]) # is this the same?? points.sort(function(a,b) {return a[2]-b[2];});
return points

def angle (self, a, b):
return math.atan2(b[1]-a[1], b[0]-a[0]) * 180 / math.pi

def insert (self, index, heap, position, segments, destination, map):
intersect = self.intersectLines(segments[index][0], segments[index][1], position, destination)
if len(intersect) == 0:
return
cur = len(heap)
heap.append(index)
map[index] = cur
while (cur > 0):
parent = self.parent(cur)
if not self.lessThan(heap[cur], heap[parent], position, segments, destination):
break
map[heap[parent]] = cur
map[heap[cur]] = parent
temp = heap[cur]
heap[cur] = heap[parent]
heap[parent] = temp
cur = parent

def intersectLines(self, a1, a2, b1, b2):
a1 = map(float, a1)
a2 = map(float, a2)
b1 = map(float, b1)
b2 = map(float, b2)
ua_t = (b2[0] - b1[0]) * (a1[1] - b1[1]) - (b2[1] - b1[1]) * (a1[0] - b1[0])
ub_t = (a2[0] - a1[0]) * (a1[1] - b1[1]) - (a2[1] - a1[1]) * (a1[0] - b1[0])
u_b  = (b2[1] - b1[1]) * (a2[0] - a1[0]) - (b2[0] - b1[0]) * (a2[1] - a1[1])
if (u_b != 0):
ua = ua_t / u_b
ub = ub_t / u_b
return [a1[0] - ua * (a1[0] - a2[0]), a1[1] - ua * (a1[1] - a2[1])]
return []

def parent (self, index):
return int(math.floor((index-1)/2))

def lessThan (self, index1, index2, position, segments, destination):
inter1 = self.intersectLines(segments[index1][0], segments[index1][1], position, destination)
inter2 = self.intersectLines(segments[index2][0], segments[index2][1], position, destination)
if not self.equal(inter1, inter2):
d1 = self.distance(inter1, position)
d2 = self.distance(inter2, position)
return d1 < d2

end1 = 0
if (self.equal(inter1, segments[index1][0])):
end1 = 1
end2 = 0
if (self.equal(inter2, segments[index2][0])):
end2 = 1
a1 = self.angle2(segments[index1][end1], inter1, position)
a2 = self.angle2(segments[index2][end2], inter2, position)
if (a1 < 180):
if (a2 > 180):
return True
return a2 < a1
return a1 < a2

def equal (self, a, b):
if (abs(a[0] - b[0]) < self.epsilon() and abs(a[1] - b[1]) < self.epsilon()):
return True
return False

def epsilon (self):
return 0.0000001  #is this crazy, or what?

def distance (self, a, b):
return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])

def angle2(self, a, b, c):
a1 = self.angle(a,b)
a2 = self.angle(b,c)
a3 = a1 - a2;
if (a3 < 0):
a3 += 360
if (a3 > 360):
a3 -= 360
return a3

def remove (self, index, heap, position, segments, destination, map):
map[heap[index]] = -1
if (index == len(heap) - 1):
heap.pop()
return
heap[index] = heap.pop()
map[heap[index]] = index
cur = index
parent = self.parent(cur)
if (cur != 0 and self.lessThan(heap[cur], heap[parent], position, segments, destination)):
while (cur > 0):
parent = self.parent(cur)
if not self.lessThan(heap[cur], heap[parent], position, segments, destination):
break
map[heap[parent]] = cur
map[heap[cur]] = parent
temp = heap[cur]
heap[cur] = heap[parent]
heap[parent] = temp
cur = parent
else:
while True:
left = self.child(cur);
right = left + 1;
if (left < len(heap) and self.lessThan(heap[left], heap[cur], position, segments, destination) and
(right == len(heap) or self.lessThan(heap[left], heap[right], position, segments, destination))):
map[heap[left]] = cur
map[heap[cur]] = left
temp = heap[left]
heap[left] = heap[cur]
heap[cur] = temp
cur = left
elif (right < len(heap) and self.lessThan(heap[right], heap[cur], position, segments, destination)):
map[heap[right]] = cur
map[heap[cur]] = right
temp = heap[right]
heap[right] = heap[cur]
heap[cur] = temp
cur = right
else:
break

def child (self,index):
return 2*index+1

def convertToSegments (self, polygons):
segments = []
for i in xrange(len(polygons)):
for j in xrange(len(polygons[i])):
k = j+1
if (k == len(polygons[i])):
k = 0
segments.append([polygons[i][j], polygons[i][k]])
return segments

if __name__ == '__main__':
from PIL import Image, ImageDraw
VP=VisibilityPolygon1()
polygons = []

polygons.append([[-1,-1],[501,-1],[501,501],[-1,501]])
polygons.append([[240,240],[260,240],[260,260],[240,260]])
polygons.append([[240,260],[260,260],[260,280],[240,280]])
polygons.append([[260,240],[280,240],[280,260],[260,260]])
polygons.append([[440,240],[460,240],[460,260],[440,260]])
polygons.append([[250,100],[260,140],[240,140]])
polygons.append([[280,100],[290,60],[270,60]])
polygons.append([[310,100],[320,140],[300,140]])
polygons.append([[50,450],[60,370],[70,450]])
polygons.append([[450,450],[460,370],[470,450]])
polygons.append([[50,50],[60,30],[70,50]])
polygons.append([[450,50],[460,30],[470,50]])
polygons.append([[140,340],[160,240],[180,340],[360,340],[360,360],[250,390],[140,360]])
polygons.append([[140,140],[150,130],[150,145],[165,150],[160,160],[140,160]])

segments = VP.convertToSegments(polygons)
position = [209, 109]
visibility = VP.compute(position, segments)

# Debug PIL Image out
image = Image.new("RGBA", (500,500), (0,0,0,1))
draw = ImageDraw.Draw(image)
for i in xrange(1, len(polygons)):
draw.polygon(map(tuple, polygons[i]), fill = 'red')
draw.polygon(map(tuple, visibility), fill = 'white')
draw.ellipse((position[0]-3, position[1]-3, position[0]+3, position[1]+3), fill='blue')
del draw
image.save("test.png", "PNG")``````

The biggest trouble where in the intersectLines. Calculating should be done with floating points.
Not sure that my other changes is critical.

That did it, I’m off to integrate it with my little project and I should be posting something interesting in a day or two.
Big thanks, kudos, Спасибо, очень хорошо!

Just found at he forum link to th Py2D Library github.com/sseemayer/Py2D
Look at 1:55 youtube.com/watch?v=PSRmE7kIVhU

That looks very usable. For the time I’ll stick with what I’ve got, but Py2D is going to my bookmarks.