Javascript 检查多边形是否在多边形内
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4833802/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Check if polygon is inside a polygon
提问by Chuy
Yesterday I was looking to check if a point was inside a polygon and found this great script: https://github.com/tparkin/Google-Maps-Point-in-Polygon
昨天我想检查一个点是否在多边形内并找到了这个很棒的脚本：https: //github.com/tparkin/Google-Maps-Point-in-Polygon
But today at work I was told that our client needs to check if one polygon is inside another polygon. I am wondering if is there a formula where I can take, let's say, two coordinates (instead of one to check a point), and from those two coordinates generate a rectangle and check if that rectangle is inside a polygon.
但是今天在工作中我被告知我们的客户需要检查一个多边形是否在另一个多边形内。我想知道是否有一个公式可以让我采用两个坐标（而不是一个来检查一个点），然后从这两个坐标生成一个矩形并检查该矩形是否在多边形内。
I don't know if I'm asking a stupid question (a teacher in highschool used to say "there are no stupid questions, there is only fools who don't ask"), but if you don't understand me totally but just a bit, I'd be grateful if you just tell me where to start.
不知道是不是问了个傻问题（高中老师常说“没有傻问题，只有不问的傻瓜”），但是如果你完全不理解我的话只是一点点，如果你能告诉我从哪里开始，我将不胜感激。
回答by moinudin
Perform line intersectiontests for each pair of lines, one from each polygon. If no pairs of lines intersect and one of the line end-points of polygon A is inside polygon B, then A is entirely inside B.
对每对线执行线相交测试，每个线都有一个。如果没有线对相交，并且多边形 A 的线端点之一在多边形 B 内，则 A 完全在 B 内。
The above works for any type of polygon. If the polygons are convex, you can skip the line intersection tests and just test that all line end-points of A are inside B.
以上适用于任何类型的多边形。如果多边形是凸的，则可以跳过线相交测试，只测试 A 的所有线端点都在 B 内。
If really necessary, you can speed up the line intersection tests using the sweep line algorithm.
如果真的有必要，您可以使用扫描线算法加快线相交测试。
回答by Guffa
First check that one of the corner points in the polygon is inside the other polygon using the script. Then check if any of the lines in the polygon crosses any of the lines in the other polygon. If they don't, the polygon is inside the other polygon.
首先使用脚本检查多边形中的一个角点是否在另一个多边形内。然后检查多边形中的任何一条线是否与另一个多边形中的任何一条线相交。如果不是，则该多边形位于另一个多边形内。
回答by zeta
Maybe this part of the code can help you:
也许这部分代码可以帮助您：
package com.polygons;
import java.awt.Point;
import java.awt.Polygon;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import org.apache.commons.collections.CollectionUtils;
/**
* Utility to Manipulate Polygons
*
* @author fernando.hernandez
*
*/
public class PolygonUtils {
/**
* Check if polygon2 is inside polygon to polygon1
* @param polygon1 polygon that contains other
* @param polygon2 polygon that is inner to other
* @return true if polygon2 is inner to polygon1
*/
public boolean isInsidePolygon(Polygon polygon1, Polygon polygon2){
//all points in inner Polygon should be contained in polygon
int[] xpoints = polygon2.xpoints;
int[] ypoints = polygon2.ypoints;
boolean result = true;
for (int i = 0, j = 0; i < polygon2.npoints ; i++,j++) {
result = polygon1.contains(new Point(xpoints[i], ypoints[j]));
if(!result) break;
}
return result;
}
}
回答by crazartist
I had to find a similar solution. Here is what i have so far :
我不得不找到一个类似的解决方案。这是我到目前为止所拥有的：
- First i fetched all the level 1 polygon coordinates in an
array[pol1cords[cord1,cord2...],pol2cords[cord1,cord2...],..] - Then fetched all the level 3 polygons and plotted them
- Then for each level 1 polygon, i checked if each of the polygon coordinates was inside the plotted level 3 coordinate with
google.maps.geometry.poly.containsLocation(latLng, pol) - If it returned
truecounter would go up - At last if the counter was equal to the length of that array, the result would be true(the level 1 polygon is inside the level3 polygon).
- 首先，我获取了所有 1 级多边形坐标
array[pol1cords[cord1,cord2...],pol2cords[cord1,cord2...],..] - 然后获取所有 3 级多边形并绘制它们
- 然后对于每个 1 级多边形，我检查每个多边形坐标是否在绘制的 3 级坐标内
google.maps.geometry.poly.containsLocation(latLng, pol) - 如果它返回
true计数器会上升 - 最后，如果计数器等于该数组的长度，则结果为真（第 1 级多边形在第 3 级多边形内）。
My algorithm looks something like this:
我的算法看起来像这样：
""Zone(level 3)->District(level 2)->VDC(level 1)"" vdcs = getVDCs(); -> gives vdcs in an array which has name, id and polygon coordinates zones = getZones(); ->gives zones in an array which has name, id and polygon coordinates
""Zone(level 3)->District(level 2)->VDC(level 1)"" vdcs = getVDCs(); -> 在一个数组中给出 vdcs，该数组具有名称、id 和多边形坐标 zone = getZones(); -> 在具有名称、id 和多边形坐标的数组中给出区域
foreach(zones as zone){
drawPolygon(zone[coordinates]);
foreach(vdcs as vdc){
foreach(vdc[coordinates] as coordinate){
result = checkLocation(zone, coordinate);
if(result) counter++;
}
if(counter = vdc[coordinates].length){writeConsole(vdc_id+"true in"+zone_id)}
}
}
回答by sdleihssirhc
Is the polygon convex? Because, if it is, you could just run the "point in polygon" script for both "corners" of your "rectangle." If both corners are in, and the polygon has no "curves" inward, then wouldn't the whole rectangle be in?
多边形是凸的吗？因为，如果是这样，您可以为“矩形”的两个“角”运行“多边形中的点”脚本。如果两个角都在里面，并且多边形向内没有“曲线”，那么整个矩形不会在里面吗？
