-2
$\begingroup$

There are $N$ regions which are numbered from $1$ to $N$. Each region is represented by a single simple polygon on the 2D plane. Simple polygon means the boundary of the polygon does not cross itself. You should not confuse simple polygon with convex polygon. There are no two regions share a common point.

Now given $Q$ queries,I have to find the polygon that contain a specific point. Note that a point on the boundary of the polygon is considered to be inside the polygon.

Now ,suppose if we have $N=2$ which can be as large as $10^6$ in input.and suppose the two regions coordinates are given as follow:-

Region 1 : $4$ (show number of coordinates pair)

$(1,4),(1,7),(7,7),(7,4)$

Region 2 : $3$

$(1,1),(5,3),(7,1)$

Now ,suppose we have $3$ queries :

$(2,3),(3,6),(6,2)$

We can clearly see first one is not in any of the regions second is in first region and third is in third region.

How to solve this problem if I have large number of queries of order $10^6$ and provided that $3 ≤$ total coordinate pairs for each polygon $≤ 300,000$ and all coordinates are non-negative integer which do not exceed $10^9$.

$\endgroup$

closed as off-topic by David White, Ramiro de la Vega, Dmitri Pavlov, Todd Trimble Nov 9 '13 at 21:14

  • This question does not appear to be about research level mathematics within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Smells like a Project Euler problem. $\endgroup$ – Gerry Myerson Nov 8 '13 at 22:59
  • $\begingroup$ Which problem..?Tell me plz... $\endgroup$ – hackerrrr Nov 9 '13 at 10:11
  • $\begingroup$ I didn't have a specific one in mind. I meant, it smells like the kind of problem that they use at Project Euler, especially with your request for computer code. $\endgroup$ – Gerry Myerson Nov 9 '13 at 10:17
  • 3
    $\begingroup$ From the net? URL, please? $\endgroup$ – Gerry Myerson Nov 9 '13 at 11:11
  • 7
    $\begingroup$ Flagging to close: the comments show the OP got this problem from somewhere and refuses to divulge the source. This is a dangerous precedent. I'm sure none of us want to be responsible for MO being used to cheat. $\endgroup$ – David White Nov 9 '13 at 18:36
7
$\begingroup$

The most practical method is to partition your polygon into trapezoids, and use Seidel's randomized point location algorithm:
   Trapezoid Decomp
There is a high-level description in Wikipedia here. You can find more detailed explanations in many locations, including Section 7.11.4 of Computational Geometry in C. And Seidel's original paper is quite readable:

Seidel, Raimund. "A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons." Computational Geometry 1.1 (1991): 51-64. (Journal link)

From the Abstract:

"As a by-product our algorithm creates a search structure of expected linear size that allows point location queries in the resulting trapezoidation in logarithmic expected time."

(Added.) You may find a working Java applet here.

$\endgroup$
  • $\begingroup$ Is it applicable to polygons in 2D..? $\endgroup$ – hackerrrr Nov 8 '13 at 13:19
  • $\begingroup$ Yes, 2D. That's what you specified in your question. $\endgroup$ – Joseph O'Rourke Nov 8 '13 at 13:20
  • $\begingroup$ K...What is its time complexity(in terms of big Oh notations to check for particular point).? $\endgroup$ – hackerrrr Nov 8 '13 at 13:24
  • $\begingroup$ $O(\log n)$, for a total of $n$ vertices. I added a quote from the abstract. $\endgroup$ – Joseph O'Rourke Nov 8 '13 at 13:29
  • 2
    $\begingroup$ hackerrrr: after this very helpful and detailed reply from Joseph O'Rourke, you might consider officially accepting it as the answer to your question. You should see a check mark next to his answer that you can click. Please note that the MO software will periodically recycle questions with unaccepted answers to the front page, which we don't want. (Also, 2 points are added to your reputation each time you officially accept an answer.) $\endgroup$ – Todd Trimble Nov 9 '13 at 13:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.