How to draw a line between a set of points while trying to satisfy a set of conditions?

user_9907909 0
Viewed 125

I have a polygon in closed (ends in the starting vertex) and simple (no holes inside) form, I'm trying to think of an algorithm that draws lines between vertices such that these conditions are met:

  1. The two sides of the line should have balanced number of vertices (at most 1 more vertex on one side is okay)
  2. When lines join each other they have to make up either an angle of 90 or 135 degrees.

Here's an example image, as you can see the blue lines are drawn such that the above conditions are met:

Sample

polygon computational-geometry math geometry
1 Answers

Hint:

If you project the vertices orthogonally on a line, the vertices of the "sides" of your shape that are well aligned with the projection direction will form clusters, and if you pick one of these clusters, the line that projects onto the median of the cluster will meet your balancing condition.

So a possible path of attack is to consider several initial directions and the ones rotated in the appropriate multiples of 90° and 135°, and study the clusters so obtained.

Needless to say, nothing simple. (But your problem isn't.)

user_11965490
Related