1
$\begingroup$

Given the four line segments where $s= $start point $e = $end point.

$- s(1,1)e(5,1) - s(5,1)e(5,5) - s(5,5)e(5,0) - s(5,0)e(1,0)$

The shape is drawn

roughly like this

Which clearly has an open profile.

Is there a method to go about determining if a group of lines contains an open profile?

Note

  • The points are not always in order. (I just provide them this way for the sake of you guys.)
  • The start and end points are subject to being flipped. (line direction is irrelevant as long as the points are the same)

I am a software developer, not so much a mathematician so any help provided would be great.

$\endgroup$
9
  • $\begingroup$ Well, the first point is not equal to the last point. $\endgroup$
    – user856
    Commented Apr 25, 2019 at 18:55
  • $\begingroup$ There should be some more tags, but honestly I'm not sure which ones. $\endgroup$ Commented Apr 25, 2019 at 18:57
  • 1
    $\begingroup$ Couldn't you try to match start and end points - if there is a start point with no corresponding end point then you must have an open contour. Unless you are allowing for closure by intersection. Then you could do some tests, maybe looping through all lines to search for nontrivial intersections. If point is found, then see if it lies on another line. $\endgroup$ Commented Apr 25, 2019 at 18:57
  • $\begingroup$ @JacobCheverie Two things. The points are not always ordered like they were above. also, no the lines are actually segments. (i edited the question) $\endgroup$ Commented Apr 25, 2019 at 19:01
  • $\begingroup$ Scan for intersections, $n$ segments must have at least $n$ intersections to be closed. $\endgroup$ Commented Apr 25, 2019 at 19:04

1 Answer 1

0
$\begingroup$

You can use your collection of points to construct lines, one for each segment. Run a loop to find the intersection point of each line to each other. Obviously if the lines are parallel there will be none. When you find an intersection point, make sure that it is actually in the domain/range of both segments that it joins. If you have $n$ segments, you need at least $n$ intersections. This still allows for the possibility of having a "tail" but it will ensure at least one closed region. To avoid having a tail, you can do a slight perturbative check - when you have an intersection point, move out a small amount in each direction parallel to each intersecting line and see if the point falls on the segment and remains in the domain/range. Obviously one direction will (it'll be in the interior) but the other one shouldn't if you do not want tails.

EDIT: If you want to make it more robust, then you should adapt your algorithm as follows: If a line has $0$ intersection points that are within it's range, then do not include it in your segment count. The reason I say this is you can have many parallel lines and then a triangle. You will have many segments and only three intersections, implying you don't have $n$ for $n$. Ex:

---

---

---

---

---

---

$\Delta$

Would have 9 segments but only three intersections. Since the parallels do not intersect anything along their range, I would not count those toward the determination of closure (which you have with the triangle). Obviously you have a segment in space and do not have complete closure, but I do not fully understand your intent. Just coming up with possibilities.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .