How to detect if an object lies between two points

Question

Currently I am working on a minimum corridor length algorithm, and part of the setup involves coming up with a list of all adjacent points in the problem. Currently I have two arrays: one sorted with adjacent points on the x coordinate and the other list with the points on the y coordinate. Also, I am finding the adjacencies by simply looking at nearby points given the two lists, if the points have the same y (on the list sorted by x adjacent) then they lie on the same line. Similarly if they have the same x (on the y list) the lie on the same line.

For example, suppose we have the following room:

Then list with x-adjacent points will have the points in the following order: {v1, v2, v3, v4, v5, ... v21, v22} (they stay in the same order as they are labeled) Also, the list with y-adjacent points will be: {v22, v16, v14, v9, v4, v13, v8, v3, v21, ... v5, v1} (basically a reflection of the graph on y=x)

As mentioned I find adjacent points by looking at nearby points on the list. That works fine for most points, however it fails for the following edge case:

As the x-adjacent list will have {v1, v2, ... v6, v7 ... v11, v12} and my algorithm will detect v6 and v7 as adjacent points. How can detect that there is a room in between those two points? Note that I have the set of rectangles and points on their vertexes also available to me. Thanks in advance.

Answer 1

I would suggest abandoning your position-based approach, because there is no way to tell whether v6 and v7 in your last example are adjacent (i.e. connected) based solely on their position. Instead, make a graph indicating which points are connected to which other points: the points will be vertices of the graph, and you add an edge between each pair of vertices that are adjacent/connected.

To construct the graph, you could try this algorithm (just off the top of my head):

1. Create a graph with the given vertices and no edges
2. Group the vertices (points) by their x coordinate. Create a map of vertices to groups, or some other way to look up which group a given vertex is in.
3. For each group, create a disjoint set data structure with the vertices in that group.
4. Iterate through all the vertical edges of the rectangles, and for each edge, perform a union on the subsets corresponding to the two vertices at the ends of that edge.
5. Iterate through the groups, and for each group iterate through its subsets. For each subset, first sort the vertices in that subset by y coordinate, and add edges to the graph between pairs of consecutive vertices.

Then repeat steps 2-5 with the role of x and y coordinates switched (and using horizontal edges instead of vertical edges).

Naturally, this relies on the assumption that all edges (lines) are either horizontal or vertical.