Sure, here’s the translation: 将多边形形状分割 Java

huangapple go评论77阅读模式
英文:

Divide Polygon Shape Java

问题

我有一个简单的2D多边形,有4个点。

int[] x = {38, 100, 80, 18};
int[] y = {50, 50, 100, 100};

Polygon poly = new Polygon(x, y, 4);

上面的多边形只是一个示例。上面的多边形实际上可以是任何形状,只要多边形始终是凸形的,始终有4个点,并且是一个平行四边形。我需要将其分割成任意数量的部分,所有部分与较大的多边形成比例,只要数量是一个平方数。有没有简单的方法可以做到这一点?如果这很重要,我是在Jframe上使用Graphics。

英文:

I have a simple 2D polygon with 4 points.

    int[] x = {38, 100, 80, 18};
	int[] y = {50, 50, 100, 100};
	
	Polygon poly = new Polygon(x, y, 4);

The above polygon is just an example. The polygon above could really be anything as long as the polygon is always convex, always has 4 points, and is a parallelogram. I need to split it into any number of even parts, all proportional to the bigger polygon, as long as the number is a square number. Is there any simple way I can do this? I am using Graphics on a Jframe if that's important at all.

答案1

得分: 3

以下是已翻译的内容:

代码如下,适用于任何凸四边形。当初始四边形是平行四边形时,其结果子多边形也是“天然”的平行四边形,全部具有相同的大小,即它们是偶数大小。

由于所需的“parts”数必须是一个平方数,这意味着我们可以将四边形在水平和垂直方向上简单地分割为“partsPerSide = sqrt(parts)”。

当我们将四边形分割为多个部分时,可能会得到不精确的整数坐标。我们可以将该值四舍五入为整数,但是这样的话,这些片段的大小就不会完全相等。是否可以接受这种情况是个人的选择。从视觉上看,四舍五入是可以注意到的,因为直线不会是100%笔直的。

在下面的代码中,我们假设不接受四舍五入,即我们希望获得精确的均匀大小。如果可以接受四舍五入,请在末尾注释掉if (rounded != delta) throw new ArithmeticException()代码,然后使用所需的“partsPerSide”调用splitFourSided()

好了,下面是代码:

private static Polygon[][] splitFourSided(Polygon poly, int partsPerSide) {
    if (poly.npoints != 4)
        throw new IllegalArgumentException("Polygon must be 4-sided");
    if (partsPerSide <= 0)
        throw new IllegalArgumentException("There must be a positive number of parts per side");
    int[][] x = splitFourSided(poly.xpoints, partsPerSide);
    int[][] y = splitFourSided(poly.ypoints, partsPerSide);
    Polygon[][] pieces = new Polygon[partsPerSide][partsPerSide];
    for (int row = 0; row < partsPerSide; row++) {
        for (int col = 0; col < partsPerSide; col++) {
            pieces[row][col] = new Polygon(
                    new int[] { x[row][col], x[row][col+1], x[row+1][col+1], x[row+1][col] },
                    new int[] { y[row][col], y[row][col+1], y[row+1][col+1], y[row+1][col] },
                    4);
        }
    }
    return pieces;
}
private static int[][] splitFourSided(int[] xy, int parts) {
    // To visualize, assume values are [topLeft, topRight, bottomRight, bottomLeft].
    // The 'xy' array is either the x-coordinates or the y-coordinates.
    // First we split left and right sides, e.g. for 3 parts:
    //   From: ┌     To: ┐
    //         ├         ┤
    //         ├         ┤
    //         └         ┘
    // Then we split between those:
    //   ┌─┬─┬─┐
    //   ├─┼─┼─┤
    //   ├─┼─┼─┤
    //   └─┴─┴─┘
    int[] from = splitRange(xy[0], xy[3], parts);
    int[] to = splitRange(xy[1], xy[2], parts);
    int[][] grid = new int[parts + 1][];
    for (int i = 0; i <= parts; i++)
        grid[i] = splitRange(from[i], to[i], parts);
    return grid;
}
private static int[] splitRange(int from, int to, int parts) {
    int[] prorated = new int[parts + 1];
    for (int i = 0; i <= parts; i++)
        prorated[i] = prorate(from, to, i, parts);
    return prorated;
}
private static int prorate(int from, int to, int index, int parts) {
    if (index == 0)
        return from;
    if (index == parts)
        return to;
    double delta = (to - (double) from) * index / parts;
    int rounded = (int) Math.round(delta);
    if (rounded != delta)
        throw new ArithmeticException("Cannot prorate to integer value");
    return from + rounded;
}

测试

int[] x = {38, 100, 80, 18};
int[] y = {50, 50, 100, 100};
Polygon poly = new Polygon(x, y, 4);
splitAndDrawFourSided(g, poly, 2);
private static void splitAndDrawFourSided(Graphics g, Polygon poly, int partsPerSide) {
    Polygon[][] pieces = splitFourSided(poly, partsPerSide);
    for (int row = 0; row < partsPerSide; row++)
        for (int col = 0; col < partsPerSide; col++)
            g.drawPolygon(pieces[row][col]);
    Graphics gMain = g.create();
    try {
        gMain.setColor(Color.RED);
        gMain.drawPolygon(poly);
    } finally {
        gMain.dispose();
    }
}

结果

Sure, here’s the translation:
将多边形形状分割 Java

英文:

