SHOW:
|
|
- or go back to the newest paste.
| 1 | import pygame | |
| 2 | import random | |
| 3 | import math | |
| 4 | ||
| 5 | pygame.init() | |
| 6 | ||
| 7 | screen = pygame.display.set_mode([300,300]) | |
| 8 | ||
| 9 | def random_point_coud_2D(n, radius=10, deviation=3): | |
| 10 | pts = [(0, 0)]*n | |
| 11 | for i in range(n): | |
| 12 | angle = random.random() * 2 * math.pi | |
| 13 | rad = random.gauss(radius, deviation) | |
| 14 | pts[i] = (math.cos(angle)*rad, math.sin(angle)*rad) | |
| 15 | return pts | |
| 16 | ||
| 17 | def translate_pts(pts, shift): | |
| 18 | return [(pt[0] + shift[0], pt[1] + shift[1])for pt in pts] | |
| 19 | ||
| 20 | def translate_edges(edges, shift): | |
| 21 | tx, ty = shift | |
| 22 | return [((ptA[0] + tx, ptA[1] + ty), (ptB[0] + tx, ptB[1] + ty)) for (ptA, ptB) in edges] | |
| 23 | ||
| 24 | def pt_center(pts): | |
| 25 | if(len(pts) == 0): | |
| 26 | return (0,0) | |
| 27 | sum_x = 0 | |
| 28 | sum_y = 0 | |
| 29 | for (x, y) in pts: | |
| 30 | sum_x += x | |
| 31 | sum_y += y | |
| 32 | return (sum_x / len(pts), sum_y / len(pts)) | |
| 33 | ||
| 34 | def dot(ptA, ptB): | |
| 35 | return ptA[0]*ptB[0] + ptA[1]*ptB[1] | |
| 36 | ||
| 37 | def crossz(ptA, ptB): | |
| 38 | return ptA[0]*ptB[1] - ptA[1]*ptB[0] | |
| 39 | ||
| 40 | def norm(vec): | |
| 41 | l = math.sqrt(vec[0]*vec[0] + vec[1]*vec[1]) | |
| 42 | return (vec[0] / l, vec[1] / l) | |
| 43 | ||
| 44 | def point_in_triangle(pt, edges): | |
| 45 | for (ptA, ptB) in edges: | |
| 46 | vecside = norm((ptB[0]-ptA[0], ptB[1]-ptA[1])) | |
| 47 | vecpt = norm((pt[0]-ptA[0], pt[1]-ptA[1])) | |
| 48 | side = (crossz(vecside, vecpt) > 0) # pt is on correct side of this edge | |
| 49 | proj = 0 <= dot(vecside, vecpt) and dot(vecside, vecpt) <= 1 # pt lies between A and B in projection | |
| 50 | if(not (side and proj)): | |
| 51 | # test failed for any edge.. fails overall | |
| 52 | return False | |
| 53 | return True | |
| 54 | ||
| 55 | # this is a hack. horrible n^3 time | |
| 56 | def get_center_triangle(pts): | |
| 57 | # sort points in terms of angle from x-axis | |
| 58 | pts.sort( cmp=lambda (ax, ay), (bx, by): cmp(math.atan2(ay, ax), math.atan2(by, bx))) | |
| 59 | # test every combination of 3 points | |
| 60 | for i in range(len(pts)): | |
| 61 | ptA = pts[i] | |
| 62 | for j in range(len(pts)): | |
| 63 | if j == i: | |
| 64 | continue | |
| 65 | ptB = pts[j] | |
| 66 | for k in range(len(pts)): | |
| 67 | if k == j or k == i: | |
| 68 | continue | |
| 69 | ptC = pts[k] | |
| 70 | if point_in_triangle((0,0), [(ptA, ptB), (ptB, ptC), (ptC, ptA)]): | |
| 71 | return (ptA, ptB, ptC) | |
| 72 | print "NO CENTER TRIANGLE FOUND" | |
| 73 | return None | |
| 74 | ||
| 75 | def surface(pts): | |
| 76 | center = pt_center(pts) | |
| 77 | tx = -center[0] | |
| 78 | ty = -center[1] | |
| 79 | pts = translate_pts(pts, (tx, ty)) | |
| 80 | # tricky part: initialization | |
| 81 | # initialize edges such that you have a triangle with the origin inside of it | |
| 82 | # in 3D, this will be a tetrahedron. | |
| 83 | ptA, ptB, ptC = get_center_triangle(pts) | |
| 84 | print ptA, ptB, ptC | |
| 85 | # tracking edges we've already included (triangles in 3D) | |
| 86 | edges = [(ptA, ptB), (ptB, ptC), (ptC, ptA)] | |
| 87 | # loop over all other points | |
| 88 | pts.remove(ptA) | |
| 89 | pts.remove(ptB) | |
| 90 | pts.remove(ptC) | |
| 91 | draw_scene(translate_pts(pts, (-tx, -ty)), translate_edges(edges, (-tx, -ty))) | |
| 92 | pygame.event.wait() | |
| 93 | for pt in pts: | |
| 94 | ptA = (0,0) | |
| 95 | ptB = (0,0) | |
| 96 | # find the edge that this point will be splitting | |
| 97 | for (ptA, ptB) in edges: | |
| 98 | - | edges = [((ptA[0] - tx, ptA[1] - ty), (ptB[0] - tx, ptB[1] - ty)) for (ptA, ptB) in edges] |
| 98 | + | |
| 99 | break | |
| 100 | edges.remove((ptA, ptB)) | |
| 101 | edges.append((ptA, pt)) | |
| 102 | edges.append((pt, ptB)) | |
| 103 | draw_scene(translate_pts(pts, (-tx, -ty)), translate_edges(edges, (-tx, -ty))) | |
| 104 | pygame.event.wait() | |
| 105 | ||
| 106 | # translate everything back | |
| 107 | edges = translate_edges(edges, (-tx, -ty)) | |
| 108 | return edges | |
| 109 | ||
| 110 | # PYGAME/GRAPHICS | |
| 111 | ||
| 112 | def clear_screen(): | |
| 113 | screen.fill([255,255,255]) | |
| 114 | ||
| 115 | def draw_pts(pts, clear=True, size=1): | |
| 116 | if clear: | |
| 117 | clear_screen() | |
| 118 | for pt in pts: | |
| 119 | pygame.draw.circle(screen, (0, 0, 0), (int(pt[0]), int(pt[1])), size) | |
| 120 | ||
| 121 | def draw_lines(lines, clear=True, size=1): | |
| 122 | if(clear): | |
| 123 | clear_screen() | |
| 124 | for line in lines: | |
| 125 | pygame.draw.line(screen, (0,0,0), (int(line[0][0]), int(line[0][1])), (int(line[1][0]), int(line[1][1])), size) | |
| 126 | ||
| 127 | def draw_scene(pts, lines): | |
| 128 | draw_pts(pts, size=3) | |
| 129 | - | pause = raw_input() |
| 129 | + | |
| 130 | pygame.display.update() | |
| 131 | ||
| 132 | if __name__ == '__main__': | |
| 133 | pts = random_point_coud_2D(100, radius=100, deviation=10) | |
| 134 | pts = translate_pts(pts, (150, 150)) | |
| 135 | # draw_scene(pts, []) | |
| 136 | # pause = raw_input() | |
| 137 | draw_scene(pts, surface(pts)) | |
| 138 | pygame.image.save(screen, '/home/richard/Documents/code/SillyCode/point_cloud_demo.jpg') | |
| 139 | pygame.quit() |
