Алгоритм целого числа обмоток с краевыми случаями - PullRequest
Новая
       16

Алгоритм целого числа обмоток с краевыми случаями

5 голосов
/ 10 декабря 2011

Мне нужно число обмоток замкнутого кусочно-линейного пути (например, многоугольника) вокруг точки, но, кроме того, я хочу определить, когда путь проходит через точку.По этой причине я удваиваю стандартное число обмоток.Для непересекающегося многоугольника с ориентацией против часовой стрелки значение будет равно:

  • 0, если точка находится за пределами многоугольника
  • 1, если точка находится на ребре или вершинемногоугольник
  • 2, если точка находится внутри многоугольника

И аналогично в других случаях.(РЕДАКТИРОВАТЬ: изображение нескольких примеров )

Каждый обнаруженный мной алгоритм терпит неудачу, когда точка находится на ребре или вершине.

Мое другое требование - этодолжен давать точно правильные результаты, когда все входные данные (т. е. координаты точки и вершины пути) являются целыми числами.Так что это в значительной степени исключает триггерные функции или квадратные корни, и деление должно быть использовано осторожно.

Я делаю , а не необходимо обрабатывать вырожденные пути, которые имеют две последовательные совпадающие точки, или 180- градусный поворот.

В любом случае, думаю, у меня есть решение.Тем не менее, это выглядит немного не элегантно, и я не уверен, что это правильно.(Я действительно запутался в том, что происходит, когда точка находится на вершине.) Вот это в python: 

def orient((x,y), (a0,b0), (a1,b1)):
    return cmp((a1-a0)*y + (b0-b1)*x + a0*b1-a1*b0, 0)
def windingnumber(p0, ps):
    w, h = 0, [cmp(p, p0) for p in ps]
    for j in range(len(ps)):
        i, k = (j-1)%len(ps), (j+1)%len(ps)
        if h[j] * h[k] == -1:
            w += orient(p0, ps[j], ps[k])
        elif h[j] == 0 and h[i] == h[k]:
            w += orient(ps[k], ps[i], ps[j])
    return w

Ссылка на версию с комментариями и юнит-тестами.

Мне нужна ссылка на правильный алгоритм, или какое-то подтверждение того, что мой алгоритм правильный, или тестовый случай, в котором мой алгоритм терпит неудачу.Спасибо!

1 Ответ

3 голосов
/ 10 декабря 2011

Проблема в том, что ваше предположение неверно.

Число обмоток не определено для точек на контуре. (Интеграл не очень хорошо определен, в частности).

Если вы идете по одному и тому же пути дважды, вы получите двойное число обмоток. Таким образом, если ваше предположение, что число будет равно 1, если точка на счетчике было истинным, то это фактически означало бы, что число обмоток, если вы идете один раз, равно 1/2, но это явно неверно, потому что число обмоток всегда целое число.

...