The code below works for any convex 4-sided polygon. When the initial polygon is a parallelogram, the resultant sub-polygons are by nature all parallelograms too, all with the same size, i.e. they are even-sized.

Since the desired number of parts must be a square number, it means we can simply split the 4-sided polygon horizontally and vertically into partsPerSide = sqrt(parts).

When we split a 4-sided polygon into multiple parts, we may end up with coordinates that are not exact integers. We can simply round the value to an integer, but then the pieces wouldn't be exactly even in size. Whether that is acceptable is a matter of choice. Visually, the rounding can be noticed, since the lines won't be 100% straight.

In the code below, we assume that rounding is not acceptable, i.e. we want exact even sizes. If rounding is ok, simply comment out the if (rounded != delta) throw new ArithmeticException() code at the end, then call splitFourSided() with the desired number of partsPerSide.

Enough talk, here is the code:

private static Polygon[][] splitFourSided(Polygon poly, int partsPerSide) {
	if (poly.npoints != 4)
		throw new IllegalArgumentException(&quot;Polygon must be 4-sided&quot;);
	if (partsPerSide &lt;= 0)
		throw new IllegalArgumentException(&quot;There must be a positive number of parts per side&quot;);
	int[][] x = splitFourSided(poly.xpoints, partsPerSide);
	int[][] y = splitFourSided(poly.ypoints, partsPerSide);
	Polygon[][] pieces = new Polygon[partsPerSide][partsPerSide];
	for (int row = 0; row &lt; partsPerSide; row++) {
		for (int col = 0; col &lt; partsPerSide; col++) {
			pieces[row][col] = new Polygon(
					new int[] { x[row][col], x[row][col+1], x[row+1][col+1], x[row+1][col] },
					new int[] { y[row][col], y[row][col+1], y[row+1][col+1], y[row+1][col] },
					4);
		}
	}
	return pieces;
}
private static int[][] splitFourSided(int[] xy, int parts) {
	// To visualize, assume values are [topLeft, topRight, bottomRight, bottomLeft].
	// The &#39;xy&#39; array is either the x-coordinates or the y-coordinates.
	// First we split left and right sides, e.g. for 3 parts:
	//   From: ┌     To: ┐
	//         ├         ┤
	//         ├         ┤
	//         └         ┘
	// Then we split between those:
	//   ┌─┬─┬─┐
	//   ├─┼─┼─┤
	//   ├─┼─┼─┤
	//   └─┴─┴─┘
	int[] from = splitRange(xy[0], xy[3], parts);
	int[] to = splitRange(xy[1], xy[2], parts);
	int[][] grid = new int[parts + 1][];
	for (int i = 0; i &lt;= parts; i++)
		grid[i] = splitRange(from[i], to[i], parts);
	return grid;
}
private static int[] splitRange(int from, int to, int parts) {
	int[] prorated = new int[parts + 1];
	for (int i = 0; i &lt;= parts; i++)
		prorated[i] = prorate(from, to, i, parts);
	return prorated;
}
private static int prorate(int from, int to, int index, int parts) {
	if (index == 0)
		return from;
	if (index == parts)
		return to;
	double delta = (to - (double) from) * index / parts;
	int rounded = (int) Math.round(delta);
	if (rounded != delta)
		throw new ArithmeticException(&quot;Cannot prorate to integer value&quot;);
	return from + rounded;
}

Test

int[] x = {38, 100, 80, 18};
int[] y = {50, 50, 100, 100};
Polygon poly = new Polygon(x, y, 4);
splitAndDrawFourSided(g, poly, 2);
private static void splitAndDrawFourSided(Graphics g, Polygon poly, int partsPerSide) {
	Polygon[][] pieces = splitFourSided(poly, partsPerSide);
	for (int row = 0; row &lt; partsPerSide; row++)
		for (int col = 0; col &lt; partsPerSide; col++)
			g.drawPolygon(pieces[row][col]);
	Graphics gMain = g.create();
	try {
		gMain.setColor(Color.RED);
		gMain.drawPolygon(poly);
	} finally {
		gMain.dispose();
	}
}

Result

Sure, here’s the translation:
将多边形形状分割 Java


To search for a valid number of parts, we can add a search loop, and change the coordinates so they are only divisible by 7.

int[] x = {37, 100, 79, 16};
int[] y = {50, 50, 99, 99};
Polygon poly = new Polygon(x, y, 4);
for (int partsPerSide : new int[] { 2, 3, 5, 7, 11, 13, 17, 19 }) {
	try {
		splitAndDrawFourSided(g, poly, partsPerSide);
		break; // stop when successful
	} catch (@SuppressWarnings(&quot;unused&quot;) ArithmeticException ignored) {
		continue; // try next number of parts
	}
}

Result

Sure, here’s the translation:
将多边形形状分割 Java


If we remove the rounding check, that code will of course always just split by 2 parts per side, i.e. into 4 parts. This shows the effect of rounding, e.g. in this case the center row coordinates ended up a bit to the right, causing the black and red lines to not match up. Even without the red line depicting the input parallelogram, the rounding can be noticed. Anti-aliasing helps, but it can still be noticed that the vertical lines aren't 100% straight.

Sure, here’s the translation:
将多边形形状分割 Java
Sure, here’s the translation:
将多边形形状分割 Java
Sure, here’s the translation:
将多边形形状分割 Java

huangapple
  • 本文由 发表于 2020年8月31日 09:20:06
  • 转载请务必保留本文链接:https://go.coder-hub.com/63663624.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定