Polygon division method and apparatus

A polygon division apparatus comprising:

• apex judging means for judging whether each apex of a polygon is a concave apex or a convex apex;
• apex number holding means for holding a total number of apexes of said polygon;
• first convex apex selection means for selecting one convex apex;
• triangle judging means for judging whether or not another apex is present 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 for cutting said triangle from said polygon, for decrementing said total 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, indicating that no apex is present in said interior of said triangle;
• and
• second convex apex selection means for selecting a different convex apex based on a judgement result, from said triangle judging means, indicating that another apex is present in said interior of said triangle.

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 total number of apexes of the polygon;
• detecting apexes which overlap with one another;
• selecting one convex apex of the polygon from apexes other than apexes detected as overlapping to obtain a selected apex;
• judging whether or not another apex is present in an interior of a triangle which is formed by two sides that unite at the selected convex apex and a line segment that interconnects ends of the two 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 the judgment in said step of judging whether or not another apex is present is that no apex is present in the interior of the triangle;
• selecting a different convex apex from among the apexes other than the apexes detected as overlapping when the judgment in said step of judging whether or not another apex is present is that another apex is present in the interior of the triangle;
• when division of the polygon is not completed by selecting convex apexes other than apexes detected as overlapping, selecting an overlapping convex apex which does not include any concave apex therein to obtain a selected overlapping convex apex, judging whether or not another apex is present in an interior of a triangle which is formed by two sides that unite at the selected overlapping convex apex and a line segment that interconnects ends of the two sides and cutting the triangle from the polygon when it is possible to cut the triangle from the polygon;
• and
• repeating the selecting step for selecting another convex apex and the judging step for judging whether or not another apex is present in the interior of the triangle, or the apex judging step, the detection step for overlap apexes, the convex apex selection step and the judging step for judging whether or not another apex is present in the interior of the triangle for the remaining polygon.

A polygon division apparatus comprising:

• apex judging means for judging whether each apex of a polygon is a concave apex or a convex apex;
• apex number holding means for holding a total number of apexes of said polygon;
• detection means for detecting overlap apexes which overlap one another;
• first convex apex selection means for selecting one convex apex of the polygon, other than one of the overlap apexes;
• triangle judging means for judging whether or not another apex is present 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 for cutting said triangle from said polygon, for decrementing said total 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, indicating that no apex is present in said interior of said triangle;
• second convex apex selection means for selecting a different convex apex based on a judgement result, from said triangle judging means, indicating that another apex is present in said interior of said triangle;
• and
• overlap apex selection means for selecting a convex apex which includes no concave apexes and for operating a judging operation by said triangle judging means when convex apexes other than said overlap convex apexes have been sequentially selected and said polygon remains incompletely divided.

A polygon division method comprising the steps of:

• judging whether or not an apex, which has varied from a convex apex to a concave apex during every triangle cutting operation to a polygon, is present;
• continuing division of the polygon when judging that no apex which has varied from a convex apex to a concave apex is present;
• and
• terminating division of the polygon when judging that an apex which has varied from a convex apex to a concave apex is present.

A polygon division apparatus comprising:

• apex judging means for judging whether each apex of a polygon is a concave apex or a concave apex;
• apex number holding means for holding a total number of apexes of said polygon;
• convex apex selection means for selecting one convex apex from among all apexes of said polygon;
• triangle judging means for judging whether or not another apex is present in an interior of a triangle which is formed by two sides uniting at a convex apex selected b said convex apex selection means and a line segment interconnecting ends of said sides;
• triangle cutting means for cutting said triangle from said polygon and for decrementing said total number of apexes of said polygon based on the judgement results, from said triangle judging means, indicating that no apex is present in said interior of said triangle;
• varied apex judging means for judging whether or not an apex has varied from a convex apex to a concave apex during every cutting of a triangle from said polygon;
• first repetition control means for repetitively operating said apex judging means, said apex number holding means, said convex apex selection means and said triangle judging means 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, indicating that no apex is present which has varied from a convex apex to a concave apex;
• second repetition control means for repetitively operating said convex apex selection means and said triangle judging means based on a judgement result, from said triangle judging means, indicating that another apex is present in an interior of said triangle of said polygon;
• and
• terminating means for terminating division of said polygon based on a judgement result, from said varied apex judging means, indicating that an apex which has varied from a convex apex to a concave apex is present.