I'm assuming you've already ordered the vertices as you describe above, and that they indeed define a convex polygon.
Each vertex defines a horizontal line. For V vertices, then, you will have a set of V lines. Discard any line that meets one of the following criteria:
- The vertex or vertices defining that line has/have the highest or lowest Y component (if one vertex, that line intersects the polygon only at that point; if two, that line coincides with a polygon edge)
- If two vertices have equal Y coordinates otherwise, keep only one of those lines (it's duplicated).
The result will resemble a "banding" of the polygon.
Each horizontal line intersects the polygon at two points. One is its defining vertex. The other is either another vertex, or a point on a segment defined by two vertices. You can determine which is the case easily enough - just simple comparison of Y coords. The coordinates of the intersection with a segment is also easy math, which I leave to you.
Each intersection defines a vertical segment. The segment is contained within the polygon (if it coincides with an edge, you can discard it), and the other end meets either another horizontal line, or the edge of the polygon if that edge is itself horizontal. Determining the case is again a matter of mere comparison of coords. Finally, there may be 0-2 additional vertical segments, defined by the vertices with the highest and/or lowest Y coords, if there is only one of either.
The resulting diagram now shows each band with a right triangle trimmed off each end if possible. Each triangle should meet your criteria. The leftover regions are rectangles; draw an arbitrary diagonal to split each into two more right triangles meeting your criteria.
You're done.