Polygon division method and apparatus

Claim 2

A polygon division apparatus comprising; apex judging means (2) for judging whether each apex of a polygon is a concave apex or a convex apex; apex number holding means (3) for holding a number of apexes of said polygon; first convex apex selection means (4) for selecting one convex apex; triangle judging means (5, 6) for judging whether or not another apex exists in an interior of a triangle which is formed by two sides uniting at a convex apex selected by said first convex apex selection means (4) and a line segment interconnecting ends of said sides; triangle cutting means (7, 8, 9, 11) for cutting said triangle from said polygon, for decrementing said number of apexes of said polygon and for selecting another convex apex on a remaining polygon formed by cutting said triangle, based on a judgement result from said triangle judging means (6) indicating that no apex exists in said interior of said triangle; and second convex apex selection means (4) for selecting a different convex apex based on a judgement result from said triangle judging means (6) indicating that another apex exists in said interior of said triangle.

Claim 3

A polygon division method comprising the steps of; judging for all apexes of a polygon whether each apex is a concave apex or a convex apex; obtaining a number of apexes of the polygon, detecting apexes which overlap one another; selecting one convex apex of the polygon other than the overlapping apexes thereof; judging whether or not another apex exists in an interior of a triangle of the polygon which triangle is formed by two sides uniting at the selected convex apex and a line segment interconnecting ends of the sides; cutting the triangle from the polygon, decrementing the number of apexes, and selecting another convex apex on a remaining polygon formed by cutting the triangle, when it is judged that no apex exists in the interior of the triangle; selecting a different convex apex from the apexes other than the overlapping apexes when it is judged that another apex exists in the interior of the triangle; when division of the polygon is not completed by selecting of the convex apexes other than the overlapping apexes, selecting an overlapping convex apex which does not include any concave apex therein, judging whether or not another apex exists in an interior a triangle which is formed by two sides uniting at the selected overlapping convex apex and a line segment interconnecting ends of the sides and cutting the triangle from the polygon when it is possible to cut the triangle from the polygon; and repeating the selection operation for selecting another convex apex and the judging operation for judging whether or not another apex exists in the interior of the triangle, or the apex judging operation, the detection operation for overlap apexes, the convex apex selection operation and the judging operation for judging whether or not another apex exists in the interior of the triangle for the remaining polygon.

Claim 4

A polygon division apparatus comprising; apex judging means (2) for judging whether each apex of a polygon is a concave apex or a convex apex; apex number holding means (3) for holding a number of apexes of said polygon; detection means (12) for detecting overlap apexes which overlap one another; first convex apex selection means (4a) for selecting one convex apex of the polygon other than the overlap apexes; triangle judging means (5, 6) for judging whether or not another apex exists in an interior of a triangle which is formed by two sides uniting at a convex apex selected by said first convex apex selection means and a line segment interconnecting ends of said sides; triangle cutting means (7, 8, 9, 11) for cutting said triangle from said polygon, for decrementing said number of apexes of said polygon, and for selecting another convex apex on a remaining polygon formed by cutting said triangle based on a judgement result from said triangle judging means (6) indicating that no apex exists in said interior of said triangle; second convex apex selection means (4a) for selecting a different convex apex based on a judgement result from said triangle judging means (6) indicating that another apex exists in said interior of said triangle; and overlap apex selection means (4b) for selecting a convex apex which includes no concave apexes therein and for operating a judging operation by said triangle judging means (6) when convex apexes other than said overlapping convex apexes have been sequentially selected and said polygon remains incompletely divided.

Claim 5

A polygon division method comprising the steps of; judging whether or not an apex exists which has varied from a convex apex to a concave apex at every operation of cutting of a triangle from a polygon; continuing division of the polygon when it is judged that no apex exists which has varied from a convex apex to a concave apex; and forcibly terminating division of the polygon when it is judged that an apex exists which has varied from a convex apex to a concave apex.

Claim 6

A polygon division apparatus comprising; apex judging means (2) for judging whether each apex of a polygon is a concave apex or a convex apex; apex number holding means (3) for holding a number of apexes of said polygon; convex apex selection means (4a, 4b) for selecting one convex apex among all apexes of said polygon; triangle judging means (5, 6) for judging whether or not another apex exists in an interior of a triangle which is formed by two sides uniting at a convex apex selected by said convex apex selection means (4a) and a line segment interconnecting ends of said sides; triangle cutting means (7, 9) for cutting said triangle from said polygon and for decrementing said number of apexes of said polygon based on the judgement result from said triangle judging means (6) indicating that no apex exists in said interior of said triangle; varied apex judging means (14) for judging whether or not an apex has varied from a convex apex to a concave apex at every cutting of a triangle from said polygon; first repetition control means (11, 13) for repetitively operating said apex judging means (2), said apex number holding means (3), said convex apex selection means (4a) and said triangle judging means (5, 6) for a remaining polygon which is formed by cutting said triangle from said polygon based on a judgement result from said varied apex judging means (14) indicating that no apex exists which has varied from a convex apex to a concave apex; second repetition control means (11, 13) for repetitively operating said convex apex selection means (4a, 4b) and said triangle judging means (5, 6) based on a judgement result from said triangle judging means (5, 6) indicating that another apex exists in an interior of said triangle of said polygon; and forcibly terminating means (15) for forcibly terminating division of said polygon based on a judgement result from said varied apex judging means (14) indicating that an apex exists which has varied from a convex apex to a concave apex.