Возможно, есть некоторые ограничения, которые могут позволить более простое решение.
Таким образом, следующее не может быть удовлетворительным решением для вашего случая!
Но это очень общее решение, поэтому я надеюсь, что все будет в порядке, чтобы опубликовать его здесь.
Прежде всего, на чертеже выглядит, что прямоугольники всегда центрированы в начале координат (оба). Если это допустимое предположение, части следующего решения могут быть упрощены.
Тогда не совсем понятно, как следует использовать предложенное вами "базовое" решение. Вы предложили сгенерировать точки (x, y), и для каждой вы проверяете, содержится ли она во внутреннем прямоугольнике. Если он содержится во внутреннем прямоугольнике, то он отбрасывается.
Теперь представьте, что вы хотите взять 100 точек из синей области. Сколько очков вам нужно набрать, чтобы убедиться, что вы нашли 100 очков, у которых не было отброшено?
Это не может быть решено детерминистически. Или более формально: вы не можете предоставить полностью правильную реализацию этого. Генератор случайных чисел может всегда генерировать точки, которые находятся во внутреннем прямоугольнике и, следовательно, отбрасываться. Конечно, на практике это не удастся, но вы не можете это доказать, и в этом суть.
Если внутренний прямоугольник «большой» по сравнению с внешним, это будет иметь практические последствия. Возможно, вам придется сгенерировать несколько миллионов точек, чтобы получить 100 из них, которые находятся в узком поле между внутренним и внешним прямоугольником.
Однако следующее является решением, которое не страдает от вышеупомянутых проблем. Это обходится дорого: это не особенно эффективное решение (хотя, как упоминалось выше, «относительная эффективность» по сравнению с базовым решением зависит от размеров прямоугольников и схемы использования).
Предполагая, что координаты угловых точек даны как на этом рисунке:
(x0,y0) (x3,y3)
O------------------------------O
| |
| (ix0,iy0) (ix3,iy3) |
| O----------------O |
| | | |
| | | |
| | | |
| | | |
| | | |
| O----------------O |
| (ix1,iy1) (ix2,iy2) |
| |
O------------------------------O
(x1,y1) (x2,y2)
(обратите внимание, что координаты произвольны, а прямоугольники не обязательно центрированы в начале координат)
Исходя из этого, вы можете вычислить регионы, которые могут содержать точки:
O------O----------------O------O
| | | |
| R0 | R1 | R2 |
O------O----------------O------|
| | | |
| | | |
| R2 | | R4 |
| | | |
| | | |
O------O----------------O------O
| R5 | R6 | R7 |
| | | |
O------O----------------O------O
Теперь, когда вы хотите выбрать n точек, вы можете для каждой точки случайным образом выбрать один из этих регионов и поместить точку в случайное положение внутри этого региона.
Предостережение - это выбор региона: регион следует выбирать с вероятностью, соответствующей области региона, относительно общей площади всех регионов. Прагматично, вы можете вычислить общую площадь всех регионов (как outer.w*outer.h-inner.w*inner.h), а затем вычислить совокупное распределение вероятностей для точки, заканчивающейся в одной из областей R0...R7. Из этих кумулятивных распределений вы можете отобразить случайное значение между 0.0 и 1.0 в соответствующий регион.
Преимущества этого подхода:
- это работает для любых прямоугольников (пока внешний содержит внутренний ...)
- вы можете напрямую указать количество точек, которые должны быть сгенерированы, заранее , и это сгенерирует точно правильное количество точек
- это может быть реализовано детерминистически (то есть полностью правильно)
Вот пример, показывающий результат, перетаскивая ползунок, чтобы сгенерировать 1 ... 2000 точек:
Он был создан с помощью следующего MCVE. Он реализован в Java, но если у вас есть некоторые структуры, такие как Point и Rectangle, перенести это на другие языки будет довольно тривиально:
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JSlider;
import javax.swing.SwingUtilities;
public class RegionNoiseTest
{
public static void main(String[] args)
{
SwingUtilities.invokeLater(() -> createAndShowGUI());
}
private static void createAndShowGUI()
{
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.getContentPane().setLayout(new BorderLayout());
RegionNoiseTestPanel panel =
new RegionNoiseTestPanel();
f.getContentPane().add(panel, BorderLayout.CENTER);
JSlider nSlider = new JSlider(1, 2000, 1);
nSlider.addChangeListener(e ->
{
panel.generatePoints(nSlider.getValue());
});
nSlider.setValue(100);
f.getContentPane().add(nSlider, BorderLayout.SOUTH);
f.setSize(500,450);
f.setLocationRelativeTo(null);
f.setVisible(true);
}
}
class RegionNoiseTestPanel extends JPanel
{
private final Rectangle2D outer;
private final Rectangle2D inner;
private List<Point2D> points;
RegionNoiseTestPanel()
{
outer = new Rectangle2D.Double(50, 50, 400, 300);
inner = new Rectangle2D.Double(90, 100, 300, 200);
}
public void generatePoints(int n)
{
this.points = createPoints(n, outer, inner, new Random(0));
repaint();
}
@Override
protected void paintComponent(Graphics gr)
{
super.paintComponent(gr);
Graphics2D g = (Graphics2D)gr;
g.setRenderingHint(
RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
g.setColor(new Color(220, 220, 220));
g.fill(outer);
g.setColor(new Color(160, 160, 160));
g.fill(inner);
if (points != null)
{
g.setColor(Color.BLUE);
for (Point2D p : points)
{
double r = 2;
double x = p.getX();
double y = p.getY();
g.fill(new Ellipse2D.Double(x - r, y - r, r + r, r + r));
}
}
}
private static List<Point2D> createPoints(
int n, Rectangle2D outer, Rectangle2D inner, Random random)
{
List<Rectangle2D> regions = computeRegions(outer, inner);
double cumulativeRegionAreas[] = new double[8];
double outerArea = outer.getWidth() * outer.getHeight();
double innerArea = inner.getWidth() * inner.getHeight();
double relevantArea = outerArea - innerArea;
double areaSum = 0;
for (int i = 0; i < regions.size(); i++)
{
Rectangle2D region = regions.get(i);
double area = region.getWidth() * region.getHeight();
areaSum += area;
cumulativeRegionAreas[i] = areaSum / relevantArea;
}
List<Point2D> points = new ArrayList<Point2D>();
for (int i=0; i<n; i++)
{
points.add(createPoint(
regions, cumulativeRegionAreas, random));
}
return points;
}
private static List<Rectangle2D> computeRegions(
Rectangle2D outer, Rectangle2D inner)
{
List<Rectangle2D> regions = new ArrayList<Rectangle2D>();
for (int r = 0; r < 8; r++)
{
regions.add(createRegion(outer, inner, r));
}
return regions;
}
private static Point2D createPoint(
List<Rectangle2D> regions,
double normalizedCumulativeRegionAreas[],
Random random)
{
double alpha = random.nextDouble();
int index = Arrays.binarySearch(normalizedCumulativeRegionAreas, alpha);
if (index < 0)
{
index = -(index + 1);
}
Rectangle2D region = regions.get(index);
double minX = region.getMinX();
double minY = region.getMinY();
double maxX = region.getMaxX();
double maxY = region.getMaxY();
double x = minX + random.nextDouble() * (maxX - minX);
double y = minY + random.nextDouble() * (maxY - minY);
return new Point2D.Double(x, y);
}
private static Rectangle2D createRegion(
Rectangle2D outer, Rectangle2D inner, int region)
{
double minX = 0;
double minY = 0;
double maxX = 0;
double maxY = 0;
switch (region)
{
case 0:
minX = outer.getMinX();
minY = outer.getMinY();
maxX = inner.getMinX();
maxY = inner.getMinY();
break;
case 1:
minX = inner.getMinX();
minY = outer.getMinY();
maxX = inner.getMaxX();
maxY = inner.getMinY();
break;
case 2:
minX = inner.getMaxX();
minY = outer.getMinY();
maxX = outer.getMaxX();
maxY = inner.getMinY();
break;
case 3:
minX = outer.getMinX();
minY = inner.getMinY();
maxX = inner.getMinX();
maxY = inner.getMaxY();
break;
case 4:
minX = inner.getMaxX();
minY = inner.getMinY();
maxX = outer.getMaxX();
maxY = inner.getMaxY();
break;
case 5:
minX = outer.getMinX();
minY = inner.getMaxY();
maxX = inner.getMinX();
maxY = outer.getMaxY();
break;
case 6:
minX = inner.getMinX();
minY = inner.getMaxY();
maxX = inner.getMaxX();
maxY = outer.getMaxY();
break;
case 7:
minX = inner.getMaxX();
minY = inner.getMaxY();
maxX = outer.getMaxX();
maxY = outer.getMaxY();
break;
}
return new Rectangle2D.Double(minX, minY, maxX - minX, maxY - minY);
}
}
Мне все еще было бы любопытно, найдет ли кто-нибудь изящный, детерминированный подход, когда не необходимо для определения видов "областей" для точек, которые будут сгенерированы ...