确定一个点一个任意形状内坐镇？ [英] determine if a point sits inside an arbitrary shape?

问题描述

给定一个点的坐标，我怎么能确定它是否是任意形状内？

的形状是由点组成的数组定义的，我不知道那里的形状封闭的一部分，我真正需要帮助的是找出其中形状被关闭。

下面是一个图像来说明我的意思好一点：

解决方案

其实，如果你给出一个点的数组，你可以检查形状接近如下：
考虑点对 P [I] 和 P [I + 1] 给出的数组中 - 他们形成了一些片段你的形状的边界。如果存在两个这样的段相交，它可以在进行检查O（N ^ 2）时间（你需要检查什么是仅仅通过检查所有可能对这类段）。如果存在的交点，这意味着你的形状是封闭的。
注意：您必须留心不要忘记检查段 P [0]，P [N-1] 或者（即数组中的第一个和最后一个点）<。 / P>

Given a point's coordinates, how can I determine if it is within an arbitrary shape?

The shape is defined by an array of points, I do not know where the shape is 'closed', the part I really need help is to work out where the shape is closed.

Here's an image to illustrate what I mean a little better:

解决方案

Actually, if you are given an array of points, you can check the closeness of the shape as follows:
Consider pairs of points P[i] and P[i+1] given in the array - they form some segment of the border of your shape. What you need to check is if there exist two such segments that intersect, which can be checked in O(N^2) time (just by checking all possible pairs of such segments). If there exists an intersection, that means that your shape is closed.
Note: you must be attentive not to forget to check the segment P[0],P[n-1] either (i.e. first and last points in the array).

这篇关于确定一个点一个任意形状内坐镇？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！