我想用 processing (Java) 编写一个游戏，玩家画一条可能是曲线的线，然后在这条线上画一个点。我想，我会只用像素画线，而不是贝塞尔曲线或线，并且可能将绘制的像素存储在 ArrayList 中。但是有两个问题我不确定如何解决fast：
a) 该线不得与自身或任何其他现有线相交。这意味着，如果当前绘制的像素已经存储在 ArrayList 中，我必须检查 during 绘图。
b) 玩家必须在其最后绘制的线上且仅在该线上的某处放置一个点或小圆圈。那么我应该为每条绘制的线额外使用一个 ArrayList 吗？每条线都包含一个像素数组列表？
有没有经典的方法可以有效地做到这一点？有什么数学方法吗？
提前致谢，Ingo
关于合适的数据结构、数学或源代码的任何提示都会很棒。
a) 该线不得与自身或任何其他现有线相交。这意味着，如果当前绘制的像素已经存储在 ArrayList 中，我必须检查 during 绘图。
最简单的解决方案是将所有像素存储在位图中，因此您可以查看它以了解像素是否已经着色。要么使用也用于渲染线条的相同内存，要么使用单独的
BufferedImage请注意，如果您的画线算法进行对角线跳跃，那么您可能仍然有两条线相互交叉而不共享任何像素。像这样：
2 1111
211111
111112
1 2
所以在这种情况下，您可能想在对角线连接期间环顾四周，如果对角线的两个像素都已经着色，则拒绝它。
b) 玩家必须在其最后绘制的线上且仅在该线上的某处放置一个点或小圆圈。那么我应该为每条绘制的线额外使用一个 ArrayList 吗？每条线都包含一个像素数组列表？
这是一种选择。另一种选择是为当前行的像素设置第二个缓冲图像。在直线包含许多像素但只有一个小邻域是圆圈放置的候选者的情况下，这将使找到最近的像素更便宜一些。不过，管理额外图片所需的开销会抵消好处，因此如果您需要在线条图之间放置多个圆圈，这将是最有用的。
有没有什么经典的方法可以有效地做到这一点？
通用技术可能是不怕重复数据。如果将相同的信息表示为位置列表对于某些任务更好，而对于其他任务则更好地表示为黑白图像，那么可以随意同时使用这两种图像并确保它们保持同步，除非这本身比第二个数据结构的收益。
有什么数学方法吗？
有些东西可以用来找到最近的点。想到四叉树。但这对您的用户案例来说感觉有点矫枉过正。如果你决定对你的线条而不是像素进行参数化描述，那么表达它们的交点肯定会符合数学考虑。一个简单的东西，比如方向谓词，可以告诉你三个点是按顺时针还是逆时针顺序排列，这对检查线段的交点有很大帮助。