Algorithm to find polygon that encloses a point - Only lines are defined

1
votes

I have a 2D drawing with many straight lines. All those lines are mathematically known. And they are independent of the others.

You can consider I know start and end point of each line and I can make them intersect to find all intersection points. (In detail, they are in Autocad, but I can only work via code. So, I want an Algorythm more than an Autocad solution, although Autocad solution is welcome as well).

The problem is: given a point (anywhere), I want to find the smaller polygon that contains it. That polygon would be formed by the nearest lines.

Details:

I have no declared polygons. Just lines. Any number of lines, any size, any position. And a given point.

Those lines may form one polygon, many or none. So there's no rule to what the polygons looks like. Any number of sides, no regularity. (The points that form the polygons are found by intersecting the lines. And the lines are finite, if they don't intersect, they don't form a polygon.)

My answer is the smallest polygon possible containing a given point.

2
algorithmlinespolygonspoint-in-polygonautocad-plugin
What defines the polygon? Are you guaranteed that the lines given connect to form a complete polygon? Are you assuming that the polygon is a quadrilateral? Or will the solution be more akin to a convex hull? – Sildoreth
Any number of lines, any size, any position. Given point. Polygon is the smallest one that can be formed with those lines containing the point inside. There are only two possible results: the polygon or nothing (in case lines don't enclose the point) – Daniel Möller
Could you maybe include a picture or set of pictures showing what are valid solutions and what are not? For instance... Can the solution polygon have sides that intersect any of the given lines? If one of the given lines is part of the solution, does it have to BE an edge of the solution polygon, or can just one of its endpoints be used as a vertex of the solution? – Sildoreth
Wait a moment. I may have been viewing this the wrong way. Is it that all the edges of the solution polygon must be colinear with line segments that were given? But the edges can be longer or shorter than the given line segments? – Sildoreth
Yes. Imagine a tic-tac-toe, for a very simple example. Those 4 lines form one polygon, wich is the center square. If my given point is inside that square, I want that square. If given point is elsewhere, there's no polygon containing it. That's why I said I can find all line intersections if needed (because the intersections are the points forming the polygon). – Daniel Möller

2 Answers

2
votes

Okay, I've been pondering this for a while, and I have formulated a backtracking algorithm that I believe will work. The idea is that you will attempt to build a polygon in a counter-clockwise fashion. And we will set up the problem such that the first polygon we find will be the smallest. That way, we don't have to find all of them.

Algorithm:

  1. Sort the line segments in order of how close they are to the target point.
    • Henceforth whenever you need to loop over the lines, loop over them in this sorted order
    • Treat the line segments as infinite lines when calculating their distance from the target point. point/line distance
  2. Perform Step 3 with the closest line segment, using the 2nd intersection point along the line in the "counter-clockwise" direction
    • Take "counter-clockwise" to mean the direction that puts the target point on the left side of the line.
    • NOTE: the 1st intersection point is hopefully the place where we will end up once we've worked our way around the target point

  3. On the newly-found line...

    A. Loop over all of the other lines that are not already part of the shape you are building, finding their intersection points with this line
    B. Sort the intersection points counter-clockwise with respect to the target point.
    counter-clockwise sorting

  4. Find the next intersection point counter-clockwise on the current line. If this is the first point we're checking on this line, then the "next" point is the one after the intersection point that brought us to this line.

    A. If there is no such point (this might mean that we've already checked all of the points on the current line), then the current candidate solution is infeasible...

    • Backtrack to the previous line and repeat Step 4 with the next point on that line.
    • If there is no previous line (i.e., you're on the line where you started the shape), Backtrack and do Step 2 with the next-closest line, starting a new shape.

    B. If the line that forms the intersection point does not have the target point on it's left side (counter-clockwise), then the polygon it would form does not enclose the target point. Repeat Step 4 for the current line with its next point.
    C. If the line that forms the intersection point is the line you started with, then we have found the solution
    D. If none of the above is true, do Step 3 for the line that formed the intersection point.

Optimizations:

  1. If there are fewer than 3 lines, there is no solution. Don't do any work.
  2. You may want to cache the intersection points when you find them so that you don't have to recalculate them
    • If you choose to do this, I recommend using a 2D array
  3. I recommend throwing out lines when you know that they aren't part of the solution.
    • Example: if you already tried the line closest to the target point, but it didn't lead to a solution, it doesn't make sense to include that line when finding intersection points on other lines.

Remarks:

  • This algorithm will be easiest to implement recursively.
  • You will have to decide what to do if the target point is on one of the lines
1
votes

I believe the following algorithm will work:

  1. If there are fewer than 3 lines, quit. There is no solution.
  2. Determine the line that is nearest to the target point. This line is guaranteed to be part of the solution.
  3. Let P1 be the the perpendicular projection of the target point on L1.
  4. Find the two intersection points of the other lines with L1 that are nearest to P1 and on opposite sides of it. These two points are guaranteed to be part of the solution.
    • Lets call these points P2 & P3, and call the lines L2 and L3
    • If there are no such points, there is no solution.
  5. Find the nearest point on each of L2 and L3 that are closest to P2 & P3 respectively and are on the same side of L1 as the target point.
  6. Repeat steps 4 and 5 until:
    • The line found coming from both directions is the same line
    • The intersection point found coming from both directions is the same point
    • There are no points to be found that match the criteria. This means there is no solution.