

In [57]:

    
import random
import numpy

Priprava podatkov

Najprej sem pri Gašperju v Blenderju narisal krivuljo. Dobil sem triangulacijo objekta. Odstranil sem stranice, ki se nahajajo v dveh trikotnikih in tako sem dobil zunanjost krivulje (ki je sklenjena).



In [15]:

    
-



In [16]:

    
triangles = ((0, 1, 2),
(3, 4, 5),
(6, 7, 8),
(4, 9, 10),
(6, 8, 11),
(12, 3, 13),
(11, 8, 14),
(9, 15, 16),
(11, 14, 17),
(15, 18, 16),
(14, 19, 17),
(20, 21, 22),
(14, 23, 19),
(18, 24, 16),
(14, 25, 26),
(27, 28, 29),
(25, 30, 26),
(28, 31, 32),
(33, 19, 23),
(31, 34, 35),
(23, 14, 26),
(34, 36, 37),
(25, 38, 30),
(36, 39, 40),
(30, 38, 20),
(39, 41, 42),
(22, 30, 20),
(39, 42, 40),
(20, 12, 21),
(43, 21, 12),
(13, 44, 12),
(45, 46, 47),
(44, 43, 12),
(45, 47, 48),
(5, 13, 3),
(45, 48, 49),
(36, 40, 37),
(49, 48, 50),
(37, 51, 34),
(49, 50, 52),
(51, 53, 34),
(52, 50, 5),
(53, 54, 34),
(55, 52, 5),
(34, 54, 35),
(56, 57, 58),
(31, 35, 59),
(56, 58, 60),
(31, 59, 61),
(56, 60, 62),
(63, 64, 65),
(62, 60, 66),
(67, 63, 68),
(62, 66, 69),
(64, 70, 71),
(66, 72, 69),
(70, 73, 74),
(66, 55, 72),
(73, 75, 74),
(55, 76, 72),
(77, 67, 68),
(72, 76, 78),
(70, 74, 71),
(79, 80, 81),
(64, 71, 65),
(80, 82, 81),
(63, 65, 68),
(80, 83, 82),
(84, 77, 85),
(82, 83, 86),
(77, 68, 85),
(83, 87, 86),
(84, 85, 88),
(86, 87, 89),
(61, 84, 31),
(89, 87, 72),
(84, 88, 31),
(89, 72, 78),
(31, 88, 32),
(55, 5, 76),
(28, 32, 90),
(76, 4, 91),
(28, 92, 93),
(91, 4, 94),
(90, 95, 28),
(94, 4, 96),
(95, 92, 28),
(96, 4, 97),
(28, 93, 98),
(97, 4, 10),
(28, 98, 29),
(76, 5, 4),
(27, 29, 99),
(100, 10, 9),
(101, 102, 103),
(104, 105, 106),
(102, 107, 108),
(109, 105, 110),
(111, 101, 112),
(113, 109, 110),
(114, 115, 116),
(117, 105, 109),
(99, 111, 118),
(119, 113, 110),
(120, 107, 102),
(104, 121, 105),
(116, 120, 114),
(121, 122, 123),
(120, 124, 107),
(123, 122, 125),
(126, 127, 128),
(129, 130, 131),
(127, 132, 133),
(134, 135, 136),
(137, 126, 138),
(135, 129, 136),
(127, 133, 128),
(136, 129, 139),
(126, 128, 138),
(139, 129, 131),
(137, 138, 140),
(130, 141, 131),
(137, 140, 124),
(131, 141, 142),
(124, 140, 107),
(141, 125, 142),
(120, 102, 114),
(125, 122, 142),
(102, 108, 103),
(121, 123, 105),
(101, 103, 112),
(105, 117, 106),
(111, 112, 118),
(106, 117, 143),
(27, 99, 16),
(143, 117, 144),
(99, 118, 145),
(146, 147, 144),
(99, 145, 148),
(146, 149, 147),
(99, 148, 16),
(2, 106, 0),
(24, 27, 16),
(150, 151, 152),
(100, 9, 16),
(153, 154, 155),
(149, 100, 156),
(157, 158, 159),
(160, 2, 1),
(158, 155, 159),
(100, 16, 156),
(158, 153, 155),
(149, 156, 147),
(154, 161, 155),
(162, 163, 160),
(154, 150, 161),
(163, 151, 160),
(161, 150, 152),
(144, 147, 143),
(143, 0, 106),
(1, 162, 160),
(151, 163, 152),
)



In [17]:

    
def lines(triangle):
    t = sorted(triangle)
    return [(t[0], t[1]), (t[0], t[2]), (t[1], t[2])]



In [18]:

    
hull = set()
for triangle in triangles:
    for line in lines(triangle):
        if line in hull:
            hull.remove(line)
        else:
            hull.add(line)



In [19]:

    
hull









    Out[19]:





