Oliver прав. Этот код (сообщество викифицировало) генерирует и виды все возможные комбинации массива 4 точек.
#include <cstdio>
#include <algorithm>
struct PointF {
float x;
float y;
};
// Returns the z-component of the cross product of a and b
inline double CrossProductZ(const PointF &a, const PointF &b) {
return a.x * b.y - a.y * b.x;
}
// Orientation is positive if abc is counterclockwise, negative if clockwise.
// (It is actually twice the area of triangle abc, calculated using the
// Shoelace formula: http://en.wikipedia.org/wiki/Shoelace_formula .)
inline double Orientation(const PointF &a, const PointF &b, const PointF &c) {
return CrossProductZ(a, b) + CrossProductZ(b, c) + CrossProductZ(c, a);
}
void Sort4PointsClockwise(PointF points[4]){
PointF& a = points[0];
PointF& b = points[1];
PointF& c = points[2];
PointF& d = points[3];
if (Orientation(a, b, c) < 0.0) {
// Triangle abc is already clockwise. Where does d fit?
if (Orientation(a, c, d) < 0.0) {
return; // Cool!
} else if (Orientation(a, b, d) < 0.0) {
std::swap(d, c);
} else {
std::swap(a, d);
}
} else if (Orientation(a, c, d) < 0.0) {
// Triangle abc is counterclockwise, i.e. acb is clockwise.
// Also, acd is clockwise.
if (Orientation(a, b, d) < 0.0) {
std::swap(b, c);
} else {
std::swap(a, b);
}
} else {
// Triangle abc is counterclockwise, and acd is counterclockwise.
// Therefore, abcd is counterclockwise.
std::swap(a, c);
}
}
void PrintPoints(const char *caption, const PointF points[4]){
printf("%s: (%f,%f),(%f,%f),(%f,%f),(%f,%f)\n", caption,
points[0].x, points[0].y, points[1].x, points[1].y,
points[2].x, points[2].y, points[3].x, points[3].y);
}
int main(){
PointF points[] = {
{5.0f, 20.0f},
{5.0f, 5.0f},
{20.0f, 20.0f},
{20.0f, 5.0f}
};
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
if(j == i) continue;
for(int k = 0; k < 4; k++){
if(j == k || i == k) continue;
for(int l = 0; l < 4; l++){
if(j == l || i == l || k == l) continue;
PointF sample[4];
sample[0] = points[i];
sample[1] = points[j];
sample[2] = points[k];
sample[3] = points[l];
PrintPoints("input: ", sample);
Sort4PointsClockwise(sample);
PrintPoints("output: ", sample);
printf("\n");
}
}
}
}
return 0;
}
Pear Services_JSON проанализирует эту строку (проверенная версия 1.31). Но учитывая, что это парсер JSON и что это недействительный JSON, у вас нет гарантии, что будущие версии будут работать.
Это звучало как забавная задача, поэтому я написал крошечный синтаксический анализатор: D
class JsParserException extends Exception {}
function parse_jsobj($str, &$data) {
$str = trim($str);
if(strlen($str) < 1) return;
if($str{0} != '{') {
throw new JsParserException('The given string is not a JS object');
}
$str = substr($str, 1);
/* While we have data, and it's not the end of this dict (the comma is needed for nested dicts) */
while(strlen($str) && $str{0} != '}' && $str{0} != ',') {
/* find the key */
if($str{0} == "'" || $str{0} == '"') {
/* quoted key */
list($str, $key) = parse_jsdata($str, ':');
} else {
$match = null;
/* unquoted key */
if(!preg_match('/^\s*[a-zA-z_][a-zA-Z_\d]*\s*:/', $str, $match)) {
throw new JsParserException('Invalid key ("'.$str.'")');
}
$key = $match[0];
$str = substr($str, strlen($key));
$key = trim(substr($key, 0, -1)); /* discard the ':' */
}
list($str, $data[$key]) = parse_jsdata($str, '}');
}
"Finshed dict. Str: '$str'\n";
return substr($str, 1);
}
function comma_or_term_pos($str, $term) {
$cpos = strpos($str, ',');
$tpos = strpos($str, $term);
if($cpos === false && $tpos === false) {
throw new JsParserException('unterminated dict or array');
} else if($cpos === false) {
return $tpos;
} else if($tpos === false) {
return $cpos;
}
return min($tpos, $cpos);
}
function parse_jsdata($str, $term="}") {
$str = trim($str);
if(is_numeric($str{0}."0")) {
/* a number (int or float) */
$newpos = comma_or_term_pos($str, $term);
$num = trim(substr($str, 0, $newpos));
$str = substr($str, $newpos+1); /* discard num and comma */
if(!is_numeric($num)) {
throw new JsParserException('OOPSIE while parsing number: "'.$num.'"');
}
return array(trim($str), $num+0);
} else if($str{0} == '"' || $str{0} == "'") {
/* string */
$q = $str{0};
$offset = 1;
do {
$pos = strpos($str, $q, $offset);
$offset = $pos;
} while($str{$pos-1} == '\\'); /* find un-escaped quote */
$data = substr($str, 1, $pos-1);
$str = substr($str, $pos);
$pos = comma_or_term_pos($str, $term);
$str = substr($str, $pos+1);
return array(trim($str), $data);
} else if($str{0} == '{') {
/* dict */
$data = array();
$str = parse_jsobj($str, $data);
return array($str, $data);
} else if($str{0} == '[') {
/* array */
$arr = array();
$str = substr($str, 1);
while(strlen($str) && $str{0} != $term && $str{0} != ',') {
$val = null;
list($str, $val) = parse_jsdata($str, ']');
$arr[] = $val;
$str = trim($str);
}
$str = trim(substr($str, 1));
return array($str, $arr);
} else if(stripos($str, 'true') === 0) {
/* true */
$pos = comma_or_term_pos($str, $term);
$str = substr($str, $pos+1); /* discard terminator */
return array(trim($str), true);
} else if(stripos($str, 'false') === 0) {
/* false */
$pos = comma_or_term_pos($str, $term);
$str = substr($str, $pos+1); /* discard terminator */
return array(trim($str), false);
} else if(stripos($str, 'null') === 0) {
/* null */
$pos = comma_or_term_pos($str, $term);
$str = substr($str, $pos+1); /* discard terminator */
return array(trim($str), null);
} else if(strpos($str, 'undefined') === 0) {
/* null */
$pos = comma_or_term_pos($str, $term);
$str = substr($str, $pos+1); /* discard terminator */
return array(trim($str), null);
} else {
throw new JsParserException('Cannot figure out how to parse "'.$str.'" (term is '.$term.')');
}
}
Использование:
$data = '{fu:"bar",baz:["bat"]}';
$parsed = array();
parse_jsobj($data, $parsed);
var_export($parsed);
Дает:
array (
'fu' => 'bar',
'baz' =>
array (
0 => 'bat',
),
)
Протестировано с этими строками:
'{fu:"bar",baz:["bat"]}',
'{rec:{rec:{rec:false}}}',
'{foo:[1,2,[3,4]]}',
'{fu:{fu:"bar"},bar:{fu:"bar"}}',
'{"quoted key":[1,2,3]}',
'{und:undefined,"baz":[1,2,"3"]}',
'{arr:["a","b"],"baz":"foo","gar":{"faz":false,t:"2"},f:false}',