我有一个空间区域，二维，从(0,0)到(MAX_X, MAX_Y)。
在这个空间区域内，我画了一些线，它们与该区域的周长相交，并且它们可能彼此相交。通过这种方式，这些线将我的空间区域划分为子区域，如果将这些子区域相加，则给出整个空间区域。
在这片空间区域内，有一些点(x,y)。我必须确定
我正在尝试用 java 编写代码，但语言并不是很重要。我不知道如何完成这两项任务。如果有人可以给我一个提示，我将非常感激。
这确实是一道数学题。考虑到这个问题，我假设解决方案将非常复杂和/或昂贵（计算方面）。
你从一个子区域列表 R 开始，从一个元素开始：整个区域。接下来，您循环遍历您的行列表。对于每条线，您循环每个 R。如果该线与 Region 相交，则将其分成两部分。在线区域交叉点检查的帮助应该很容易在网上获得。只需寻找一条线和一个凸面区域之间的交点。该算法的问题在于它的运行时间约为 O(n^3)。n 行的 O(n) 乘以区域的 O(n) 乘以交叉点检查的 O(n) （但是您可能能够显着加快最后一部分的速度，从而使您在结尾）。
检查您的哪些区域包含特定点是凸分析的经典问题。应该有可用的算法。我猜您想要做的是遍历您的线条并检查您的点是该线条的“左侧还是右侧”。如果您在第一步中将子区域链接到您的行，这将为您提供 O(n) 中的适当子区域。
第一个问题可以用更复杂的算法更快地解决，就像我说的，我解释的那个可以显着加快。
基本上，如果您想了解有关该主题的更多信息，则可以查看凸分析。
但是，如果所有这些都对您没有帮助，那么您可能会不知所措（无意冒犯，您在这里处理的是非常复杂的数学）。
这是计算几何中比较难的问题。一种可能的方法是通过原始矩形的平面细分来表示结果区域。细分将由双向连接边列表 (DCEL)表示。这包括有向半边列表、区域列表（面）和顶点列表（线的交点）。所有这些数据都是完全互连的，因此在给定一些其他数据的情况下查找任何数据非常有效。
DCEL 将被迭代地构建，从作为原始矩形的一个区域开始，然后一行接一行地添加。增加一条线，就是用这条线切割当前的DCEL，得到更精细的DCEL。
构建最终的 DCEL 后，可用于查找和标记包含点的区域。由于区域是凸多边形，因此可以有效地测试点是否在区域中。
M. de Berg, et.al.: Computational Geometry 是一本关于 DCEL 的好书。您还可以在 Web 上找到许多资源。您还将找到实现和各种软件包。