Блог пользователя tom

Polygon and N lines
Автор tom, история, 9 лет назад, По-английски

Hello everyone,

Problem statement:

We have n > 2 pairs:  < line, side > , side . How can we check fast if they make non-empty polygon (or point)?

Cheers

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It looks like application of simplex algorithm

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

One approach is to sort lines by angle and then build convex hull by maintaiing stack.It might be tricky to correctly handle the case where resulting shape is single point.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

This is a well-studied problem in computational geometry, known as "Half-plane intersection".

https://web.stanford.edu/class/cs97si/09-computational-geometry.pdf

code for O(n^3) : http://ideone.com/8t36e9

I would really appreciate for any help in O(nlgn) algorithm.

→ Ответить