{(0, 1),
 (0, 143),
 (1, 162),
 (2, 106),
 (2, 160),
 (3, 4),
 (3, 12),
 (4, 9),
 (5, 13),
 (5, 50),
 (6, 7),
 (6, 11),
 (7, 8),
 (8, 14),
 (9, 15),
 (10, 97),
 (10, 100),
 (11, 17),
 (12, 20),
 (13, 44),
 (14, 25),
 (15, 18),
 (16, 148),
 (16, 156),
 (17, 19),
 (18, 24),
 (19, 33),
 (20, 38),
 (21, 22),
 (21, 43),
 (22, 30),
 (23, 26),
 (23, 33),
 (24, 27),
 (25, 38),
 (26, 30),
 (27, 28),
 (28, 31),
 (29, 98),
 (29, 99),
 (31, 34),
 (32, 88),
 (32, 90),
 (34, 36),
 (35, 54),
 (35, 59),
 (36, 39),
 (37, 40),
 (37, 51),
 (39, 41),
 (40, 42),
 (41, 42),
 (43, 44),
 (45, 46),
 (45, 49),
 (46, 47),
 (47, 48),
 (48, 50),
 (49, 52),
 (51, 53),
 (52, 55),
 (53, 54),
 (55, 66),
 (56, 57),
 (56, 62),
 (57, 58),
 (58, 60),
 (59, 61),
 (60, 66),
 (61, 84),
 (62, 69),
 (63, 64),
 (63, 67),
 (64, 70),
 (65, 68),
 (65, 71),
 (67, 77),
 (68, 85),
 (69, 72),
 (70, 73),
 (71, 74),
 (72, 87),
 (73, 75),
 (74, 75),
 (76, 78),
 (76, 91),
 (77, 84),
 (78, 89),
 (79, 80),
 (79, 81),
 (80, 83),
 (81, 82),
 (82, 86),
 (83, 87),
 (85, 88),
 (86, 89),
 (90, 95),
 (91, 94),
 (92, 93),
 (92, 95),
 (93, 98),
 (94, 96),
 (96, 97),
 (99, 111),
 (100, 149),
 (101, 102),
 (101, 111),
 (102, 114),
 (103, 108),
 (103, 112),
 (104, 106),
 (104, 121),
 (105, 110),
 (105, 123),
 (107, 108),
 (107, 140),
 (109, 113),
 (109, 117),
 (110, 119),
 (112, 118),
 (113, 119),
 (114, 115),
 (115, 116),
 (116, 120),
 (117, 144),
 (118, 145),
 (120, 124),
 (121, 122),
 (122, 142),
 (123, 125),
 (124, 137),
 (125, 141),
 (126, 127),
 (126, 137),
 (127, 132),
 (128, 133),
 (128, 138),
 (129, 130),
 (129, 135),
 (130, 141),
 (131, 139),
 (131, 142),
 (132, 133),
 (134, 135),
 (134, 136),
 (136, 139),
 (138, 140),
 (143, 147),
 (144, 146),
 (145, 148),
 (146, 149),
 (147, 156),
 (150, 151),
 (150, 154),
 (151, 160),
 (152, 161),
 (152, 163),
 (153, 154),
 (153, 158),
 (155, 159),
 (155, 161),
 (157, 158),
 (157, 159),
 (162, 163)}

Each point should be in the hull exactly twice.



In [20]:

    
points = dict()
for line in hull:
    for point in line:
        if point not in points:
            points[point] = 1
        else:
            points[point] += 1



In [21]:

    
for key in points.keys():
    assert points[key] == 2

Now check whether a ray originating from the point (x, y) in the east dirrection intersects a line segment with endpoints (ax, ay) and (bx, by). First we check whether y lies in the segment [ay, by]. The we observe whether x, a, b makes a left turn.



In [58]:

    
def intersects(p, a, b):
    p = (p[0] + random.random()*0.000001, p[1] + random.random()*0.000001)
    a, b = sorted([a, b], key=lambda p: p[1])
    if a[1] < p[1] and p[1] < b[1]:
        # Check the turn
        a = numpy.array([[1] + list(p),
                         [1] + list(a),
                         [1] + list(b)])
        return numpy.linalg.det(a) > 0
    return False



In [24]:

    
a = (1, 3)
b = (-3, 5)
sorted([a, b], key=lambda p: p[1])









    Out[24]:





[(1, 3), (-3, 5)]



In [47]:

    
intersects((0.00001, 0.00001), (1, -1), (-0.5, 1))









    Out[47]:





True



In [42]:

    
def count_intersections(point_coordines, lines, point):
    intersections = 0
    for line in lines:
        a, b = point_coordinates[line[0]], point_coordinates[line[1]]
        if intersects(point, a, b):
            intersections += 1
    return intersections



In [63]:

    
count_intersections(point_coordinates, hull, (0,0))









    Out[63]:





7



In [ ]: