4

I have a graph G composed of edges {E} and vertices {V}. The vertices in {V} are expressed in 2-D coordinates. The graph is planar, it means that no two edges intersect.

Graph G has some loops, and let's say a point is inside the graph if it falls in one of the loops of G. A loop example may be A---B---C---A, where A, B and C are vertices and --- is an edge.

Now given a point (x, y), how can I determine whether it is is inside the graph or outside? What is the best way or the simplest way of doing so?

I am using Python, if that helps.

UPDATE: Yes, all the edges are straight lines.

sbeliakov
  • 2,169
  • 1
  • 20
  • 37
  • How are loops represented? If they are circles, you're better of asking how to detect if a point is inside a circle. – loopbackbee Oct 18 '13 at 08:51
  • @mavErick: Are all the edges straight lines? – Ankur Ankan Oct 18 '13 at 08:55
  • 1
    @HighPerformanceMark He perfectly defined what he means by "inside/outside" a graph in the question (assuming (v1,v2) is a straight line between them) – amit Oct 18 '13 at 08:56
  • I meant the *geometric* representation. A graph is a mathematical concept, as are vertices, edges and loops. It makes no sense asking how to detect if a point is inside a graph / loop. If you're trying to solve a geometric problem, you should describe it as so. – loopbackbee Oct 18 '13 at 08:57
  • @AnkurAnkan Yes, all straight. –  Oct 18 '13 at 08:58
  • @mavErick your problem, then, is detecting whether a point is inside a polygon. There's [plenty of information available on that](http://en.wikipedia.org/wiki/Point_in_polygon) – loopbackbee Oct 18 '13 at 09:01
  • @goncalopp No, it was the problem is you looked inside a *specific* loop, you could have exponential number of loops - and you have no idea which of them to check against the point. – amit Oct 18 '13 at 09:02
  • @goncalopp I also realized that before, but the reason why I am reluctant to treat this as one problem of that type is that I only have the point coordinates and their connectivities now. So to do *detecting whether a point is inside a polygon* kinda requires me to find out all the polygons first... –  Oct 18 '13 at 09:04
  • @amit you're right, of course - but is there a better algorithm than simply checking all of them? – loopbackbee Oct 18 '13 at 09:06
  • @goncalopp Don't know, but this question is worth asking. Maybe someone can prove there is no way, or maybe someone can find a way to do it - until then, we shouldn't be close minded to it. – amit Oct 18 '13 at 09:07
  • Can the edges cross over each other? In other words, is the graph planar? – Peter de Rivaz Oct 18 '13 at 09:08
  • @mavErick Finding all the polygons is the same as [finding all the cycles](http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph) – loopbackbee Oct 18 '13 at 09:08
  • @PeterdeRivaz No crossings. –  Oct 18 '13 at 09:10

3 Answers3

2

@Peter de Rivaz offers a fundamental insight, albeit with no proof: the point is inside a loop iff it is inside the hull of formed by the outer vertices of the graph. We can prove this by proving:

  • Any point inside the hull is inside a loop
  • Any point outside the hull is not inside any loop

The first is easy to prove: any point inside the hull is inside a loop, because the hull itself is a loop.

The second can be proved by reductio ad absurdum. Very informally, for a point outside outside the hull to be inside a loop, there needs to be at least a vertex outside the hull, and for it to form a loop with at least two other vertices inside the loop, such that the point is inside that same loop. However, there can't be any vertices outside the loop, because, by definition, all vertices are inside it. Thus, by reductio ad absurdum, there are no points outside the hull that are inside any loop.

Now that we are sure we have a correct way to test what we want, we still need an algorithm that can tell whether a point is inside the hull. This may be accomplished through a simple extension of the ray casting algorithm.

Basically, we start with the list of all vertices, sorted by the vertical coordinate. Then, for each pair of successive vertices, we "create" a horizontal line that goes between them, and check what is the first and last edge that the line intersects. Those two edges are part of the hull. If the tested point is between any of these two edges, it will be inside the hull.

Here's a graphical representation of the first 3 iterations:

iteration 1 iteration 2 iteration 3

loopbackbee
  • 21,962
  • 10
  • 62
  • 97
1

As the graph is planar you can do this by tracing the outline of each connected set of vertices and then testing to see if your point is inside any of these polygons.

This picture illustrates the idea:

enter image description here

The red line is the polygon representing the outline of the left hand connected component, while the green line is the polygon representing the outline of the right hand component.

Your point will be inside a loop if and only if it is inside one of the outlines.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
0

First, I would find the set cycles (loops) in my graph. For this see this SO question Finding all cycles in undirected graphs

Then compute the set of maximal cycles i.e. those that are not included in another cycle (maybe you can do these first two steps at the same time).

Once you have the maximal cycles, this is a matter of detecting wether a point in within a polygon. Various methods exist, e.g. - draw a line and the number of edge intersection - sum of angles to the vertices of the polygon from the point (0° -> outside, 360° -> inside).

See How can I determine whether a 2D Point is within a Polygon?

François Legras
  • 308
  • 2
  • 12