0

It's problem from the book:

"Computational Geometry: Algorithms and Applications", Springer-Verlag.

Given two simple and disjoint polygons P and Q, where P lies strictly to the left of Q, computes the first points on the polygons that will collide if P is translated horizontally and in the positive x-direction, or determines that they do not collide.

enter image description here

I have a quadratic solution, but it should be O((n+m) log(n+m))

Al-bambino
  • 51
  • 6

2 Answers2

0

Probably not the answer you are looking for, but the simple, quick and easy to develop solution would be to draw the polygons, fill them and do bitwise masking AND function to determine the bits that overlap on a bitmap.

Looping with increments of 1 bit on the x-scale and performing the AND masking test each iteration gives you the perfect contact point in exact pixels.

pixel perfect collision detection

Ratbyte Boss
  • 461
  • 4
  • 13
  • Yes, thanks for the answer but I'm looking for a more geometrical approach – Al-bambino Dec 15 '18 at 21:36
  • Trying all positions is horribly inefficient. If polygon filling is allowed (it is not, as this is a question in computational geometry), there is no need to do that. –  Dec 15 '18 at 23:02
0

Sort both polygons top to bottom and implement a sweepline process. The vertices are the event points. While sweeping, keep a trace of the rightmost edge of P and the leftmost edge of Q. You can draw horizontal segments in between, and keep the shortest of all.

enter image description here

  • Yes, the `log` looks like there is some sorting involved (that was a guess that I also made in my answer). Implementing this properly is probably not *that* hard, but might have some caveats, so I didn't try it yet. Maybe I'll extend my answer later with the sweepline approach that you proposed. A +1 until then. – Marco13 Dec 15 '18 at 23:20
  • @Marco13: this is a standard technique in CG. Can probably be implemented with a heap structure for the active list(s). –  Dec 15 '18 at 23:23
  • Sure, it is a common problem, and there are related questions like https://stackoverflow.com/q/18973808/3182664 or https://stackoverflow.com/q/3700983/3182664 . But usually, I appreciate *code* in answers, and the answers in the other questions are only linking to external resources. A [MCVE] with a solution here would be nice... – Marco13 Dec 15 '18 at 23:34
  • @Marco13: MCV examples are for questions posted by the OP. We are not a coding factory. And code alone gives no insight on a solution. It gives you a false feeling that the problem is solved, but does not allow you to verity the complexity claim. –  Dec 15 '18 at 23:40
  • When I'm looking for an answer here, I'm not looking for pointers into the web or vague sketches of ideas, but for *solutions*. That does not mean "code alone", but also explanations. The balance of the two, i.e. what it means *exactly*, is up to individual interpretations or preferences, so there's no need to argue about that. – Marco13 Dec 15 '18 at 23:42
  • @Marco13: if you post code, make sure that it is fully correct (which is very tricky here) and truly respects the O((n+m) log(n+m)) constraint. Otherwise you remain in the realm of sketches of ideas and clutter the Web with yet another harmful implementation. –  Dec 15 '18 at 23:49
  • Now that I think about it: I don't consider this answer as "useful" any more. – Marco13 Dec 15 '18 at 23:54
  • I see here that you coloured some of the edges totally, but some of them were partly coloured, what is the reason, how do you colour them and why? – Al-bambino Dec 18 '18 at 16:18
  • @Al-bambino: I only colored the horizontally visible parts. –  Dec 18 '18 at 17:36
  • @YvesDaoust I couldn't find some online materials, how do you find visible projections of the polygon? – Al-bambino Dec 19 '18 at 08:32
  • @Al-bambino; draw horizontals –  Dec 19 '18 at 10:00