2
$\begingroup$

In computational geometry, is there any algorithm to find all vertices that are inside of a shape?

  • All vertices of graph has $x$- and $y$-coordinates
  • Shape is a set of points with $x$- and $y$-coordinates (unicyclic graph)
  • I need a fast algorithm. I am trying to avoid iterating over all vertices

Example:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! My first reaction is, what a beautiful illustration! Then I wonder, is the point at the low left corner inside or outside or part of the shape? Wait, what is a shape? "a set of points with x and y". Hmm, I guess, points must mean vertices. What is "x" and "y"? Hmm, it must mean two-dimensional coordinates. Why are there parentheses enclosing unicycle? So "a set of points with x and y" means unicycle? That would be a new definition of unicycle. The example should illustrate "all vertices that are inside of a shape". Have I seen "all vertices" and which is "a shape"? $\endgroup$ – Apass.Jack Oct 23 '18 at 22:12
  • 1
    $\begingroup$ Then I looked at the answer. Aha, I had been so slow to understand. This question is about deciding, on a 2D plane, whether a point in a polygon or not. Thanks to Juho's answer, now I understand the question! $\endgroup$ – Apass.Jack Oct 23 '18 at 22:17
2
$\begingroup$

It seems to me that the problem is not about graph theory, but computational geometry. Phrased slightly differently, your input is a set of two-dimensional points $P$ (corresponding to the coordinates of the vertices of some graph drawing) and a polygon $Q$. The task to determine a subset $P'$ of the points $P$ that are contained within $Q$.

One possible algorithm is to iterate over each point $p$ in $P$, and check whether $p$ is inside $Q$. This classic point in polygon problem has many simple and efficient algorithms.

$\endgroup$
  • $\begingroup$ That is the point! I'm trying to avoid iterating over all vertices. I'm thinking to start search from a given point $v$ $\endgroup$ – Andrey Oct 23 '18 at 22:24
  • 1
    $\begingroup$ @Andrey OK. It would be good to state in your original question what you already know to get more focused answer. If you already knew there was an algorithm, your question could have been "is there a faster algorithm than ..." instead of "is there an algorithm?". Perhaps one way to speed this up in practice could be to get the center point of $Q$, get all neighbors of it at a suitable distance $d$, and perform the point-in-polygon check only for those. There is a lot of work on data structures that give you efficient nearest neighbors. $\endgroup$ – Juho Oct 24 '18 at 6:59
  • $\begingroup$ Do you know if there is any algorithm in the literature that does this or something like that? Thank you $\endgroup$ – Andrey Oct 24 '18 at 10:44
  • $\begingroup$ @Andrey Can you be more specific? What exactly are your requirements for the algorithm (or what do you refer to with "this" or "something like that")? My answer contains an algorithm for the precise problem you stated. $\endgroup$ – Juho Oct 24 '18 at 11:22
  • $\begingroup$ I just want know if there is an approach in a scientific paper or books, that cover this kind of problem $\endgroup$ – Andrey Oct 24 '18 at 12:34
1
$\begingroup$

As said elsewhere, this is a problem in computational geometry. The graph structure is of no use.

There is a simple sweepline solution.

Sort the points and polygon vertices by ordinates. Now by a merge-like traversal, you an enumerate all the points in the slab between two successive vertices. By counting the number of edges on the left of every point, you can determine the insideness.

The number of operations will be $O(n\log n+m\log m)$ for the sorts ($n$ points and $m$ edges). Then assuming that the slabs contain on average $e$ edges (a small even number for ordinary polygons), the counting phase will cost like $O(e(n+m))$ operations.

With a little more sophistication, I suspect that this can be limited to $O(n\log m+m)$ in the worst case.

enter image description here

$\endgroup$
  • $\begingroup$ Good answer. The point is that I'm trying to avoid iterating over all vertices. This is because I'm working with a graph based on road networks. You and @juho gave me an idea. Draw a bounding box (BB) that cover the polygon with some padding. Find the closest point to the center of BB and apply a BFS algorithm. For each vertex check if is inside the polygon using Ray Casting. $\endgroup$ – Andrey Oct 24 '18 at 16:35
  • $\begingroup$ @Andrey: you don't seem to realize that the approach in my answer is much more efficient. In fact, virtually $O(1)$ per query point. $\endgroup$ – Yves Daoust Oct 24 '18 at 17:01
  • $\begingroup$ The problem is sort process. In best case a I can sort all vertices in $O(n \log n)$ $\endgroup$ – Andrey Oct 24 '18 at 17:06
  • 1
    $\begingroup$ @Andrey: if you prfer $O(nm)$, that's your choice. $\endgroup$ – Yves Daoust Oct 24 '18 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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