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