tom's blog

Polygon and N lines
By tom, history, 8 years ago, In English

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

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It looks like application of simplex algorithm

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply