1
$\begingroup$

I have a set of piecewise-linear curves (i.e. "points connected by line segments") as shown in the figure below:

enter image description here

additional points are added on the borders (drawn in red) "closing" the open regions of the figure. In fact, the figure can be any plot with some closed piecewise-linear shapes on it (i.e. there are no lines or curves with open ends).

I need to find some (one is enough, but more is OK too if it doesn't significantly slow down the algorithm) testing points inside of EVERY closed contour (see e.g. the figure above). By adding the border lines all "open" regions become closed ones, so the whole figure consists of simple "closed" regions. However, this condition is not necessary in general.

The test points should also lie on some minimal distance from the boundary (this condition assures the meaningful results).

I also have a possible solution to the problem:

1) By a curve intersection algorithm all intersection points of any curve (incl. the "borders") with any other curve were found. By this procedure every curve was divided into segments by the intersection points lying on the curve.

2) Next, two normals are drawn from some linear piece of a segment to "infinity" (i.e. the length of the normals is big enough to place their endpoints outside of the plotted/bounded region).

3) The two nearest intersections are found, and the two test points are chosen at the half of the distance between the normals' origins and their two nearest intersections. If the distance is too small - choose another piece of the segment and repeat (2) and (3). This should work since every curve is a border of some closed contour.

4) repeat (2) and (3) for all segments found in (1)

The proposed solution doesn't require that the closed contours are "detected" (i.e. that they are available as ordered lists of points). However, it can be assumed that the closed contours are "known" (their detection was discussed e.g. in detect closed shapes formed by points)

The main concern about the proposed solution is that it might be not quite efficient, because we need first NN/2 intersection checks (since the curves are checked pair by pair) in order to find all intersections. N is the number of curves. And then we need at least MN/2 intersection checks in order to analyze every segment. M is the number of curve segments.

However, in this problem the speed IS an issue.

$\endgroup$
  • $\begingroup$ mathoverflow.net/questions/56655/get-a-point-inside-a-polygon this topic seems to be helpful, esp. if the closed contours are "detected". However, the proposed solution (Subject 2.06) exaflop.org/docs/cgafaq/… is not quite clear. E.g. what is the convex vertex? The algorithm itself is also a bit unclear for me (although its general idea seems to be clear..) Unfortunatelly, commenting on mathoverflow.net requires 50 reputation that needs some time to earn. $\endgroup$ – Omicron_Persei_11 Feb 7 '14 at 10:04
  • 1
    $\begingroup$ My guess is that a convex vertex is a vertex on the convex hull of the polygon. One way to find one is to compute the convex hull, though that might be wasteful. $\endgroup$ – Yuval Filmus Feb 9 '14 at 16:00

Your Answer

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

Browse other questions tagged or ask your own question.