从平面点形成一个矩形
Form a rectangle from plane points
我有一组红线，从中我得到一组绿色交点（在屏幕上可见）：
然后我想找到最有可能描述矩形的四个点（如果有多个选项，则选择面积最大的）。我阅读了关于如何找到完全形成矩形的点的类似问题：
find if 4 points on a plane form a rectangle?
有一个选项可以遍历所有四个点并计算它们形成矩形的概率（或与矩形的某些相似系数）。假设此刻我们正在考虑A、B、C、D四个点。我尝试了2个相似函数：
,
其中 <> 表示点积，|| - 向量范数。
,
其中 std 是假定矩形的顶点到质心的距离的标准差，mean 是平均距离。
两个功能都表现不佳。
有没有办法引入一个函数，当平面的四个点靠近矩形的顶点时接近1，在离矩形最远的位置时等于0（假设它们在 1 行)?
我真的不能说找到合适的成本函数来对“好”矩形进行评分。从评论来看，似乎有很多讨论，但没有达成共识。所以现在我将只使用一个评分函数来惩罚四点形状，因为它们的角度远离 90 度。具体来说，我对平方距离求和。如果您想要不同的评分指标，您可以替换 scoreFunc 函数中的计算。
我设置了一个交互式 window，您可以在其中单击以添加积分。当您按 'q' 时，它将获取这些点，找到 4 个点的所有可能组合（不是排列），然后 运行 每个点的评分函数并得出最好的。
我正在使用递归的强力搜索。为了避免出现大量重复，我想出了一个不管顺序如何都可以工作的散列函数。我使用质数来标识每个点，而哈希函数只是采用点的 ID 的乘积。这确保 (1,3,5,7) 与 (3,1,7,5) 相同。我使用素数是因为素数的乘积在这种情况下是唯一的（因为它们是素数，所以不能分解和聚集）。
搜索后，我必须确保这些点的排列方式不会使直线相交。我正在利用 OpenCV 的 contourArea 为我进行计算。我可以将第一个点与它的水平和垂直邻居交换，并将这些区域与原始区域进行比较。相交线的“领结”形状比非相交形状的面积要小（我很确定它们实际上面积为零，因为它们不算作闭合形状）。
import cv2
import numpy as np
import math
# get mouse click
click_pos = None;
click = False;
def mouseClick(event, x, y, flags, param):
# hook to globals
global click_pos;
global click;
# check for left mouseclick
if event == cv2.EVENT_LBUTTONDOWN:
click = True;
click_pos = (x,y);
# prime hash function
def phash(points):
total = 1;
for point in points:
total *= point[0];
return total;
# checks if an id is already present in list
def isInList(point, curr_list):
pid = point[0];
for item in curr_list:
if item[0] == pid:
return True;
return False;
# look for rectangles
def getAllRects(points, curr_list, rects, curr_point):
# check if already in curr_list
if isInList(curr_point, curr_list):
return curr_list;
# add self to list
curr_list.append(curr_point);
# check end condition
if len(curr_list) == 4:
# add to dictionary (no worry for duplicates)
rects[phash(curr_list)] = curr_list[:];
curr_list = curr_list[:-1];
return curr_list;
# continue search
for point in points:
curr_list = getAllRects(points, curr_list, rects, point);
curr_list = curr_list[:-1];
return curr_list;
# checks if a number is prime
def isPrime(num):
bound = int(math.sqrt(num));
curr = 3;
while curr <= bound:
if num % curr == 0:
return False;
# skip evens
curr += 2;
return True;
# generate prime number id's for each point
def genPrimes(num):
primes = [];
curr = 1;
while len(primes) < num:
if isPrime(curr):
primes.append(curr);
# +2 to skip evens
curr += 2;
return primes;
# swap sides (fix intersecting lines issue)
def swapH(box):
new_box = np.copy(box);
new_box[0] = box[1];
new_box[1] = box[0];
return new_box;
def swapV(box):
new_box = np.copy(box);
new_box[0] = box[3];
new_box[3] = box[0];
return new_box;
# removes intersections
def noNoodles(box):
# get three variants
hbox = swapH(box);
vbox = swapV(box);
# get areas and choose max
sortable = [];
sortable.append([cv2.contourArea(box), box]);
sortable.append([cv2.contourArea(hbox), hbox]);
sortable.append([cv2.contourArea(vbox), vbox]);
sortable.sort(key = lambda a : a[0]);
return sortable[-1][1];
# 2d distance
def dist2D(one, two):
dx = one[0] - two[0];
dy = one[1] - two[1];
return math.sqrt(dx*dx + dy*dy);
# angle between three points (the last point is the middle)
# law of cosines
def angle3P(p1, p2, p3):
# get distances
a = dist2D(p3, p1);
b = dist2D(p3, p2);
c = dist2D(p1, p2);
# calculate angle // assume a and b are nonzero
numer = c**2 - a**2 - b**2;
denom = -2 * a * b;
if denom == 0:
denom = 0.000001;
rads = math.acos(numer / denom);
degs = math.degrees(rads);
return degs;
# calculates a score
def scoreFunc(box):
# for each point, calculate angle
angles = [];
for a in range(len(box)):
prev = box[a-2][0];
curr = box[a-1][0];
next = box[a][0];
angles.append(angle3P(prev, next, curr));
# for each angle, score on squared distance from 90
score = 0;
for angle in angles:
score += (angle - 90)**2;
return score;
# evaluates each box (assigns a score)
def evaluate(boxes):
sortable = [];
for box in boxes:
# INSERT YOUR OWN SCORING FUNC HERE
sortable.append([scoreFunc(box), box]);
sortable.sort(key = lambda a : a[0]);
return sortable;
# set up callback
cv2.namedWindow("Display");
cv2.setMouseCallback("Display", mouseClick);
# set up screen
res = (600,600,3);
bg = np.zeros(res, np.uint8);
# loop
done = False;
points = [];
while not done:
# reset display
display = np.copy(bg);
# check for new click
if click:
click = False;
points.append(click_pos);
# draw points
for point in points:
cv2.circle(display, point, 4, (0,200,0), -1);
# show
cv2.imshow("Display", display);
key = cv2.waitKey(1);
# check keypresses
done = key == ord('q');
# generate prime number id's for each point
# if you have a lot of points, it would be worth it
# to just have a .txt file with a bunch of pre-gen primes in it
primes = genPrimes(len(points));
print(primes);
withPrimes = [];
for a in range(len(points)):
withPrimes.append([primes[a], points[a]]);
# run brute-force search over all points
rects = {};
for a in range(len(withPrimes)):
getAllRects(withPrimes, [], rects, withPrimes[a]);
print(len(rects));
# extract just the points (don't need the prime id's anymore)
boxes = [];
for key in rects:
box = [];
for item in rects[key]:
box.append([item[1]]);
boxes.append(np.array(box));
# go through all of the boxes and un-intersect their sides
for a in range(len(boxes)):
boxes[a] = noNoodles(boxes[a]);
# draw each one to check for noodles
# for box in boxes:
# blank = np.zeros_like(bg, np.uint8);
# cv2.drawContours(blank, [box], -1, (255,255,255), -1);
# cv2.imshow("Box", blank);
# cv2.waitKey(0);
# noodles have been squared get best box
sortedBoxes = evaluate(boxes);
bestBox = sortedBoxes[0][1];
# draw
blank = np.zeros_like(bg, np.uint8);
cv2.drawContours(blank, [bestBox], -1, (255,255,255), -1);
for point in points:
cv2.circle(blank, point, 4, (0,200,0), -1);
cv2.imshow("Best", blank);
cv2.waitKey(0);
我有一组红线，从中我得到一组绿色交点（在屏幕上可见）：
然后我想找到最有可能描述矩形的四个点（如果有多个选项，则选择面积最大的）。我阅读了关于如何找到完全形成矩形的点的类似问题：
find if 4 points on a plane form a rectangle?
有一个选项可以遍历所有四个点并计算它们形成矩形的概率（或与矩形的某些相似系数）。假设此刻我们正在考虑A、B、C、D四个点。我尝试了2个相似函数：
其中 <> 表示点积，|| - 向量范数。
其中 std 是假定矩形的顶点到质心的距离的标准差，mean 是平均距离。
两个功能都表现不佳。
有没有办法引入一个函数，当平面的四个点靠近矩形的顶点时接近1，在离矩形最远的位置时等于0（假设它们在 1 行)?
我真的不能说找到合适的成本函数来对“好”矩形进行评分。从评论来看，似乎有很多讨论，但没有达成共识。所以现在我将只使用一个评分函数来惩罚四点形状，因为它们的角度远离 90 度。具体来说，我对平方距离求和。如果您想要不同的评分指标，您可以替换 scoreFunc 函数中的计算。
我设置了一个交互式 window，您可以在其中单击以添加积分。当您按 'q' 时，它将获取这些点，找到 4 个点的所有可能组合（不是排列），然后 运行 每个点的评分函数并得出最好的。
我正在使用递归的强力搜索。为了避免出现大量重复，我想出了一个不管顺序如何都可以工作的散列函数。我使用质数来标识每个点，而哈希函数只是采用点的 ID 的乘积。这确保 (1,3,5,7) 与 (3,1,7,5) 相同。我使用素数是因为素数的乘积在这种情况下是唯一的（因为它们是素数，所以不能分解和聚集）。
搜索后，我必须确保这些点的排列方式不会使直线相交。我正在利用 OpenCV 的 contourArea 为我进行计算。我可以将第一个点与它的水平和垂直邻居交换，并将这些区域与原始区域进行比较。相交线的“领结”形状比非相交形状的面积要小（我很确定它们实际上面积为零，因为它们不算作闭合形状）。
import cv2
import numpy as np
import math
# get mouse click
click_pos = None;
click = False;
def mouseClick(event, x, y, flags, param):
# hook to globals
global click_pos;
global click;
# check for left mouseclick
if event == cv2.EVENT_LBUTTONDOWN:
click = True;
click_pos = (x,y);
# prime hash function
def phash(points):
total = 1;
for point in points:
total *= point[0];
return total;
# checks if an id is already present in list
def isInList(point, curr_list):
pid = point[0];
for item in curr_list:
if item[0] == pid:
return True;
return False;
# look for rectangles
def getAllRects(points, curr_list, rects, curr_point):
# check if already in curr_list
if isInList(curr_point, curr_list):
return curr_list;
# add self to list
curr_list.append(curr_point);
# check end condition
if len(curr_list) == 4:
# add to dictionary (no worry for duplicates)
rects[phash(curr_list)] = curr_list[:];
curr_list = curr_list[:-1];
return curr_list;
# continue search
for point in points:
curr_list = getAllRects(points, curr_list, rects, point);
curr_list = curr_list[:-1];
return curr_list;
# checks if a number is prime
def isPrime(num):
bound = int(math.sqrt(num));
curr = 3;
while curr <= bound:
if num % curr == 0:
return False;
# skip evens
curr += 2;
return True;
# generate prime number id's for each point
def genPrimes(num):
primes = [];
curr = 1;
while len(primes) < num:
if isPrime(curr):
primes.append(curr);
# +2 to skip evens
curr += 2;
return primes;
# swap sides (fix intersecting lines issue)
def swapH(box):
new_box = np.copy(box);
new_box[0] = box[1];
new_box[1] = box[0];
return new_box;
def swapV(box):
new_box = np.copy(box);
new_box[0] = box[3];
new_box[3] = box[0];
return new_box;
# removes intersections
def noNoodles(box):
# get three variants
hbox = swapH(box);
vbox = swapV(box);
# get areas and choose max
sortable = [];
sortable.append([cv2.contourArea(box), box]);
sortable.append([cv2.contourArea(hbox), hbox]);
sortable.append([cv2.contourArea(vbox), vbox]);
sortable.sort(key = lambda a : a[0]);
return sortable[-1][1];
# 2d distance
def dist2D(one, two):
dx = one[0] - two[0];
dy = one[1] - two[1];
return math.sqrt(dx*dx + dy*dy);
# angle between three points (the last point is the middle)
# law of cosines
def angle3P(p1, p2, p3):
# get distances
a = dist2D(p3, p1);
b = dist2D(p3, p2);
c = dist2D(p1, p2);
# calculate angle // assume a and b are nonzero
numer = c**2 - a**2 - b**2;
denom = -2 * a * b;
if denom == 0:
denom = 0.000001;
rads = math.acos(numer / denom);
degs = math.degrees(rads);
return degs;
# calculates a score
def scoreFunc(box):
# for each point, calculate angle
angles = [];
for a in range(len(box)):
prev = box[a-2][0];
curr = box[a-1][0];
next = box[a][0];
angles.append(angle3P(prev, next, curr));
# for each angle, score on squared distance from 90
score = 0;
for angle in angles:
score += (angle - 90)**2;
return score;
# evaluates each box (assigns a score)
def evaluate(boxes):
sortable = [];
for box in boxes:
# INSERT YOUR OWN SCORING FUNC HERE
sortable.append([scoreFunc(box), box]);
sortable.sort(key = lambda a : a[0]);
return sortable;
# set up callback
cv2.namedWindow("Display");
cv2.setMouseCallback("Display", mouseClick);
# set up screen
res = (600,600,3);
bg = np.zeros(res, np.uint8);
# loop
done = False;
points = [];
while not done:
# reset display
display = np.copy(bg);
# check for new click
if click:
click = False;
points.append(click_pos);
# draw points
for point in points:
cv2.circle(display, point, 4, (0,200,0), -1);
# show
cv2.imshow("Display", display);
key = cv2.waitKey(1);
# check keypresses
done = key == ord('q');
# generate prime number id's for each point
# if you have a lot of points, it would be worth it
# to just have a .txt file with a bunch of pre-gen primes in it
primes = genPrimes(len(points));
print(primes);
withPrimes = [];
for a in range(len(points)):
withPrimes.append([primes[a], points[a]]);
# run brute-force search over all points
rects = {};
for a in range(len(withPrimes)):
getAllRects(withPrimes, [], rects, withPrimes[a]);
print(len(rects));
# extract just the points (don't need the prime id's anymore)
boxes = [];
for key in rects:
box = [];
for item in rects[key]:
box.append([item[1]]);
boxes.append(np.array(box));
# go through all of the boxes and un-intersect their sides
for a in range(len(boxes)):
boxes[a] = noNoodles(boxes[a]);
# draw each one to check for noodles
# for box in boxes:
# blank = np.zeros_like(bg, np.uint8);
# cv2.drawContours(blank, [box], -1, (255,255,255), -1);
# cv2.imshow("Box", blank);
# cv2.waitKey(0);
# noodles have been squared get best box
sortedBoxes = evaluate(boxes);
bestBox = sortedBoxes[0][1];
# draw
blank = np.zeros_like(bg, np.uint8);
cv2.drawContours(blank, [bestBox], -1, (255,255,255), -1);
for point in points:
cv2.circle(blank, point, 4, (0,200,0), -1);
cv2.imshow("Best", blank);
cv2.waitKey(0);