确定空间区域是否为空
我有一个二维空间区域，从 (0,0) 到 (MAX_X, MAX_Y)。
在这个空间区域内，我画了一些线，它们与该区域的周界相交，并且它们可能彼此相交。通过这种方式，这些线将我的空间区域划分为子区域，如果将这些子区域相加，就给出了整个空间区域。
在这个空间区域内，有一些点(x,y)。 我必须确定
- 组成由线创建的所有空间子区域的所有顶点的坐标
- 如果给定的空间子区域包含或不包含一个或多个点，
，我试图在java中对此进行编码，但该语言不是真的很重要。我不知道如何完成这两项任务。如果有人能给我一个提示，我将非常感激。
I have a region of space, 2 dimensions, from (0,0) to (MAX_X, MAX_Y).
Inside this region of space, I draw some lines, they intersect the perimeter of the region and they may intersect one another. In this way, these lines partition my region of space in subregions which, if summed, give the entire region of space.
Inside this region of space, there are some points (x,y). I have to determine
- the coordinates of all the vertices composing all the subregions of space created by the lines
- if a given subregion of space contains or not one or more of the points
I'm trying to code this in java, but the language is not really important. I don't have any idea about how to accomplish these two tasks. If anybody can give me an hint I'd really appreciate it.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这确实是一道数学题。考虑这个问题，我认为解决方案将非常复杂和/或昂贵（计算方面）。
您从子区域列表 R 开始，从一个元素开始：整个区域。接下来，您将循环遍历行列表。对于每条线，您循环每个 R。如果线与区域相交，则将其分为两部分。关于线区域相交检查的帮助应该可以在网上轻松获得。只需寻找直线和凸面区域之间的交点即可。该算法的问题在于它的运行时间约为 O(n^3)。 n 条线的 O(n) 乘以区域的 O(n) 乘以交叉点检查的 O(n) （但是，您可能能够显着加快最后一部分的速度，使您在结尾）。
检查哪个区域包含特定点是凸分析的经典问题。应该有可用的算法。我想您想要做的就是遍历您的线并检查您的点是否位于该线的“左侧”或“右侧”。如果您在第一步中将子区域链接到线路，这将为您提供 O(n) 的适当子区域。
使用更复杂的算法可以更快地解决第一个问题，并且正如我所说，我解释的问题可以显着加快。
基本上，如果您想了解有关该主题的更多信息，您可以查看凸分析。
然而，如果所有这些对你根本没有帮助，你可能会不知所措（无意冒犯，你在这里处理非常复杂的数学）。
That is indeed quite a math question. Thinking about the problem I assume that the solution will be quite complicated and/or expensive (computation-wise).
You start with a list R of subregions, starting with one element: the whole region. Next you loop over your list of lines. For every line you loop every R. If the line intersects the Region you divide it into two. Help on the line-area intersection check should be easily available on the net. Just look for intersections between a line and a convex area. The problem with this algorithm is that it will have a runtime of about O(n^3). O(n) for n lines times O(n) for the areas times O(n) for the intersection checks (however you might be able to speed that last part up significantly, bringing you down to O(n^2) in the end).
Checking which of your areas contains a specific point is classical problem of convex analysis. There should be algorithms available for that. I guess what you will be wanting to do is loop over your lines and check if your point is "left or right" of that line. If you link your subregions to your lines in the first step, this will give you the appropriate subregion in O(n).
The first problem can be solved considerably quicker with a more sophisticated algorithm and, like I said, the one I explained could be sped up significantly.
Basically if you want more information on the subject you are looking at convex analysis.
However, if all that doesn't help you at all, you are probably in over your head (no offense intended, you are handling really complicated math here).
这是计算几何中一个相当困难的问题。一种可能的方法是通过原始矩形的平面细分来表示结果区域。细分将由双连接边列表（DCEL）表示。它由一系列有向半边、一系列区域（面）和一系列顶点（线的交点）组成。所有这些数据都是完全相互关联的，因此在给定其他数据的情况下查找任何数据都是非常有效的。
DCEL 将迭代构建，从原始矩形的一个区域开始，并添加一行又一行。增加一条线，就是通过这条线对当前的DCEL进行切割，得到更精细的DCEL。
当构建最终的 DCEL 时，它可用于查找和标记包含点的区域。由于区域是凸多边形，因此可以有效地测试点是否在区域中。
M. de Berg 等人的一本关于 DCEL 的好书是：计算几何。您还可以在 Web 上找到许多资源。您还可以找到实现和各种软件包。
This is a rather difficult problem of computational geometry. A possible approach could be to represent the resulting regions by a planar subdivision of the original rectangle. The subdivison would be represented by doubly connected edge list (DCEL). This consists of a list of directed half-edges, a list of regions (faces) and a list of vertexes (intersections of the lines). All these data are completely inerconnected, such that finding any data given some other data is very efficient.
The DCEL would be built iteratively, starting with one region which is the original rectangle and adding one line after another. Adding a line means to cut the current DCEL by this line and to obtain a more refined DCEL.
When the final DCEL is constructed, it can be used for finding and marking regions that contain a point. Testing whether a point is in a region can be done efficienly because the regions are convex polygons.
A good book on DCEL is M. de Berg, et.al.: Computational Geometry. You can also find many resources on the Web. You will also find implementations and various software packages.