Return to Answer

For the general polygonal area (not connected, not simply connected, possibly overlapping lines, self intersection allowed provided they happen at a vertex) the solution I came up with is:

1. sort all y values
2. for any pair of consecutive distinct y values $y_i < y_{i+1}$ compute the horizontal spans that the polygon is intercepting on the line

$$y={y_i + y_{i+1} \over 2}$$

The middle point of any non-empty span is inside the polygon and you can stop the search (note that by construction that point cannot be on an horizontal line). Care as usual must be taken for horizontal segments; for example by considering an edge $(x_a, y_a)-(x_b, y_b)$ intersecting the horizontal line if and only if

$${\rm min}(y_a, y_b) \le y \lt {\rm max}(y_a, y_b)$$

How the horizontal spans are constructed depends on the rule chosen for area definition (even-odd, non-zero winding, positive or negative winding). Note that in the general case (non-simple) polygon there may be no solution (consider the "triangle" built from three aligned points, no point in the plane is "inside").

Also, as usual for practical computer implementation, there can be problems when using floating point values where for example $y_{i} < y_{i+1}$ does NOT imply $y_{i} < {y_{i}+y_{i+1}\over 2} < y_{i+1}$ because, in a computer, the average of two distinct values can be equal to one of the values.

For the general polygonal area (not connected, not simply connected, possibly overlapping lines, self intersection allowed provided they happen at a vertex) the solution I came up with is:

1. sort all y values
2. for any pair of consecutive distinct y values $y_i < y_{i+1}$ compute the horizontal spans that the polygon is intercepting on the line

$$y={y_i + y_{i+1} \over 2}$$

The middle point of any non-empty span is inside the polygon and you can stop the search (note that by construction that point cannot be on an horizontal line). Care as usual must be taken for horizontal segments; for example by considering an edge $(x_a, y_a)-(x_b, y_b)$ intersecting the horizontal line if and only if

$${\rm min}(y_a, y_b) \le y \lt {\rm max}(y_a, y_b)$$

How the horizontal spans are constructed depends on the rule chosen for area definition (even-odd, non-zero winding, positive or negative winding). Note that in the general case (non-simple) polygon there may be no solution (consider the "triangle" built from three aligned points, no point in the plane is "inside").

Also, as usual for practical computer implementation, there can be problems when using floating point values where for example $y_{i} < y_{i+1}$ does NOT imply $y_{i} < {y_{i}+y_{i+1}\over 2} < y_{i+1}$ because, in a computer, the average of two distinct floating point values can be equal to one of the values.

For the general polygonal area (not connected, not simply connected, possibly overlapping lines, self intersection allowed provided they happen at a vertex) the solution I came up with is:

1. sort all y values
2. for any pair of consecutive distinct y values $y_i < y_{i+1}$ compute the horizontal spans that the polygon is intercepting on the line

$$y={y_i + y_{i+1} \over 2}$$

The middle point of any non-empty span is inside the polygon and you can stop the search (note that by construction that point cannot be on an horizontal line). Care as usual must be taken for horizontal segments; for example by considering an edge $(x_a, y_a)-(x_b, y_b)$ intersecting the horizontal line if and only if

$${\rm min}(y_a, y_b) \le y \lt {\rm max}(y_a, y_b)$$

How the horizontal spans are constructed depends on the rule chosen for area definition (even-odd, non-zero winding, positive or negative winding). Note that in the general case (non-simple) polygon there may be no solution (consider the "triangle" built from three aligned points, no point in the plane is "inside").

For the general polygonal area (not connected, not simply connected, possibly overlapping lines, self intersection allowed provided they happen at a vertex) the solution I came up with is:

1. sort all y values
2. for any pair of consecutive distinct y values $y_i < y_{i+1}$ compute the horizontal spans that the polygon is intercepting on the line

$$y={y_i + y_{i+1} \over 2}$$

The middle point of any non-empty span is inside the polygon and you can stop the search (note that by construction that point cannot be on an horizontal line). Care as usual must be taken for horizontal segments; for example by considering an edge $(x_a, y_a)-(x_b, y_b)$ intersecting the horizontal line if and only if

$${\rm min}(y_a, y_b) \le y \lt {\rm max}(y_a, y_b)$$

How the horizontal spans are constructed depends on the rule chosen for area definition (even-odd, non-zero winding, positive or negative winding). Note that in the general case (non-simple) polygon there may be no solution (consider the "triangle" built from three aligned points, no point in the plane is "inside").

Also, as usual for practical computer implementation, there can be problems when using floating point values where for example $y_{i} < y_{i+1}$ does NOT imply $y_{i} < {y_{i}+y_{i+1}\over 2} < y_{i+1}$ because, in a computer, the average of two distinct values can be equal to one of the values.

For the general polygonal area (not connected, not simply connected, possibly overlapping lines, self intersection allowed provided it happens at a vertex) the solution I came up with is:

1. sort all y values
2. for any pair of consecutive distinct y values $y_i < y_{i+1}$ compute the horizontal spans that the polygon is intercepting on the line

$$y={y_i + y_{i+1} \over 2}$$

The middle point of any non-empty span is inside the polygon and you can stop the search (note that by construction that point cannot be on an horizontal line). Care as usual must be taken for horizontal segments; for example by considering an edge $(x_a, y_a)-(x_b, y_b)$ intersecting the horizontal line if and only if

$${\rm min}(y_a, y_b) \le y \lt {\rm max}(y_a, y_b)$$

How the horizontal spans are constructed depends on the rule chosen for area definition (even-odd, non-zero winding, positive or negative winding). Note that in the general case (non-simple) polygon there may be no solution (consider the "triangle" built from three aligned points, no point in the plane is "inside").

For the general polygonal area (not connected, not simply connected, possibly overlapping lines, self intersection allowed provided they happen at a vertex) the solution I came up with is:

1. sort all y values
2. for any pair of consecutive distinct y values $y_i < y_{i+1}$ compute the horizontal spans that the polygon is intercepting on the line

$$y={y_i + y_{i+1} \over 2}$$

The middle point of any non-empty span is inside the polygon and you can stop the search (note that by construction that point cannot be on an horizontal line). Care as usual must be taken for horizontal segments; for example by considering an edge $(x_a, y_a)-(x_b, y_b)$ intersecting the horizontal line if and only if

$${\rm min}(y_a, y_b) \le y \lt {\rm max}(y_a, y_b)$$

How the horizontal spans are constructed depends on the rule chosen for area definition (even-odd, non-zero winding, positive or negative winding). Note that in the general case (non-simple) polygon there may be no solution (consider the "triangle" built from three aligned points, no point in the plane is "inside").